// 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 <cassert>
#include <limits>

#include <boost/assert.hpp>
#include <boost/heap/detail/tree_iterator.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/concept_check.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(NULL), current_index((std::numeric_limits<size_t>::max)()),
        unvisited_nodes(compare_by_heap_value(NULL, 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 detail */
} /* namespace heap */
} /* namespace boost */

#endif /* BOOST_HEAP_DETAIL_ORDERED_ADAPTOR_ITERATOR_HPP */