1// boost heap: node tree iterator helper classes
2//
3// Copyright (C) 2010 Tim Blechmann
4//
5// Distributed under the Boost Software License, Version 1.0. (See
6// accompanying file LICENSE_1_0.txt or copy at
7// http://www.boost.org/LICENSE_1_0.txt)
8
9#ifndef BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP
10#define BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP
11
12#include <functional>
13#include <vector>
14
15#include <boost/core/allocator_access.hpp>
16#include <boost/iterator/iterator_adaptor.hpp>
17#include <boost/type_traits/conditional.hpp>
18#include <queue>
19
20namespace boost {
21namespace heap {
22namespace detail {
23
24
25template<typename type>
26struct identity
27{
28 type& operator()(type& x) const BOOST_NOEXCEPT
29 { return x; }
30
31 const type& operator()(const type& x) const BOOST_NOEXCEPT
32 { return x; }
33};
34
35template<typename Node>
36struct dereferencer
37{
38 template <typename Iterator>
39 Node * operator()(Iterator const & it)
40 {
41 return static_cast<Node *>(*it);
42 }
43};
44
45template<typename Node>
46struct pointer_to_reference
47{
48 template <typename Iterator>
49 const Node * operator()(Iterator const & it)
50 {
51 return static_cast<const Node *>(&*it);
52 }
53};
54
55
56template <typename HandleType,
57 typename Alloc,
58 typename ValueCompare
59 >
60struct unordered_tree_iterator_storage
61{
62 unordered_tree_iterator_storage(ValueCompare const & cmp)
63 {}
64
65 void push(HandleType h)
66 {
67 data_.push_back(h);
68 }
69
70 HandleType const & top(void)
71 {
72 return data_.back();
73 }
74
75 void pop(void)
76 {
77 data_.pop_back();
78 }
79
80 bool empty(void) const
81 {
82 return data_.empty();
83 }
84
85 std::vector<HandleType, typename boost::allocator_rebind<Alloc, HandleType>::type> data_;
86};
87
88template <typename ValueType,
89 typename HandleType,
90 typename Alloc,
91 typename ValueCompare,
92 typename ValueExtractor
93 >
94struct ordered_tree_iterator_storage:
95 ValueExtractor
96{
97 struct compare_values_by_handle:
98 ValueExtractor,
99 ValueCompare
100 {
101 compare_values_by_handle(ValueCompare const & cmp):
102 ValueCompare(cmp)
103 {}
104
105 bool operator()(HandleType const & lhs, HandleType const & rhs) const
106 {
107 ValueType const & lhs_value = ValueExtractor::operator()(lhs->value);
108 ValueType const & rhs_value = ValueExtractor::operator()(rhs->value);
109 return ValueCompare::operator()(lhs_value, rhs_value);
110 }
111 };
112
113 ordered_tree_iterator_storage(ValueCompare const & cmp):
114 data_(compare_values_by_handle(cmp))
115 {}
116
117 void push(HandleType h)
118 {
119 data_.push(h);
120 }
121
122 void pop(void)
123 {
124 data_.pop();
125 }
126
127 HandleType const & top(void)
128 {
129 return data_.top();
130 }
131
132 bool empty(void) const BOOST_NOEXCEPT
133 {
134 return data_.empty();
135 }
136
137 std::priority_queue<HandleType,
138 std::vector<HandleType, typename boost::allocator_rebind<Alloc, HandleType>::type>,
139 compare_values_by_handle> data_;
140};
141
142
143/* tree iterator helper class
144 *
145 * Requirements:
146 * Node provides child_iterator
147 * ValueExtractor can convert Node->value to ValueType
148 *
149 * */
150template <typename Node,
151 typename ValueType,
152 typename Alloc = std::allocator<Node>,
153 typename ValueExtractor = identity<typename Node::value_type>,
154 typename PointerExtractor = dereferencer<Node>,
155 bool check_null_pointer = false,
156 bool ordered_iterator = false,
157 typename ValueCompare = std::less<ValueType>
158 >
159class tree_iterator:
160 public boost::iterator_adaptor<tree_iterator<Node,
161 ValueType,
162 Alloc,
163 ValueExtractor,
164 PointerExtractor,
165 check_null_pointer,
166 ordered_iterator,
167 ValueCompare
168 >,
169 const Node *,
170 ValueType,
171 boost::forward_traversal_tag
172 >,
173 ValueExtractor,
174 PointerExtractor
175{
176 typedef boost::iterator_adaptor<tree_iterator<Node,
177 ValueType,
178 Alloc,
179 ValueExtractor,
180 PointerExtractor,
181 check_null_pointer,
182 ordered_iterator,
183 ValueCompare
184 >,
185 const Node *,
186 ValueType,
187 boost::forward_traversal_tag
188 > adaptor_type;
189
190 friend class boost::iterator_core_access;
191
192 typedef typename boost::conditional< ordered_iterator,
193 ordered_tree_iterator_storage<ValueType, const Node*, Alloc, ValueCompare, ValueExtractor>,
194 unordered_tree_iterator_storage<const Node*, Alloc, ValueCompare>
195 >::type
196 unvisited_node_container;
197
198public:
199 tree_iterator(void):
200 adaptor_type(0), unvisited_nodes(ValueCompare())
201 {}
202
203 tree_iterator(ValueCompare const & cmp):
204 adaptor_type(0), unvisited_nodes(cmp)
205 {}
206
207 tree_iterator(const Node * it, ValueCompare const & cmp):
208 adaptor_type(it), unvisited_nodes(cmp)
209 {
210 if (it)
211 discover_nodes(n: it);
212 }
213
214 /* fills the iterator from a list of possible top nodes */
215 template <typename NodePointerIterator>
216 tree_iterator(NodePointerIterator begin, NodePointerIterator end, const Node * top_node, ValueCompare const & cmp):
217 adaptor_type(0), unvisited_nodes(cmp)
218 {
219 BOOST_STATIC_ASSERT(ordered_iterator);
220 if (begin == end)
221 return;
222
223 adaptor_type::base_reference() = top_node;
224 discover_nodes(n: top_node);
225
226 for (NodePointerIterator it = begin; it != end; ++it) {
227 const Node * current_node = static_cast<const Node*>(&*it);
228 if (current_node != top_node)
229 unvisited_nodes.push(current_node);
230 }
231 }
232
233 bool operator!=(tree_iterator const & rhs) const
234 {
235 return adaptor_type::base() != rhs.base();
236 }
237
238 bool operator==(tree_iterator const & rhs) const
239 {
240 return !operator!=(rhs);
241 }
242
243 const Node * get_node() const
244 {
245 return adaptor_type::base_reference();
246 }
247
248private:
249 void increment(void)
250 {
251 if (unvisited_nodes.empty())
252 adaptor_type::base_reference() = 0;
253 else {
254 const Node * next = unvisited_nodes.top();
255 unvisited_nodes.pop();
256 discover_nodes(n: next);
257 adaptor_type::base_reference() = next;
258 }
259 }
260
261 ValueType const & dereference() const
262 {
263 return ValueExtractor::operator()(adaptor_type::base_reference()->value);
264 }
265
266 void discover_nodes(const Node * n)
267 {
268 for (typename Node::const_child_iterator it = n->children.begin(); it != n->children.end(); ++it) {
269 const Node * n = PointerExtractor::operator()(it);
270 if (check_null_pointer && n == NULL)
271 continue;
272 unvisited_nodes.push(n);
273 }
274 }
275
276 unvisited_node_container unvisited_nodes;
277};
278
279template <typename Node, typename NodeList>
280struct list_iterator_converter
281{
282 typename NodeList::const_iterator operator()(const Node * node)
283 {
284 return NodeList::s_iterator_to(*node);
285 }
286
287 Node * operator()(typename NodeList::const_iterator it)
288 {
289 return const_cast<Node*>(static_cast<const Node*>(&*it));
290 }
291};
292
293template <typename Node,
294 typename NodeIterator,
295 typename ValueType,
296 typename ValueExtractor = identity<typename Node::value_type>,
297 typename IteratorCoverter = identity<NodeIterator>
298 >
299class recursive_tree_iterator:
300 public boost::iterator_adaptor<recursive_tree_iterator<Node,
301 NodeIterator,
302 ValueType,
303 ValueExtractor,
304 IteratorCoverter
305 >,
306 NodeIterator,
307 ValueType const,
308 boost::bidirectional_traversal_tag>,
309 ValueExtractor, IteratorCoverter
310{
311 typedef boost::iterator_adaptor<recursive_tree_iterator<Node,
312 NodeIterator,
313 ValueType,
314 ValueExtractor,
315 IteratorCoverter
316 >,
317 NodeIterator,
318 ValueType const,
319 boost::bidirectional_traversal_tag> adaptor_type;
320
321 friend class boost::iterator_core_access;
322
323
324public:
325 recursive_tree_iterator(void):
326 adaptor_type(0)
327 {}
328
329 explicit recursive_tree_iterator(NodeIterator const & it):
330 adaptor_type(it)
331 {}
332
333 void increment(void)
334 {
335 NodeIterator next = adaptor_type::base_reference();
336
337 const Node * n = get_node(next);
338 if (n->children.empty()) {
339 const Node * parent = get_node(next)->get_parent();
340
341 ++next;
342
343 while (true) {
344 if (parent == NULL || next != parent->children.end())
345 break;
346
347 next = IteratorCoverter::operator()(parent);
348 parent = get_node(next)->get_parent();
349 ++next;
350 }
351 } else
352 next = n->children.begin();
353
354 adaptor_type::base_reference() = next;
355 return;
356 }
357
358 ValueType const & dereference() const
359 {
360 return ValueExtractor::operator()(get_node(adaptor_type::base_reference())->value);
361 }
362
363 static const Node * get_node(NodeIterator const & it)
364 {
365 return static_cast<const Node *>(&*it);
366 }
367
368 const Node * get_node() const
369 {
370 return get_node(adaptor_type::base_reference());
371 }
372};
373
374
375} /* namespace detail */
376} /* namespace heap */
377} /* namespace boost */
378
379#endif /* BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP */
380

source code of boost/libs/heap/include/boost/heap/detail/tree_iterator.hpp