Boost C++ Libraries

boost/heap/detail/ordered_adaptor_iterator.hpp

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

#include <boost/assert.hpp>
#include <boost/concept_check.hpp>
#include <boost/heap/detail/tree_iterator.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/iterator/iterator_facade.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( nullptr ),
        current_index( ( std::numeric_limits< size_t >::max )() ),
        unvisited_nodes( compare_by_heap_value( nullptr, 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 boost::allocator_rebind< Alloc, size_t >::type >,
                         compare_by_heap_value >
        unvisited_nodes;
};


}}}    // namespace boost::heap::detail

#endif /* BOOST_HEAP_DETAIL_ORDERED_ADAPTOR_ITERATOR_HPP */