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 compare_by_heap_valueboost::heap::detail::ordered_adaptor_iterator::compare_by_heap_value61 compare_by_heap_value (const ContainerType * container, ValueCompare const & cmp): 62 ValueCompare(cmp), container(container) 63 {} 64 operator ()boost::heap::detail::ordered_adaptor_iterator::compare_by_heap_value65 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: ordered_adaptor_iterator(void)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 ordered_adaptor_iterator(const ContainerType * container,ValueCompare const & cmp)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 ordered_adaptor_iterator(size_t initial_index,const ContainerType * container,ValueCompare const & cmp)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: equal(ordered_adaptor_iterator const & rhs) const96 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 increment(void)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 dereference() const118 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 discover_nodes(size_t index)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 boost::allocator_rebind<Alloc, size_t>::type>, 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 */ 147