aGrUM 2.3.2
a C++ library for (probabilistic) graphical models
sharedAVLTree_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 <functional>
44#include <sstream>
45#include <utility>
46
47#include <agrum/base/core/exceptions.h>
48#include <agrum/base/core/sharedAVLTree.h>
49
50#include <type_traits>
51
52#ifndef DOXYGEN_SHOULD_SKIP_THIS
53
54namespace gum {
55
57 template < typename Val, typename Cmp >
58 INLINE SharedAVLTree< Val, Cmp >::SharedAVLTree(const Cmp& compare) :
59 AVLTree< Val, Cmp >(compare) {
60 this->owns_nodes_ = false;
61
62 // for debugging purposes
63 GUM_CONSTRUCTOR(SharedAVLTree);
64 }
65
67 template < typename Val, typename Cmp >
68 INLINE SharedAVLTree< Val, Cmp >::SharedAVLTree(SharedAVLTree< Val, Cmp >&& from) noexcept :
69 AVLTree< Val, Cmp >(std::move(from)) {
70 // for debugging purposes
71 GUM_CONS_MOV(SharedAVLTree);
72 }
73
75 template < typename Val, typename Cmp >
76 INLINE SharedAVLTree< Val, Cmp >::~SharedAVLTree() {
77 // for debugging purposes
78 GUM_DESTRUCTOR(SharedAVLTree);
79 }
80
82 template < typename Val, typename Cmp >
83 INLINE SharedAVLTree< Val, Cmp >&
84 SharedAVLTree< Val, Cmp >::operator=(SharedAVLTree< Val, Cmp >&& from) {
85 operator=(std::move(from));
86 return *this;
87 }
88
90 template < typename Val, typename Cmp >
91 INLINE typename SharedAVLTree< Val, Cmp >::AVLNode*
92 SharedAVLTree< Val, Cmp >::highestNode() const noexcept {
93 return this->highest_node_;
94 }
95
97 template < typename Val, typename Cmp >
98 INLINE typename SharedAVLTree< Val, Cmp >::AVLNode*
99 SharedAVLTree< Val, Cmp >::lowestNode() const noexcept {
100 return this->lowest_node_;
101 }
102
104 template < typename Val, typename Cmp >
105 INLINE void SharedAVLTree< Val, Cmp >::insert(AVLNode* node) {
106 // the insert_ method will update the parent of node, but we should also
107 // guarantee that the children are null pointers before the insertion (as the
108 // node will be added to the
109 node->left_child = nullptr;
110 node->right_child = nullptr;
111 this->insert_(node);
112 }
113
115 template < typename Val, typename Cmp >
116 INLINE void SharedAVLTree< Val, Cmp >::erase(AVLNode* node) {
117 this->removeNodeFromTree_(node);
118 }
119
121 template < typename Val, typename Cmp >
122 INLINE void SharedAVLTree< Val, Cmp >::erase(iterator_safe& iter) {
123 this->removeNodeFromTree_(iter.node_);
124 }
125
127 template < typename Val, typename Cmp >
128 INLINE void SharedAVLTree< Val, Cmp >::erase(reverse_iterator_safe& iter) {
129 this->removeNodeFromTree_(iter.node_);
130 }
131
133 template < typename Val, typename Cmp >
134 INLINE typename SharedAVLTree< Val, Cmp >::iterator SharedAVLTree< Val, Cmp >::begin() const {
135 return SharedAVLTreeIterator(*this);
136 }
137
139 template < typename Val, typename Cmp >
140 constexpr const typename SharedAVLTree< Val, Cmp >::iterator&
141 SharedAVLTree< Val, Cmp >::end() const {
142 return *(reinterpret_cast< const iterator* >(_SharedAVLTree_end_));
143 }
144
146 template < typename Val, typename Cmp >
147 INLINE typename SharedAVLTree< Val, Cmp >::reverse_iterator
148 SharedAVLTree< Val, Cmp >::rbegin() const {
149 return SharedAVLTreeReverseIterator(*this, true);
150 }
151
153 template < typename Val, typename Cmp >
154 constexpr const typename SharedAVLTree< Val, Cmp >::reverse_iterator&
155 SharedAVLTree< Val, Cmp >::rend() const {
156 return *(reinterpret_cast< const reverse_iterator* >(_SharedAVLTree_rend_));
157 }
158
160 template < typename Val, typename Cmp >
161 INLINE typename SharedAVLTree< Val, Cmp >::iterator_safe SharedAVLTree< Val, Cmp >::beginSafe() {
162 return SharedAVLTreeIteratorSafe(*this);
163 }
164
166 template < typename Val, typename Cmp >
167 constexpr const typename SharedAVLTree< Val, Cmp >::iterator_safe&
168 SharedAVLTree< Val, Cmp >::endSafe() const {
169 return *(reinterpret_cast< const iterator_safe* >(_SharedAVLTree_end_safe_));
170 }
171
173 template < typename Val, typename Cmp >
174 INLINE typename SharedAVLTree< Val, Cmp >::reverse_iterator_safe
175 SharedAVLTree< Val, Cmp >::rbeginSafe() {
176 return SharedAVLTreeReverseIteratorSafe(*this, true);
177 }
178
180 template < typename Val, typename Cmp >
181 constexpr const typename SharedAVLTree< Val, Cmp >::reverse_iterator_safe&
182 SharedAVLTree< Val, Cmp >::rendSafe() const {
183 return *(reinterpret_cast< const reverse_iterator_safe* >(_SharedAVLTree_rend_safe_));
184 }
185
187
189 template < typename Val, typename Cmp >
190 INLINE SharedAVLTreeIterator< Val, Cmp >::SharedAVLTreeIterator(
191 const SharedAVLTree< Val, Cmp >& tree,
192 const bool begin) noexcept : AVLTreeIterator< Val, Cmp >(tree, begin) {
193 GUM_CONSTRUCTOR(SharedAVLTreeIterator)
194 }
195
197 template < typename Val, typename Cmp >
198 INLINE SharedAVLTreeIterator< Val, Cmp >::SharedAVLTreeIterator(
199 const SharedAVLTreeIterator< Val, Cmp >& from) noexcept : AVLTreeIterator< Val, Cmp >(from) {
200 GUM_CONS_CPY(SharedAVLTreeIterator)
201 }
202
204 template < typename Val, typename Cmp >
205 INLINE SharedAVLTreeIterator< Val, Cmp >::SharedAVLTreeIterator(
206 SharedAVLTreeIterator< Val, Cmp >&& from) noexcept :
207 AVLTreeIterator< Val, Cmp >(std::move(from)) {
208 GUM_CONS_MOV(SharedAVLTreeIterator)
209 }
210
212 template < typename Val, typename Cmp >
213 INLINE SharedAVLTreeIterator< Val, Cmp >::~SharedAVLTreeIterator() noexcept {
214 GUM_DESTRUCTOR(SharedAVLTreeIterator)
215 }
216
218 template < typename Val, typename Cmp >
219 INLINE SharedAVLTreeIterator< Val, Cmp >& SharedAVLTreeIterator< Val, Cmp >::operator=(
220 const SharedAVLTreeIterator< Val, Cmp >& from) noexcept {
221 AVLTreeIterator< Val, Cmp >::operator=(from);
222 return *this;
223 }
224
226 template < typename Val, typename Cmp >
227 INLINE SharedAVLTreeIterator< Val, Cmp >& SharedAVLTreeIterator< Val, Cmp >::operator=(
228 SharedAVLTreeIterator< Val, Cmp >&& from) noexcept {
229 AVLTreeIterator< Val, Cmp >::operator=(std::move(from));
230 return *this;
231 }
232
234 template < typename Val, typename Cmp >
235 INLINE bool SharedAVLTreeIterator< Val, Cmp >::operator==(
236 const SharedAVLTreeIterator< Val, Cmp >& from) const {
237 return AVLTreeIterator< Val, Cmp >::operator==(from);
238 }
239
241 template < typename Val, typename Cmp >
242 INLINE bool SharedAVLTreeIterator< Val, Cmp >::operator!=(
243 const SharedAVLTreeIterator< Val, Cmp >& from) const {
244 return !SharedAVLTreeIterator< Val, Cmp >::operator==(from);
245 }
246
248 template < typename Val, typename Cmp >
249 INLINE SharedAVLTreeIterator< Val, Cmp >&
250 SharedAVLTreeIterator< Val, Cmp >::operator++() noexcept {
251 AVLTreeIterator< Val, Cmp >::operator++();
252 return *this;
253 }
254
256 template < typename Val, typename Cmp >
257 INLINE SharedAVLTreeIterator< Val, Cmp >&
258 SharedAVLTreeIterator< Val, Cmp >::operator+=(const Size k) noexcept {
259 AVLTreeIterator< Val, Cmp >::operator+=(k);
260 return *this;
261 }
262
264 template < typename Val, typename Cmp >
265 INLINE SharedAVLTreeIterator< Val, Cmp >&
266 SharedAVLTreeIterator< Val, Cmp >::operator--() noexcept {
267 AVLTreeIterator< Val, Cmp >::operator--();
268 return *this;
269 }
270
272 template < typename Val, typename Cmp >
273 INLINE SharedAVLTreeIterator< Val, Cmp >&
274 SharedAVLTreeIterator< Val, Cmp >::operator-=(const Size k) noexcept {
275 AVLTreeIterator< Val, Cmp >::operator-=(k);
276 return *this;
277 }
278
280 template < typename Val, typename Cmp >
281 INLINE typename SharedAVLTreeIterator< Val, Cmp >::const_reference
282 SharedAVLTreeIterator< Val, Cmp >::operator*() const {
283 if (this->node_ != nullptr) return *(this->node_);
284 else {
285 if ((this->next_node_ == nullptr) || (this->preceding_node_ == nullptr)) {
286 GUM_ERROR(NotFound, "an end SharedAVLTree iterator does not contain any value")
287 } else {
288 GUM_ERROR(NotFound, "the SharedAVLTree iterator points to an erased value")
289 }
290 }
291 }
292
294 template < typename Val, typename Cmp >
295 INLINE typename SharedAVLTreeIterator< Val, Cmp >::const_pointer
296 SharedAVLTreeIterator< Val, Cmp >::operator->() const {
297 return this->node_;
298 }
299
301
303 template < typename Val, typename Cmp >
304 INLINE SharedAVLTreeIteratorSafe< Val, Cmp >::SharedAVLTreeIteratorSafe(
305 SharedAVLTree< Val, Cmp >& tree,
306 const bool rbegin) : AVLTreeIteratorSafe< Val, Cmp >(tree, rbegin) {
307 GUM_CONSTRUCTOR(SharedAVLTreeIteratorSafe)
308 }
309
311 template < typename Val, typename Cmp >
312 INLINE SharedAVLTreeIteratorSafe< Val, Cmp >::SharedAVLTreeIteratorSafe(
313 const SharedAVLTreeIteratorSafe< Val, Cmp >& from) : AVLTreeIteratorSafe< Val, Cmp >(from) {
314 GUM_CONS_CPY(SharedAVLTreeIteratorSafe)
315 }
316
318 template < typename Val, typename Cmp >
319 INLINE SharedAVLTreeIteratorSafe< Val, Cmp >::SharedAVLTreeIteratorSafe(
320 SharedAVLTreeIteratorSafe< Val, Cmp >&& from) :
321 AVLTreeIteratorSafe< Val, Cmp >(std::move(from)) {
322 GUM_CONS_CPY(SharedAVLTreeIteratorSafe)
323 }
324
326 template < typename Val, typename Cmp >
327 INLINE SharedAVLTreeIteratorSafe< Val, Cmp >::~SharedAVLTreeIteratorSafe() noexcept {
328 GUM_DESTRUCTOR(SharedAVLTreeIteratorSafe)
329 }
330
332 template < typename Val, typename Cmp >
333 INLINE SharedAVLTreeIteratorSafe< Val, Cmp >& SharedAVLTreeIteratorSafe< Val, Cmp >::operator=(
334 const SharedAVLTreeIteratorSafe< Val, Cmp >& from) {
335 AVLTreeIteratorSafe< Val, Cmp >::operator=(from);
336 return *this;
337 }
338
340 template < typename Val, typename Cmp >
341 INLINE SharedAVLTreeIteratorSafe< Val, Cmp >& SharedAVLTreeIteratorSafe< Val, Cmp >::operator=(
342 SharedAVLTreeIteratorSafe< Val, Cmp >&& from) {
343 AVLTreeIteratorSafe< Val, Cmp >::operator=(std::move(from));
344 return *this;
345 }
346
348 template < typename Val, typename Cmp >
349 INLINE bool SharedAVLTreeIteratorSafe< Val, Cmp >::operator==(
350 const SharedAVLTreeIteratorSafe< Val, Cmp >& from) const {
351 return AVLTreeIteratorSafe< Val, Cmp >::operator==(from);
352 }
353
355 template < typename Val, typename Cmp >
356 INLINE bool SharedAVLTreeIteratorSafe< Val, Cmp >::operator!=(
357 const SharedAVLTreeIteratorSafe< Val, Cmp >& from) const {
358 return !SharedAVLTreeIteratorSafe< Val, Cmp >::operator==(from);
359 }
360
362 template < typename Val, typename Cmp >
363 INLINE SharedAVLTreeIteratorSafe< Val, Cmp >&
364 SharedAVLTreeIteratorSafe< Val, Cmp >::operator++() noexcept {
365 AVLTreeIteratorSafe< Val, Cmp >::operator++();
366 return *this;
367 }
368
370 template < typename Val, typename Cmp >
371 INLINE SharedAVLTreeIteratorSafe< Val, Cmp >&
372 SharedAVLTreeIteratorSafe< Val, Cmp >::operator+=(const Size k) noexcept {
373 AVLTreeIteratorSafe< Val, Cmp >::operator+=(k);
374 return *this;
375 }
376
378 template < typename Val, typename Cmp >
379 INLINE SharedAVLTreeIteratorSafe< Val, Cmp >&
380 SharedAVLTreeIteratorSafe< Val, Cmp >::operator--() noexcept {
381 AVLTreeIteratorSafe< Val, Cmp >::operator--();
382 return *this;
383 }
384
386 template < typename Val, typename Cmp >
387 INLINE SharedAVLTreeIteratorSafe< Val, Cmp >&
388 SharedAVLTreeIteratorSafe< Val, Cmp >::operator-=(const Size k) noexcept {
389 AVLTreeIteratorSafe< Val, Cmp >::operator-=(k);
390 return *this;
391 }
392
394 template < typename Val, typename Cmp >
395 INLINE typename SharedAVLTreeIteratorSafe< Val, Cmp >::const_reference
396 SharedAVLTreeIteratorSafe< Val, Cmp >::operator*() const {
397 if (this->node_ != nullptr) return *(this->node_);
398 else {
399 if ((this->next_node_ == nullptr) || (this->preceding_node_ == nullptr)) {
400 GUM_ERROR(NotFound, "an end SharedAVLTree iterator does not contain any value")
401 } else {
402 GUM_ERROR(NotFound, "the SharedAVLTree iterator points to an erased value")
403 }
404 }
405 }
406
408 template < typename Val, typename Cmp >
409 INLINE typename SharedAVLTreeIteratorSafe< Val, Cmp >::const_pointer
410 SharedAVLTreeIteratorSafe< Val, Cmp >::operator->() const {
411 return this->node_;
412 }
413
415
417 template < typename Val, typename Cmp >
418 INLINE SharedAVLTreeReverseIterator< Val, Cmp >::SharedAVLTreeReverseIterator(
419 const SharedAVLTree< Val, Cmp >& tree,
420 const bool rbegin) noexcept : SharedAVLTreeIterator< Val, Cmp >(tree, !rbegin) {
421 GUM_CONSTRUCTOR(SharedAVLTreeReverseIterator)
422 }
423
425 template < typename Val, typename Cmp >
426 INLINE SharedAVLTreeReverseIterator< Val, Cmp >::SharedAVLTreeReverseIterator(
427 const SharedAVLTreeReverseIterator< Val, Cmp >& from) noexcept :
428 SharedAVLTreeIterator< Val, Cmp >(from) {
429 GUM_CONS_CPY(SharedAVLTreeReverseIterator)
430 }
431
433 template < typename Val, typename Cmp >
434 INLINE SharedAVLTreeReverseIterator< Val, Cmp >::SharedAVLTreeReverseIterator(
435 SharedAVLTreeReverseIterator< Val, Cmp >&& from) noexcept :
436 SharedAVLTreeIterator< Val, Cmp >(std::move(from)) {
437 GUM_CONS_CPY(SharedAVLTreeReverseIterator)
438 }
439
441 template < typename Val, typename Cmp >
442 INLINE SharedAVLTreeReverseIterator< Val, Cmp >::~SharedAVLTreeReverseIterator() noexcept {
443 GUM_DESTRUCTOR(SharedAVLTreeReverseIterator)
444 }
445
447 template < typename Val, typename Cmp >
448 INLINE SharedAVLTreeReverseIterator< Val, Cmp >&
449 SharedAVLTreeReverseIterator< Val, Cmp >::operator=(
450 const SharedAVLTreeReverseIterator< Val, Cmp >& from) noexcept {
451 SharedAVLTreeIterator< Val, Cmp >::operator=(from);
452 return *this;
453 }
454
456 template < typename Val, typename Cmp >
457 INLINE SharedAVLTreeReverseIterator< Val, Cmp >&
458 SharedAVLTreeReverseIterator< Val, Cmp >::operator=(
459 SharedAVLTreeReverseIterator< Val, Cmp >&& from) noexcept {
460 SharedAVLTreeIterator< Val, Cmp >::operator=(std::move(from));
461 return *this;
462 }
463
465 template < typename Val, typename Cmp >
466 INLINE bool SharedAVLTreeReverseIterator< Val, Cmp >::operator==(
467 const SharedAVLTreeReverseIterator< Val, Cmp >& from) const {
468 // when node_ is different from nullptr, testing whether "this" is equal to from
469 // simply amounts to comparing their node_ fields. However, due to erasures in
470 // the tree, it may happen that two iterators pointing to different nodes have
471 // a nullptr node_ field. In this case, they will be equal if and only if their
472 // preceding_node_ fields are equal. Here, it is important to use the preceding_node_
473 // rather than their next_node_ field because the rend iterator has nullptr
474 // as the value of its next_node_ while a reverse iterator moving by ++ operators
475 // up to the end will not have this value for its next_node_. However, it
476 // will have a preceding_node_ equal to nullptr, exactly as the end iterator.
477 return (this->node_ == from.node_) && (this->preceding_node_ == from.preceding_node_);
478 }
479
481 template < typename Val, typename Cmp >
482 INLINE bool SharedAVLTreeReverseIterator< Val, Cmp >::operator!=(
483 const SharedAVLTreeReverseIterator< Val, Cmp >& from) const {
484 return !SharedAVLTreeReverseIterator< Val, Cmp >::operator==(from);
485 }
486
488 template < typename Val, typename Cmp >
489 INLINE SharedAVLTreeReverseIterator< Val, Cmp >&
490 SharedAVLTreeReverseIterator< Val, Cmp >::operator++() noexcept {
491 SharedAVLTreeIterator< Val, Cmp >::operator--();
492 return *this;
493 }
494
496 template < typename Val, typename Cmp >
497 INLINE SharedAVLTreeReverseIterator< Val, Cmp >&
498 SharedAVLTreeReverseIterator< Val, Cmp >::operator+=(const Size k) noexcept {
499 SharedAVLTreeIterator< Val, Cmp >::operator-=(k);
500 return *this;
501 }
502
504 template < typename Val, typename Cmp >
505 INLINE SharedAVLTreeReverseIterator< Val, Cmp >&
506 SharedAVLTreeReverseIterator< Val, Cmp >::operator--() noexcept {
507 SharedAVLTreeIterator< Val, Cmp >::operator++();
508 return *this;
509 }
510
512 template < typename Val, typename Cmp >
513 INLINE SharedAVLTreeReverseIterator< Val, Cmp >&
514 SharedAVLTreeReverseIterator< Val, Cmp >::operator-=(const Size k) noexcept {
515 SharedAVLTreeIterator< Val, Cmp >::operator+=(k);
516 return *this;
517 }
518
520
522 template < typename Val, typename Cmp >
523 INLINE SharedAVLTreeReverseIteratorSafe< Val, Cmp >::SharedAVLTreeReverseIteratorSafe(
524 SharedAVLTree< Val, Cmp >& tree,
525 const bool rbegin) : SharedAVLTreeIteratorSafe< Val, Cmp >(tree, !rbegin) {
526 GUM_CONSTRUCTOR(SharedAVLTreeReverseIteratorSafe)
527 }
528
530 template < typename Val, typename Cmp >
531 INLINE SharedAVLTreeReverseIteratorSafe< Val, Cmp >::SharedAVLTreeReverseIteratorSafe(
532 const SharedAVLTreeReverseIteratorSafe< Val, Cmp >& from) :
533 SharedAVLTreeIteratorSafe< Val, Cmp >(from) {
534 GUM_CONS_CPY(SharedAVLTreeReverseIteratorSafe)
535 }
536
538 template < typename Val, typename Cmp >
539 INLINE SharedAVLTreeReverseIteratorSafe< Val, Cmp >::SharedAVLTreeReverseIteratorSafe(
540 SharedAVLTreeReverseIteratorSafe< Val, Cmp >&& from) :
541 SharedAVLTreeIteratorSafe< Val, Cmp >(std::move(from)) {
542 GUM_CONS_MOV(SharedAVLTreeReverseIteratorSafe)
543 }
544
546 template < typename Val, typename Cmp >
547 INLINE
548 SharedAVLTreeReverseIteratorSafe< Val, Cmp >::~SharedAVLTreeReverseIteratorSafe() noexcept {
549 GUM_DESTRUCTOR(SharedAVLTreeReverseIteratorSafe)
550 }
551
553 template < typename Val, typename Cmp >
554 INLINE SharedAVLTreeReverseIteratorSafe< Val, Cmp >&
555 SharedAVLTreeReverseIteratorSafe< Val, Cmp >::operator=(
556 const SharedAVLTreeReverseIteratorSafe< Val, Cmp >& from) {
557 SharedAVLTreeIteratorSafe< Val, Cmp >::operator=(from);
558 return *this;
559 }
560
562 template < typename Val, typename Cmp >
563 INLINE SharedAVLTreeReverseIteratorSafe< Val, Cmp >&
564 SharedAVLTreeReverseIteratorSafe< Val, Cmp >::operator=(
565 SharedAVLTreeReverseIteratorSafe< Val, Cmp >&& from) {
566 SharedAVLTreeIteratorSafe< Val, Cmp >::operator=(std::move(from));
567 return *this;
568 }
569
571 template < typename Val, typename Cmp >
572 INLINE bool SharedAVLTreeReverseIteratorSafe< Val, Cmp >::operator==(
573 const SharedAVLTreeReverseIteratorSafe< Val, Cmp >& from) const {
574 // when node_ is different from nullptr, testing whether "this" is equal to from
575 // simply amounts to comparing their node_ fields. However, due to erasures in
576 // the tree, it may happen that two iterators pointing to different nodes have
577 // a nullptr node_ field. In this case, they will be equal if and only if their
578 // preceding_node_ fields are equal. Here, it is important to use the preceding_node_
579 // rather than their next_node_ field because the rend iterator has nullptr
580 // as the value of its next_node_ while a reverse iterator moving by ++ operators
581 // up to the end will not have this value for its next_node_. However, it
582 // will have a preceding_node_ equal to nullptr, exactly as the end iterator.
583 return (this->node_ == from.node_) && (this->preceding_node_ == from.preceding_node_);
584 }
585
587 template < typename Val, typename Cmp >
588 INLINE bool SharedAVLTreeReverseIteratorSafe< Val, Cmp >::operator!=(
589 const SharedAVLTreeReverseIteratorSafe< Val, Cmp >& from) const {
590 return !SharedAVLTreeReverseIteratorSafe< Val, Cmp >::operator==(from);
591 }
592
594 template < typename Val, typename Cmp >
595 INLINE SharedAVLTreeReverseIteratorSafe< Val, Cmp >&
596 SharedAVLTreeReverseIteratorSafe< Val, Cmp >::operator++() noexcept {
597 SharedAVLTreeIteratorSafe< Val, Cmp >::operator--();
598 return *this;
599 }
600
602 template < typename Val, typename Cmp >
603 INLINE SharedAVLTreeReverseIteratorSafe< Val, Cmp >&
604 SharedAVLTreeReverseIteratorSafe< Val, Cmp >::operator+=(const Size k) noexcept {
605 SharedAVLTreeIteratorSafe< Val, Cmp >::operator-=(k);
606 return *this;
607 }
608
610 template < typename Val, typename Cmp >
611 INLINE SharedAVLTreeReverseIteratorSafe< Val, Cmp >&
612 SharedAVLTreeReverseIteratorSafe< Val, Cmp >::operator--() noexcept {
613 SharedAVLTreeIteratorSafe< Val, Cmp >::operator++();
614 return *this;
615 }
616
618 template < typename Val, typename Cmp >
619 INLINE SharedAVLTreeReverseIteratorSafe< Val, Cmp >&
620 SharedAVLTreeReverseIteratorSafe< Val, Cmp >::operator-=(const Size k) noexcept {
621 SharedAVLTreeIteratorSafe< Val, Cmp >::operator+=(k);
622 return *this;
623 }
624
625
626} // namespace gum
627
628#endif // DOXYGEN_SHOULD_SKIP_THIS
gum::AVLTree
AVL binary search tree.
Definition AVLTree.h:168
NotFound
Exception : the element we looked for cannot be found.
exceptions.h
aGrUM's exceptions
GUM_ERROR
#define GUM_ERROR(type, msg)
Definition exceptions.h:72
gum
gum is the global namespace for all aGrUM entities
Definition agrum.h:46
std
STL namespace.
sharedAVLTree.h
AVL binary search trees that do not possess their own nodes.
aGrUM 2.3.2

© PHW&CG&others - 2022
DoXyGeN 1.16.1