]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // boost heap: ordered iterator helper classes for container adaptors |
2 | // | |
3 | // Copyright (C) 2011 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_ORDERED_ADAPTOR_ITERATOR_HPP | |
10 | #define BOOST_HEAP_DETAIL_ORDERED_ADAPTOR_ITERATOR_HPP | |
11 | ||
12 | #include <cassert> | |
13 | #include <limits> | |
14 | ||
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> | |
19 | ||
20 | namespace boost { | |
21 | namespace heap { | |
22 | namespace detail { | |
23 | ||
24 | /* ordered iterator helper classes for container adaptors | |
25 | * | |
26 | * Requirements for Dispatcher: | |
27 | * | |
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 | |
33 | * | |
34 | * */ | |
35 | template <typename ValueType, | |
36 | typename InternalType, | |
37 | typename ContainerType, | |
38 | typename Alloc, | |
39 | typename ValueCompare, | |
40 | typename Dispatcher | |
41 | > | |
42 | class ordered_adaptor_iterator: | |
43 | public boost::iterator_facade<ordered_adaptor_iterator<ValueType, | |
44 | InternalType, | |
45 | ContainerType, | |
46 | Alloc, | |
47 | ValueCompare, | |
48 | Dispatcher>, | |
49 | ValueType, | |
50 | boost::forward_traversal_tag | |
51 | >, | |
52 | Dispatcher | |
53 | { | |
54 | friend class boost::iterator_core_access; | |
55 | ||
56 | struct compare_by_heap_value: | |
57 | ValueCompare | |
58 | { | |
59 | const ContainerType * container; | |
60 | ||
61 | compare_by_heap_value (const ContainerType * container, ValueCompare const & cmp): | |
62 | ValueCompare(cmp), container(container) | |
63 | {} | |
64 | ||
65 | bool operator()(size_t lhs, size_t rhs) | |
66 | { | |
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)); | |
71 | } | |
72 | }; | |
73 | ||
74 | const ContainerType * container; | |
75 | size_t current_index; // current index: special value -1 denotes `end' iterator | |
76 | ||
77 | public: | |
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())) | |
81 | {} | |
82 | ||
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())) | |
86 | {} | |
87 | ||
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)) | |
91 | { | |
92 | discover_nodes(initial_index); | |
93 | } | |
94 | ||
95 | private: | |
96 | bool equal (ordered_adaptor_iterator const & rhs) const | |
97 | { | |
98 | if (current_index != rhs.current_index) | |
99 | return false; | |
100 | ||
101 | if (container != rhs.container) // less likely than first check | |
102 | return false; | |
103 | ||
104 | return true; | |
105 | } | |
106 | ||
107 | void increment(void) | |
108 | { | |
109 | if (unvisited_nodes.empty()) | |
110 | current_index = Dispatcher::max_index(container) + 1; | |
111 | else { | |
112 | current_index = unvisited_nodes.top(); | |
113 | unvisited_nodes.pop(); | |
114 | discover_nodes(current_index); | |
115 | } | |
116 | } | |
117 | ||
118 | ValueType const & dereference() const | |
119 | { | |
120 | BOOST_ASSERT(current_index <= Dispatcher::max_index(container)); | |
121 | return Dispatcher::get_value(Dispatcher::get_internal_value(container, current_index)); | |
122 | } | |
123 | ||
124 | void discover_nodes(size_t index) | |
125 | { | |
126 | if (Dispatcher::is_leaf(container, index)) | |
127 | return; | |
128 | ||
129 | std::pair<size_t, size_t> child_range = Dispatcher::get_child_nodes(container, index); | |
130 | ||
131 | for (size_t i = child_range.first; i <= child_range.second; ++i) | |
132 | unvisited_nodes.push(i); | |
133 | } | |
134 | ||
135 | std::priority_queue<size_t, | |
136 | std::vector<size_t, typename Alloc::template rebind<size_t>::other >, | |
137 | compare_by_heap_value | |
138 | > unvisited_nodes; | |
139 | }; | |
140 | ||
141 | ||
142 | } /* namespace detail */ | |
143 | } /* namespace heap */ | |
144 | } /* namespace boost */ | |
145 | ||
146 | #endif /* BOOST_HEAP_DETAIL_ORDERED_ADAPTOR_ITERATOR_HPP */ |