| // boost heap: ordered iterator helper classes for container adaptors |
| // |
| // Copyright (C) 2011 Tim Blechmann |
| // |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| |
| #ifndef BOOST_HEAP_DETAIL_ORDERED_ADAPTOR_ITERATOR_HPP |
| #define BOOST_HEAP_DETAIL_ORDERED_ADAPTOR_ITERATOR_HPP |
| |
| #include <cassert> |
| #include <limits> |
| |
| #include <boost/assert.hpp> |
| #include <boost/heap/detail/tree_iterator.hpp> |
| #include <boost/iterator/iterator_adaptor.hpp> |
| #include <boost/concept_check.hpp> |
| |
| namespace boost { |
| namespace heap { |
| namespace detail { |
| |
| /* ordered iterator helper classes for container adaptors |
| * |
| * Requirements for Dispatcher: |
| * |
| * * static size_type max_index(const ContainerType * heap); // return maximum index |
| * * static bool is_leaf(const ContainerType * heap, size_type index); // return if index denotes a leaf |
| * * static std::pair<size_type, size_type> get_child_nodes(const ContainerType * heap, size_type index); // get index range of child nodes |
| * * static internal_type const & get_internal_value(const ContainerType * heap, size_type index); // get internal value at index |
| * * static value_type const & get_value(internal_type const & arg) const; // get value_type from internal_type |
| * |
| * */ |
| template <typename ValueType, |
| typename InternalType, |
| typename ContainerType, |
| typename Alloc, |
| typename ValueCompare, |
| typename Dispatcher |
| > |
| class ordered_adaptor_iterator: |
| public boost::iterator_facade<ordered_adaptor_iterator<ValueType, |
| InternalType, |
| ContainerType, |
| Alloc, |
| ValueCompare, |
| Dispatcher>, |
| ValueType, |
| boost::forward_traversal_tag |
| >, |
| Dispatcher |
| { |
| friend class boost::iterator_core_access; |
| |
| struct compare_by_heap_value: |
| ValueCompare |
| { |
| const ContainerType * container; |
| |
| compare_by_heap_value (const ContainerType * container, ValueCompare const & cmp): |
| ValueCompare(cmp), container(container) |
| {} |
| |
| bool operator()(size_t lhs, size_t rhs) |
| { |
| BOOST_ASSERT(lhs <= Dispatcher::max_index(container)); |
| BOOST_ASSERT(rhs <= Dispatcher::max_index(container)); |
| return ValueCompare::operator()(Dispatcher::get_internal_value(container, lhs), |
| Dispatcher::get_internal_value(container, rhs)); |
| } |
| }; |
| |
| const ContainerType * container; |
| size_t current_index; // current index: special value -1 denotes `end' iterator |
| |
| public: |
| ordered_adaptor_iterator(void): |
| container(NULL), current_index((std::numeric_limits<size_t>::max)()), |
| unvisited_nodes(compare_by_heap_value(NULL, ValueCompare())) |
| {} |
| |
| ordered_adaptor_iterator(const ContainerType * container, ValueCompare const & cmp): |
| container(container), current_index(container->size()), |
| unvisited_nodes(compare_by_heap_value(container, ValueCompare())) |
| {} |
| |
| ordered_adaptor_iterator(size_t initial_index, const ContainerType * container, ValueCompare const & cmp): |
| container(container), current_index(initial_index), |
| unvisited_nodes(compare_by_heap_value(container, cmp)) |
| { |
| discover_nodes(initial_index); |
| } |
| |
| private: |
| bool equal (ordered_adaptor_iterator const & rhs) const |
| { |
| if (current_index != rhs.current_index) |
| return false; |
| |
| if (container != rhs.container) // less likely than first check |
| return false; |
| |
| return true; |
| } |
| |
| void increment(void) |
| { |
| if (unvisited_nodes.empty()) |
| current_index = Dispatcher::max_index(container) + 1; |
| else { |
| current_index = unvisited_nodes.top(); |
| unvisited_nodes.pop(); |
| discover_nodes(current_index); |
| } |
| } |
| |
| ValueType const & dereference() const |
| { |
| BOOST_ASSERT(current_index <= Dispatcher::max_index(container)); |
| return Dispatcher::get_value(Dispatcher::get_internal_value(container, current_index)); |
| } |
| |
| void discover_nodes(size_t index) |
| { |
| if (Dispatcher::is_leaf(container, index)) |
| return; |
| |
| std::pair<size_t, size_t> child_range = Dispatcher::get_child_nodes(container, index); |
| |
| for (size_t i = child_range.first; i <= child_range.second; ++i) |
| unvisited_nodes.push(i); |
| } |
| |
| std::priority_queue<size_t, |
| std::vector<size_t, typename Alloc::template rebind<size_t>::other >, |
| compare_by_heap_value |
| > unvisited_nodes; |
| }; |
| |
| |
| } /* namespace detail */ |
| } /* namespace heap */ |
| } /* namespace boost */ |
| |
| #endif /* BOOST_HEAP_DETAIL_ORDERED_ADAPTOR_ITERATOR_HPP */ |