annotate DEPENDENCIES/generic/include/boost/heap/priority_queue.hpp @ 125:34e428693f5d vext

Vext -> Repoint
author Chris Cannam
date Thu, 14 Jun 2018 11:15:39 +0100
parents c530137014c0
children
rev   line source
Chris@16 1 // boost heap: wrapper for stl heap
Chris@16 2 //
Chris@16 3 // Copyright (C) 2010 Tim Blechmann
Chris@16 4 //
Chris@16 5 // Distributed under the Boost Software License, Version 1.0. (See
Chris@16 6 // accompanying file LICENSE_1_0.txt or copy at
Chris@16 7 // http://www.boost.org/LICENSE_1_0.txt)
Chris@16 8
Chris@16 9 #ifndef BOOST_HEAP_PRIORITY_QUEUE_HPP
Chris@16 10 #define BOOST_HEAP_PRIORITY_QUEUE_HPP
Chris@16 11
Chris@16 12 #include <algorithm>
Chris@16 13 #include <queue>
Chris@16 14 #include <utility>
Chris@16 15 #include <vector>
Chris@16 16
Chris@16 17 #include <boost/assert.hpp>
Chris@16 18
Chris@16 19 #include <boost/heap/detail/heap_comparison.hpp>
Chris@16 20 #include <boost/heap/detail/stable_heap.hpp>
Chris@16 21
Chris@101 22 #ifdef BOOST_HAS_PRAGMA_ONCE
Chris@101 23 #pragma once
Chris@101 24 #endif
Chris@101 25
Chris@101 26
Chris@16 27 namespace boost {
Chris@16 28 namespace heap {
Chris@16 29 namespace detail {
Chris@16 30
Chris@16 31 typedef parameter::parameters<boost::parameter::optional<tag::allocator>,
Chris@16 32 boost::parameter::optional<tag::compare>,
Chris@16 33 boost::parameter::optional<tag::stable>,
Chris@16 34 boost::parameter::optional<tag::stability_counter_type>
Chris@16 35 > priority_queue_signature;
Chris@16 36 }
Chris@16 37
Chris@16 38 /**
Chris@16 39 * \class priority_queue
Chris@16 40 * \brief priority queue, based on stl heap functions
Chris@16 41 *
Chris@16 42 * The priority_queue class is a wrapper for the stl heap functions.<br>
Chris@16 43 * The template parameter T is the type to be managed by the container.
Chris@16 44 * The user can specify additional options and if no options are provided default options are used.
Chris@16 45 *
Chris@16 46 * The container supports the following options:
Chris@16 47 * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> >
Chris@16 48 * - \c boost::heap::stable<>, defaults to \c stable<false>
Chris@16 49 * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t>
Chris@16 50 * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> >
Chris@16 51 *
Chris@16 52 */
Chris@16 53 #ifdef BOOST_DOXYGEN_INVOKED
Chris@16 54 template<class T, class ...Options>
Chris@16 55 #else
Chris@16 56 template <typename T,
Chris@16 57 class A0 = boost::parameter::void_,
Chris@16 58 class A1 = boost::parameter::void_,
Chris@16 59 class A2 = boost::parameter::void_,
Chris@16 60 class A3 = boost::parameter::void_
Chris@16 61 >
Chris@16 62 #endif
Chris@16 63 class priority_queue:
Chris@16 64 private detail::make_heap_base<T, typename detail::priority_queue_signature::bind<A0, A1, A2, A3>::type, false>::type
Chris@16 65 {
Chris@16 66 typedef detail::make_heap_base<T, typename detail::priority_queue_signature::bind<A0, A1, A2, A3>::type, false> heap_base_maker;
Chris@16 67
Chris@16 68 typedef typename heap_base_maker::type super_t;
Chris@16 69 typedef typename super_t::internal_type internal_type;
Chris@16 70 typedef typename heap_base_maker::allocator_argument::template rebind<internal_type>::other internal_type_allocator;
Chris@16 71 typedef std::vector<internal_type, internal_type_allocator> container_type;
Chris@16 72
Chris@16 73 template <typename Heap1, typename Heap2>
Chris@16 74 friend struct detail::heap_merge_emulate;
Chris@16 75
Chris@16 76 container_type q_;
Chris@16 77
Chris@16 78 #ifndef BOOST_DOXYGEN_INVOKED
Chris@16 79 struct implementation_defined:
Chris@16 80 detail::extract_allocator_types<typename heap_base_maker::allocator_argument>
Chris@16 81 {
Chris@16 82 typedef typename heap_base_maker::compare_argument value_compare;
Chris@16 83 typedef detail::stable_heap_iterator<T, typename container_type::const_iterator, super_t> iterator;
Chris@16 84 typedef iterator const_iterator;
Chris@16 85 typedef typename container_type::allocator_type allocator_type;
Chris@16 86 };
Chris@16 87 #endif
Chris@16 88
Chris@16 89 public:
Chris@16 90 typedef T value_type;
Chris@16 91 typedef typename implementation_defined::size_type size_type;
Chris@16 92 typedef typename implementation_defined::difference_type difference_type;
Chris@16 93 typedef typename implementation_defined::value_compare value_compare;
Chris@16 94 typedef typename implementation_defined::allocator_type allocator_type;
Chris@16 95 typedef typename implementation_defined::reference reference;
Chris@16 96 typedef typename implementation_defined::const_reference const_reference;
Chris@16 97 typedef typename implementation_defined::pointer pointer;
Chris@16 98 typedef typename implementation_defined::const_pointer const_pointer;
Chris@16 99 /**
Chris@16 100 * \b Note: The iterator does not traverse the priority queue in order of the priorities.
Chris@16 101 * */
Chris@16 102 typedef typename implementation_defined::iterator iterator;
Chris@16 103 typedef typename implementation_defined::const_iterator const_iterator;
Chris@16 104
Chris@16 105 static const bool constant_time_size = true;
Chris@16 106 static const bool has_ordered_iterators = false;
Chris@16 107 static const bool is_mergable = false;
Chris@16 108 static const bool is_stable = heap_base_maker::is_stable;
Chris@16 109 static const bool has_reserve = true;
Chris@16 110
Chris@16 111 /**
Chris@16 112 * \b Effects: constructs an empty priority queue.
Chris@16 113 *
Chris@16 114 * \b Complexity: Constant.
Chris@16 115 *
Chris@16 116 * */
Chris@16 117 explicit priority_queue(value_compare const & cmp = value_compare()):
Chris@16 118 super_t(cmp)
Chris@16 119 {}
Chris@16 120
Chris@16 121 /**
Chris@16 122 * \b Effects: copy-constructs priority queue from rhs.
Chris@16 123 *
Chris@16 124 * \b Complexity: Linear.
Chris@16 125 *
Chris@16 126 * */
Chris@16 127 priority_queue (priority_queue const & rhs):
Chris@16 128 super_t(rhs), q_(rhs.q_)
Chris@16 129 {}
Chris@16 130
Chris@16 131 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@16 132 /**
Chris@16 133 * \b Effects: C++11-style move constructor.
Chris@16 134 *
Chris@16 135 * \b Complexity: Constant.
Chris@16 136 *
Chris@16 137 * \b Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
Chris@16 138 * */
Chris@16 139 priority_queue(priority_queue && rhs):
Chris@16 140 super_t(std::move(rhs)), q_(std::move(rhs.q_))
Chris@16 141 {}
Chris@16 142
Chris@16 143 /**
Chris@16 144 * \b Effects: C++11-style move assignment.
Chris@16 145 *
Chris@16 146 * \b Complexity: Constant.
Chris@16 147 *
Chris@16 148 * \b Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
Chris@16 149 * */
Chris@16 150 priority_queue & operator=(priority_queue && rhs)
Chris@16 151 {
Chris@16 152 super_t::operator=(std::move(rhs));
Chris@16 153 q_ = std::move(rhs.q_);
Chris@16 154 return *this;
Chris@16 155 }
Chris@16 156 #endif
Chris@16 157
Chris@16 158 /**
Chris@16 159 * \b Effects: Assigns priority queue from rhs.
Chris@16 160 *
Chris@16 161 * \b Complexity: Linear.
Chris@16 162 *
Chris@16 163 * */
Chris@16 164 priority_queue & operator=(priority_queue const & rhs)
Chris@16 165 {
Chris@16 166 static_cast<super_t&>(*this) = static_cast<super_t const &>(rhs);
Chris@16 167 q_ = rhs.q_;
Chris@16 168 return *this;
Chris@16 169 }
Chris@16 170
Chris@16 171 /**
Chris@16 172 * \b Effects: Returns true, if the priority queue contains no elements.
Chris@16 173 *
Chris@16 174 * \b Complexity: Constant.
Chris@16 175 *
Chris@16 176 * */
Chris@16 177 bool empty(void) const
Chris@16 178 {
Chris@16 179 return q_.empty();
Chris@16 180 }
Chris@16 181
Chris@16 182 /**
Chris@16 183 * \b Effects: Returns the number of elements contained in the priority queue.
Chris@16 184 *
Chris@16 185 * \b Complexity: Constant.
Chris@16 186 *
Chris@16 187 * */
Chris@16 188 size_type size(void) const
Chris@16 189 {
Chris@16 190 return q_.size();
Chris@16 191 }
Chris@16 192
Chris@16 193 /**
Chris@16 194 * \b Effects: Returns the maximum number of elements the priority queue can contain.
Chris@16 195 *
Chris@16 196 * \b Complexity: Constant.
Chris@16 197 *
Chris@16 198 * */
Chris@16 199 size_type max_size(void) const
Chris@16 200 {
Chris@16 201 return q_.max_size();
Chris@16 202 }
Chris@16 203
Chris@16 204 /**
Chris@16 205 * \b Effects: Removes all elements from the priority queue.
Chris@16 206 *
Chris@16 207 * \b Complexity: Linear.
Chris@16 208 *
Chris@16 209 * */
Chris@16 210 void clear(void)
Chris@16 211 {
Chris@16 212 q_.clear();
Chris@16 213 }
Chris@16 214
Chris@16 215 /**
Chris@16 216 * \b Effects: Returns allocator.
Chris@16 217 *
Chris@16 218 * \b Complexity: Constant.
Chris@16 219 *
Chris@16 220 * */
Chris@16 221 allocator_type get_allocator(void) const
Chris@16 222 {
Chris@16 223 return q_.get_allocator();
Chris@16 224 }
Chris@16 225
Chris@16 226 /**
Chris@16 227 * \b Effects: Returns a const_reference to the maximum element.
Chris@16 228 *
Chris@16 229 * \b Complexity: Constant.
Chris@16 230 *
Chris@16 231 * */
Chris@16 232 const_reference top(void) const
Chris@16 233 {
Chris@16 234 BOOST_ASSERT(!empty());
Chris@16 235 return super_t::get_value(q_.front());
Chris@16 236 }
Chris@16 237
Chris@16 238 /**
Chris@16 239 * \b Effects: Adds a new element to the priority queue.
Chris@16 240 *
Chris@16 241 * \b Complexity: Logarithmic (amortized). Linear (worst case).
Chris@16 242 *
Chris@16 243 * */
Chris@16 244 void push(value_type const & v)
Chris@16 245 {
Chris@16 246 q_.push_back(super_t::make_node(v));
Chris@16 247 std::push_heap(q_.begin(), q_.end(), static_cast<super_t const &>(*this));
Chris@16 248 }
Chris@16 249
Chris@16 250 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@16 251 /**
Chris@16 252 * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place.
Chris@16 253 *
Chris@16 254 * \b Complexity: Logarithmic (amortized). Linear (worst case).
Chris@16 255 *
Chris@16 256 * */
Chris@16 257 template <class... Args>
Chris@16 258 void emplace(Args&&... args)
Chris@16 259 {
Chris@16 260 q_.emplace_back(super_t::make_node(std::forward<Args>(args)...));
Chris@16 261 std::push_heap(q_.begin(), q_.end(), static_cast<super_t const &>(*this));
Chris@16 262 }
Chris@16 263 #endif
Chris@16 264
Chris@16 265 /**
Chris@16 266 * \b Effects: Removes the top element from the priority queue.
Chris@16 267 *
Chris@16 268 * \b Complexity: Logarithmic (amortized). Linear (worst case).
Chris@16 269 *
Chris@16 270 * */
Chris@16 271 void pop(void)
Chris@16 272 {
Chris@16 273 BOOST_ASSERT(!empty());
Chris@16 274 std::pop_heap(q_.begin(), q_.end(), static_cast<super_t const &>(*this));
Chris@16 275 q_.pop_back();
Chris@16 276 }
Chris@16 277
Chris@16 278 /**
Chris@16 279 * \b Effects: Swaps two priority queues.
Chris@16 280 *
Chris@16 281 * \b Complexity: Constant.
Chris@16 282 *
Chris@16 283 * */
Chris@16 284 void swap(priority_queue & rhs)
Chris@16 285 {
Chris@16 286 super_t::swap(rhs);
Chris@16 287 q_.swap(rhs.q_);
Chris@16 288 }
Chris@16 289
Chris@16 290 /**
Chris@16 291 * \b Effects: Returns an iterator to the first element contained in the priority queue.
Chris@16 292 *
Chris@16 293 * \b Complexity: Constant.
Chris@16 294 *
Chris@16 295 * */
Chris@16 296 iterator begin(void) const
Chris@16 297 {
Chris@16 298 return iterator(q_.begin());
Chris@16 299 }
Chris@16 300
Chris@16 301 /**
Chris@16 302 * \b Effects: Returns an iterator to the end of the priority queue.
Chris@16 303 *
Chris@16 304 * \b Complexity: Constant.
Chris@16 305 *
Chris@16 306 * */
Chris@16 307 iterator end(void) const
Chris@16 308 {
Chris@16 309 return iterator(q_.end());
Chris@16 310 }
Chris@16 311
Chris@16 312 /**
Chris@16 313 * \b Effects: Reserves memory for element_count elements
Chris@16 314 *
Chris@16 315 * \b Complexity: Linear.
Chris@16 316 *
Chris@16 317 * \b Node: Invalidates iterators
Chris@16 318 *
Chris@16 319 * */
Chris@16 320 void reserve(size_type element_count)
Chris@16 321 {
Chris@16 322 q_.reserve(element_count);
Chris@16 323 }
Chris@16 324
Chris@16 325 /**
Chris@16 326 * \b Effect: Returns the value_compare object used by the priority queue
Chris@16 327 *
Chris@16 328 * */
Chris@16 329 value_compare const & value_comp(void) const
Chris@16 330 {
Chris@16 331 return super_t::value_comp();
Chris@16 332 }
Chris@16 333
Chris@16 334 /**
Chris@16 335 * \b Returns: Element-wise comparison of heap data structures
Chris@16 336 *
Chris@16 337 * \b Requirement: the \c value_compare object of both heaps must match.
Chris@16 338 *
Chris@16 339 * */
Chris@16 340 template <typename HeapType>
Chris@16 341 bool operator<(HeapType const & rhs) const
Chris@16 342 {
Chris@16 343 return detail::heap_compare(*this, rhs);
Chris@16 344 }
Chris@16 345
Chris@16 346 /**
Chris@16 347 * \b Returns: Element-wise comparison of heap data structures
Chris@16 348 *
Chris@16 349 * \b Requirement: the \c value_compare object of both heaps must match.
Chris@16 350 *
Chris@16 351 * */
Chris@16 352 template <typename HeapType>
Chris@16 353 bool operator>(HeapType const & rhs) const
Chris@16 354 {
Chris@16 355 return detail::heap_compare(rhs, *this);
Chris@16 356 }
Chris@16 357
Chris@16 358 /**
Chris@16 359 * \b Returns: Element-wise comparison of heap data structures
Chris@16 360 *
Chris@16 361 * \b Requirement: the \c value_compare object of both heaps must match.
Chris@16 362 *
Chris@16 363 * */
Chris@16 364 template <typename HeapType>
Chris@16 365 bool operator>=(HeapType const & rhs) const
Chris@16 366 {
Chris@16 367 return !operator<(rhs);
Chris@16 368 }
Chris@16 369
Chris@16 370 /**
Chris@16 371 * \b Returns: Element-wise comparison of heap data structures
Chris@16 372 *
Chris@16 373 * \b Requirement: the \c value_compare object of both heaps must match.
Chris@16 374 *
Chris@16 375 * */
Chris@16 376 template <typename HeapType>
Chris@16 377 bool operator<=(HeapType const & rhs) const
Chris@16 378 {
Chris@16 379 return !operator>(rhs);
Chris@16 380 }
Chris@16 381
Chris@16 382 /** \brief Equivalent comparison
Chris@16 383 * \b Returns: True, if both heap data structures are equivalent.
Chris@16 384 *
Chris@16 385 * \b Requirement: the \c value_compare object of both heaps must match.
Chris@16 386 *
Chris@16 387 * */
Chris@16 388 template <typename HeapType>
Chris@16 389 bool operator==(HeapType const & rhs) const
Chris@16 390 {
Chris@16 391 return detail::heap_equality(*this, rhs);
Chris@16 392 }
Chris@16 393
Chris@16 394 /** \brief Equivalent comparison
Chris@16 395 * \b Returns: True, if both heap data structures are not equivalent.
Chris@16 396 *
Chris@16 397 * \b Requirement: the \c value_compare object of both heaps must match.
Chris@16 398 *
Chris@16 399 * */
Chris@16 400 template <typename HeapType>
Chris@16 401 bool operator!=(HeapType const & rhs) const
Chris@16 402 {
Chris@16 403 return !(*this == rhs);
Chris@16 404 }
Chris@16 405 };
Chris@16 406
Chris@16 407 } /* namespace heap */
Chris@16 408 } /* namespace boost */
Chris@16 409
Chris@16 410 #endif /* BOOST_HEAP_PRIORITY_QUEUE_HPP */