boost/boost/heap/detail/mutable_heap.hpp - nest-cam/4320010/boost - Git at Google

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