aGrUM 2.3.2
a C++ library for (probabilistic) graphical models
sortedPriorityQueue_tpl.h
Go to the documentation of this file.
1/****************************************************************************
2 * This file is part of the aGrUM/pyAgrum library. *
3 * *
4 * Copyright (c) 2005-2025 by *
5 * - Pierre-Henri WUILLEMIN(_at_LIP6) *
6 * - Christophe GONZALES(_at_AMU) *
7 * *
8 * The aGrUM/pyAgrum library is free software; you can redistribute it *
9 * and/or modify it under the terms of either : *
10 * *
11 * - the GNU Lesser General Public License as published by *
12 * the Free Software Foundation, either version 3 of the License, *
13 * or (at your option) any later version, *
14 * - the MIT license (MIT), *
15 * - or both in dual license, as here. *
16 * *
17 * (see https://agrum.gitlab.io/articles/dual-licenses-lgplv3mit.html) *
18 * *
19 * This aGrUM/pyAgrum library is distributed in the hope that it will be *
20 * useful, but WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, *
21 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES MERCHANTABILITY or FITNESS *
22 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE *
23 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER *
24 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, *
25 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR *
26 * OTHER DEALINGS IN THE SOFTWARE. *
27 * *
28 * See LICENCES for more details. *
29 * *
30 * SPDX-FileCopyrightText: Copyright 2005-2025 *
31 * - Pierre-Henri WUILLEMIN(_at_LIP6) *
32 * - Christophe GONZALES(_at_AMU) *
33 * SPDX-License-Identifier: LGPL-3.0-or-later OR MIT *
34 * *
35 * Contact : info_at_agrum_dot_org *
36 * homepage : http://agrum.gitlab.io *
37 * gitlab : https://gitlab.com/agrumery/agrum *
38 * *
39 ****************************************************************************/
40#pragma once
41
42
43#include <agrum/base/core/sortedPriorityQueue.h>
44
45#ifndef DOXYGEN_SHOULD_SKIP_THIS
46
47namespace gum {
48
49 // basic constructor
50 template < typename Val, typename Priority, typename Cmp >
51 INLINE SortedPriorityQueue< Val, Priority, Cmp >::SortedPriorityQueue(Cmp compare,
52 Size capacity) :
53 _nodes_(capacity, true, true), _tree_cmp_(compare) {
54 GUM_CONSTRUCTOR(SortedPriorityQueue);
55 }
56
57 // initializer list constructor
58 template < typename Val, typename Priority, typename Cmp >
59 SortedPriorityQueue< Val, Priority, Cmp >::SortedPriorityQueue(
60 std::initializer_list< std::pair< Val, Priority > > list) :
61 _nodes_(Size(list.size()) / 2, true, true) {
62 // fill the queue
63 for (const auto& elt: list) {
64 insert(elt.first, elt.second);
65 }
66
67 GUM_CONSTRUCTOR(SortedPriorityQueue);
68 }
69
70 // copy constructor
71 template < typename Val, typename Priority, typename Cmp >
72 SortedPriorityQueue< Val, Priority, Cmp >::SortedPriorityQueue(
73 const SortedPriorityQueue< Val, Priority, Cmp >& from) :
74 _nodes_(from._nodes_), _tree_cmp_(from._tree_cmp_) {
75 // fill the heap structure
76 for (const auto& node_prio: _nodes_) {
77 _tree_.insert(&node_prio.first);
78 }
79
80 GUM_CONS_CPY(SortedPriorityQueue);
81 }
82
83 // move constructor
84 template < typename Val, typename Priority, typename Cmp >
85 SortedPriorityQueue< Val, Priority, Cmp >::SortedPriorityQueue(
86 SortedPriorityQueue< Val, Priority, Cmp >&& from) noexcept :
87 _tree_(std::move(from._tree_)), _nodes_(std::move(from._nodes_)),
88 _tree_cmp_(std::move(from._tree_cmp_)) {
89 GUM_CONS_MOV(SortedPriorityQueue)
90 }
91
92 // destructor
93 template < typename Val, typename Priority, typename Cmp >
94 SortedPriorityQueue< Val, Priority, Cmp >::~SortedPriorityQueue() {
95 GUM_DESTRUCTOR(SortedPriorityQueue);
96 }
97
98 // copy operator
99 template < typename Val, typename Priority, typename Cmp >
100 SortedPriorityQueue< Val, Priority, Cmp >& SortedPriorityQueue< Val, Priority, Cmp >::operator=(
101 const SortedPriorityQueue< Val, Priority, Cmp >& from) {
102 // avoid self assignment
103 if (this != &from) {
104 GUM_OP_CPY(SortedPriorityQueue)
105
106 try {
107 // set the comparison function
108 _tree_cmp_ = from._tree_cmp_;
109
110 // copy the nodes within the hash table
111 _nodes_ = from._nodes_;
112
113 // fill the AVL tree
114 for (const auto& node_prio: _nodes_)
115 _tree_.insert(&node_prio.first);
116 } catch (...) {
117 _tree_.clear();
118 _nodes_.clear();
119 throw;
120 }
121 }
122
123 return *this;
124 }
125
126 // move operator
127 template < typename Val, typename Priority, typename Cmp >
128 INLINE SortedPriorityQueue< Val, Priority, Cmp >&
129 SortedPriorityQueue< Val, Priority, Cmp >::operator=(
130 SortedPriorityQueue< Val, Priority, Cmp >&& from) noexcept {
131 // avoid self assignment
132 if (this != &from) {
133 GUM_OP_MOV(SortedPriorityQueue)
134
135 _nodes_ = std::move(from._nodes_);
136 _tree_ = std::move(from._tree_);
137 _tree_cmp_ = std::move(from._tree_cmp_);
138 }
139
140 return *this;
141 }
142
143 // returns the number of elements in the priority queue
144 template < typename Val, typename Priority, typename Cmp >
145 INLINE Size SortedPriorityQueue< Val, Priority, Cmp >::size() const noexcept {
146 return _tree_.size();
147 }
148
149 // indicates whether the priority queue is empty
150 template < typename Val, typename Priority, typename Cmp >
151 INLINE bool SortedPriorityQueue< Val, Priority, Cmp >::empty() const noexcept {
152 return (_tree_.empty());
153 }
154
155 // indicates whether the priority queue contains a given value
156 template < typename Val, typename Priority, typename Cmp >
157 INLINE bool SortedPriorityQueue< Val, Priority, Cmp >::contains(const Val& val) const noexcept {
158 if constexpr (std::is_scalar_v< Val >) {
159 return _nodes_.exists(AVLTreeNode< Val >(val));
160 } else {
161 AVLTreeNode< Val > xval(std::move(const_cast< Val& >(val)));
162 bool res = _nodes_.exists(xval);
163 const_cast< Val& >(val) = std::move(xval.value);
164 return res;
165 }
166 }
167
168 // returns the element at the top of the priority queue
169 template < typename Val, typename Priority, typename Cmp >
170 INLINE const Val& SortedPriorityQueue< Val, Priority, Cmp >::top() const {
171 if (_tree_.empty()) { GUM_ERROR(NotFound, "An empty sorted priority queue has no top element") }
172
173 return _tree_.highestNode()->value;
174 }
175
176 // returns the element at the bottom of the priority queue
177 template < typename Val, typename Priority, typename Cmp >
178 INLINE const Val& SortedPriorityQueue< Val, Priority, Cmp >::bottom() const {
179 if (_tree_.empty()) {
180 GUM_ERROR(NotFound, "An empty sorted priority queue has no bottom element")
181 }
182
183 return _tree_.lowestNode()->value;
184 }
185
186 // returns the priority of the top element
187 template < typename Val, typename Priority, typename Cmp >
188 INLINE const Priority& SortedPriorityQueue< Val, Priority, Cmp >::topPriority() const {
189 if (_tree_.empty()) { GUM_ERROR(NotFound, "An empty priority queue has no top priority") }
190
191 return _tree_cmp_.getPriority(_tree_.highestNode()->value);
192 }
193
194 // returns the priority of the top element
195 template < typename Val, typename Priority, typename Cmp >
196 INLINE const Priority& SortedPriorityQueue< Val, Priority, Cmp >::bottomPriority() const {
197 if (_tree_.empty()) { GUM_ERROR(NotFound, "An empty priority queue has no bottom priority") }
198
199 return _tree_cmp_.getPriority(_tree_.lowestNode()->value);
200 }
201
202 // removes the top element from the priority queue and return it
203 template < typename Val, typename Priority, typename Cmp >
204 INLINE Val SortedPriorityQueue< Val, Priority, Cmp >::popTop() {
205 if (_tree_.empty()) { GUM_ERROR(NotFound, "An empty sorted priority queue has no top element") }
206
207 // erase the node from the tree
208 AVLNode* node = _tree_.highestNode();
209 _tree_.erase(node);
210
211 // erase the node from the hash table
212 Val v = std::move(node->value);
213 _nodes_.erase(*node);
214
215 return v;
216 }
217
218 // removes the top element from the priority queue and return it
219 template < typename Val, typename Priority, typename Cmp >
220 INLINE Val SortedPriorityQueue< Val, Priority, Cmp >::pop() {
221 return popTop();
222 }
223
224 // removes the bottom element from the priority queue and return it
225 template < typename Val, typename Priority, typename Cmp >
226 INLINE Val SortedPriorityQueue< Val, Priority, Cmp >::popBottom() {
227 if (_tree_.empty()) {
228 GUM_ERROR(NotFound, "An empty sorted priority queue has no bottom element")
229 }
230
231 // erase the node from the tree
232 AVLNode* node = _tree_.lowestNode();
233 _tree_.erase(node);
234
235 // erase the node from the hash table
236 Val v = std::move(node->value);
237 _nodes_.erase(*node);
238
239 return v;
240 }
241
242 // inserts a new (a copy) element in the priority queue
243 template < typename Val, typename Priority, typename Cmp >
244 INLINE typename SortedPriorityQueue< Val, Priority, Cmp >::const_reference
245 SortedPriorityQueue< Val, Priority, Cmp >::insert(const Val& val, const Priority& priority) {
246 // create the entry in the _nodes_ hashtable (if the element already exists,
247 // _nodes_.insert will raise a DuplicateElement exception)
248 Priority new_priority(priority);
249 const auto& new_elt = _nodes_.insert(AVLNode(val), std::move(new_priority));
250
251 // update the tree
252 _tree_.insert(const_cast< AVLTreeNode< Val >* >(&new_elt.first));
253
254 return new_elt.first.value;
255 }
256
257 // inserts by move a new element in the priority queue
258 template < typename Val, typename Priority, typename Cmp >
259 INLINE typename SortedPriorityQueue< Val, Priority, Cmp >::const_reference
260 SortedPriorityQueue< Val, Priority, Cmp >::insert(Val&& val, Priority&& priority) {
261 // create the entry in the indices hashtable (if the element already exists,
262 // _nodes_.insert will raise a DuplicateElement exception)
263 const auto& new_elt = _nodes_.insert(AVLNode(std::move(val)), std::move(priority));
264
265 // update the tree
266 _tree_.insert(const_cast< AVLTreeNode< Val >* >(&new_elt.first));
267
268 return new_elt.first.value;
269 }
270
271 // emplace a new element into the priority queue
272 template < typename Val, typename Priority, typename Cmp >
273 template < typename... Args >
274 INLINE typename SortedPriorityQueue< Val, Priority, Cmp >::const_reference
275 SortedPriorityQueue< Val, Priority, Cmp >::emplace(Args&&... args) {
276 auto new_elt = std::make_pair< Val, Priority >(std::forward< Args >(args)...);
277 return insert(std::move(new_elt.first), std::move(new_elt.second));
278 }
279
280 // removes the top of the priority queue (but does not return it)
281 template < typename Val, typename Priority, typename Cmp >
282 INLINE void SortedPriorityQueue< Val, Priority, Cmp >::eraseTop() {
283 if (_tree_.empty()) return;
284 AVLNode* node = _tree_.highestNode();
285 _tree_.erase(node);
286 _nodes_.erase(*node);
287 }
288
289 // removes the bottom of the priority queue (but does not return it)
290 template < typename Val, typename Priority, typename Cmp >
291 INLINE void SortedPriorityQueue< Val, Priority, Cmp >::eraseBottom() {
292 if (_tree_.empty()) return;
293 AVLNode* node = _tree_.lowestNode();
294 _tree_.erase(node);
295 _nodes_.erase(*node);
296 }
297
298 // returns the node in the hash table corresponding to a given value
299 template < typename Val, typename Priority, typename Cmp >
300 INLINE AVLTreeNode< Val >&
301 SortedPriorityQueue< Val, Priority, Cmp >::getNode_(const Val& val) const {
302 // Some compilers are optimizing _tree_cmp_.getNode(val) for Val=string. This
303 // induces a lot of warnings. To prevent this, we have an optimized code for
304 // non-strings and a less optimal but warning-free
305 if constexpr (!is_basic_string< Val >::value)
306 return const_cast< AVLTreeNode< Val >& >(_nodes_.key(*(_tree_cmp_.getNode(val))));
307 else {
308 AVLTreeNode< Val > xval(std::move(const_cast< Val& >(val)));
309 try {
310 auto& node = const_cast< AVLTreeNode< Val >& >(_nodes_.key(xval));
311 const_cast< Val& >(val) = std::move(xval.value);
312 return node;
313 } catch (NotFound const&) {
314 // restore into val the value that was moved
315 const_cast< Val& >(val) = std::move(xval.value);
316 throw;
317 }
318 }
319 }
320
321 // removes a given element from the priority queue (but does not return it)
322 template < typename Val, typename Priority, typename Cmp >
323 INLINE void SortedPriorityQueue< Val, Priority, Cmp >::erase(const Val& val) {
324 try {
325 AVLNode& node = getNode_(val);
326 _tree_.erase(&node);
327 _nodes_.erase(node);
328 } catch (NotFound const&) {}
329 }
330
331 // modifies the priority of a given element
332 template < typename Val, typename Priority, typename Cmp >
333 INLINE void SortedPriorityQueue< Val, Priority, Cmp >::setPriority(const Val& elt,
334 const Priority& new_priority) {
335 try {
336 AVLNode& node = getNode_(elt);
337 _tree_.erase(&node);
338 _nodes_[node] = new_priority;
339 _tree_.insert(&node);
340 } catch (NotFound const&) {
341 GUM_ERROR(NotFound,
342 "The sorted priority queue does not contain"
343 << elt << ". Hence it is not possible to change its priority")
344 }
345 }
346
347 // modifies the priority of a given element
348 template < typename Val, typename Priority, typename Cmp >
349 INLINE void SortedPriorityQueue< Val, Priority, Cmp >::setPriority(const Val& elt,
350 Priority&& new_priority) {
351 try {
352 AVLNode& node = getNode_(elt);
353 _tree_.erase(&node);
354 _nodes_[node] = std::move(new_priority);
355 _tree_.insert(&node);
356 } catch (NotFound const&) {
357 GUM_ERROR(NotFound,
358 "The sorted priority queue does not contain"
359 << elt << ". Hence it is not possible to change its priority")
360 }
361 }
362
363 // returns the priority of a given element
364 template < typename Val, typename Priority, typename Cmp >
365 INLINE const Priority& SortedPriorityQueue< Val, Priority, Cmp >::priority(const Val& elt) const {
366 return _nodes_[getNode_(elt)];
367 }
368
369 // removes all the elements from the queue
370 template < typename Val, typename Priority, typename Cmp >
371 INLINE void SortedPriorityQueue< Val, Priority, Cmp >::clear() {
372 _tree_.clear();
373 _nodes_.clear();
374 }
375
376 // displays the content of the queue
377 template < typename Val, typename Priority, typename Cmp >
378 std::string SortedPriorityQueue< Val, Priority, Cmp >::toString() const {
379 bool deja = false;
380 std::stringstream stream;
381 stream << "[";
382
383 // parse the tree from the highest element to the lowest
384 for (auto iter = _tree_.rbegin(); iter != _tree_.rend(); ++iter) {
385 if (deja) stream << " ; ";
386 else deja = true;
387
388 stream << "(" << iter->value << ", " << _tree_cmp_.getPriority(iter->value) << ")";
389 }
390
391 stream << "]";
392
393 return stream.str();
394 }
395
397 template < typename Val, typename Priority, typename Cmp >
398 INLINE typename SortedPriorityQueue< Val, Priority, Cmp >::iterator
399 SortedPriorityQueue< Val, Priority, Cmp >::begin() const {
400 return iterator(*this);
401 }
402
404 template < typename Val, typename Priority, typename Cmp >
405 INLINE constexpr const typename SortedPriorityQueue< Val, Priority, Cmp >::iterator&
406 SortedPriorityQueue< Val, Priority, Cmp >::end() const {
407 return *(reinterpret_cast< const iterator* >(_SortedPriorityQueue_end_));
408 }
409
411 template < typename Val, typename Priority, typename Cmp >
412 INLINE typename SortedPriorityQueue< Val, Priority, Cmp >::reverse_iterator
413 SortedPriorityQueue< Val, Priority, Cmp >::rbegin() const {
414 return reverse_iterator(*this, true);
415 }
416
418 template < typename Val, typename Priority, typename Cmp >
419 INLINE constexpr const typename SortedPriorityQueue< Val, Priority, Cmp >::reverse_iterator&
420 SortedPriorityQueue< Val, Priority, Cmp >::rend() const {
421 return *(reinterpret_cast< const reverse_iterator* >(_SortedPriorityQueue_rend_));
422 }
423
425 template < typename Val, typename Priority, typename Cmp >
426 INLINE typename SortedPriorityQueue< Val, Priority, Cmp >::iterator_safe
427 SortedPriorityQueue< Val, Priority, Cmp >::beginSafe() {
428 return iterator_safe(*this);
429 }
430
432 template < typename Val, typename Priority, typename Cmp >
433 INLINE constexpr const typename SortedPriorityQueue< Val, Priority, Cmp >::iterator_safe&
434 SortedPriorityQueue< Val, Priority, Cmp >::endSafe() const {
435 return *(reinterpret_cast< const iterator_safe* >(_SortedPriorityQueue_end_safe_));
436 }
437
439 template < typename Val, typename Priority, typename Cmp >
440 INLINE typename SortedPriorityQueue< Val, Priority, Cmp >::reverse_iterator_safe
441 SortedPriorityQueue< Val, Priority, Cmp >::rbeginSafe() {
442 return reverse_iterator_safe(*this, true);
443 }
444
446 template < typename Val, typename Priority, typename Cmp >
447 INLINE constexpr const typename SortedPriorityQueue< Val, Priority, Cmp >::reverse_iterator_safe&
448 SortedPriorityQueue< Val, Priority, Cmp >::rendSafe() const {
449 return *(reinterpret_cast< const reverse_iterator_safe* >(_SortedPriorityQueue_rend_safe_));
450 }
451
452 // return the size of the array storing the priority queue
453 template < typename Val, typename Priority, typename Cmp >
454 INLINE Size SortedPriorityQueue< Val, Priority, Cmp >::capacity() const noexcept {
455 return Size(_nodes_.capacity());
456 }
457
458 // changes the size of the array storing the priority queue
459 template < typename Val, typename Priority, typename Cmp >
460 INLINE void SortedPriorityQueue< Val, Priority, Cmp >::resize(Size new_size) {
461 if (new_size < _tree_.size() / 2) return;
462 _nodes_.resize(new_size);
463 }
464
466
468 template < typename Val, typename Priority, typename Cmp >
469 INLINE SortedPriorityQueueIterator< Val, Priority, Cmp >::SortedPriorityQueueIterator(
470 const SortedPriorityQueue< Val, Priority, Cmp >& queue,
471 const bool begin) noexcept :
472 SharedAVLTreeReverseIterator< Val, TreeCmp >(queue._tree_, begin) {
473 GUM_CONSTRUCTOR(SortedPriorityQueueIterator)
474 }
475
477 template < typename Val, typename Priority, typename Cmp >
478 INLINE SortedPriorityQueueIterator< Val, Priority, Cmp >::SortedPriorityQueueIterator(
479 const SortedPriorityQueueIterator< Val, Priority, Cmp >& from) noexcept :
480 SharedAVLTreeReverseIterator< Val, TreeCmp >(from) {
481 GUM_CONS_CPY(SortedPriorityQueueIterator)
482 }
483
485 template < typename Val, typename Priority, typename Cmp >
486 INLINE SortedPriorityQueueIterator< Val, Priority, Cmp >::SortedPriorityQueueIterator(
487 SortedPriorityQueueIterator< Val, Priority, Cmp >&& from) noexcept :
488 SharedAVLTreeReverseIterator< Val, TreeCmp >(std::move(from)) {
489 GUM_CONS_MOV(SortedPriorityQueueIterator)
490 }
491
493 template < typename Val, typename Priority, typename Cmp >
494 INLINE
495 SortedPriorityQueueIterator< Val, Priority, Cmp >::~SortedPriorityQueueIterator() noexcept {
496 GUM_DESTRUCTOR(SortedPriorityQueueIterator)
497 }
498
500 template < typename Val, typename Priority, typename Cmp >
501 INLINE SortedPriorityQueueIterator< Val, Priority, Cmp >&
502 SortedPriorityQueueIterator< Val, Priority, Cmp >::operator=(
503 const SortedPriorityQueueIterator< Val, Priority, Cmp >& from) noexcept {
504 SharedAVLTreeReverseIterator< Val, TreeCmp >::operator=(from);
505 return *this;
506 }
507
509 template < typename Val, typename Priority, typename Cmp >
510 INLINE SortedPriorityQueueIterator< Val, Priority, Cmp >&
511 SortedPriorityQueueIterator< Val, Priority, Cmp >::operator=(
512 SortedPriorityQueueIterator< Val, Priority, Cmp >&& from) noexcept {
513 SharedAVLTreeReverseIterator< Val, TreeCmp >::operator=(std::move(from));
514 return *this;
515 }
516
518 template < typename Val, typename Priority, typename Cmp >
519 INLINE bool SortedPriorityQueueIterator< Val, Priority, Cmp >::operator==(
520 const SortedPriorityQueueIterator< Val, Priority, Cmp >& from) const {
521 return SharedAVLTreeReverseIterator< Val, TreeCmp >::operator==(from);
522 }
523
525 template < typename Val, typename Priority, typename Cmp >
526 INLINE bool SortedPriorityQueueIterator< Val, Priority, Cmp >::operator!=(
527 const SortedPriorityQueueIterator< Val, Priority, Cmp >& from) const {
528 return !operator==(from);
529 }
530
532 template < typename Val, typename Priority, typename Cmp >
533 INLINE SortedPriorityQueueIterator< Val, Priority, Cmp >&
534 SortedPriorityQueueIterator< Val, Priority, Cmp >::operator++() noexcept {
535 SharedAVLTreeReverseIterator< Val, TreeCmp >::operator++();
536 return *this;
537 }
538
540 template < typename Val, typename Priority, typename Cmp >
541 INLINE SortedPriorityQueueIterator< Val, Priority, Cmp >&
542 SortedPriorityQueueIterator< Val, Priority, Cmp >::operator+=(const Size k) noexcept {
543 SharedAVLTreeReverseIterator< Val, TreeCmp >::operator+=(k);
544 return *this;
545 }
546
548 template < typename Val, typename Priority, typename Cmp >
549 INLINE SortedPriorityQueueIterator< Val, Priority, Cmp >&
550 SortedPriorityQueueIterator< Val, Priority, Cmp >::operator--() noexcept {
551 SharedAVLTreeReverseIterator< Val, TreeCmp >::operator--();
552 return *this;
553 }
554
556 template < typename Val, typename Priority, typename Cmp >
557 INLINE SortedPriorityQueueIterator< Val, Priority, Cmp >&
558 SortedPriorityQueueIterator< Val, Priority, Cmp >::operator-=(const Size k) noexcept {
559 SharedAVLTreeReverseIterator< Val, TreeCmp >::operator-=(k);
560 return *this;
561 }
562
564 template < typename Val, typename Priority, typename Cmp >
565 INLINE typename SortedPriorityQueueIterator< Val, Priority, Cmp >::const_reference
566 SortedPriorityQueueIterator< Val, Priority, Cmp >::operator*() const {
567 return SharedAVLTreeReverseIterator< Val, TreeCmp >::operator*().value;
568 }
569
571 template < typename Val, typename Priority, typename Cmp >
572 INLINE typename SortedPriorityQueueIterator< Val, Priority, Cmp >::const_pointer
573 SortedPriorityQueueIterator< Val, Priority, Cmp >::operator->() const {
574 auto node = SharedAVLTreeReverseIterator< Val, TreeCmp >::operator->();
575 if (node != nullptr) return &(node->value);
576 else { GUM_ERROR(NotFound, "The sorted priority queue iterator does not point on any value") }
577 }
578
580
582 template < typename Val, typename Priority, typename Cmp >
583 INLINE SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >::SortedPriorityQueueIteratorSafe(
584 SortedPriorityQueue< Val, Priority, Cmp >& queue,
585 const bool rbegin) : SharedAVLTreeReverseIteratorSafe< Val, TreeCmp >(queue._tree_, rbegin) {
586 GUM_CONSTRUCTOR(SortedPriorityQueueIteratorSafe)
587 }
588
590 template < typename Val, typename Priority, typename Cmp >
591 INLINE SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >::SortedPriorityQueueIteratorSafe(
592 const SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >& from) :
593 SharedAVLTreeReverseIteratorSafe< Val, TreeCmp >(from) {
594 GUM_CONS_CPY(SortedPriorityQueueIteratorSafe)
595 }
596
598 template < typename Val, typename Priority, typename Cmp >
599 INLINE SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >::SortedPriorityQueueIteratorSafe(
600 SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >&& from) :
601 SharedAVLTreeReverseIteratorSafe< Val, TreeCmp >(std::move(from)) {
602 GUM_CONS_CPY(SortedPriorityQueueIteratorSafe)
603 }
604
606 template < typename Val, typename Priority, typename Cmp >
607 INLINE SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >::
608 ~SortedPriorityQueueIteratorSafe() noexcept {
609 GUM_DESTRUCTOR(SortedPriorityQueueIteratorSafe)
610 }
611
613 template < typename Val, typename Priority, typename Cmp >
614 INLINE SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >&
615 SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >::operator=(
616 const SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >& from) {
617 SharedAVLTreeReverseIteratorSafe< Val, TreeCmp >::operator=(from);
618 return *this;
619 }
620
622 template < typename Val, typename Priority, typename Cmp >
623 INLINE SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >&
624 SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >::operator=(
625 SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >&& from) {
626 SharedAVLTreeReverseIteratorSafe< Val, TreeCmp >::operator=(std::move(from));
627 return *this;
628 }
629
631 template < typename Val, typename Priority, typename Cmp >
632 INLINE bool SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >::operator==(
633 const SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >& from) const {
634 return SharedAVLTreeReverseIteratorSafe< Val, TreeCmp >::operator==(from);
635 }
636
638 template < typename Val, typename Priority, typename Cmp >
639 INLINE bool SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >::operator!=(
640 const SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >& from) const {
641 return !operator==(from);
642 }
643
645 template < typename Val, typename Priority, typename Cmp >
646 INLINE SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >&
647 SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >::operator++() noexcept {
648 SharedAVLTreeReverseIteratorSafe< Val, TreeCmp >::operator++();
649 return *this;
650 }
651
653 template < typename Val, typename Priority, typename Cmp >
654 INLINE SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >&
655 SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >::operator+=(const Size k) noexcept {
656 SharedAVLTreeReverseIteratorSafe< Val, TreeCmp >::operator+=(k);
657 return *this;
658 }
659
661 template < typename Val, typename Priority, typename Cmp >
662 INLINE SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >&
663 SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >::operator--() noexcept {
664 SharedAVLTreeReverseIteratorSafe< Val, TreeCmp >::operator--();
665 return *this;
666 }
667
669 template < typename Val, typename Priority, typename Cmp >
670 INLINE SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >&
671 SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >::operator-=(const Size k) noexcept {
672 SharedAVLTreeReverseIteratorSafe< Val, TreeCmp >::operator-=(k);
673 return *this;
674 }
675
677 template < typename Val, typename Priority, typename Cmp >
678 INLINE typename SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >::const_reference
679 SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >::operator*() const {
680 return SharedAVLTreeReverseIteratorSafe< Val, TreeCmp >::operator*().value;
681 }
682
684 template < typename Val, typename Priority, typename Cmp >
685 INLINE typename SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >::const_pointer
686 SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >::operator->() const {
687 auto node = SharedAVLTreeReverseIteratorSafe< Val, TreeCmp >::operator->();
688 if (node != nullptr) return &(node->value);
689 else { GUM_ERROR(NotFound, "The sorted priority queue iterator does not point on any value") }
690 }
691
693
695 template < typename Val, typename Priority, typename Cmp >
696 INLINE
697 SortedPriorityQueueReverseIterator< Val, Priority, Cmp >::SortedPriorityQueueReverseIterator(
698 const SortedPriorityQueue< Val, Priority, Cmp >& queue,
699 const bool rbegin) noexcept :
700 SharedAVLTreeIterator< Val, TreeCmp >(queue._tree_, rbegin) {
701 GUM_CONSTRUCTOR(SortedPriorityQueueReverseIterator)
702 }
703
705 template < typename Val, typename Priority, typename Cmp >
706 INLINE
707 SortedPriorityQueueReverseIterator< Val, Priority, Cmp >::SortedPriorityQueueReverseIterator(
708 const SortedPriorityQueueReverseIterator< Val, Priority, Cmp >& from) noexcept :
709 SharedAVLTreeIterator< Val, TreeCmp >(from) {
710 GUM_CONS_CPY(SortedPriorityQueueReverseIterator)
711 }
712
714 template < typename Val, typename Priority, typename Cmp >
715 INLINE
716 SortedPriorityQueueReverseIterator< Val, Priority, Cmp >::SortedPriorityQueueReverseIterator(
717 SortedPriorityQueueReverseIterator< Val, Priority, Cmp >&& from) noexcept :
718 SharedAVLTreeIterator< Val, TreeCmp >(std::move(from)) {
719 GUM_CONS_MOV(SortedPriorityQueueReverseIterator)
720 }
721
723 template < typename Val, typename Priority, typename Cmp >
724 INLINE SortedPriorityQueueReverseIterator< Val, Priority, Cmp >::
725 ~SortedPriorityQueueReverseIterator() noexcept {
726 GUM_DESTRUCTOR(SortedPriorityQueueReverseIterator)
727 }
728
730 template < typename Val, typename Priority, typename Cmp >
731 INLINE SortedPriorityQueueReverseIterator< Val, Priority, Cmp >&
732 SortedPriorityQueueReverseIterator< Val, Priority, Cmp >::operator=(
733 const SortedPriorityQueueReverseIterator< Val, Priority, Cmp >& from) noexcept {
734 SharedAVLTreeIterator< Val, TreeCmp >::operator=(from);
735 return *this;
736 }
737
739 template < typename Val, typename Priority, typename Cmp >
740 INLINE SortedPriorityQueueReverseIterator< Val, Priority, Cmp >&
741 SortedPriorityQueueReverseIterator< Val, Priority, Cmp >::operator=(
742 SortedPriorityQueueReverseIterator< Val, Priority, Cmp >&& from) noexcept {
743 SharedAVLTreeIterator< Val, TreeCmp >::operator=(std::move(from));
744 return *this;
745 }
746
748 template < typename Val, typename Priority, typename Cmp >
749 INLINE bool SortedPriorityQueueReverseIterator< Val, Priority, Cmp >::operator==(
750 const SortedPriorityQueueReverseIterator< Val, Priority, Cmp >& from) const {
751 return SharedAVLTreeIterator< Val, TreeCmp >::operator==(from);
752 }
753
755 template < typename Val, typename Priority, typename Cmp >
756 INLINE bool SortedPriorityQueueReverseIterator< Val, Priority, Cmp >::operator!=(
757 const SortedPriorityQueueReverseIterator< Val, Priority, Cmp >& from) const {
758 return !operator==(from);
759 }
760
762 template < typename Val, typename Priority, typename Cmp >
763 INLINE SortedPriorityQueueReverseIterator< Val, Priority, Cmp >&
764 SortedPriorityQueueReverseIterator< Val, Priority, Cmp >::operator++() noexcept {
765 SharedAVLTreeIterator< Val, TreeCmp >::operator++();
766 return *this;
767 }
768
770 template < typename Val, typename Priority, typename Cmp >
771 INLINE SortedPriorityQueueReverseIterator< Val, Priority, Cmp >&
772 SortedPriorityQueueReverseIterator< Val, Priority, Cmp >::operator+=(const Size k) noexcept {
773 SharedAVLTreeIterator< Val, TreeCmp >::operator+=(k);
774 return *this;
775 }
776
778 template < typename Val, typename Priority, typename Cmp >
779 INLINE SortedPriorityQueueReverseIterator< Val, Priority, Cmp >&
780 SortedPriorityQueueReverseIterator< Val, Priority, Cmp >::operator--() noexcept {
781 SharedAVLTreeIterator< Val, TreeCmp >::operator--();
782 return *this;
783 }
784
786 template < typename Val, typename Priority, typename Cmp >
787 INLINE SortedPriorityQueueReverseIterator< Val, Priority, Cmp >&
788 SortedPriorityQueueReverseIterator< Val, Priority, Cmp >::operator-=(const Size k) noexcept {
789 SharedAVLTreeIterator< Val, TreeCmp >::operator-=(k);
790 return *this;
791 }
792
794 template < typename Val, typename Priority, typename Cmp >
795 INLINE typename SortedPriorityQueueReverseIterator< Val, Priority, Cmp >::const_reference
796 SortedPriorityQueueReverseIterator< Val, Priority, Cmp >::operator*() const {
797 return SharedAVLTreeIterator< Val, TreeCmp >::operator*().value;
798 }
799
801 template < typename Val, typename Priority, typename Cmp >
802 INLINE typename SortedPriorityQueueReverseIterator< Val, Priority, Cmp >::const_pointer
803 SortedPriorityQueueReverseIterator< Val, Priority, Cmp >::operator->() const {
804 auto node = SharedAVLTreeIterator< Val, TreeCmp >::operator->();
805 if (node != nullptr) return &(node->value);
806 else { GUM_ERROR(NotFound, "The sorted priority queue iterator does not point on any value") }
807 }
808
810
812 template < typename Val, typename Priority, typename Cmp >
813 INLINE SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >::
814 SortedPriorityQueueReverseIteratorSafe(SortedPriorityQueue< Val, Priority, Cmp >& queue,
815 const bool rbegin) :
816 SharedAVLTreeIteratorSafe< Val, TreeCmp >(queue._tree_, rbegin) {
817 GUM_CONSTRUCTOR(SortedPriorityQueueReverseIteratorSafe)
818 }
819
821 template < typename Val, typename Priority, typename Cmp >
822 INLINE SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >::
823 SortedPriorityQueueReverseIteratorSafe(
824 const SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >& from) :
825 SharedAVLTreeIteratorSafe< Val, TreeCmp >(from) {
826 GUM_CONS_CPY(SortedPriorityQueueReverseIteratorSafe)
827 }
828
830 template < typename Val, typename Priority, typename Cmp >
831 INLINE SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >::
832 SortedPriorityQueueReverseIteratorSafe(
833 SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >&& from) :
834 SharedAVLTreeIteratorSafe< Val, TreeCmp >(std::move(from)) {
835 GUM_CONS_MOV(SortedPriorityQueueReverseIteratorSafe)
836 }
837
839 template < typename Val, typename Priority, typename Cmp >
840 INLINE SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >::
841 ~SortedPriorityQueueReverseIteratorSafe() noexcept {
842 GUM_DESTRUCTOR(SortedPriorityQueueReverseIteratorSafe)
843 }
844
846 template < typename Val, typename Priority, typename Cmp >
847 INLINE SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >&
848 SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >::operator=(
849 const SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >& from) {
850 SharedAVLTreeIteratorSafe< Val, TreeCmp >::operator=(from);
851 return *this;
852 }
853
855 template < typename Val, typename Priority, typename Cmp >
856 INLINE SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >&
857 SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >::operator=(
858 SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >&& from) {
859 SharedAVLTreeIteratorSafe< Val, TreeCmp >::operator=(std::move(from));
860 return *this;
861 }
862
864 template < typename Val, typename Priority, typename Cmp >
865 INLINE bool SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >::operator==(
866 const SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >& from) const {
867 return SharedAVLTreeIteratorSafe< Val, TreeCmp >::operator==(from);
868 }
869
871 template < typename Val, typename Priority, typename Cmp >
872 INLINE bool SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >::operator!=(
873 const SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >& from) const {
874 return !operator==(from);
875 }
876
878 template < typename Val, typename Priority, typename Cmp >
879 INLINE SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >&
880 SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >::operator++() noexcept {
881 SharedAVLTreeIteratorSafe< Val, TreeCmp >::operator++();
882 return *this;
883 }
884
886 template < typename Val, typename Priority, typename Cmp >
887 INLINE SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >&
888 SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >::operator+=(
889 const Size k) noexcept {
890 SharedAVLTreeIteratorSafe< Val, TreeCmp >::operator+=(k);
891 return *this;
892 }
893
895 template < typename Val, typename Priority, typename Cmp >
896 INLINE SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >&
897 SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >::operator--() noexcept {
898 SharedAVLTreeIteratorSafe< Val, TreeCmp >::operator--();
899 return *this;
900 }
901
903 template < typename Val, typename Priority, typename Cmp >
904 INLINE SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >&
905 SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >::operator-=(
906 const Size k) noexcept {
907 SharedAVLTreeIteratorSafe< Val, TreeCmp >::operator-=(k);
908 return *this;
909 }
910
912 template < typename Val, typename Priority, typename Cmp >
913 INLINE typename SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >::const_reference
914 SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >::operator*() const {
915 return SharedAVLTreeIteratorSafe< Val, TreeCmp >::operator*().value;
916 }
917
919 template < typename Val, typename Priority, typename Cmp >
920 INLINE typename SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >::const_pointer
921 SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >::operator->() const {
922 auto node = SharedAVLTreeIteratorSafe< Val, TreeCmp >::operator->();
923 if (node != nullptr) return &(node->value);
924 else { GUM_ERROR(NotFound, "The sorted priority queue iterator does not point on any value") }
925 }
926
927
928} // namespace gum
929
930#endif // DOXYGEN_SHOULD_SKIP_THIS
NotFound
Exception : the element we looked for cannot be found.
gum::SortedPriorityQueue::SortedPriorityQueue
SortedPriorityQueue(Cmp compare=Cmp(), Size capacity=GUM_PRIORITY_QUEUE_DEFAULT_CAPACITY)
Basic constructor.
GUM_ERROR
#define GUM_ERROR(type, msg)
Definition exceptions.h:72
gum::Size
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition types.h:74
gum
gum is the global namespace for all aGrUM entities
Definition agrum.h:46
std
STL namespace.
sortedPriorityQueue.h
Priority queues which can be parsed using iterators.
operator==
bool operator==(const TiXmlString &a, const TiXmlString &b)
Definition tinystr.h:243
aGrUM 2.3.2

© PHW&CG&others - 2022
DoXyGeN 1.16.1