http://www.ousob.com --- Legacy Redefined OuSob - File: /wwwroot/clipx/usr/include/boost/graph/detail/array_binary_tree.hpp

// //======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) //======================================================================= // #ifndef ADSTL_ARRAY_BINARY_TREE_HPP #define ADSTL_ARRAY_BINARY_TREE_HPP #include <iterator> #include <functional> #include <boost/config.hpp> namespace adstl { /* Note: array_binary_tree is a completey balanced binary tree */ #if !defined BOOST_NO_STD_ITERATOR_TRAITS template <class RandomAccessIterator, class ID> #else template <class RandomAccessIterator, class ValueType, class ID> #endif class array_binary_tree_node { public: typedef array_binary_tree_node ArrayBinaryTreeNode; typedef RandomAccessIterator rep_iterator; #if !defined BOOST_NO_STD_ITERATOR_TRAITS typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type; typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type; #else typedef int difference_type; typedef ValueType value_type; #endif typedef difference_type size_type; struct children_type { struct iterator : boost::iterator<std::bidirectional_iterator_tag, ArrayBinaryTreeNode, difference_type, array_binary_tree_node*, ArrayBinaryTreeNode&> { // replace with iterator_adaptor implementation -JGS inline iterator() : i(0), n(0) { } inline iterator(const iterator& x) : r(x.r), i(x.i), n(x.n), id(x.id) { } inline iterator& operator=(const iterator& x) { r = x.r; i = x.i; n = x.n; /*egcs generate a warning*/ id = x.id; return *this; } inline iterator(rep_iterator rr, size_type ii, size_type nn, const ID& _id) : r(rr), i(ii), n(nn), id(_id) { } inline array_binary_tree_node operator*() { return ArrayBinaryTreeNode(r, i, n, id); } inline iterator& operator++() { ++i; return *this; } inline iterator operator++(int) { iterator t = *this; ++(*this); return t; } inline bool operator==(const iterator& x) const { return i == x.i; } inline bool operator!=(const iterator& x) const { return !(*this == x); } rep_iterator r; size_type i; size_type n; ID id; }; inline children_type() : i(0), n(0) { } inline children_type(const children_type& x) : r(x.r), i(x.i), n(x.n), id(x.id) { } inline children_type& operator=(const children_type& x) { r = x.r; i = x.i; n = x.n; /*egcs generate a warning*/ id = x.id; return *this; } inline children_type(rep_iterator rr, size_type ii, size_type nn, const ID& _id) : r(rr), i(ii), n(nn), id(_id) { } inline iterator begin() { return iterator(r, 2 * i + 1, n, id); } inline iterator end() { return iterator(r, 2 * i + 1 + size(), n, id); } inline size_type size() const { size_type c = 2 * i + 1; size_type s; if (c + 1 < n) s = 2; else if (c < n) s = 1; else s = 0; return s; } rep_iterator r; size_type i; size_type n; ID id; }; inline array_binary_tree_node() : i(0), n(0) { } inline array_binary_tree_node(const array_binary_tree_node& x) : r(x.r), i(x.i), n(x.n), id(x.id) { } inline ArrayBinaryTreeNode& operator=(const ArrayBinaryTreeNode& x) { r = x.r; i = x.i; n = x.n; /*egcs generate a warning*/ id = x.id; return *this; } inline array_binary_tree_node(rep_iterator start, rep_iterator end, rep_iterator pos, const ID& _id) : r(start), i(pos - start), n(end - start), id(_id) { } inline array_binary_tree_node(rep_iterator rr, size_type ii, size_type nn, const ID& _id) : r(rr), i(ii), n(nn), id(_id) { } inline value_type& value() { return *(r + i); } inline const value_type& value() const { return *(r + i); } inline ArrayBinaryTreeNode parent() const { return ArrayBinaryTreeNode(r, (i - 1) / 2, n, id); } inline bool has_parent() const { return i != 0; } inline children_type children() { return children_type(r, i, n, id); } /* inline void swap(array_binary_tree_node x) { value_type tmp = x.value(); x.value() = value(); value() = tmp; i = x.i; } */ template <class ExternalData> inline void swap(ArrayBinaryTreeNode x, ExternalData& edata ) { value_type tmp = x.value(); /*swap external data*/ edata[ boost::get(id, tmp) ] = i; edata[ boost::get(id, value()) ] = x.i; x.value() = value(); value() = tmp; i = x.i; } inline const children_type children() const { return children_type(r, i, n); } inline size_type index() const { return i; } rep_iterator r; size_type i; size_type n; ID id; }; template <class RandomAccessContainer, class Compare = std::less<typename RandomAccessContainer::value_type> > struct compare_array_node { typedef typename RandomAccessContainer::value_type value_type; compare_array_node(const Compare& x) : comp(x) {} compare_array_node(const compare_array_node& x) : comp(x.comp) {} template< class node_type > inline bool operator()(const node_type& x, const node_type& y) { return comp(x.value(), y.value()); } template< class node_type > inline bool operator()(const node_type& x, const node_type& y) const { return comp(x.value(), y.value()); } Compare comp; }; } /* namespace adstl */ #endif /* ADSTL_ARRAY_BINARY_TREE_H */