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 /* 22 * Note: array_binary_tree is a completey balanced binary tree. 23 */ 24 #if !defined BOOST_NO_STD_ITERATOR_TRAITS 25 template < class RandomAccessIterator, class ID > 26 #else 27 template < class RandomAccessIterator, class ValueType, class ID > 28 #endif 29 class array_binary_tree_node 30 { 31 public: 32 typedef array_binary_tree_node ArrayBinaryTreeNode; 33 typedef RandomAccessIterator rep_iterator; 34 #if !defined BOOST_NO_STD_ITERATOR_TRAITS 35 typedef 36 typename std::iterator_traits< RandomAccessIterator >::difference_type 37 difference_type; 38 typedef typename std::iterator_traits< RandomAccessIterator >::value_type 39 value_type; 40 #else 41 typedef int difference_type; 42 typedef ValueType value_type; 43 #endif 44 typedef difference_type size_type; 45 46 struct children_type 47 { 48 struct iterator 49 { // replace with iterator_adaptor implementation -JGS 50 typedef std::bidirectional_iterator_tag iterator_category; 51 typedef ArrayBinaryTreeNode value_type; 52 typedef size_type difference_type; 53 typedef array_binary_tree_node* pointer; 54 typedef ArrayBinaryTreeNode& reference; 55 iteratorboost::array_binary_tree_node::children_type::iterator56 inline iterator() : i(0), n(0) {} iteratorboost::array_binary_tree_node::children_type::iterator57 inline iterator(const iterator& x) 58 : r(x.r), i(x.i), n(x.n), id(x.id) 59 { 60 } operator =boost::array_binary_tree_node::children_type::iterator61 inline iterator& operator=(const iterator& x) 62 { 63 r = x.r; 64 i = x.i; 65 n = x.n; 66 /*egcs generate a warning*/ 67 id = x.id; 68 return *this; 69 } iteratorboost::array_binary_tree_node::children_type::iterator70 inline iterator( 71 rep_iterator rr, size_type ii, size_type nn, const ID& _id) 72 : r(rr), i(ii), n(nn), id(_id) 73 { 74 } operator *boost::array_binary_tree_node::children_type::iterator75 inline array_binary_tree_node operator*() 76 { 77 return ArrayBinaryTreeNode(r, i, n, id); 78 } operator ++boost::array_binary_tree_node::children_type::iterator79 inline iterator& operator++() 80 { 81 ++i; 82 return *this; 83 } operator ++boost::array_binary_tree_node::children_type::iterator84 inline iterator operator++(int) 85 { 86 iterator t = *this; 87 ++(*this); 88 return t; 89 } operator --boost::array_binary_tree_node::children_type::iterator90 inline iterator& operator--() 91 { 92 --i; 93 return *this; 94 } operator --boost::array_binary_tree_node::children_type::iterator95 inline iterator operator--(int) 96 { 97 iterator t = *this; 98 --(*this); 99 return t; 100 } operator ==boost::array_binary_tree_node::children_type::iterator101 inline bool operator==(const iterator& x) const { return i == x.i; } operator !=boost::array_binary_tree_node::children_type::iterator102 inline bool operator!=(const iterator& x) const 103 { 104 return !(*this == x); 105 } 106 rep_iterator r; 107 size_type i; 108 size_type n; 109 ID id; 110 }; children_typeboost::array_binary_tree_node::children_type111 inline children_type() : i(0), n(0) {} children_typeboost::array_binary_tree_node::children_type112 inline children_type(const children_type& x) 113 : r(x.r), i(x.i), n(x.n), id(x.id) 114 { 115 } operator =boost::array_binary_tree_node::children_type116 inline children_type& operator=(const children_type& x) 117 { 118 r = x.r; 119 i = x.i; 120 n = x.n; 121 /*egcs generate a warning*/ 122 id = x.id; 123 return *this; 124 } children_typeboost::array_binary_tree_node::children_type125 inline children_type( 126 rep_iterator rr, size_type ii, size_type nn, const ID& _id) 127 : r(rr), i(ii), n(nn), id(_id) 128 { 129 } beginboost::array_binary_tree_node::children_type130 inline iterator begin() { return iterator(r, 2 * i + 1, n, id); } endboost::array_binary_tree_node::children_type131 inline iterator end() { return iterator(r, 2 * i + 1 + size(), n, id); } sizeboost::array_binary_tree_node::children_type132 inline size_type size() const 133 { 134 size_type c = 2 * i + 1; 135 size_type s; 136 if (c + 1 < n) 137 s = 2; 138 else if (c < n) 139 s = 1; 140 else 141 s = 0; 142 return s; 143 } 144 rep_iterator r; 145 size_type i; 146 size_type n; 147 ID id; 148 }; array_binary_tree_node()149 inline array_binary_tree_node() : i(0), n(0) {} array_binary_tree_node(const array_binary_tree_node & x)150 inline array_binary_tree_node(const array_binary_tree_node& x) 151 : r(x.r), i(x.i), n(x.n), id(x.id) 152 { 153 } operator =(const ArrayBinaryTreeNode & x)154 inline ArrayBinaryTreeNode& operator=(const ArrayBinaryTreeNode& x) 155 { 156 r = x.r; 157 i = x.i; 158 n = x.n; 159 /*egcs generate a warning*/ 160 id = x.id; 161 return *this; 162 } array_binary_tree_node(rep_iterator start,rep_iterator end,rep_iterator pos,const ID & _id)163 inline array_binary_tree_node( 164 rep_iterator start, rep_iterator end, rep_iterator pos, const ID& _id) 165 : r(start), i(pos - start), n(end - start), id(_id) 166 { 167 } array_binary_tree_node(rep_iterator rr,size_type ii,size_type nn,const ID & _id)168 inline array_binary_tree_node( 169 rep_iterator rr, size_type ii, size_type nn, const ID& _id) 170 : r(rr), i(ii), n(nn), id(_id) 171 { 172 } value()173 inline value_type& value() { return *(r + i); } value() const174 inline const value_type& value() const { return *(r + i); } parent() const175 inline ArrayBinaryTreeNode parent() const 176 { 177 return ArrayBinaryTreeNode(r, (i - 1) / 2, n, id); 178 } has_parent() const179 inline bool has_parent() const { return i != 0; } children()180 inline children_type children() { return children_type(r, i, n, id); } 181 /* 182 inline void swap(array_binary_tree_node x) { 183 value_type tmp = x.value(); 184 x.value() = value(); 185 value() = tmp; 186 i = x.i; 187 } 188 */ 189 template < class ExternalData > swap(ArrayBinaryTreeNode x,ExternalData & edata)190 inline void swap(ArrayBinaryTreeNode x, ExternalData& edata) 191 { 192 using boost::get; 193 194 value_type tmp = x.value(); 195 196 /*swap external data*/ 197 edata[get(id, tmp)] = i; 198 edata[get(id, value())] = x.i; 199 200 x.value() = value(); 201 value() = tmp; 202 i = x.i; 203 } children() const204 inline const children_type children() const 205 { 206 return children_type(r, i, n); 207 } index() const208 inline size_type index() const { return i; } 209 rep_iterator r; 210 size_type i; 211 size_type n; 212 ID id; 213 }; 214 215 template < class RandomAccessContainer, 216 class Compare = std::less< typename RandomAccessContainer::value_type > > 217 struct compare_array_node 218 { 219 typedef typename RandomAccessContainer::value_type value_type; compare_array_nodeboost::compare_array_node220 compare_array_node(const Compare& x) : comp(x) {} compare_array_nodeboost::compare_array_node221 compare_array_node(const compare_array_node& x) : comp(x.comp) {} 222 223 template < class node_type > operator ()boost::compare_array_node224 inline bool operator()(const node_type& x, const node_type& y) 225 { 226 return comp(x.value(), y.value()); 227 } 228 229 template < class node_type > operator ()boost::compare_array_node230 inline bool operator()(const node_type& x, const node_type& y) const 231 { 232 return comp(x.value(), y.value()); 233 } 234 Compare comp; 235 }; 236 237 } // namespace boost 238 239 #endif /* BOOST_ARRAY_BINARY_TREE_HPP */ 240