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 <limits>
0013
0014 #include <boost/assert.hpp>
0015 #include <boost/concept_check.hpp>
0016 #include <boost/heap/detail/tree_iterator.hpp>
0017 #include <boost/iterator/iterator_adaptor.hpp>
0018 #include <boost/iterator/iterator_facade.hpp>
0019
0020 namespace boost { namespace heap { namespace detail {
0021
0022 /* ordered iterator helper classes for container adaptors
0023  *
0024  * Requirements for Dispatcher:
0025  *
0026  * * static size_type max_index(const ContainerType * heap); // return maximum index
0027  * * static bool is_leaf(const ContainerType * heap, size_type index); // return if index denotes a leaf
0028  * * static std::pair<size_type, size_type> get_child_nodes(const ContainerType * heap, size_type index); // get index
0029  * range of child nodes
0030  * * static internal_type const & get_internal_value(const ContainerType * heap, size_type index); // get internal value
0031  * 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, typename InternalType, typename ContainerType, typename Alloc, typename ValueCompare, typename Dispatcher >
0036 class ordered_adaptor_iterator :
0037     public boost::iterator_facade<
0038         ordered_adaptor_iterator< ValueType, InternalType, ContainerType, Alloc, ValueCompare, Dispatcher >,
0039         ValueType,
0040         boost::forward_traversal_tag >,
0041     Dispatcher
0042 {
0043     friend class boost::iterator_core_access;
0044
0045     struct compare_by_heap_value : ValueCompare
0046     {
0047         const ContainerType* container;
0048
0049         compare_by_heap_value( const ContainerType* container, ValueCompare const& cmp ) :
0050             ValueCompare( cmp ),
0051             container( container )
0052         {}
0053
0054         bool operator()( size_t lhs, size_t rhs )
0055         {
0056             BOOST_ASSERT( lhs <= Dispatcher::max_index( container ) );
0057             BOOST_ASSERT( rhs <= Dispatcher::max_index( container ) );
0058             return ValueCompare::operator()( Dispatcher::get_internal_value( container, lhs ),
0059                                              Dispatcher::get_internal_value( container, rhs ) );
0060         }
0061     };
0062
0063     const ContainerType* container;
0064     size_t               current_index; // current index: special value -1 denotes `end' iterator
0065
0066 public:
0067     ordered_adaptor_iterator( void ) :
0068         container( nullptr ),
0069         current_index( ( std::numeric_limits< size_t >::max )() ),
0070         unvisited_nodes( compare_by_heap_value( nullptr, ValueCompare() ) )
0071     {}
0072
0073     ordered_adaptor_iterator( const ContainerType* container, ValueCompare const& cmp ) :
0074         container( container ),
0075         current_index( container->size() ),
0076         unvisited_nodes( compare_by_heap_value( container, ValueCompare() ) )
0077     {}
0078
0079     ordered_adaptor_iterator( size_t initial_index, const ContainerType* container, ValueCompare const& cmp ) :
0080         container( container ),
0081         current_index( initial_index ),
0082         unvisited_nodes( compare_by_heap_value( container, cmp ) )
0083     {
0084         discover_nodes( initial_index );
0085     }
0086
0087 private:
0088     bool equal( ordered_adaptor_iterator const& rhs ) const
0089     {
0090         if ( current_index != rhs.current_index )
0091             return false;
0092
0093         if ( container != rhs.container ) // less likely than first check
0094             return false;
0095
0096         return true;
0097     }
0098
0099     void increment( void )
0100     {
0101         if ( unvisited_nodes.empty() )
0102             current_index = Dispatcher::max_index( container ) + 1;
0103         else {
0104             current_index = unvisited_nodes.top();
0105             unvisited_nodes.pop();
0106             discover_nodes( current_index );
0107         }
0108     }
0109
0110     ValueType const& dereference() const
0111     {
0112         BOOST_ASSERT( current_index <= Dispatcher::max_index( container ) );
0113         return Dispatcher::get_value( Dispatcher::get_internal_value( container, current_index ) );
0114     }
0115
0116     void discover_nodes( size_t index )
0117     {
0118         if ( Dispatcher::is_leaf( container, index ) )
0119             return;
0120
0121         std::pair< size_t, size_t > child_range = Dispatcher::get_child_nodes( container, index );
0122
0123         for ( size_t i = child_range.first; i <= child_range.second; ++i )
0124             unvisited_nodes.push( i );
0125     }
0126
0127     std::priority_queue< size_t,
0128                          std::vector< size_t, typename boost::allocator_rebind< Alloc, size_t >::type >,
0129                          compare_by_heap_value >
0130         unvisited_nodes;
0131 };
0132
0133
0134 }}}    // namespace boost::heap::detail
0135
0136 #endif /* BOOST_HEAP_DETAIL_ORDERED_ADAPTOR_ITERATOR_HPP */