| // |
| //======================================================================= |
| // 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 BOOST_ARRAY_BINARY_TREE_HPP |
| #define BOOST_ARRAY_BINARY_TREE_HPP |
| |
| #include <iterator> |
| #include <functional> |
| #include <boost/config.hpp> |
| |
| namespace boost { |
| |
| /* |
| * 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 ) { |
| using boost::get; |
| |
| value_type tmp = x.value(); |
| |
| /*swap external data*/ |
| edata[ get(id, tmp) ] = i; |
| edata[ 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 boost |
| |
| #endif /* BOOST_ARRAY_BINARY_TREE_HPP */ |