]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
49 | inline iterator() : i(0), n(0) { } | |
50 | inline iterator(const iterator& x) : r(x.r), i(x.i), n(x.n), id(x.id) { } | |
51 | 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 | } | |
57 | 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) { } | |
61 | inline array_binary_tree_node operator*() { | |
62 | return ArrayBinaryTreeNode(r, i, n, id); } | |
63 | inline iterator& operator++() { ++i; return *this; } | |
64 | inline iterator operator++(int) | |
65 | { iterator t = *this; ++(*this); return t; } | |
66 | inline iterator& operator--() { --i; return *this; } | |
67 | inline iterator operator--(int) | |
68 | { iterator t = *this; --(*this); return t; } | |
69 | inline bool operator==(const iterator& x) const { return i == x.i; } | |
70 | inline bool operator!=(const iterator& x) const | |
71 | { return !(*this == x); } | |
72 | rep_iterator r; | |
73 | size_type i; | |
74 | size_type n; | |
75 | ID id; | |
76 | }; | |
77 | inline children_type() : i(0), n(0) { } | |
78 | inline children_type(const children_type& x) | |
79 | : r(x.r), i(x.i), n(x.n), id(x.id) { } | |
80 | inline children_type& operator=(const children_type& x) { | |
81 | r = x.r; i = x.i; n = x.n; | |
82 | /*egcs generate a warning*/ | |
83 | id = x.id; | |
84 | return *this; | |
85 | } | |
86 | inline children_type(rep_iterator rr, | |
87 | size_type ii, | |
88 | size_type nn, | |
89 | const ID& _id) : r(rr), i(ii), n(nn), id(_id) { } | |
90 | inline iterator begin() { return iterator(r, 2 * i + 1, n, id); } | |
91 | inline iterator end() { return iterator(r, 2 * i + 1 + size(), n, id); } | |
92 | inline size_type size() const { | |
93 | size_type c = 2 * i + 1; | |
94 | size_type s; | |
95 | if (c + 1 < n) s = 2; | |
96 | else if (c < n) s = 1; | |
97 | else s = 0; | |
98 | return s; | |
99 | } | |
100 | rep_iterator r; | |
101 | size_type i; | |
102 | size_type n; | |
103 | ID id; | |
104 | }; | |
105 | inline array_binary_tree_node() : i(0), n(0) { } | |
106 | inline array_binary_tree_node(const array_binary_tree_node& x) | |
107 | : r(x.r), i(x.i), n(x.n), id(x.id) { } | |
108 | inline ArrayBinaryTreeNode& operator=(const ArrayBinaryTreeNode& x) { | |
109 | r = x.r; | |
110 | i = x.i; | |
111 | n = x.n; | |
112 | /*egcs generate a warning*/ | |
113 | id = x.id; | |
114 | return *this; | |
115 | } | |
116 | inline array_binary_tree_node(rep_iterator start, | |
117 | rep_iterator end, | |
118 | rep_iterator pos, const ID& _id) | |
119 | : r(start), i(pos - start), n(end - start), id(_id) { } | |
120 | inline array_binary_tree_node(rep_iterator rr, | |
121 | size_type ii, | |
122 | size_type nn, const ID& _id) | |
123 | : r(rr), i(ii), n(nn), id(_id) { } | |
124 | inline value_type& value() { return *(r + i); } | |
125 | inline const value_type& value() const { return *(r + i); } | |
126 | inline ArrayBinaryTreeNode parent() const { | |
127 | return ArrayBinaryTreeNode(r, (i - 1) / 2, n, id); | |
128 | } | |
129 | inline bool has_parent() const { return i != 0; } | |
130 | inline children_type children() { return children_type(r, i, n, id); } | |
131 | /* | |
132 | inline void swap(array_binary_tree_node x) { | |
133 | value_type tmp = x.value(); | |
134 | x.value() = value(); | |
135 | value() = tmp; | |
136 | i = x.i; | |
137 | } | |
138 | */ | |
139 | template <class ExternalData> | |
140 | inline void swap(ArrayBinaryTreeNode x, ExternalData& edata ) { | |
141 | using boost::get; | |
142 | ||
143 | value_type tmp = x.value(); | |
144 | ||
145 | /*swap external data*/ | |
146 | edata[ get(id, tmp) ] = i; | |
147 | edata[ get(id, value()) ] = x.i; | |
148 | ||
149 | x.value() = value(); | |
150 | value() = tmp; | |
151 | i = x.i; | |
152 | } | |
153 | inline const children_type children() const { | |
154 | return children_type(r, i, n); | |
155 | } | |
156 | inline size_type index() const { return i; } | |
157 | rep_iterator r; | |
158 | size_type i; | |
159 | size_type n; | |
160 | ID id; | |
161 | }; | |
162 | ||
163 | template <class RandomAccessContainer, | |
164 | class Compare = std::less<typename RandomAccessContainer::value_type> > | |
165 | struct compare_array_node { | |
166 | typedef typename RandomAccessContainer::value_type value_type; | |
167 | compare_array_node(const Compare& x) : comp(x) {} | |
168 | compare_array_node(const compare_array_node& x) : comp(x.comp) {} | |
169 | ||
170 | template< class node_type > | |
171 | inline bool operator()(const node_type& x, const node_type& y) { | |
172 | return comp(x.value(), y.value()); | |
173 | } | |
174 | ||
175 | template< class node_type > | |
176 | inline bool operator()(const node_type& x, const node_type& y) const { | |
177 | return comp(x.value(), y.value()); | |
178 | } | |
179 | Compare comp; | |
180 | }; | |
181 | ||
182 | } // namespace boost | |
183 | ||
184 | #endif /* BOOST_ARRAY_BINARY_TREE_HPP */ |