• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
20 namespace boost  {
21 namespace heap   {
22 namespace detail {
23 
24 
25 template<typename type>
26 struct identity
27 {
operator ()boost::heap::detail::identity28     type& operator()(type& x) const BOOST_NOEXCEPT
29     { return x; }
30 
operator ()boost::heap::detail::identity31     const type& operator()(const type& x) const BOOST_NOEXCEPT
32     { return x; }
33 };
34 
35 template<typename Node>
36 struct dereferencer
37 {
38     template <typename Iterator>
operator ()boost::heap::detail::dereferencer39     Node * operator()(Iterator const & it)
40     {
41         return static_cast<Node *>(*it);
42     }
43 };
44 
45 template<typename Node>
46 struct pointer_to_reference
47 {
48     template <typename Iterator>
operator ()boost::heap::detail::pointer_to_reference49     const Node * operator()(Iterator const & it)
50     {
51         return static_cast<const Node *>(&*it);
52     }
53 };
54 
55 
56 template <typename HandleType,
57           typename Alloc,
58           typename ValueCompare
59          >
60 struct unordered_tree_iterator_storage
61 {
unordered_tree_iterator_storageboost::heap::detail::unordered_tree_iterator_storage62     unordered_tree_iterator_storage(ValueCompare const & cmp)
63     {}
64 
pushboost::heap::detail::unordered_tree_iterator_storage65     void push(HandleType h)
66     {
67         data_.push_back(h);
68     }
69 
topboost::heap::detail::unordered_tree_iterator_storage70     HandleType const & top(void)
71     {
72         return data_.back();
73     }
74 
popboost::heap::detail::unordered_tree_iterator_storage75     void pop(void)
76     {
77         data_.pop_back();
78     }
79 
emptyboost::heap::detail::unordered_tree_iterator_storage80     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 
88 template <typename ValueType,
89           typename HandleType,
90           typename Alloc,
91           typename ValueCompare,
92           typename ValueExtractor
93          >
94 struct ordered_tree_iterator_storage:
95     ValueExtractor
96 {
97     struct compare_values_by_handle:
98         ValueExtractor,
99         ValueCompare
100     {
compare_values_by_handleboost::heap::detail::ordered_tree_iterator_storage::compare_values_by_handle101         compare_values_by_handle(ValueCompare const & cmp):
102             ValueCompare(cmp)
103         {}
104 
operator ()boost::heap::detail::ordered_tree_iterator_storage::compare_values_by_handle105         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 
ordered_tree_iterator_storageboost::heap::detail::ordered_tree_iterator_storage113     ordered_tree_iterator_storage(ValueCompare const & cmp):
114         data_(compare_values_by_handle(cmp))
115     {}
116 
pushboost::heap::detail::ordered_tree_iterator_storage117     void push(HandleType h)
118     {
119         data_.push(h);
120     }
121 
popboost::heap::detail::ordered_tree_iterator_storage122     void pop(void)
123     {
124         data_.pop();
125     }
126 
topboost::heap::detail::ordered_tree_iterator_storage127     HandleType const & top(void)
128     {
129         return data_.top();
130     }
131 
emptyboost::heap::detail::ordered_tree_iterator_storage132     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  * */
150 template <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          >
159 class 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 
198 public:
tree_iterator(void)199     tree_iterator(void):
200         adaptor_type(0), unvisited_nodes(ValueCompare())
201     {}
202 
tree_iterator(ValueCompare const & cmp)203     tree_iterator(ValueCompare const & cmp):
204         adaptor_type(0), unvisited_nodes(cmp)
205     {}
206 
tree_iterator(const Node * it,ValueCompare const & cmp)207     tree_iterator(const Node * it, ValueCompare const & cmp):
208         adaptor_type(it), unvisited_nodes(cmp)
209     {
210         if (it)
211             discover_nodes(it);
212     }
213 
214     /* fills the iterator from a list of possible top nodes */
215     template <typename NodePointerIterator>
tree_iterator(NodePointerIterator begin,NodePointerIterator end,const Node * top_node,ValueCompare const & cmp)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(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 
operator !=(tree_iterator const & rhs) const233     bool operator!=(tree_iterator const & rhs) const
234     {
235         return adaptor_type::base() != rhs.base();
236     }
237 
operator ==(tree_iterator const & rhs) const238     bool operator==(tree_iterator const & rhs) const
239     {
240         return !operator!=(rhs);
241     }
242 
get_node() const243     const Node * get_node() const
244     {
245         return adaptor_type::base_reference();
246     }
247 
248 private:
increment(void)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(next);
257             adaptor_type::base_reference() = next;
258         }
259     }
260 
dereference() const261     ValueType const & dereference() const
262     {
263         return ValueExtractor::operator()(adaptor_type::base_reference()->value);
264     }
265 
discover_nodes(const Node * n)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 
279 template <typename Node, typename NodeList>
280 struct list_iterator_converter
281 {
operator ()boost::heap::detail::list_iterator_converter282     typename NodeList::const_iterator operator()(const Node * node)
283     {
284         return NodeList::s_iterator_to(*node);
285     }
286 
operator ()boost::heap::detail::list_iterator_converter287     Node * operator()(typename NodeList::const_iterator it)
288     {
289         return const_cast<Node*>(static_cast<const Node*>(&*it));
290     }
291 };
292 
293 template <typename Node,
294           typename NodeIterator,
295           typename ValueType,
296           typename ValueExtractor = identity<typename Node::value_type>,
297           typename IteratorCoverter = identity<NodeIterator>
298          >
299 class 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 
324 public:
recursive_tree_iterator(void)325     recursive_tree_iterator(void):
326         adaptor_type(0)
327     {}
328 
recursive_tree_iterator(NodeIterator const & it)329     explicit recursive_tree_iterator(NodeIterator const & it):
330         adaptor_type(it)
331     {}
332 
increment(void)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 
dereference() const358     ValueType const & dereference() const
359     {
360         return ValueExtractor::operator()(get_node(adaptor_type::base_reference())->value);
361     }
362 
get_node(NodeIterator const & it)363     static const Node * get_node(NodeIterator const & it)
364     {
365         return static_cast<const Node *>(&*it);
366     }
367 
get_node() const368     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