123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150 |
- // 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,
- #ifdef BOOST_NO_CXX11_ALLOCATOR
- std::vector<size_t, typename Alloc::template rebind<size_t>::other >,
- #else
- std::vector<size_t, typename std::allocator_traits<Alloc>::template rebind_alloc<size_t> >,
- #endif
- compare_by_heap_value
- > unvisited_nodes;
- };
- } /* namespace detail */
- } /* namespace heap */
- } /* namespace boost */
- #endif /* BOOST_HEAP_DETAIL_ORDERED_ADAPTOR_ITERATOR_HPP */
|