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