Chris@16: // boost heap
Chris@16: //
Chris@16: // Copyright (C) 2010 Tim Blechmann
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_HEAP_DETAIL_MUTABLE_HEAP_HPP
Chris@16: #define BOOST_HEAP_DETAIL_MUTABLE_HEAP_HPP
Chris@16: 
Chris@16: /*! \file
Chris@16:  * INTERNAL ONLY
Chris@16:  */
Chris@16: 
Chris@16: #include <list>
Chris@16: #include <utility>
Chris@16: 
Chris@16: #include <boost/iterator/iterator_adaptor.hpp>
Chris@16: #include <boost/heap/detail/ordered_adaptor_iterator.hpp>
Chris@16: 
Chris@16: namespace boost  {
Chris@16: namespace heap   {
Chris@16: namespace detail {
Chris@16: 
Chris@16: /* wrapper for a mutable heap container adaptors
Chris@16:  *
Chris@16:  * this wrapper introduces an additional indirection. the heap is not constructed from objects,
Chris@16:  * but instead from std::list iterators. this way, the mutability is achieved
Chris@16:  *
Chris@16:  */
Chris@16: template <typename PriorityQueueType>
Chris@16: class priority_queue_mutable_wrapper
Chris@16: {
Chris@16: public:
Chris@16:     typedef typename PriorityQueueType::value_type value_type;
Chris@16:     typedef typename PriorityQueueType::size_type size_type;
Chris@16:     typedef typename PriorityQueueType::value_compare value_compare;
Chris@16:     typedef typename PriorityQueueType::allocator_type allocator_type;
Chris@16: 
Chris@16:     typedef typename PriorityQueueType::reference reference;
Chris@16:     typedef typename PriorityQueueType::const_reference const_reference;
Chris@16:     typedef typename PriorityQueueType::pointer pointer;
Chris@16:     typedef typename PriorityQueueType::const_pointer const_pointer;
Chris@16:     static const bool is_stable = PriorityQueueType::is_stable;
Chris@16: 
Chris@16: private:
Chris@16:     typedef std::pair<value_type, size_type> node_type;
Chris@16: 
Chris@16:     typedef std::list<node_type, typename allocator_type::template rebind<node_type>::other> object_list;
Chris@16: 
Chris@16:     typedef typename object_list::iterator list_iterator;
Chris@16:     typedef typename object_list::const_iterator const_list_iterator;
Chris@16: 
Chris@16:     template <typename Heap1, typename Heap2>
Chris@16:     friend struct heap_merge_emulate;
Chris@16: 
Chris@16:     typedef typename PriorityQueueType::super_t::stability_counter_type stability_counter_type;
Chris@16: 
Chris@16:     stability_counter_type get_stability_count(void) const
Chris@16:     {
Chris@16:         return q_.get_stability_count();
Chris@16:     }
Chris@16: 
Chris@16:     void set_stability_count(stability_counter_type new_count)
Chris@16:     {
Chris@16:         q_.set_stability_count(new_count);
Chris@16:     }
Chris@16: 
Chris@16:     struct index_updater
Chris@16:     {
Chris@16:         template <typename It>
Chris@16:         static void run(It & it, size_type new_index)
Chris@16:         {
Chris@16:             q_type::get_value(it)->second = new_index;
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16: public:
Chris@16:     struct handle_type
Chris@16:     {
Chris@16:         value_type & operator*() const
Chris@16:         {
Chris@16:             return iterator->first;
Chris@16:         }
Chris@16: 
Chris@16:         handle_type (void)
Chris@16:         {}
Chris@16: 
Chris@16:         handle_type(handle_type const & rhs):
Chris@16:             iterator(rhs.iterator)
Chris@16:         {}
Chris@16: 
Chris@16:         bool operator==(handle_type const & rhs) const
Chris@16:         {
Chris@16:             return iterator == rhs.iterator;
Chris@16:         }
Chris@16: 
Chris@16:         bool operator!=(handle_type const & rhs) const
Chris@16:         {
Chris@16:             return iterator != rhs.iterator;
Chris@16:         }
Chris@16: 
Chris@16:     private:
Chris@16:         explicit handle_type(list_iterator const & it):
Chris@16:             iterator(it)
Chris@16:         {}
Chris@16: 
Chris@16:         list_iterator iterator;
Chris@16: 
Chris@16:         friend class priority_queue_mutable_wrapper;
Chris@16:     };
Chris@16: 
Chris@16: private:
Chris@16:     struct indirect_cmp:
Chris@16:         public value_compare
Chris@16:     {
Chris@16:         indirect_cmp(value_compare const & cmp = value_compare()):
Chris@16:             value_compare(cmp)
Chris@16:         {}
Chris@16: 
Chris@16:         bool operator()(const_list_iterator const & lhs, const_list_iterator const & rhs) const
Chris@16:         {
Chris@16:             return value_compare::operator()(lhs->first, rhs->first);
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     typedef typename PriorityQueueType::template rebind<list_iterator,
Chris@16:                                                         indirect_cmp,
Chris@16:                                                         allocator_type, index_updater >::other q_type;
Chris@16: 
Chris@16: protected:
Chris@16:     q_type q_;
Chris@16:     object_list objects;
Chris@16: 
Chris@16: protected:
Chris@16:     priority_queue_mutable_wrapper(value_compare const & cmp = value_compare()):
Chris@16:         q_(cmp)
Chris@16:     {}
Chris@16: 
Chris@16:     priority_queue_mutable_wrapper(priority_queue_mutable_wrapper const & rhs):
Chris@16:         q_(rhs.q_), objects(rhs.objects)
Chris@16:     {
Chris@16:         for (typename object_list::iterator it = objects.begin(); it != objects.end(); ++it)
Chris@16:             q_.push(it);
Chris@16:     }
Chris@16: 
Chris@16:     priority_queue_mutable_wrapper & operator=(priority_queue_mutable_wrapper const & rhs)
Chris@16:     {
Chris@16:         q_ = rhs.q_;
Chris@16:         objects = rhs.objects;
Chris@16:         q_.clear();
Chris@16:         for (typename object_list::iterator it = objects.begin(); it != objects.end(); ++it)
Chris@16:             q_.push(it);
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16: #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@16:     priority_queue_mutable_wrapper (priority_queue_mutable_wrapper && rhs):
Chris@16:         q_(std::move(rhs.q_))
Chris@16:     {
Chris@16:         /// FIXME: msvc seems to invalidate iterators when moving std::list
Chris@16:         std::swap(objects, rhs.objects);
Chris@16:     }
Chris@16: 
Chris@16:     priority_queue_mutable_wrapper & operator=(priority_queue_mutable_wrapper && rhs)
Chris@16:     {
Chris@16:         q_ = std::move(rhs.q_);
Chris@16:         objects.clear();
Chris@16:         std::swap(objects, rhs.objects);
Chris@16:         return *this;
Chris@16:     }
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@16: public:
Chris@16:     template <typename iterator_type>
Chris@16:     class iterator_base:
Chris@16:         public boost::iterator_adaptor<iterator_base<iterator_type>,
Chris@16:                                        iterator_type,
Chris@16:                                        value_type const,
Chris@16:                                        boost::bidirectional_traversal_tag>
Chris@16:     {
Chris@16:         typedef boost::iterator_adaptor<iterator_base<iterator_type>,
Chris@16:                                        iterator_type,
Chris@16:                                        value_type const,
Chris@16:                                        boost::bidirectional_traversal_tag> super_t;
Chris@16: 
Chris@16:         friend class boost::iterator_core_access;
Chris@16:         friend class priority_queue_mutable_wrapper;
Chris@16: 
Chris@16:         iterator_base(void):
Chris@16:             super_t(0)
Chris@16:         {}
Chris@16: 
Chris@16:         template <typename T>
Chris@16:         explicit iterator_base(T const & it):
Chris@16:             super_t(it)
Chris@16:         {}
Chris@16: 
Chris@16:         value_type const & dereference() const
Chris@16:         {
Chris@16:             return super_t::base()->first;
Chris@16:         }
Chris@16: 
Chris@16:         iterator_type get_list_iterator() const
Chris@16:         {
Chris@16:             return super_t::base_reference();
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     typedef iterator_base<list_iterator> iterator;
Chris@16:     typedef iterator_base<const_list_iterator> const_iterator;
Chris@16: 
Chris@16:     typedef typename object_list::difference_type difference_type;
Chris@16: 
Chris@16:     class ordered_iterator:
Chris@16:         public boost::iterator_adaptor<ordered_iterator,
Chris@16:                                        const_list_iterator,
Chris@16:                                        value_type const,
Chris@16:                                        boost::forward_traversal_tag
Chris@16:                                       >,
Chris@16:         q_type::ordered_iterator_dispatcher
Chris@16:     {
Chris@16:         typedef boost::iterator_adaptor<ordered_iterator,
Chris@16:                                         const_list_iterator,
Chris@16:                                         value_type const,
Chris@16:                                         boost::forward_traversal_tag
Chris@16:                                       > adaptor_type;
Chris@16: 
Chris@16:         typedef const_list_iterator iterator;
Chris@16:         typedef typename q_type::ordered_iterator_dispatcher ordered_iterator_dispatcher;
Chris@16: 
Chris@16:         friend class boost::iterator_core_access;
Chris@16: 
Chris@16:     public:
Chris@16:         ordered_iterator(void):
Chris@16:             adaptor_type(0), unvisited_nodes(indirect_cmp()), q_(NULL)
Chris@16:         {}
Chris@16: 
Chris@16:         ordered_iterator(const priority_queue_mutable_wrapper * q, indirect_cmp const & cmp):
Chris@16:             adaptor_type(0), unvisited_nodes(cmp), q_(q)
Chris@16:         {}
Chris@16: 
Chris@16:         ordered_iterator(const_list_iterator it, const priority_queue_mutable_wrapper * q, indirect_cmp const & cmp):
Chris@16:             adaptor_type(it), unvisited_nodes(cmp), q_(q)
Chris@16:         {
Chris@16:             if (it != q->objects.end())
Chris@16:                 discover_nodes(it);
Chris@16:         }
Chris@16: 
Chris@16:         bool operator!=(ordered_iterator const & rhs) const
Chris@16:         {
Chris@16:             return adaptor_type::base() != rhs.base();
Chris@16:         }
Chris@16: 
Chris@16:         bool operator==(ordered_iterator const & rhs) const
Chris@16:         {
Chris@16:             return !operator!=(rhs);
Chris@16:         }
Chris@16: 
Chris@16:     private:
Chris@16:         void increment(void)
Chris@16:         {
Chris@16:             if (unvisited_nodes.empty())
Chris@16:                 adaptor_type::base_reference() = q_->objects.end();
Chris@16:             else {
Chris@16:                 iterator next = unvisited_nodes.top();
Chris@16:                 unvisited_nodes.pop();
Chris@16:                 discover_nodes(next);
Chris@16:                 adaptor_type::base_reference() = next;
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         value_type const & dereference() const
Chris@16:         {
Chris@16:             return adaptor_type::base()->first;
Chris@16:         }
Chris@16: 
Chris@16:         void discover_nodes(iterator current)
Chris@16:         {
Chris@16:             size_type current_index = current->second;
Chris@16:             const q_type * q = &(q_->q_);
Chris@16: 
Chris@16:             if (ordered_iterator_dispatcher::is_leaf(q, current_index))
Chris@16:                 return;
Chris@16: 
Chris@16:             std::pair<size_type, size_type> child_range = ordered_iterator_dispatcher::get_child_nodes(q, current_index);
Chris@16: 
Chris@16:             for (size_type i = child_range.first; i <= child_range.second; ++i) {
Chris@16:                 typename q_type::internal_type const & internal_value_at_index = ordered_iterator_dispatcher::get_internal_value(q, i);
Chris@16:                 typename q_type::value_type const & value_at_index = q_->q_.get_value(internal_value_at_index);
Chris@16: 
Chris@16:                 unvisited_nodes.push(value_at_index);
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         std::priority_queue<iterator,
Chris@16:                             std::vector<iterator, typename allocator_type::template rebind<iterator>::other >,
Chris@16:                             indirect_cmp
Chris@16:                            > unvisited_nodes;
Chris@16:         const priority_queue_mutable_wrapper * q_;
Chris@16:     };
Chris@16: 
Chris@16:     bool empty(void) const
Chris@16:     {
Chris@16:         return q_.empty();
Chris@16:     }
Chris@16: 
Chris@16:     size_type size(void) const
Chris@16:     {
Chris@16:         return q_.size();
Chris@16:     }
Chris@16: 
Chris@16:     size_type max_size(void) const
Chris@16:     {
Chris@16:         return objects.max_size();
Chris@16:     }
Chris@16: 
Chris@16:     void clear(void)
Chris@16:     {
Chris@16:         q_.clear();
Chris@16:         objects.clear();
Chris@16:     }
Chris@16: 
Chris@16:     allocator_type get_allocator(void) const
Chris@16:     {
Chris@16:         return q_.get_allocator();
Chris@16:     }
Chris@16: 
Chris@16:     void swap(priority_queue_mutable_wrapper & rhs)
Chris@16:     {
Chris@16:         objects.swap(rhs.objects);
Chris@16:         q_.swap(rhs.q_);
Chris@16:     }
Chris@16: 
Chris@16:     const_reference top(void) const
Chris@16:     {
Chris@16:         BOOST_ASSERT(!empty());
Chris@16:         return q_.top()->first;
Chris@16:     }
Chris@16: 
Chris@16:     handle_type push(value_type const & v)
Chris@16:     {
Chris@16:         objects.push_front(std::make_pair(v, 0));
Chris@16:         list_iterator ret = objects.begin();
Chris@16:         q_.push(ret);
Chris@16:         return handle_type(ret);
Chris@16:     }
Chris@16: 
Chris@16: #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@16:     template <class... Args>
Chris@16:     handle_type emplace(Args&&... args)
Chris@16:     {
Chris@16:         objects.push_front(std::make_pair(std::forward<Args>(args)..., 0));
Chris@16:         list_iterator ret = objects.begin();
Chris@16:         q_.push(ret);
Chris@16:         return handle_type(ret);
Chris@16:     }
Chris@16: #endif
Chris@16: 
Chris@16:     void pop(void)
Chris@16:     {
Chris@16:         BOOST_ASSERT(!empty());
Chris@16:         list_iterator q_top = q_.top();
Chris@16:         q_.pop();
Chris@16:         objects.erase(q_top);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * */
Chris@16:     void update(handle_type handle, const_reference v)
Chris@16:     {
Chris@16:         list_iterator it = handle.iterator;
Chris@16:         value_type const & current_value = it->first;
Chris@16:         value_compare const & cmp = q_.value_comp();
Chris@16:         if (cmp(v, current_value))
Chris@16:             decrease(handle, v);
Chris@16:         else
Chris@16:             increase(handle, v);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
Chris@16:      * */
Chris@16:     void update(handle_type handle)
Chris@16:     {
Chris@16:         list_iterator it = handle.iterator;
Chris@16:         size_type index = it->second;
Chris@16:         q_.update(index);
Chris@16:     }
Chris@16: 
Chris@16:      /**
Chris@16:      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * \b Note: The new value is expected to be greater than the current one
Chris@16:      * */
Chris@16:     void increase(handle_type handle, const_reference v)
Chris@16:     {
Chris@16:         BOOST_ASSERT(!value_compare()(v, handle.iterator->first));
Chris@16:         handle.iterator->first = v;
Chris@16:         increase(handle);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * \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!
Chris@16:      * */
Chris@16:     void increase(handle_type handle)
Chris@16:     {
Chris@16:         list_iterator it = handle.iterator;
Chris@16:         size_type index = it->second;
Chris@16:         q_.increase(index);
Chris@16:     }
Chris@16: 
Chris@16:      /**
Chris@16:      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * \b Note: The new value is expected to be less than the current one
Chris@16:      * */
Chris@16:     void decrease(handle_type handle, const_reference v)
Chris@16:     {
Chris@16:         BOOST_ASSERT(!value_compare()(handle.iterator->first, v));
Chris@16:         handle.iterator->first = v;
Chris@16:         decrease(handle);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * \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!
Chris@16:      * */
Chris@16:     void decrease(handle_type handle)
Chris@16:     {
Chris@16:         list_iterator it = handle.iterator;
Chris@16:         size_type index = it->second;
Chris@16:         q_.decrease(index);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Removes the element handled by \c handle from the priority_queue.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      * */
Chris@16:     void erase(handle_type handle)
Chris@16:     {
Chris@16:         list_iterator it = handle.iterator;
Chris@16:         size_type index = it->second;
Chris@16:         q_.erase(index);
Chris@16:         objects.erase(it);
Chris@16:     }
Chris@16: 
Chris@16:     const_iterator begin(void) const
Chris@16:     {
Chris@16:         return const_iterator(objects.begin());
Chris@16:     }
Chris@16: 
Chris@16:     const_iterator end(void) const
Chris@16:     {
Chris@16:         return const_iterator(objects.end());
Chris@16:     }
Chris@16: 
Chris@16:     iterator begin(void)
Chris@16:     {
Chris@16:         return iterator(objects.begin());
Chris@16:     }
Chris@16: 
Chris@16:     iterator end(void)
Chris@16:     {
Chris@16:         return iterator(objects.end());
Chris@16:     }
Chris@16: 
Chris@16:     ordered_iterator ordered_begin(void) const
Chris@16:     {
Chris@16:         if (!empty())
Chris@16:             return ordered_iterator(q_.top(), this, indirect_cmp(q_.value_comp()));
Chris@16:         else
Chris@16:             return ordered_end();
Chris@16:     }
Chris@16: 
Chris@16:     ordered_iterator ordered_end(void) const
Chris@16:     {
Chris@16:         return ordered_iterator(objects.end(), this, indirect_cmp(q_.value_comp()));
Chris@16:     }
Chris@16: 
Chris@16:     static handle_type s_handle_from_iterator(iterator const & it)
Chris@16:     {
Chris@16:         return handle_type(it.get_list_iterator());
Chris@16:     }
Chris@16: 
Chris@16:     value_compare const & value_comp(void) const
Chris@16:     {
Chris@16:         return q_.value_comp();
Chris@16:     }
Chris@16: 
Chris@16:     void reserve (size_type element_count)
Chris@16:     {
Chris@16:         q_.reserve(element_count);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: } /* namespace detail */
Chris@16: } /* namespace heap */
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif /* BOOST_HEAP_DETAIL_MUTABLE_HEAP_HPP */