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