1 // boost heap: node tree iterator helper classes
3 // Copyright (C) 2010 Tim Blechmann
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)
9 #ifndef BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP
10 #define BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP
15 #include <boost/iterator/iterator_adaptor.hpp>
23 template<typename type>
26 type& operator()(type& x) const BOOST_NOEXCEPT
29 const type& operator()(const type& x) const BOOST_NOEXCEPT
33 template<typename Node>
36 template <typename Iterator>
37 Node * operator()(Iterator const & it)
39 return static_cast<Node *>(*it);
43 template<typename Node>
44 struct pointer_to_reference
46 template <typename Iterator>
47 const Node * operator()(Iterator const & it)
49 return static_cast<const Node *>(&*it);
54 template <typename HandleType,
58 struct unordered_tree_iterator_storage
60 unordered_tree_iterator_storage(ValueCompare const & cmp)
63 void push(HandleType h)
68 HandleType const & top(void)
78 bool empty(void) const
83 std::vector<HandleType, typename Alloc::template rebind<HandleType>::other > data_;
86 template <typename ValueType,
89 typename ValueCompare,
90 typename ValueExtractor
92 struct ordered_tree_iterator_storage:
95 struct compare_values_by_handle:
99 compare_values_by_handle(ValueCompare const & cmp):
103 bool operator()(HandleType const & lhs, HandleType const & rhs) const
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);
111 ordered_tree_iterator_storage(ValueCompare const & cmp):
112 data_(compare_values_by_handle(cmp))
115 void push(HandleType h)
125 HandleType const & top(void)
130 bool empty(void) const BOOST_NOEXCEPT
132 return data_.empty();
135 std::priority_queue<HandleType,
136 std::vector<HandleType, typename Alloc::template rebind<HandleType>::other>,
137 compare_values_by_handle> data_;
141 /* tree iterator helper class
144 * Node provides child_iterator
145 * ValueExtractor can convert Node->value to ValueType
148 template <typename Node,
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>
158 public boost::iterator_adaptor<tree_iterator<Node,
169 boost::forward_traversal_tag
174 typedef boost::iterator_adaptor<tree_iterator<Node,
185 boost::forward_traversal_tag
188 friend class boost::iterator_core_access;
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>
194 unvisited_node_container;
198 adaptor_type(0), unvisited_nodes(ValueCompare())
201 tree_iterator(ValueCompare const & cmp):
202 adaptor_type(0), unvisited_nodes(cmp)
205 tree_iterator(const Node * it, ValueCompare const & cmp):
206 adaptor_type(it), unvisited_nodes(cmp)
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)
217 BOOST_STATIC_ASSERT(ordered_iterator);
221 adaptor_type::base_reference() = top_node;
222 discover_nodes(top_node);
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);
231 bool operator!=(tree_iterator const & rhs) const
233 return adaptor_type::base() != rhs.base();
236 bool operator==(tree_iterator const & rhs) const
238 return !operator!=(rhs);
241 const Node * get_node() const
243 return adaptor_type::base_reference();
249 if (unvisited_nodes.empty())
250 adaptor_type::base_reference() = 0;
252 const Node * next = unvisited_nodes.top();
253 unvisited_nodes.pop();
254 discover_nodes(next);
255 adaptor_type::base_reference() = next;
259 ValueType const & dereference() const
261 return ValueExtractor::operator()(adaptor_type::base_reference()->value);
264 void discover_nodes(const Node * n)
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)
270 unvisited_nodes.push(n);
274 unvisited_node_container unvisited_nodes;
277 template <typename Node, typename NodeList>
278 struct list_iterator_converter
280 typename NodeList::const_iterator operator()(const Node * node)
282 return NodeList::s_iterator_to(*node);
285 Node * operator()(typename NodeList::const_iterator it)
287 return const_cast<Node*>(static_cast<const Node*>(&*it));
291 template <typename Node,
292 typename NodeIterator,
294 typename ValueExtractor = identity<typename Node::value_type>,
295 typename IteratorCoverter = identity<NodeIterator>
297 class recursive_tree_iterator:
298 public boost::iterator_adaptor<recursive_tree_iterator<Node,
306 boost::bidirectional_traversal_tag>,
307 ValueExtractor, IteratorCoverter
309 typedef boost::iterator_adaptor<recursive_tree_iterator<Node,
317 boost::bidirectional_traversal_tag> adaptor_type;
319 friend class boost::iterator_core_access;
323 recursive_tree_iterator(void):
327 explicit recursive_tree_iterator(NodeIterator const & it):
333 NodeIterator next = adaptor_type::base_reference();
335 const Node * n = get_node(next);
336 if (n->children.empty()) {
337 const Node * parent = get_node(next)->get_parent();
342 if (parent == NULL || next != parent->children.end())
345 next = IteratorCoverter::operator()(parent);
346 parent = get_node(next)->get_parent();
350 next = n->children.begin();
352 adaptor_type::base_reference() = next;
356 ValueType const & dereference() const
358 return ValueExtractor::operator()(get_node(adaptor_type::base_reference())->value);
361 static const Node * get_node(NodeIterator const & it)
363 return static_cast<const Node *>(&*it);
366 const Node * get_node() const
368 return get_node(adaptor_type::base_reference());
373 } /* namespace detail */
374 } /* namespace heap */
375 } /* namespace boost */
377 #endif /* BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP */