1 // boost heap: ordered iterator helper classes for container adaptors
3 // Copyright (C) 2011 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_ORDERED_ADAPTOR_ITERATOR_HPP
10 #define BOOST_HEAP_DETAIL_ORDERED_ADAPTOR_ITERATOR_HPP
15 #include <boost/assert.hpp>
16 #include <boost/heap/detail/tree_iterator.hpp>
17 #include <boost/iterator/iterator_adaptor.hpp>
18 #include <boost/concept_check.hpp>
24 /* ordered iterator helper classes for container adaptors
26 * Requirements for Dispatcher:
28 * * static size_type max_index(const ContainerType * heap); // return maximum index
29 * * static bool is_leaf(const ContainerType * heap, size_type index); // return if index denotes a leaf
30 * * static std::pair<size_type, size_type> get_child_nodes(const ContainerType * heap, size_type index); // get index range of child nodes
31 * * static internal_type const & get_internal_value(const ContainerType * heap, size_type index); // get internal value at index
32 * * static value_type const & get_value(internal_type const & arg) const; // get value_type from internal_type
35 template <typename ValueType,
36 typename InternalType,
37 typename ContainerType,
39 typename ValueCompare,
42 class ordered_adaptor_iterator:
43 public boost::iterator_facade<ordered_adaptor_iterator<ValueType,
50 boost::forward_traversal_tag
54 friend class boost::iterator_core_access;
56 struct compare_by_heap_value:
59 const ContainerType * container;
61 compare_by_heap_value (const ContainerType * container, ValueCompare const & cmp):
62 ValueCompare(cmp), container(container)
65 bool operator()(size_t lhs, size_t rhs)
67 BOOST_ASSERT(lhs <= Dispatcher::max_index(container));
68 BOOST_ASSERT(rhs <= Dispatcher::max_index(container));
69 return ValueCompare::operator()(Dispatcher::get_internal_value(container, lhs),
70 Dispatcher::get_internal_value(container, rhs));
74 const ContainerType * container;
75 size_t current_index; // current index: special value -1 denotes `end' iterator
78 ordered_adaptor_iterator(void):
79 container(NULL), current_index((std::numeric_limits<size_t>::max)()),
80 unvisited_nodes(compare_by_heap_value(NULL, ValueCompare()))
83 ordered_adaptor_iterator(const ContainerType * container, ValueCompare const & cmp):
84 container(container), current_index(container->size()),
85 unvisited_nodes(compare_by_heap_value(container, ValueCompare()))
88 ordered_adaptor_iterator(size_t initial_index, const ContainerType * container, ValueCompare const & cmp):
89 container(container), current_index(initial_index),
90 unvisited_nodes(compare_by_heap_value(container, cmp))
92 discover_nodes(initial_index);
96 bool equal (ordered_adaptor_iterator const & rhs) const
98 if (current_index != rhs.current_index)
101 if (container != rhs.container) // less likely than first check
109 if (unvisited_nodes.empty())
110 current_index = Dispatcher::max_index(container) + 1;
112 current_index = unvisited_nodes.top();
113 unvisited_nodes.pop();
114 discover_nodes(current_index);
118 ValueType const & dereference() const
120 BOOST_ASSERT(current_index <= Dispatcher::max_index(container));
121 return Dispatcher::get_value(Dispatcher::get_internal_value(container, current_index));
124 void discover_nodes(size_t index)
126 if (Dispatcher::is_leaf(container, index))
129 std::pair<size_t, size_t> child_range = Dispatcher::get_child_nodes(container, index);
131 for (size_t i = child_range.first; i <= child_range.second; ++i)
132 unvisited_nodes.push(i);
135 std::priority_queue<size_t,
136 std::vector<size_t, typename Alloc::template rebind<size_t>::other >,
137 compare_by_heap_value
142 } /* namespace detail */
143 } /* namespace heap */
144 } /* namespace boost */
146 #endif /* BOOST_HEAP_DETAIL_ORDERED_ADAPTOR_ITERATOR_HPP */