ceph/src/boost/libs/heap/include/boost/heap/detail/ordered_adaptor_iterator.hpp

   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 */