• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // boost heap: helper classes for stable priority queues
2 //
3 // Copyright (C) 2010 Tim Blechmann
4 //
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)
8 
9 #ifndef BOOST_HEAP_DETAIL_STABLE_HEAP_HPP
10 #define BOOST_HEAP_DETAIL_STABLE_HEAP_HPP
11 
12 #include <limits>
13 #include <stdexcept>
14 #include <utility>
15 
16 #include <boost/cstdint.hpp>
17 #include <boost/throw_exception.hpp>
18 #include <boost/core/allocator_access.hpp>
19 #include <boost/iterator/iterator_adaptor.hpp>
20 
21 #include <boost/heap/policies.hpp>
22 #include <boost/heap/heap_merge.hpp>
23 
24 #include <boost/type_traits/is_nothrow_move_constructible.hpp>
25 #include <boost/type_traits/is_nothrow_move_assignable.hpp>
26 
27 namespace boost  {
28 namespace heap   {
29 namespace detail {
30 
31 template<bool ConstantSize, class SizeType>
32 struct size_holder
33 {
34     static const bool constant_time_size = ConstantSize;
35     typedef SizeType  size_type;
36 
size_holderboost::heap::detail::size_holder37     size_holder(void) BOOST_NOEXCEPT:
38         size_(0)
39     {}
40 
41 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
size_holderboost::heap::detail::size_holder42     size_holder(size_holder && rhs) BOOST_NOEXCEPT:
43         size_(rhs.size_)
44     {
45         rhs.size_ = 0;
46     }
47 
size_holderboost::heap::detail::size_holder48     size_holder(size_holder const & rhs) BOOST_NOEXCEPT:
49         size_(rhs.size_)
50     {}
51 
operator =boost::heap::detail::size_holder52     size_holder & operator=(size_holder && rhs) BOOST_NOEXCEPT
53     {
54         size_ = rhs.size_;
55         rhs.size_ = 0;
56         return *this;
57     }
58 
operator =boost::heap::detail::size_holder59     size_holder & operator=(size_holder const & rhs) BOOST_NOEXCEPT
60     {
61         size_ = rhs.size_;
62         return *this;
63     }
64 #endif
65 
get_sizeboost::heap::detail::size_holder66     SizeType get_size() const BOOST_NOEXCEPT
67     {  return size_;  }
68 
set_sizeboost::heap::detail::size_holder69     void set_size(SizeType size) BOOST_NOEXCEPT
70     {  size_ = size; }
71 
decrementboost::heap::detail::size_holder72     void decrement() BOOST_NOEXCEPT
73     {  --size_; }
74 
incrementboost::heap::detail::size_holder75     void increment() BOOST_NOEXCEPT
76     {  ++size_; }
77 
addboost::heap::detail::size_holder78     void add(SizeType value) BOOST_NOEXCEPT
79     {  size_ += value; }
80 
subboost::heap::detail::size_holder81     void sub(SizeType value) BOOST_NOEXCEPT
82     {  size_ -= value; }
83 
swapboost::heap::detail::size_holder84     void swap(size_holder & rhs) BOOST_NOEXCEPT
85     {  std::swap(size_, rhs.size_); }
86 
87     SizeType size_;
88 };
89 
90 template<class SizeType>
91 struct size_holder<false, SizeType>
92 {
93     static const bool constant_time_size = false;
94     typedef SizeType  size_type;
95 
size_holderboost::heap::detail::size_holder96     size_holder(void) BOOST_NOEXCEPT
97     {}
98 
99 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
size_holderboost::heap::detail::size_holder100     size_holder(size_holder && rhs) BOOST_NOEXCEPT
101     {}
102 
size_holderboost::heap::detail::size_holder103     size_holder(size_holder const & rhs) BOOST_NOEXCEPT
104     {}
105 
operator =boost::heap::detail::size_holder106     size_holder & operator=(size_holder && rhs) BOOST_NOEXCEPT
107     {
108         return *this;
109     }
110 
operator =boost::heap::detail::size_holder111     size_holder & operator=(size_holder const & rhs) BOOST_NOEXCEPT
112     {
113         return *this;
114     }
115 #endif
116 
get_sizeboost::heap::detail::size_holder117     size_type get_size() const BOOST_NOEXCEPT
118     {  return 0;  }
119 
set_sizeboost::heap::detail::size_holder120     void set_size(size_type) BOOST_NOEXCEPT
121     {}
122 
decrementboost::heap::detail::size_holder123     void decrement() BOOST_NOEXCEPT
124     {}
125 
incrementboost::heap::detail::size_holder126     void increment() BOOST_NOEXCEPT
127     {}
128 
addboost::heap::detail::size_holder129     void add(SizeType /*value*/) BOOST_NOEXCEPT
130     {}
131 
subboost::heap::detail::size_holder132     void sub(SizeType /*value*/) BOOST_NOEXCEPT
133     {}
134 
swapboost::heap::detail::size_holder135     void swap(size_holder & /*rhs*/) BOOST_NOEXCEPT
136     {}
137 };
138 
139 // note: MSVC does not implement lookup correctly, we therefore have to place the Cmp object as member inside the
140 //       struct. of course, this prevents EBO and significantly reduces the readability of this code
141 template <typename T,
142           typename Cmp,
143           bool constant_time_size,
144           typename StabilityCounterType = boost::uintmax_t,
145           bool stable = false
146          >
147 struct heap_base:
148 #ifndef BOOST_MSVC
149     Cmp,
150 #endif
151     size_holder<constant_time_size, size_t>
152 {
153     typedef StabilityCounterType stability_counter_type;
154     typedef T value_type;
155     typedef T internal_type;
156     typedef size_holder<constant_time_size, size_t> size_holder_type;
157     typedef Cmp value_compare;
158     typedef Cmp internal_compare;
159     static const bool is_stable = stable;
160 
161 #ifdef BOOST_MSVC
162     Cmp cmp_;
163 #endif
164 
heap_baseboost::heap::detail::heap_base165     heap_base (Cmp const & cmp = Cmp()):
166 #ifndef BOOST_MSVC
167         Cmp(cmp)
168 #else
169         cmp_(cmp)
170 #endif
171     {}
172 
173 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
BOOST_NOEXCEPT_IFboost::heap::detail::heap_base174     heap_base(heap_base && rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_constructible<Cmp>::value):
175 #ifndef BOOST_MSVC
176         Cmp(std::move(static_cast<Cmp&>(rhs))),
177 #endif
178         size_holder_type(std::move(static_cast<size_holder_type&>(rhs)))
179 #ifdef BOOST_MSVC
180         , cmp_(std::move(rhs.cmp_))
181 #endif
182     {}
183 
heap_baseboost::heap::detail::heap_base184     heap_base(heap_base const & rhs):
185 #ifndef BOOST_MSVC
186         Cmp(static_cast<Cmp const &>(rhs)),
187 #endif
188         size_holder_type(static_cast<size_holder_type const &>(rhs))
189 #ifdef BOOST_MSVC
190         , cmp_(rhs.value_comp())
191 #endif
192     {}
193 
operator =boost::heap::detail::heap_base194     heap_base & operator=(heap_base && rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_assignable<Cmp>::value)
195     {
196         value_comp_ref().operator=(std::move(rhs.value_comp_ref()));
197         size_holder_type::operator=(std::move(static_cast<size_holder_type&>(rhs)));
198         return *this;
199     }
200 
operator =boost::heap::detail::heap_base201     heap_base & operator=(heap_base const & rhs)
202     {
203         value_comp_ref().operator=(rhs.value_comp());
204         size_holder_type::operator=(static_cast<size_holder_type const &>(rhs));
205         return *this;
206     }
207 #endif
208 
operator ()boost::heap::detail::heap_base209     bool operator()(internal_type const & lhs, internal_type const & rhs) const
210     {
211         return value_comp().operator()(lhs, rhs);
212     }
213 
make_nodeboost::heap::detail::heap_base214     internal_type make_node(T const & val)
215     {
216         return val;
217     }
218 
219 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
make_nodeboost::heap::detail::heap_base220     T && make_node(T && val)
221     {
222         return std::forward<T>(val);
223     }
224 #endif
225 
226 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
227     template <class... Args>
make_nodeboost::heap::detail::heap_base228     internal_type make_node(Args && ... val)
229     {
230         return internal_type(std::forward<Args>(val)...);
231     }
232 #endif
233 
get_valueboost::heap::detail::heap_base234     static T & get_value(internal_type & val) BOOST_NOEXCEPT
235     {
236         return val;
237     }
238 
get_valueboost::heap::detail::heap_base239     static T const & get_value(internal_type const & val) BOOST_NOEXCEPT
240     {
241         return val;
242     }
243 
value_compboost::heap::detail::heap_base244     Cmp const & value_comp(void) const BOOST_NOEXCEPT
245     {
246 #ifndef BOOST_MSVC
247         return *this;
248 #else
249         return cmp_;
250 #endif
251     }
252 
get_internal_cmpboost::heap::detail::heap_base253     Cmp const & get_internal_cmp(void) const BOOST_NOEXCEPT
254     {
255         return value_comp();
256     }
257 
swapboost::heap::detail::heap_base258     void swap(heap_base & rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_constructible<Cmp>::value && boost::is_nothrow_move_assignable<Cmp>::value)
259     {
260         std::swap(value_comp_ref(), rhs.value_comp_ref());
261         size_holder<constant_time_size, size_t>::swap(rhs);
262     }
263 
get_stability_countboost::heap::detail::heap_base264     stability_counter_type get_stability_count(void) const BOOST_NOEXCEPT
265     {
266         return 0;
267     }
268 
set_stability_countboost::heap::detail::heap_base269     void set_stability_count(stability_counter_type) BOOST_NOEXCEPT
270     {}
271 
272     template <typename Heap1, typename Heap2>
273     friend struct heap_merge_emulate;
274 
275 private:
value_comp_refboost::heap::detail::heap_base276     Cmp & value_comp_ref(void)
277     {
278 #ifndef BOOST_MSVC
279         return *this;
280 #else
281         return cmp_;
282 #endif
283     }
284 };
285 
286 
287 template <typename T,
288           typename Cmp,
289           bool constant_time_size,
290           typename StabilityCounterType
291          >
292 struct heap_base<T, Cmp, constant_time_size, StabilityCounterType, true>:
293 #ifndef BOOST_MSVC
294     Cmp,
295 #endif
296     size_holder<constant_time_size, size_t>
297 {
298     typedef StabilityCounterType stability_counter_type;
299     typedef T value_type;
300 
301     struct internal_type
302     {
303 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
304         template <class ...Args>
internal_typeboost::heap::detail::heap_base::internal_type305         internal_type(stability_counter_type cnt, Args && ... args):
306             first(std::forward<Args>(args)...), second(cnt)
307         {}
308 #endif
309 
internal_typeboost::heap::detail::heap_base::internal_type310         internal_type(stability_counter_type const & cnt, T const & value):
311             first(value), second(cnt)
312         {}
313 
314         T first;
315         stability_counter_type second;
316     };
317 
318     typedef size_holder<constant_time_size, size_t> size_holder_type;
319     typedef Cmp value_compare;
320 
321 #ifdef BOOST_MSVC
322     Cmp cmp_;
323 #endif
324 
heap_baseboost::heap::detail::heap_base325     heap_base (Cmp const & cmp = Cmp()):
326 #ifndef BOOST_MSVC
327         Cmp(cmp),
328 #else
329         cmp_(cmp),
330 #endif
331         counter_(0)
332     {}
333 
334 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
BOOST_NOEXCEPT_IFboost::heap::detail::heap_base335     heap_base(heap_base && rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_constructible<Cmp>::value):
336 #ifndef BOOST_MSVC
337         Cmp(std::move(static_cast<Cmp&>(rhs))),
338 #else
339         cmp_(std::move(rhs.cmp_)),
340 #endif
341         size_holder_type(std::move(static_cast<size_holder_type&>(rhs))), counter_(rhs.counter_)
342     {
343         rhs.counter_ = 0;
344     }
345 
heap_baseboost::heap::detail::heap_base346     heap_base(heap_base const & rhs):
347 #ifndef BOOST_MSVC
348         Cmp(static_cast<Cmp const&>(rhs)),
349 #else
350         cmp_(rhs.value_comp()),
351 #endif
352         size_holder_type(static_cast<size_holder_type const &>(rhs)), counter_(rhs.counter_)
353     {}
354 
operator =boost::heap::detail::heap_base355     heap_base & operator=(heap_base && rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_assignable<Cmp>::value)
356     {
357         value_comp_ref().operator=(std::move(rhs.value_comp_ref()));
358         size_holder_type::operator=(std::move(static_cast<size_holder_type&>(rhs)));
359 
360         counter_ = rhs.counter_;
361         rhs.counter_ = 0;
362         return *this;
363     }
364 
operator =boost::heap::detail::heap_base365     heap_base & operator=(heap_base const & rhs)
366     {
367         value_comp_ref().operator=(rhs.value_comp());
368         size_holder_type::operator=(static_cast<size_holder_type const &>(rhs));
369 
370         counter_ = rhs.counter_;
371         return *this;
372     }
373 #endif
374 
operator ()boost::heap::detail::heap_base375     bool operator()(internal_type const & lhs, internal_type const & rhs) const
376     {
377         return get_internal_cmp()(lhs, rhs);
378     }
379 
operator ()boost::heap::detail::heap_base380     bool operator()(T const & lhs, T const & rhs) const
381     {
382         return value_comp()(lhs, rhs);
383     }
384 
make_nodeboost::heap::detail::heap_base385     internal_type make_node(T const & val)
386     {
387         stability_counter_type count = ++counter_;
388         if (counter_ == (std::numeric_limits<stability_counter_type>::max)())
389             BOOST_THROW_EXCEPTION(std::runtime_error("boost::heap counter overflow"));
390         return internal_type(count, val);
391     }
392 
393 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
394     template <class... Args>
make_nodeboost::heap::detail::heap_base395     internal_type make_node(Args&&... args)
396     {
397         stability_counter_type count = ++counter_;
398         if (counter_ == (std::numeric_limits<stability_counter_type>::max)())
399             BOOST_THROW_EXCEPTION(std::runtime_error("boost::heap counter overflow"));
400         return internal_type (count, std::forward<Args>(args)...);
401     }
402 #endif
403 
get_valueboost::heap::detail::heap_base404     static T & get_value(internal_type & val) BOOST_NOEXCEPT
405     {
406         return val.first;
407     }
408 
get_valueboost::heap::detail::heap_base409     static T const & get_value(internal_type const & val) BOOST_NOEXCEPT
410     {
411         return val.first;
412     }
413 
value_compboost::heap::detail::heap_base414     Cmp const & value_comp(void) const BOOST_NOEXCEPT
415     {
416 #ifndef BOOST_MSVC
417         return *this;
418 #else
419         return cmp_;
420 #endif
421     }
422 
423     struct internal_compare:
424         Cmp
425     {
internal_compareboost::heap::detail::heap_base::internal_compare426         internal_compare(Cmp const & cmp = Cmp()):
427             Cmp(cmp)
428         {}
429 
operator ()boost::heap::detail::heap_base::internal_compare430         bool operator()(internal_type const & lhs, internal_type const & rhs) const
431         {
432             if (Cmp::operator()(lhs.first, rhs.first))
433                 return true;
434 
435             if (Cmp::operator()(rhs.first, lhs.first))
436                 return false;
437 
438             return lhs.second > rhs.second;
439         }
440     };
441 
get_internal_cmpboost::heap::detail::heap_base442     internal_compare get_internal_cmp(void) const
443     {
444         return internal_compare(value_comp());
445     }
446 
swapboost::heap::detail::heap_base447     void swap(heap_base & rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_constructible<Cmp>::value && boost::is_nothrow_move_assignable<Cmp>::value)
448     {
449 #ifndef BOOST_MSVC
450         std::swap(static_cast<Cmp&>(*this), static_cast<Cmp&>(rhs));
451 #else
452         std::swap(cmp_, rhs.cmp_);
453 #endif
454         std::swap(counter_, rhs.counter_);
455         size_holder<constant_time_size, size_t>::swap(rhs);
456     }
457 
get_stability_countboost::heap::detail::heap_base458     stability_counter_type get_stability_count(void) const
459     {
460         return counter_;
461     }
462 
set_stability_countboost::heap::detail::heap_base463     void set_stability_count(stability_counter_type new_count)
464     {
465         counter_ = new_count;
466     }
467 
468     template <typename Heap1, typename Heap2>
469     friend struct heap_merge_emulate;
470 
471 private:
value_comp_refboost::heap::detail::heap_base472     Cmp & value_comp_ref(void) BOOST_NOEXCEPT
473     {
474 #ifndef BOOST_MSVC
475         return *this;
476 #else
477         return cmp_;
478 #endif
479     }
480 
481     stability_counter_type counter_;
482 };
483 
484 template <typename node_pointer,
485           typename extractor,
486           typename reference
487          >
488 struct node_handle
489 {
node_handleboost::heap::detail::node_handle490     explicit node_handle(node_pointer n = 0):
491         node_(n)
492     {}
493 
operator *boost::heap::detail::node_handle494     reference operator*() const
495     {
496         return extractor::get_value(node_->value);
497     }
498 
operator ==boost::heap::detail::node_handle499     bool operator==(node_handle const & rhs) const
500     {
501         return node_ == rhs.node_;
502     }
503 
operator !=boost::heap::detail::node_handle504     bool operator!=(node_handle const & rhs) const
505     {
506         return node_ != rhs.node_;
507     }
508 
509     node_pointer node_;
510 };
511 
512 template <typename value_type,
513           typename internal_type,
514           typename extractor
515          >
516 struct value_extractor
517 {
operator ()boost::heap::detail::value_extractor518     value_type const & operator()(internal_type const & data) const
519     {
520         return extractor::get_value(data);
521     }
522 };
523 
524 template <typename T,
525           typename ContainerIterator,
526           typename Extractor>
527 class stable_heap_iterator:
528     public boost::iterator_adaptor<stable_heap_iterator<T, ContainerIterator, Extractor>,
529                                    ContainerIterator,
530                                    T const,
531                                    boost::random_access_traversal_tag>
532 {
533     typedef boost::iterator_adaptor<stable_heap_iterator,
534                                     ContainerIterator,
535                                     T const,
536                                     boost::random_access_traversal_tag> super_t;
537 
538 public:
stable_heap_iterator(void)539     stable_heap_iterator(void):
540         super_t(0)
541     {}
542 
stable_heap_iterator(ContainerIterator const & it)543     explicit stable_heap_iterator(ContainerIterator const & it):
544         super_t(it)
545     {}
546 
547 private:
548     friend class boost::iterator_core_access;
549 
dereference() const550     T const & dereference() const
551     {
552         return Extractor::get_value(*super_t::base());
553     }
554 };
555 
556 template <typename T, typename Parspec, bool constant_time_size>
557 struct make_heap_base
558 {
559     typedef typename parameter::binding<Parspec, tag::compare, std::less<T> >::type compare_argument;
560     typedef typename parameter::binding<Parspec, tag::allocator, std::allocator<T> >::type allocator_argument;
561     typedef typename parameter::binding<Parspec, tag::stability_counter_type, boost::uintmax_t >::type stability_counter_type;
562 
563     static const bool is_stable = extract_stable<Parspec>::value;
564 
565     typedef heap_base<T, compare_argument, constant_time_size, stability_counter_type, is_stable> type;
566 };
567 
568 
569 template <typename Alloc>
570 struct extract_allocator_types
571 {
572     typedef typename boost::allocator_size_type<Alloc>::type size_type;
573     typedef typename boost::allocator_difference_type<Alloc>::type difference_type;
574     typedef typename Alloc::value_type& reference;
575     typedef typename Alloc::value_type const& const_reference;
576     typedef typename boost::allocator_pointer<Alloc>::type pointer;
577     typedef typename boost::allocator_const_pointer<Alloc>::type const_pointer;
578 };
579 
580 
581 } /* namespace detail */
582 } /* namespace heap */
583 } /* namespace boost */
584 
585 #endif /* BOOST_HEAP_DETAIL_STABLE_HEAP_HPP */
586