1 // 2 //======================================================================= 3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. 4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek 5 // 6 // Distributed under the Boost Software License, Version 1.0. (See 7 // accompanying file LICENSE_1_0.txt or copy at 8 // http://www.boost.org/LICENSE_1_0.txt) 9 //======================================================================= 10 // 11 #ifndef BOOST_ARRAY_BINARY_TREE_HPP 12 #define BOOST_ARRAY_BINARY_TREE_HPP 13 14 #include <iterator> 15 #include <functional> 16 #include <boost/config.hpp> 17 18 namespace boost { 19 20 /* 21 * Note: array_binary_tree is a completey balanced binary tree. 22 */ 23 #if !defined BOOST_NO_STD_ITERATOR_TRAITS 24 template <class RandomAccessIterator, class ID> 25 #else 26 template <class RandomAccessIterator, class ValueType, class ID> 27 #endif 28 class array_binary_tree_node { 29 public: 30 typedef array_binary_tree_node ArrayBinaryTreeNode; 31 typedef RandomAccessIterator rep_iterator; 32 #if !defined BOOST_NO_STD_ITERATOR_TRAITS 33 typedef typename std::iterator_traits<RandomAccessIterator>::difference_type 34 difference_type; 35 typedef typename std::iterator_traits<RandomAccessIterator>::value_type 36 value_type; 37 #else 38 typedef int difference_type; 39 typedef ValueType value_type; 40 #endif 41 typedef difference_type size_type; 42 43 struct children_type { 44 struct iterator 45 : boost::iterator<std::bidirectional_iterator_tag, ArrayBinaryTreeNode, 46 difference_type, array_binary_tree_node*, ArrayBinaryTreeNode&> 47 { // replace with iterator_adaptor implementation -JGS 48 iteratorboost::array_binary_tree_node::children_type::iterator49 inline iterator() : i(0), n(0) { } iteratorboost::array_binary_tree_node::children_type::iterator50 inline iterator(const iterator& x) : r(x.r), i(x.i), n(x.n), id(x.id) { } operator =boost::array_binary_tree_node::children_type::iterator51 inline iterator& operator=(const iterator& x) { 52 r = x.r; i = x.i; n = x.n; 53 /*egcs generate a warning*/ 54 id = x.id; 55 return *this; 56 } iteratorboost::array_binary_tree_node::children_type::iterator57 inline iterator(rep_iterator rr, 58 size_type ii, 59 size_type nn, 60 const ID& _id) : r(rr), i(ii), n(nn), id(_id) { } operator *boost::array_binary_tree_node::children_type::iterator61 inline array_binary_tree_node operator*() { 62 return ArrayBinaryTreeNode(r, i, n, id); } operator ++boost::array_binary_tree_node::children_type::iterator63 inline iterator& operator++() { ++i; return *this; } operator ++boost::array_binary_tree_node::children_type::iterator64 inline iterator operator++(int) 65 { iterator t = *this; ++(*this); return t; } operator ==boost::array_binary_tree_node::children_type::iterator66 inline bool operator==(const iterator& x) const { return i == x.i; } operator !=boost::array_binary_tree_node::children_type::iterator67 inline bool operator!=(const iterator& x) const 68 { return !(*this == x); } 69 rep_iterator r; 70 size_type i; 71 size_type n; 72 ID id; 73 }; children_typeboost::array_binary_tree_node::children_type74 inline children_type() : i(0), n(0) { } children_typeboost::array_binary_tree_node::children_type75 inline children_type(const children_type& x) 76 : r(x.r), i(x.i), n(x.n), id(x.id) { } operator =boost::array_binary_tree_node::children_type77 inline children_type& operator=(const children_type& x) { 78 r = x.r; i = x.i; n = x.n; 79 /*egcs generate a warning*/ 80 id = x.id; 81 return *this; 82 } children_typeboost::array_binary_tree_node::children_type83 inline children_type(rep_iterator rr, 84 size_type ii, 85 size_type nn, 86 const ID& _id) : r(rr), i(ii), n(nn), id(_id) { } beginboost::array_binary_tree_node::children_type87 inline iterator begin() { return iterator(r, 2 * i + 1, n, id); } endboost::array_binary_tree_node::children_type88 inline iterator end() { return iterator(r, 2 * i + 1 + size(), n, id); } sizeboost::array_binary_tree_node::children_type89 inline size_type size() const { 90 size_type c = 2 * i + 1; 91 size_type s; 92 if (c + 1 < n) s = 2; 93 else if (c < n) s = 1; 94 else s = 0; 95 return s; 96 } 97 rep_iterator r; 98 size_type i; 99 size_type n; 100 ID id; 101 }; array_binary_tree_node()102 inline array_binary_tree_node() : i(0), n(0) { } array_binary_tree_node(const array_binary_tree_node & x)103 inline array_binary_tree_node(const array_binary_tree_node& x) 104 : r(x.r), i(x.i), n(x.n), id(x.id) { } operator =(const ArrayBinaryTreeNode & x)105 inline ArrayBinaryTreeNode& operator=(const ArrayBinaryTreeNode& x) { 106 r = x.r; 107 i = x.i; 108 n = x.n; 109 /*egcs generate a warning*/ 110 id = x.id; 111 return *this; 112 } array_binary_tree_node(rep_iterator start,rep_iterator end,rep_iterator pos,const ID & _id)113 inline array_binary_tree_node(rep_iterator start, 114 rep_iterator end, 115 rep_iterator pos, const ID& _id) 116 : r(start), i(pos - start), n(end - start), id(_id) { } array_binary_tree_node(rep_iterator rr,size_type ii,size_type nn,const ID & _id)117 inline array_binary_tree_node(rep_iterator rr, 118 size_type ii, 119 size_type nn, const ID& _id) 120 : r(rr), i(ii), n(nn), id(_id) { } value()121 inline value_type& value() { return *(r + i); } value() const122 inline const value_type& value() const { return *(r + i); } parent() const123 inline ArrayBinaryTreeNode parent() const { 124 return ArrayBinaryTreeNode(r, (i - 1) / 2, n, id); 125 } has_parent() const126 inline bool has_parent() const { return i != 0; } children()127 inline children_type children() { return children_type(r, i, n, id); } 128 /* 129 inline void swap(array_binary_tree_node x) { 130 value_type tmp = x.value(); 131 x.value() = value(); 132 value() = tmp; 133 i = x.i; 134 } 135 */ 136 template <class ExternalData> swap(ArrayBinaryTreeNode x,ExternalData & edata)137 inline void swap(ArrayBinaryTreeNode x, ExternalData& edata ) { 138 using boost::get; 139 140 value_type tmp = x.value(); 141 142 /*swap external data*/ 143 edata[ get(id, tmp) ] = i; 144 edata[ get(id, value()) ] = x.i; 145 146 x.value() = value(); 147 value() = tmp; 148 i = x.i; 149 } children() const150 inline const children_type children() const { 151 return children_type(r, i, n); 152 } index() const153 inline size_type index() const { return i; } 154 rep_iterator r; 155 size_type i; 156 size_type n; 157 ID id; 158 }; 159 160 template <class RandomAccessContainer, 161 class Compare = std::less<typename RandomAccessContainer::value_type> > 162 struct compare_array_node { 163 typedef typename RandomAccessContainer::value_type value_type; compare_array_nodeboost::compare_array_node164 compare_array_node(const Compare& x) : comp(x) {} compare_array_nodeboost::compare_array_node165 compare_array_node(const compare_array_node& x) : comp(x.comp) {} 166 167 template< class node_type > operator ()boost::compare_array_node168 inline bool operator()(const node_type& x, const node_type& y) { 169 return comp(x.value(), y.value()); 170 } 171 172 template< class node_type > operator ()boost::compare_array_node173 inline bool operator()(const node_type& x, const node_type& y) const { 174 return comp(x.value(), y.value()); 175 } 176 Compare comp; 177 }; 178 179 } // namespace boost 180 181 #endif /* BOOST_ARRAY_BINARY_TREE_HPP */ 182