heap/detail/ordered_adaptor_iterator.hpp

0001 // boost heap: ordered iterator helper classes for container adaptors
0002 //
0003 // Copyright (C) 2011 Tim Blechmann
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 #ifndef BOOST_HEAP_DETAIL_ORDERED_ADAPTOR_ITERATOR_HPP
0010 #define BOOST_HEAP_DETAIL_ORDERED_ADAPTOR_ITERATOR_HPP
0011
0012 #include <cassert>
0013 #include <limits>
0014
0015 #include <boost/assert.hpp>
0016 #include <boost/heap/detail/tree_iterator.hpp>
0017 #include <boost/iterator/iterator_adaptor.hpp>
0018 #include <boost/concept_check.hpp>
0019
0020 namespace boost  {
0021 namespace heap   {
0022 namespace detail {
0023
0024 /* ordered iterator helper classes for container adaptors
0025  *
0026  * Requirements for Dispatcher:
0027  *
0028  * * static size_type max_index(const ContainerType * heap); // return maximum index
0029  * * static bool is_leaf(const ContainerType * heap, size_type index); // return if index denotes a leaf
0030  * * static std::pair<size_type, size_type> get_child_nodes(const ContainerType * heap, size_type index); // get index range of child nodes
0031  * * static internal_type const & get_internal_value(const ContainerType * heap, size_type index); // get internal value at index
0032  * * static value_type const & get_value(internal_type const & arg) const; // get value_type from internal_type
0033  *
0034  * */
0035 template <typename ValueType,
0036           typename InternalType,
0037           typename ContainerType,
0038           typename Alloc,
0039           typename ValueCompare,
0040           typename Dispatcher
0041          >
0042 class ordered_adaptor_iterator:
0043     public boost::iterator_facade<ordered_adaptor_iterator<ValueType,
0044                                                            InternalType,
0045                                                            ContainerType,
0046                                                            Alloc,
0047                                                            ValueCompare,
0048                                                            Dispatcher>,
0049                                   ValueType,
0050                                   boost::forward_traversal_tag
0051                                  >,
0052     Dispatcher
0053 {
0054     friend class boost::iterator_core_access;
0055
0056     struct compare_by_heap_value:
0057         ValueCompare
0058     {
0059         const ContainerType * container;
0060
0061         compare_by_heap_value (const ContainerType * container, ValueCompare const & cmp):
0062             ValueCompare(cmp), container(container)
0063         {}
0064
0065         bool operator()(size_t lhs, size_t rhs)
0066         {
0067             BOOST_ASSERT(lhs <= Dispatcher::max_index(container));
0068             BOOST_ASSERT(rhs <= Dispatcher::max_index(container));
0069             return ValueCompare::operator()(Dispatcher::get_internal_value(container, lhs),
0070                                             Dispatcher::get_internal_value(container, rhs));
0071         }
0072     };
0073
0074     const ContainerType * container;
0075     size_t current_index; // current index: special value -1 denotes `end' iterator
0076
0077 public:
0078     ordered_adaptor_iterator(void):
0079         container(NULL), current_index((std::numeric_limits<size_t>::max)()),
0080         unvisited_nodes(compare_by_heap_value(NULL, ValueCompare()))
0081     {}
0082
0083     ordered_adaptor_iterator(const ContainerType * container, ValueCompare const & cmp):
0084         container(container), current_index(container->size()),
0085         unvisited_nodes(compare_by_heap_value(container, ValueCompare()))
0086     {}
0087
0088     ordered_adaptor_iterator(size_t initial_index, const ContainerType * container, ValueCompare const & cmp):
0089         container(container), current_index(initial_index),
0090         unvisited_nodes(compare_by_heap_value(container, cmp))
0091     {
0092         discover_nodes(initial_index);
0093     }
0094
0095 private:
0096     bool equal (ordered_adaptor_iterator const & rhs) const
0097     {
0098         if (current_index != rhs.current_index)
0099             return false;
0100
0101         if (container != rhs.container) // less likely than first check
0102             return false;
0103
0104         return true;
0105     }
0106
0107     void increment(void)
0108     {
0109         if (unvisited_nodes.empty())
0110             current_index = Dispatcher::max_index(container) + 1;
0111         else {
0112             current_index = unvisited_nodes.top();
0113             unvisited_nodes.pop();
0114             discover_nodes(current_index);
0115         }
0116     }
0117
0118     ValueType const & dereference() const
0119     {
0120         BOOST_ASSERT(current_index <= Dispatcher::max_index(container));
0121         return Dispatcher::get_value(Dispatcher::get_internal_value(container, current_index));
0122     }
0123
0124     void discover_nodes(size_t index)
0125     {
0126         if (Dispatcher::is_leaf(container, index))
0127             return;
0128
0129         std::pair<size_t, size_t> child_range = Dispatcher::get_child_nodes(container, index);
0130
0131         for (size_t i = child_range.first; i <= child_range.second; ++i)
0132             unvisited_nodes.push(i);
0133     }
0134
0135     std::priority_queue<size_t,
0136                         std::vector<size_t, typename boost::allocator_rebind<Alloc, size_t>::type>,
0137                         compare_by_heap_value
0138                        > unvisited_nodes;
0139 };
0140
0141
0142 } /* namespace detail */
0143 } /* namespace heap */
0144 } /* namespace boost */
0145
0146 #endif /* BOOST_HEAP_DETAIL_ORDERED_ADAPTOR_ITERATOR_HPP */