Boost C++ Libraries

boost/heap/detail/tree_iterator.hpp

// boost heap: node tree iterator helper classes
//
// Copyright (C) 2010 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_TREE_ITERATOR_HPP
#define BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP

#include <functional>
#include <vector>

#include <boost/core/allocator_access.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/type_traits/conditional.hpp>
#include <queue>

namespace boost { namespace heap { namespace detail {


template < typename type >
struct identity
{
    type& operator()( type& x ) const noexcept
    {
        return x;
    }

    const type& operator()( const type& x ) const noexcept
    {
        return x;
    }
};

template < typename Node >
struct dereferencer
{
    template < typename Iterator >
    Node* operator()( Iterator const& it )
    {
        return static_cast< Node* >( *it );
    }
};

template < typename Node >
struct pointer_to_reference
{
    template < typename Iterator >
    const Node* operator()( Iterator const& it )
    {
        return static_cast< const Node* >( &*it );
    }
};


template < typename HandleType, typename Alloc, typename ValueCompare >
struct unordered_tree_iterator_storage
{
    unordered_tree_iterator_storage( ValueCompare const& )
    {}

    void push( HandleType h )
    {
        data_.push_back( h );
    }

    HandleType const& top( void )
    {
        return data_.back();
    }

    void pop( void )
    {
        data_.pop_back();
    }

    bool empty( void ) const
    {
        return data_.empty();
    }

    std::vector< HandleType, typename boost::allocator_rebind< Alloc, HandleType >::type > data_;
};

template < typename ValueType, typename HandleType, typename Alloc, typename ValueCompare, typename ValueExtractor >
struct ordered_tree_iterator_storage : ValueExtractor
{
    struct compare_values_by_handle : ValueExtractor, ValueCompare
    {
        compare_values_by_handle( ValueCompare const& cmp ) :
            ValueCompare( cmp )
        {}

        bool operator()( HandleType const& lhs, HandleType const& rhs ) const
        {
            ValueType const& lhs_value = ValueExtractor::operator()( lhs->value );
            ValueType const& rhs_value = ValueExtractor::operator()( rhs->value );
            return ValueCompare::operator()( lhs_value, rhs_value );
        }
    };

    ordered_tree_iterator_storage( ValueCompare const& cmp ) :
        data_( compare_values_by_handle( cmp ) )
    {}

    void push( HandleType h )
    {
        data_.push( h );
    }

    void pop( void )
    {
        data_.pop();
    }

    HandleType const& top( void )
    {
        return data_.top();
    }

    bool empty( void ) const noexcept
    {
        return data_.empty();
    }

    std::priority_queue< HandleType,
                         std::vector< HandleType, typename boost::allocator_rebind< Alloc, HandleType >::type >,
                         compare_values_by_handle >
        data_;
};


/* tree iterator helper class
 *
 * Requirements:
 * Node provides child_iterator
 * ValueExtractor can convert Node->value to ValueType
 *
 * */
template < typename Node,
           typename ValueType,
           typename Alloc            = std::allocator< Node >,
           typename ValueExtractor   = identity< typename Node::value_type >,
           typename PointerExtractor = dereferencer< Node >,
           bool check_null_pointer   = false,
           bool ordered_iterator     = false,
           typename ValueCompare     = std::less< ValueType > >
class tree_iterator :
    public boost::iterator_adaptor<
        tree_iterator< Node, ValueType, Alloc, ValueExtractor, PointerExtractor, check_null_pointer, ordered_iterator, ValueCompare >,
        const Node*,
        ValueType,
        boost::forward_traversal_tag >,
    ValueExtractor,
    PointerExtractor
{
    typedef boost::iterator_adaptor<
        tree_iterator< Node, ValueType, Alloc, ValueExtractor, PointerExtractor, check_null_pointer, ordered_iterator, ValueCompare >,
        const Node*,
        ValueType,
        boost::forward_traversal_tag >
        adaptor_type;

    friend class boost::iterator_core_access;

    typedef typename std::conditional<
        ordered_iterator,
        ordered_tree_iterator_storage< ValueType, const Node*, Alloc, ValueCompare, ValueExtractor >,
        unordered_tree_iterator_storage< const Node*, Alloc, ValueCompare > >::type unvisited_node_container;

public:
    tree_iterator( void ) :
        adaptor_type( 0 ),
        unvisited_nodes( ValueCompare() )
    {}

    tree_iterator( ValueCompare const& cmp ) :
        adaptor_type( 0 ),
        unvisited_nodes( cmp )
    {}

    tree_iterator( const Node* it, ValueCompare const& cmp ) :
        adaptor_type( it ),
        unvisited_nodes( cmp )
    {
        if ( it )
            discover_nodes( it );
    }

    /* fills the iterator from a list of possible top nodes */
    template < typename NodePointerIterator >
    tree_iterator( NodePointerIterator begin, NodePointerIterator end, const Node* top_node, ValueCompare const& cmp ) :
        adaptor_type( 0 ),
        unvisited_nodes( cmp )
    {
        BOOST_STATIC_ASSERT( ordered_iterator );
        if ( begin == end )
            return;

        adaptor_type::base_reference() = top_node;
        discover_nodes( top_node );

        for ( NodePointerIterator it = begin; it != end; ++it ) {
            const Node* current_node = static_cast< const Node* >( &*it );
            if ( current_node != top_node )
                unvisited_nodes.push( current_node );
        }
    }

    bool operator!=( tree_iterator const& rhs ) const
    {
        return adaptor_type::base() != rhs.base();
    }

    bool operator==( tree_iterator const& rhs ) const
    {
        return !operator!=( rhs );
    }

    const Node* get_node() const
    {
        return adaptor_type::base_reference();
    }

private:
    void increment( void )
    {
        if ( unvisited_nodes.empty() )
            adaptor_type::base_reference() = 0;
        else {
            const Node* next = unvisited_nodes.top();
            unvisited_nodes.pop();
            discover_nodes( next );
            adaptor_type::base_reference() = next;
        }
    }

    ValueType const& dereference() const
    {
        return ValueExtractor::operator()( adaptor_type::base_reference()->value );
    }

    void discover_nodes( const Node* n )
    {
        for ( typename Node::const_child_iterator it = n->children.begin(); it != n->children.end(); ++it ) {
            const Node* n = PointerExtractor::operator()( it );
            if ( check_null_pointer && n == nullptr )
                continue;
            unvisited_nodes.push( n );
        }
    }

    unvisited_node_container unvisited_nodes;
};

template < typename Node, typename NodeList >
struct list_iterator_converter
{
    typename NodeList::const_iterator operator()( const Node* node )
    {
        return NodeList::s_iterator_to( *node );
    }

    Node* operator()( typename NodeList::const_iterator it )
    {
        return const_cast< Node* >( static_cast< const Node* >( &*it ) );
    }
};

template < typename Node,
           typename NodeIterator,
           typename ValueType,
           typename ValueExtractor   = identity< typename Node::value_type >,
           typename IteratorCoverter = identity< NodeIterator > >
class recursive_tree_iterator :
    public boost::iterator_adaptor< recursive_tree_iterator< Node, NodeIterator, ValueType, ValueExtractor, IteratorCoverter >,
                                    NodeIterator,
                                    ValueType const,
                                    boost::bidirectional_traversal_tag >,
    ValueExtractor,
    IteratorCoverter
{
    typedef boost::iterator_adaptor<
        recursive_tree_iterator< Node, NodeIterator, ValueType, ValueExtractor, IteratorCoverter >,
        NodeIterator,
        ValueType const,
        boost::bidirectional_traversal_tag >
        adaptor_type;

    friend class boost::iterator_core_access;


public:
    recursive_tree_iterator( void ) :
        adaptor_type( 0 )
    {}

    explicit recursive_tree_iterator( NodeIterator const& it ) :
        adaptor_type( it )
    {}

    void increment( void )
    {
        NodeIterator next = adaptor_type::base_reference();

        const Node* n = get_node( next );
        if ( n->children.empty() ) {
            const Node* parent = get_node( next )->get_parent();

            ++next;

            while ( true ) {
                if ( parent == nullptr || next != parent->children.end() )
                    break;

                next   = IteratorCoverter::operator()( parent );
                parent = get_node( next )->get_parent();
                ++next;
            }
        } else
            next = n->children.begin();

        adaptor_type::base_reference() = next;
        return;
    }

    ValueType const& dereference() const
    {
        return ValueExtractor::operator()( get_node( adaptor_type::base_reference() )->value );
    }

    static const Node* get_node( NodeIterator const& it )
    {
        return static_cast< const Node* >( &*it );
    }

    const Node* get_node() const
    {
        return get_node( adaptor_type::base_reference() );
    }
};


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

#endif /* BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP */