heap/detail/mutable_heap.hpp

// boost heap
//
// 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_MUTABLE_HEAP_HPP
#define BOOST_HEAP_DETAIL_MUTABLE_HEAP_HPP

/*! \file
 * INTERNAL ONLY
 */

#include <list>
#include <utility>

#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/heap/detail/ordered_adaptor_iterator.hpp>

namespace boost  {
namespace heap   {
namespace detail {

/* wrapper for a mutable heap container adaptors
 *
 * this wrapper introduces an additional indirection. the heap is not constructed from objects,
 * but instead from std::list iterators. this way, the mutability is achieved
 *
 */
template <typename PriorityQueueType>
class priority_queue_mutable_wrapper
{
public:
    typedef typename PriorityQueueType::value_type value_type;
    typedef typename PriorityQueueType::size_type size_type;
    typedef typename PriorityQueueType::value_compare value_compare;
    typedef typename PriorityQueueType::allocator_type allocator_type;

    typedef typename PriorityQueueType::reference reference;
    typedef typename PriorityQueueType::const_reference const_reference;
    typedef typename PriorityQueueType::pointer pointer;
    typedef typename PriorityQueueType::const_pointer const_pointer;
    static const bool is_stable = PriorityQueueType::is_stable;

private:
    typedef std::pair<value_type, size_type> node_type;

    typedef std::list<node_type, typename allocator_type::template rebind<node_type>::other> object_list;

    typedef typename object_list::iterator list_iterator;
    typedef typename object_list::const_iterator const_list_iterator;

    template <typename Heap1, typename Heap2>
    friend struct heap_merge_emulate;

    typedef typename PriorityQueueType::super_t::stability_counter_type stability_counter_type;

    stability_counter_type get_stability_count(void) const
    {
        return q_.get_stability_count();
    }

    void set_stability_count(stability_counter_type new_count)
    {
        q_.set_stability_count(new_count);
    }

    struct index_updater
    {
        template <typename It>
        static void run(It & it, size_type new_index)
        {
            q_type::get_value(it)->second = new_index;
        }
    };

public:
    struct handle_type
    {
        value_type & operator*() const
        {
            return iterator->first;
        }

        handle_type (void)
        {}

        handle_type(handle_type const & rhs):
            iterator(rhs.iterator)
        {}

        bool operator==(handle_type const & rhs) const
        {
            return iterator == rhs.iterator;
        }

        bool operator!=(handle_type const & rhs) const
        {
            return iterator != rhs.iterator;
        }

    private:
        explicit handle_type(list_iterator const & it):
            iterator(it)
        {}

        list_iterator iterator;

        friend class priority_queue_mutable_wrapper;
    };

private:
    struct indirect_cmp:
        public value_compare
    {
        indirect_cmp(value_compare const & cmp = value_compare()):
            value_compare(cmp)
        {}

        bool operator()(const_list_iterator const & lhs, const_list_iterator const & rhs) const
        {
            return value_compare::operator()(lhs->first, rhs->first);
        }
    };

    typedef typename PriorityQueueType::template rebind<list_iterator,
                                                        indirect_cmp,
                                                        allocator_type, index_updater >::other q_type;

protected:
    q_type q_;
    object_list objects;

protected:
    priority_queue_mutable_wrapper(value_compare const & cmp = value_compare()):
        q_(cmp)
    {}

    priority_queue_mutable_wrapper(priority_queue_mutable_wrapper const & rhs):
        q_(rhs.q_), objects(rhs.objects)
    {
        for (typename object_list::iterator it = objects.begin(); it != objects.end(); ++it)
            q_.push(it);
    }

    priority_queue_mutable_wrapper & operator=(priority_queue_mutable_wrapper const & rhs)
    {
        q_ = rhs.q_;
        objects = rhs.objects;
        q_.clear();
        for (typename object_list::iterator it = objects.begin(); it != objects.end(); ++it)
            q_.push(it);
        return *this;
    }

#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
    priority_queue_mutable_wrapper (priority_queue_mutable_wrapper && rhs):
        q_(std::move(rhs.q_))
    {
        /// FIXME: msvc seems to invalidate iterators when moving std::list
        std::swap(objects, rhs.objects);
    }

    priority_queue_mutable_wrapper & operator=(priority_queue_mutable_wrapper && rhs)
    {
        q_ = std::move(rhs.q_);
        objects.clear();
        std::swap(objects, rhs.objects);
        return *this;
    }
#endif


public:
    template <typename iterator_type>
    class iterator_base:
        public boost::iterator_adaptor<iterator_base<iterator_type>,
                                       iterator_type,
                                       value_type const,
                                       boost::bidirectional_traversal_tag>
    {
        typedef boost::iterator_adaptor<iterator_base<iterator_type>,
                                       iterator_type,
                                       value_type const,
                                       boost::bidirectional_traversal_tag> super_t;

        friend class boost::iterator_core_access;
        friend class priority_queue_mutable_wrapper;

        iterator_base(void):
            super_t(0)
        {}

        template <typename T>
        explicit iterator_base(T const & it):
            super_t(it)
        {}

        value_type const & dereference() const
        {
            return super_t::base()->first;
        }

        iterator_type get_list_iterator() const
        {
            return super_t::base_reference();
        }
    };

    typedef iterator_base<list_iterator> iterator;
    typedef iterator_base<const_list_iterator> const_iterator;

    typedef typename object_list::difference_type difference_type;

    class ordered_iterator:
        public boost::iterator_adaptor<ordered_iterator,
                                       const_list_iterator,
                                       value_type const,
                                       boost::forward_traversal_tag
                                      >,
        q_type::ordered_iterator_dispatcher
    {
        typedef boost::iterator_adaptor<ordered_iterator,
                                        const_list_iterator,
                                        value_type const,
                                        boost::forward_traversal_tag
                                      > adaptor_type;

        typedef const_list_iterator iterator;
        typedef typename q_type::ordered_iterator_dispatcher ordered_iterator_dispatcher;

        friend class boost::iterator_core_access;

    public:
        ordered_iterator(void):
            adaptor_type(0), unvisited_nodes(indirect_cmp()), q_(NULL)
        {}

        ordered_iterator(const priority_queue_mutable_wrapper * q, indirect_cmp const & cmp):
            adaptor_type(0), unvisited_nodes(cmp), q_(q)
        {}

        ordered_iterator(const_list_iterator it, const priority_queue_mutable_wrapper * q, indirect_cmp const & cmp):
            adaptor_type(it), unvisited_nodes(cmp), q_(q)
        {
            if (it != q->objects.end())
                discover_nodes(it);
        }

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

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

    private:
        void increment(void)
        {
            if (unvisited_nodes.empty())
                adaptor_type::base_reference() = q_->objects.end();
            else {
                iterator next = unvisited_nodes.top();
                unvisited_nodes.pop();
                discover_nodes(next);
                adaptor_type::base_reference() = next;
            }
        }

        value_type const & dereference() const
        {
            return adaptor_type::base()->first;
        }

        void discover_nodes(iterator current)
        {
            size_type current_index = current->second;
            const q_type * q = &(q_->q_);

            if (ordered_iterator_dispatcher::is_leaf(q, current_index))
                return;

            std::pair<size_type, size_type> child_range = ordered_iterator_dispatcher::get_child_nodes(q, current_index);

            for (size_type i = child_range.first; i <= child_range.second; ++i) {
                typename q_type::internal_type const & internal_value_at_index = ordered_iterator_dispatcher::get_internal_value(q, i);
                typename q_type::value_type const & value_at_index = q_->q_.get_value(internal_value_at_index);

                unvisited_nodes.push(value_at_index);
            }
        }

        std::priority_queue<iterator,
                            std::vector<iterator, typename allocator_type::template rebind<iterator>::other >,
                            indirect_cmp
                           > unvisited_nodes;
        const priority_queue_mutable_wrapper * q_;
    };

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

    size_type size(void) const
    {
        return q_.size();
    }

    size_type max_size(void) const
    {
        return objects.max_size();
    }

    void clear(void)
    {
        q_.clear();
        objects.clear();
    }

    allocator_type get_allocator(void) const
    {
        return q_.get_allocator();
    }

    void swap(priority_queue_mutable_wrapper & rhs)
    {
        objects.swap(rhs.objects);
        q_.swap(rhs.q_);
    }

    const_reference top(void) const
    {
        BOOST_ASSERT(!empty());
        return q_.top()->first;
    }

    handle_type push(value_type const & v)
    {
        objects.push_front(std::make_pair(v, 0));
        list_iterator ret = objects.begin();
        q_.push(ret);
        return handle_type(ret);
    }

#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
    template <class... Args>
    handle_type emplace(Args&&... args)
    {
        objects.push_front(std::make_pair(std::forward<Args>(args)..., 0));
        list_iterator ret = objects.begin();
        q_.push(ret);
        return handle_type(ret);
    }
#endif

    void pop(void)
    {
        BOOST_ASSERT(!empty());
        list_iterator q_top = q_.top();
        q_.pop();
        objects.erase(q_top);
    }

    /**
     * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
     *
     * \b Complexity: Logarithmic.
     *
     * */
    void update(handle_type handle, const_reference v)
    {
        list_iterator it = handle.iterator;
        value_type const & current_value = it->first;
        value_compare const & cmp = q_.value_comp();
        if (cmp(v, current_value))
            decrease(handle, v);
        else
            increase(handle, v);
    }

    /**
     * \b Effects: Updates the heap after the element handled by \c handle has been changed.
     *
     * \b Complexity: Logarithmic.
     *
     * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
     * */
    void update(handle_type handle)
    {
        list_iterator it = handle.iterator;
        size_type index = it->second;
        q_.update(index);
    }

     /**
     * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
     *
     * \b Complexity: Logarithmic.
     *
     * \b Note: The new value is expected to be greater than the current one
     * */
    void increase(handle_type handle, const_reference v)
    {
        BOOST_ASSERT(!value_compare()(v, handle.iterator->first));
        handle.iterator->first = v;
        increase(handle);
    }

    /**
     * \b Effects: Updates the heap after the element handled by \c handle has been changed.
     *
     * \b Complexity: Logarithmic.
     *
     * \b Note: The new value is expected to be greater than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
     * */
    void increase(handle_type handle)
    {
        list_iterator it = handle.iterator;
        size_type index = it->second;
        q_.increase(index);
    }

     /**
     * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
     *
     * \b Complexity: Logarithmic.
     *
     * \b Note: The new value is expected to be less than the current one
     * */
    void decrease(handle_type handle, const_reference v)
    {
        BOOST_ASSERT(!value_compare()(handle.iterator->first, v));
        handle.iterator->first = v;
        decrease(handle);
    }

    /**
     * \b Effects: Updates the heap after the element handled by \c handle has been changed.
     *
     * \b Complexity: Logarithmic.
     *
     * \b Note: The new value is expected to be less than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
     * */
    void decrease(handle_type handle)
    {
        list_iterator it = handle.iterator;
        size_type index = it->second;
        q_.decrease(index);
    }

    /**
     * \b Effects: Removes the element handled by \c handle from the priority_queue.
     *
     * \b Complexity: Logarithmic.
     * */
    void erase(handle_type handle)
    {
        list_iterator it = handle.iterator;
        size_type index = it->second;
        q_.erase(index);
        objects.erase(it);
    }

    const_iterator begin(void) const
    {
        return const_iterator(objects.begin());
    }

    const_iterator end(void) const
    {
        return const_iterator(objects.end());
    }

    iterator begin(void)
    {
        return iterator(objects.begin());
    }

    iterator end(void)
    {
        return iterator(objects.end());
    }

    ordered_iterator ordered_begin(void) const
    {
        if (!empty())
            return ordered_iterator(q_.top(), this, indirect_cmp(q_.value_comp()));
        else
            return ordered_end();
    }

    ordered_iterator ordered_end(void) const
    {
        return ordered_iterator(objects.end(), this, indirect_cmp(q_.value_comp()));
    }

    static handle_type s_handle_from_iterator(iterator const & it)
    {
        return handle_type(it.get_list_iterator());
    }

    value_compare const & value_comp(void) const
    {
        return q_.value_comp();
    }

    void reserve (size_type element_count)
    {
        q_.reserve(element_count);
    }
};


} /* namespace detail */
} /* namespace heap */
} /* namespace boost */

#endif /* BOOST_HEAP_DETAIL_MUTABLE_HEAP_HPP */