3 // Copyright (C) 2010 Tim Blechmann
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
9 #ifndef BOOST_HEAP_DETAIL_MUTABLE_HEAP_HPP
10 #define BOOST_HEAP_DETAIL_MUTABLE_HEAP_HPP
19 #include <boost/iterator/iterator_adaptor.hpp>
20 #include <boost/heap/detail/ordered_adaptor_iterator.hpp>
26 /* wrapper for a mutable heap container adaptors
28 * this wrapper introduces an additional indirection. the heap is not constructed from objects,
29 * but instead from std::list iterators. this way, the mutability is achieved
32 template <typename PriorityQueueType>
33 class priority_queue_mutable_wrapper
36 typedef typename PriorityQueueType::value_type value_type;
37 typedef typename PriorityQueueType::size_type size_type;
38 typedef typename PriorityQueueType::value_compare value_compare;
39 typedef typename PriorityQueueType::allocator_type allocator_type;
41 typedef typename PriorityQueueType::reference reference;
42 typedef typename PriorityQueueType::const_reference const_reference;
43 typedef typename PriorityQueueType::pointer pointer;
44 typedef typename PriorityQueueType::const_pointer const_pointer;
45 static const bool is_stable = PriorityQueueType::is_stable;
48 typedef std::pair<value_type, size_type> node_type;
50 typedef std::list<node_type, typename allocator_type::template rebind<node_type>::other> object_list;
52 typedef typename object_list::iterator list_iterator;
53 typedef typename object_list::const_iterator const_list_iterator;
55 template <typename Heap1, typename Heap2>
56 friend struct heap_merge_emulate;
58 typedef typename PriorityQueueType::super_t::stability_counter_type stability_counter_type;
60 stability_counter_type get_stability_count(void) const
62 return q_.get_stability_count();
65 void set_stability_count(stability_counter_type new_count)
67 q_.set_stability_count(new_count);
72 template <typename It>
73 static void run(It & it, size_type new_index)
75 q_type::get_value(it)->second = new_index;
82 value_type & operator*() const
84 return iterator->first;
90 handle_type(handle_type const & rhs):
91 iterator(rhs.iterator)
94 bool operator==(handle_type const & rhs) const
96 return iterator == rhs.iterator;
99 bool operator!=(handle_type const & rhs) const
101 return iterator != rhs.iterator;
105 explicit handle_type(list_iterator const & it):
109 list_iterator iterator;
111 friend class priority_queue_mutable_wrapper;
118 indirect_cmp(value_compare const & cmp = value_compare()):
122 bool operator()(const_list_iterator const & lhs, const_list_iterator const & rhs) const
124 return value_compare::operator()(lhs->first, rhs->first);
128 typedef typename PriorityQueueType::template rebind<list_iterator,
130 allocator_type, index_updater >::other q_type;
137 priority_queue_mutable_wrapper(value_compare const & cmp = value_compare()):
141 priority_queue_mutable_wrapper(priority_queue_mutable_wrapper const & rhs):
142 q_(rhs.q_), objects(rhs.objects)
144 for (typename object_list::iterator it = objects.begin(); it != objects.end(); ++it)
148 priority_queue_mutable_wrapper & operator=(priority_queue_mutable_wrapper const & rhs)
151 objects = rhs.objects;
153 for (typename object_list::iterator it = objects.begin(); it != objects.end(); ++it)
158 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
159 priority_queue_mutable_wrapper (priority_queue_mutable_wrapper && rhs):
160 q_(std::move(rhs.q_))
162 /// FIXME: msvc seems to invalidate iterators when moving std::list
163 std::swap(objects, rhs.objects);
166 priority_queue_mutable_wrapper & operator=(priority_queue_mutable_wrapper && rhs)
168 q_ = std::move(rhs.q_);
170 std::swap(objects, rhs.objects);
177 template <typename iterator_type>
179 public boost::iterator_adaptor<iterator_base<iterator_type>,
182 boost::bidirectional_traversal_tag>
184 typedef boost::iterator_adaptor<iterator_base<iterator_type>,
187 boost::bidirectional_traversal_tag> super_t;
189 friend class boost::iterator_core_access;
190 friend class priority_queue_mutable_wrapper;
196 template <typename T>
197 explicit iterator_base(T const & it):
201 value_type const & dereference() const
203 return super_t::base()->first;
206 iterator_type get_list_iterator() const
208 return super_t::base_reference();
212 typedef iterator_base<list_iterator> iterator;
213 typedef iterator_base<const_list_iterator> const_iterator;
215 typedef typename object_list::difference_type difference_type;
217 class ordered_iterator:
218 public boost::iterator_adaptor<ordered_iterator,
221 boost::forward_traversal_tag
223 q_type::ordered_iterator_dispatcher
225 typedef boost::iterator_adaptor<ordered_iterator,
228 boost::forward_traversal_tag
231 typedef const_list_iterator iterator;
232 typedef typename q_type::ordered_iterator_dispatcher ordered_iterator_dispatcher;
234 friend class boost::iterator_core_access;
237 ordered_iterator(void):
238 adaptor_type(0), unvisited_nodes(indirect_cmp()), q_(NULL)
241 ordered_iterator(const priority_queue_mutable_wrapper * q, indirect_cmp const & cmp):
242 adaptor_type(0), unvisited_nodes(cmp), q_(q)
245 ordered_iterator(const_list_iterator it, const priority_queue_mutable_wrapper * q, indirect_cmp const & cmp):
246 adaptor_type(it), unvisited_nodes(cmp), q_(q)
248 if (it != q->objects.end())
252 bool operator!=(ordered_iterator const & rhs) const
254 return adaptor_type::base() != rhs.base();
257 bool operator==(ordered_iterator const & rhs) const
259 return !operator!=(rhs);
265 if (unvisited_nodes.empty())
266 adaptor_type::base_reference() = q_->objects.end();
268 iterator next = unvisited_nodes.top();
269 unvisited_nodes.pop();
270 discover_nodes(next);
271 adaptor_type::base_reference() = next;
275 value_type const & dereference() const
277 return adaptor_type::base()->first;
280 void discover_nodes(iterator current)
282 size_type current_index = current->second;
283 const q_type * q = &(q_->q_);
285 if (ordered_iterator_dispatcher::is_leaf(q, current_index))
288 std::pair<size_type, size_type> child_range = ordered_iterator_dispatcher::get_child_nodes(q, current_index);
290 for (size_type i = child_range.first; i <= child_range.second; ++i) {
291 typename q_type::internal_type const & internal_value_at_index = ordered_iterator_dispatcher::get_internal_value(q, i);
292 typename q_type::value_type const & value_at_index = q_->q_.get_value(internal_value_at_index);
294 unvisited_nodes.push(value_at_index);
298 std::priority_queue<iterator,
299 std::vector<iterator, typename allocator_type::template rebind<iterator>::other >,
302 const priority_queue_mutable_wrapper * q_;
305 bool empty(void) const
310 size_type size(void) const
315 size_type max_size(void) const
317 return objects.max_size();
326 allocator_type get_allocator(void) const
328 return q_.get_allocator();
331 void swap(priority_queue_mutable_wrapper & rhs)
333 objects.swap(rhs.objects);
337 const_reference top(void) const
339 BOOST_ASSERT(!empty());
340 return q_.top()->first;
343 handle_type push(value_type const & v)
345 objects.push_front(std::make_pair(v, 0));
346 list_iterator ret = objects.begin();
348 return handle_type(ret);
351 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
352 template <class... Args>
353 handle_type emplace(Args&&... args)
355 objects.push_front(std::make_pair(std::forward<Args>(args)..., 0));
356 list_iterator ret = objects.begin();
358 return handle_type(ret);
364 BOOST_ASSERT(!empty());
365 list_iterator q_top = q_.top();
367 objects.erase(q_top);
371 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
373 * \b Complexity: Logarithmic.
376 void update(handle_type handle, const_reference v)
378 list_iterator it = handle.iterator;
379 value_type const & current_value = it->first;
380 value_compare const & cmp = q_.value_comp();
381 if (cmp(v, current_value))
388 * \b Effects: Updates the heap after the element handled by \c handle has been changed.
390 * \b Complexity: Logarithmic.
392 * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
394 void update(handle_type handle)
396 list_iterator it = handle.iterator;
397 size_type index = it->second;
402 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
404 * \b Complexity: Logarithmic.
406 * \b Note: The new value is expected to be greater than the current one
408 void increase(handle_type handle, const_reference v)
410 BOOST_ASSERT(!value_compare()(v, handle.iterator->first));
411 handle.iterator->first = v;
416 * \b Effects: Updates the heap after the element handled by \c handle has been changed.
418 * \b Complexity: Logarithmic.
420 * \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!
422 void increase(handle_type handle)
424 list_iterator it = handle.iterator;
425 size_type index = it->second;
430 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
432 * \b Complexity: Logarithmic.
434 * \b Note: The new value is expected to be less than the current one
436 void decrease(handle_type handle, const_reference v)
438 BOOST_ASSERT(!value_compare()(handle.iterator->first, v));
439 handle.iterator->first = v;
444 * \b Effects: Updates the heap after the element handled by \c handle has been changed.
446 * \b Complexity: Logarithmic.
448 * \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!
450 void decrease(handle_type handle)
452 list_iterator it = handle.iterator;
453 size_type index = it->second;
458 * \b Effects: Removes the element handled by \c handle from the priority_queue.
460 * \b Complexity: Logarithmic.
462 void erase(handle_type handle)
464 list_iterator it = handle.iterator;
465 size_type index = it->second;
470 const_iterator begin(void) const
472 return const_iterator(objects.begin());
475 const_iterator end(void) const
477 return const_iterator(objects.end());
482 return iterator(objects.begin());
487 return iterator(objects.end());
490 ordered_iterator ordered_begin(void) const
493 return ordered_iterator(q_.top(), this, indirect_cmp(q_.value_comp()));
495 return ordered_end();
498 ordered_iterator ordered_end(void) const
500 return ordered_iterator(objects.end(), this, indirect_cmp(q_.value_comp()));
503 static handle_type s_handle_from_iterator(iterator const & it)
505 return handle_type(it.get_list_iterator());
508 value_compare const & value_comp(void) const
510 return q_.value_comp();
513 void reserve (size_type element_count)
515 q_.reserve(element_count);
520 } /* namespace detail */
521 } /* namespace heap */
522 } /* namespace boost */
524 #endif /* BOOST_HEAP_DETAIL_MUTABLE_HEAP_HPP */