tlx
Loading...
Searching...
No Matches
loser_tree.hpp
Go to the documentation of this file.
1/*******************************************************************************
2 * tlx/container/loser_tree.hpp
3 *
4 * Many generic loser tree variants.
5 *
6 * Copied and modified from STXXL, see http://stxxl.org, which itself extracted
7 * it from MCSTL http://algo2.iti.uni-karlsruhe.de/singler/mcstl/. Both are
8 * distributed under the Boost Software License, Version 1.0.
9 *
10 * Part of tlx - http://panthema.net/tlx
11 *
12 * Copyright (C) 2007 Johannes Singler <singler@ira.uka.de>
13 * Copyright (C) 2014-2017 Timo Bingmann <tb@panthema.net>
14 * Copyright (C) 2015 Huyen Chau Nguyen <hello@chau-nguyen.de>
15 *
16 * All rights reserved. Published under the Boost Software License, Version 1.0
17 ******************************************************************************/
18
19#ifndef TLX_CONTAINER_LOSER_TREE_HEADER
20#define TLX_CONTAINER_LOSER_TREE_HEADER
21
22#include <algorithm>
23#include <cassert>
24#include <cstdint>
25#include <functional>
26#include <utility>
27
29#include <tlx/define/likely.hpp>
31#include <tlx/unused.hpp>
32
33namespace tlx {
34
35//! \addtogroup tlx_container
36//! \{
37//! \defgroup tlx_container_loser_tree Loser Trees
38//! Loser/Tournament tree variants
39//! \{
40
41/*!
42 * Guarded loser tree/tournament tree, either copying the whole element into the
43 * tree structure, or looking up the element via the index.
44 *
45 * This is a base class for the LoserTreeCopy<true> and <false> classes.
46 *
47 * Guarding is done explicitly through one flag sup per element, inf is not
48 * needed due to a better initialization routine. This is a well-performing
49 * variant.
50 *
51 * \tparam ValueType the element type
52 * \tparam Comparator comparator to use for binary comparisons.
53 */
54template <typename ValueType, typename Comparator = std::less<ValueType> >
56{
57public:
58 //! size of counters and array indexes
59 using Source = std::uint32_t;
60
61 //! sentinel for invalid or finished Sources
62 static constexpr Source invalid_ = Source(-1);
63
64protected:
65 //! Internal representation of a loser tree player/node
66 struct Loser {
67 //! flag, true iff is a virtual maximum sentinel
68 bool sup;
69 //! index of source
71 //! copy of key value of the element in this node
72 ValueType key;
73 };
74
75 //! number of nodes
76 const Source ik_;
77 //! log_2(ik) next greater power of 2
78 const Source k_;
79 //! array containing loser tree nodes -- avoid default-constructing
80 //! losers[].key
82 //! the comparator object
83 Comparator cmp_;
84 //! still have to construct keys
86
87public:
88 explicit LoserTreeCopyBase(const Source& k,
89 const Comparator& cmp = Comparator())
91 losers_(2 * k_), cmp_(cmp), first_insert_(true) {
92
93 for (Source i = ik_ - 1; i < k_; ++i) {
94 losers_[i + k_].sup = true;
95 losers_[i + k_].source = invalid_;
96 }
97 }
98
99 //! return the index of the player with the smallest element.
100 Source min_source() { return losers_[0].source; }
101
102 /*!
103 * Initializes the player source with the element key.
104 *
105 * \param keyp the element to insert
106 * \param source index of the player
107 * \param sup flag that determines whether the value to insert is an
108 * explicit supremum sentinel.
109 */
110 void insert_start(const ValueType* keyp, const Source& source, bool sup) {
111 Source pos = k_ + source;
112
113 assert(pos < losers_.size());
114 assert(sup == (keyp == nullptr));
115
116 losers_[pos].sup = sup;
117 losers_[pos].source = source;
118
120 // copy construct all keys from this first key
121 for (Source i = 0; i < 2 * k_; ++i) {
122 if (keyp)
123 losers_[i].key = *keyp;
124 else
125 losers_[i].key = ValueType();
126 }
127 first_insert_ = false;
128 }
129 else {
130 losers_[pos].key = keyp ? *keyp : ValueType();
131 }
132 }
133
134 /*!
135 * Computes the winner of the competition at player root. Called
136 * recursively (starting at 0) to build the initial tree.
137 *
138 * \param root index of the game to start.
139 */
140 Source init_winner(const Source& root) {
141 if (root >= k_)
142 return root;
143
144 Source left = init_winner(2 * root);
145 Source right = init_winner(2 * root + 1);
146 if (losers_[right].sup ||
147 (!losers_[left].sup &&
148 !cmp_(losers_[right].key, losers_[left].key))) {
149 // left one is less or equal
150 losers_[root] = losers_[right];
151 return left;
152 }
153 else {
154 // right one is less
155 losers_[root] = losers_[left];
156 return right;
157 }
158 }
159
160 void init() {
161 if (TLX_UNLIKELY(k_ == 0))
162 return;
163 losers_[0] = losers_[init_winner(1)];
164 }
165};
166
167/*!
168 * Guarded loser tree/tournament tree, either copying the whole element into the
169 * tree structure, or looking up the element via the index.
170 *
171 * Unstable specialization of LoserTreeCopyBase.
172 *
173 * Guarding is done explicitly through one flag sup per element, inf is not
174 * needed due to a better initialization routine. This is a well-performing
175 * variant.
176 *
177 * \tparam ValueType the element type
178 * \tparam Comparator comparator to use for binary comparisons.
179 */
180template <bool Stable /* == false */, typename ValueType,
181 typename Comparator = std::less<ValueType> >
182class LoserTreeCopy : public LoserTreeCopyBase<ValueType, Comparator>
183{
184public:
186 using Source = typename Super::Source;
187
188protected:
189 using Super::k_;
190 using Super::losers_;
191 using Super::cmp_;
192
193public:
194 explicit LoserTreeCopy(const Source& k,
195 const Comparator& cmp = Comparator())
196 : Super(k, cmp) { }
197
198 // do not pass const reference since key will be used as local variable
199 void delete_min_insert(const ValueType* keyp, bool sup) {
200 using std::swap;
201 assert(sup == (keyp == nullptr));
202
203 Source source = losers_[0].source;
204 ValueType key = keyp ? *keyp : ValueType();
205 Source pos = (k_ + source) / 2;
206
207 while (pos > 0) {
208 if (TLX_UNLIKELY(sup)) {
209 // the other candidate is smaller
210 swap(losers_[pos].sup, sup);
211 swap(losers_[pos].source, source);
212 swap(losers_[pos].key, key);
213 }
214 else if (TLX_UNLIKELY(losers_[pos].sup)) {
215 // this candidate is smaller
216 }
217 else if (cmp_(losers_[pos].key, key)) {
218 // the other one is smaller
219 swap(losers_[pos].source, source);
220 swap(losers_[pos].key, key);
221 }
222 else {
223 // this candidate is smaller
224 }
225 pos /= 2;
226 }
227
228 losers_[0].sup = sup;
229 losers_[0].source = source;
230 losers_[0].key = key;
231 }
232};
233
234/*!
235 * Guarded loser tree/tournament tree, either copying the whole element into the
236 * tree structure, or looking up the element via the index.
237 *
238 * Stable specialization of LoserTreeCopyBase.
239 *
240 * Guarding is done explicitly through one flag sup per element, inf is not
241 * needed due to a better initialization routine. This is a well-performing
242 * variant.
243 *
244 * \tparam ValueType the element type
245 * \tparam Comparator comparator to use for binary comparisons.
246 */
247template <typename ValueType, typename Comparator>
248class LoserTreeCopy</* Stable == */ true, ValueType, Comparator>
249 : public LoserTreeCopyBase<ValueType, Comparator>
250{
251public:
253 using Source = typename Super::Source;
254
255protected:
256 using Super::k_;
257 using Super::losers_;
258 using Super::cmp_;
259
260public:
261 explicit LoserTreeCopy(const Source& k,
262 const Comparator& cmp = Comparator())
263 : Super(k, cmp) { }
264
265 // do not pass const reference since key will be used as local variable
266 void delete_min_insert(const ValueType* keyp, bool sup) {
267 using std::swap;
268 assert(sup == (keyp == nullptr));
269
270 Source source = losers_[0].source;
271 ValueType key = keyp ? *keyp : ValueType();
272 Source pos = (k_ + source) / 2;
273
274 while (pos > 0) {
275 if ((TLX_UNLIKELY(sup) && (
276 !TLX_UNLIKELY(losers_[pos].sup) ||
277 losers_[pos].source < source)) ||
278 (!TLX_UNLIKELY(sup) && !TLX_UNLIKELY(losers_[pos].sup) &&
279 ((cmp_(losers_[pos].key, key)) ||
280 (!cmp_(key, losers_[pos].key) &&
281 losers_[pos].source < source)))) {
282 // the other one is smaller
283 swap(losers_[pos].sup, sup);
284 swap(losers_[pos].source, source);
285 swap(losers_[pos].key, key);
286 }
287 pos /= 2;
288 }
289
290 losers_[0].sup = sup;
291 losers_[0].source = source;
292 losers_[0].key = key;
293 }
294};
295
296/*!
297 * Guarded loser tree, using pointers to the elements instead of copying them
298 * into the tree nodes.
299 *
300 * This is a base class for the LoserTreePointer<true> and <false> classes.
301 *
302 * Guarding is done explicitly through one flag sup per element, inf is not
303 * needed due to a better initialization routine. This is a well-performing
304 * variant.
305 */
306template <typename ValueType, typename Comparator = std::less<ValueType> >
308{
309public:
310 //! size of counters and array indexes
311 using Source = std::uint32_t;
312
313 //! sentinel for invalid or finished Sources
314 static constexpr Source invalid_ = Source(-1);
315
316protected:
317 //! Internal representation of a loser tree player/node
318 struct Loser {
319 //! index of source
321 //! pointer to key value of the element in this node
322 const ValueType* keyp;
323 };
324
325 //! number of nodes
326 const Source ik_;
327 //! log_2(ik) next greater power of 2
328 const Source k_;
329 //! array containing loser tree nodes
331 //! the comparator object
332 Comparator cmp_;
333
334public:
336 Source k, const Comparator& cmp = Comparator())
338 cmp_(cmp) {
339 for (Source i = ik_ - 1; i < k_; i++) {
340 losers_[i + k_].keyp = nullptr;
341 losers_[i + k_].source = invalid_;
342 }
343 }
344
349
350 //! return the index of the player with the smallest element.
352 return losers_[0].keyp ? losers_[0].source : invalid_;
353 }
354
355 /*!
356 * Initializes the player source with the element key.
357 *
358 * \param keyp the element to insert
359 * \param source index of the player
360 * \param sup flag that determines whether the value to insert is an
361 * explicit supremum sentinel.
362 */
363 void insert_start(const ValueType* keyp, const Source& source, bool sup) {
364 Source pos = k_ + source;
365
366 assert(pos < losers_.size());
367 assert(sup == (keyp == nullptr));
368 unused(sup);
369
370 losers_[pos].source = source;
371 losers_[pos].keyp = keyp;
372 }
373
374 /*!
375 * Computes the winner of the competition at player root. Called
376 * recursively (starting at 0) to build the initial tree.
377 *
378 * \param root index of the game to start.
379 */
380 Source init_winner(const Source& root) {
381 if (root >= k_)
382 return root;
383
384 Source left = init_winner(2 * root);
385 Source right = init_winner(2 * root + 1);
386 if (!losers_[right].keyp ||
387 (losers_[left].keyp &&
388 !cmp_(*losers_[right].keyp, *losers_[left].keyp))) {
389 // left one is less or equal
390 losers_[root] = losers_[right];
391 return left;
392 }
393 else {
394 // right one is less
395 losers_[root] = losers_[left];
396 return right;
397 }
398 }
399
400 void init() {
401 if (TLX_UNLIKELY(k_ == 0))
402 return;
403 losers_[0] = losers_[init_winner(1)];
404 }
405};
406
407/*!
408 * Guarded loser tree, using pointers to the elements instead of copying them
409 * into the tree nodes.
410 *
411 * Unstable specialization of LoserTreeCopyBase.
412 *
413 * Guarding is done explicitly through one flag sup per element, inf is not
414 * needed due to a better initialization routine. This is a well-performing
415 * variant.
416 */
417template <bool Stable /* == false */, typename ValueType,
418 typename Comparator = std::less<ValueType> >
419class LoserTreePointer : public LoserTreePointerBase<ValueType, Comparator>
420{
421public:
423 using Source = typename Super::Source;
424
425protected:
426 using Super::k_;
427 using Super::losers_;
428 using Super::cmp_;
429
430public:
431 explicit LoserTreePointer(Source k, const Comparator& cmp = Comparator())
432 : Super(k, cmp) { }
433
434 void delete_min_insert(const ValueType* keyp, bool sup) {
435 using std::swap;
436 assert(sup == (keyp == nullptr));
437 unused(sup);
438
439 Source source = losers_[0].source;
440 Source pos = (k_ + source) / 2;
441
442 while (pos > 0) {
443 if (TLX_UNLIKELY(!keyp)) {
444 // the other candidate is smaller
445 swap(losers_[pos].source, source);
446 swap(losers_[pos].keyp, keyp);
447 }
448 else if (TLX_UNLIKELY(!losers_[pos].keyp)) {
449 // this candidate is smaller
450 }
451 else if (cmp_(*losers_[pos].keyp, *keyp)) {
452 // the other one is smaller
453 swap(losers_[pos].source, source);
454 swap(losers_[pos].keyp, keyp);
455 }
456 else {
457 // this candidate is smaller
458 }
459 pos /= 2;
460 }
461
462 losers_[0].source = source;
463 losers_[0].keyp = keyp;
464 }
465};
466
467/*!
468 * Guarded loser tree, using pointers to the elements instead of copying them
469 * into the tree nodes.
470 *
471 * Unstable specialization of LoserTreeCopyBase.
472 *
473 * Guarding is done explicitly through one flag sup per element, inf is not
474 * needed due to a better initialization routine. This is a well-performing
475 * variant.
476 */
477template <typename ValueType, typename Comparator>
478class LoserTreePointer</* Stable == */ true, ValueType, Comparator>
479 : public LoserTreePointerBase<ValueType, Comparator>
480{
481public:
483 using Source = typename Super::Source;
484
485protected:
486 using Super::k_;
487 using Super::losers_;
488 using Super::cmp_;
489
490public:
491 explicit LoserTreePointer(Source k, const Comparator& cmp = Comparator())
492 : Super(k, cmp) { }
493
494 void delete_min_insert(const ValueType* keyp, bool sup) {
495 using std::swap;
496 assert(sup == (keyp == nullptr));
497 unused(sup);
498
499 Source source = losers_[0].source;
500 for (Source pos = (k_ + source) / 2; pos > 0; pos /= 2) {
501 // the smaller one gets promoted, ties are broken by source
502 if ((!keyp &&
503 (losers_[pos].keyp || losers_[pos].source < source)) ||
504 (keyp && losers_[pos].keyp &&
505 ((cmp_(*losers_[pos].keyp, *keyp)) ||
506 (!cmp_(*keyp, *losers_[pos].keyp) &&
507 losers_[pos].source < source)))) {
508 // the other one is smaller
509 swap(losers_[pos].source, source);
510 swap(losers_[pos].keyp, keyp);
511 }
512 }
513
514 losers_[0].source = source;
515 losers_[0].keyp = keyp;
516 }
517};
518
519/*!
520 * Unguarded loser tree, copying the whole element into the tree structure.
521 *
522 * This is a base class for the LoserTreeCopyUnguarded<true> and <false>
523 * classes.
524 *
525 * No guarding is done, therefore not a single input sequence must run empty.
526 * This is a very fast variant.
527 */
528template <typename ValueType, typename Comparator = std::less<ValueType> >
530{
531public:
532 //! size of counters and array indexes
533 using Source = std::uint32_t;
534
535 //! sentinel for invalid or finished Sources
536 static constexpr Source invalid_ = Source(-1);
537
538protected:
539 //! Internal representation of a loser tree player/node
540 struct Loser {
541 //! index of source
543 //! copy of key value of the element in this node
544 ValueType key;
545 };
546
547 //! number of nodes
549 //! log_2(ik) next greater power of 2
551 //! array containing loser tree nodes
553 //! the comparator object
554 Comparator cmp_;
555
556public:
557 LoserTreeCopyUnguardedBase(Source k, const ValueType& sentinel,
558 const Comparator& cmp = Comparator())
560 cmp_(cmp) {
561 for (Source i = 0; i < 2 * k_; i++) {
562 losers_[i].source = invalid_;
563 losers_[i].key = sentinel;
564 }
565 }
566
567 //! return the index of the player with the smallest element.
569 assert(losers_[0].source != invalid_ &&
570 "Data underrun in unguarded merging.");
571 return losers_[0].source;
572 }
573
574 void insert_start(const ValueType* keyp, const Source& source, bool sup) {
575 Source pos = k_ + source;
576
577 assert(pos < losers_.size());
578 assert(sup == (keyp == nullptr));
579 unused(sup);
580
581 losers_[pos].source = source;
582 losers_[pos].key = *keyp;
583 }
584
585 Source init_winner(const Source& root) {
586 if (root >= k_)
587 return root;
588
589 Source left = init_winner(2 * root);
590 Source right = init_winner(2 * root + 1);
591 if (!cmp_(losers_[right].key, losers_[left].key)) {
592 // left one is less or equal
593 losers_[root] = losers_[right];
594 return left;
595 }
596 else {
597 // right one is less
598 losers_[root] = losers_[left];
599 return right;
600 }
601 }
602
603 void init() {
604 if (TLX_UNLIKELY(k_ == 0))
605 return;
606 losers_[0] = losers_[init_winner(1)];
607 }
608};
609
610template <bool Stable /* == false */, typename ValueType,
611 typename Comparator = std::less<ValueType> >
613 : public LoserTreeCopyUnguardedBase<ValueType, Comparator>
614{
615public:
617 using Source = typename Super::Source;
618
619private:
620 using Super::k_;
621 using Super::losers_;
622 using Super::cmp_;
623
624public:
625 LoserTreeCopyUnguarded(Source k, const ValueType& sentinel,
626 const Comparator& cmp = Comparator())
627 : Super(k, sentinel, cmp) { }
628
629 // do not pass const reference since key will be used as local variable
630 void delete_min_insert(const ValueType* keyp, bool sup) {
631 using std::swap;
632 assert(sup == (keyp == nullptr));
633 unused(sup);
634
635 Source source = losers_[0].source;
636 ValueType key = keyp ? *keyp : ValueType();
637
638 for (Source pos = (k_ + source) / 2; pos > 0; pos /= 2) {
639 // the smaller one gets promoted
640 if (cmp_(losers_[pos].key, key)) {
641 // the other one is smaller
642 swap(losers_[pos].source, source);
643 swap(losers_[pos].key, key);
644 }
645 }
646
647 losers_[0].source = source;
648 losers_[0].key = key;
649 }
650};
651
652template <typename ValueType, typename Comparator>
653class LoserTreeCopyUnguarded</* Stable == */ true, ValueType, Comparator>
654 : public LoserTreeCopyUnguardedBase<ValueType, Comparator>
655{
656public:
658 using Source = typename Super::Source;
659
660private:
661 using Super::k_;
662 using Super::losers_;
663 using Super::cmp_;
664
665public:
666 LoserTreeCopyUnguarded(Source k, const ValueType& sentinel,
667 const Comparator& comp = Comparator())
668 : Super(k, sentinel, comp) { }
669
670 // do not pass const reference since key will be used as local variable
671 void delete_min_insert(const ValueType* keyp, bool sup) {
672 using std::swap;
673 assert(sup == (keyp == nullptr));
674 unused(sup);
675
676 Source source = losers_[0].source;
677 ValueType key = keyp ? *keyp : ValueType();
678
679 for (Source pos = (k_ + source) / 2; pos > 0; pos /= 2) {
680 if (cmp_(losers_[pos].key, key) ||
681 (!cmp_(key, losers_[pos].key) &&
682 losers_[pos].source < source)) {
683 // the other one is smaller
684 swap(losers_[pos].source, source);
685 swap(losers_[pos].key, key);
686 }
687 }
688
689 losers_[0].source = source;
690 losers_[0].key = key;
691 }
692};
693
694/*!
695 * Unguarded loser tree, keeping only pointers to the elements in the tree
696 * structure.
697 *
698 * This is a base class for the LoserTreePointerUnguarded<true> and <false>
699 * classes.
700 *
701 * No guarding is done, therefore not a single input sequence must run empty.
702 * This is a very fast variant.
703 */
704template <typename ValueType, typename Comparator = std::less<ValueType> >
706{
707public:
708 //! size of counters and array indexes
709 using Source = std::uint32_t;
710
711 //! sentinel for invalid or finished Sources
712 static constexpr Source invalid_ = Source(-1);
713
714protected:
715 //! Internal representation of a loser tree player/node
716 struct Loser {
717 //! index of source
719 //! copy of key value of the element in this node
720 const ValueType* keyp;
721 };
722
723 //! number of nodes
725 //! log_2(ik) next greater power of 2
727 //! array containing loser tree nodes
729 //! the comparator object
730 Comparator cmp_;
731
732public:
733 LoserTreePointerUnguardedBase(const Source& k, const ValueType& sentinel,
734 const Comparator& cmp = Comparator())
736 losers_(k_ * 2), cmp_(cmp) {
737 for (Source i = ik_ - 1; i < k_; i++) {
738 losers_[i + k_].source = invalid_;
739 losers_[i + k_].keyp = &sentinel;
740 }
741 }
742
743 // non construction-copyable
745 const LoserTreePointerUnguardedBase& other) = delete;
746 // non copyable
748 const LoserTreePointerUnguardedBase&) = delete;
749
750 Source min_source() { return losers_[0].source; }
751
752 void insert_start(const ValueType* keyp, const Source& source, bool sup) {
753 Source pos = k_ + source;
754
755 assert(pos < losers_.size());
756 assert(sup == (keyp == nullptr));
757 unused(sup);
758
759 losers_[pos].source = source;
760 losers_[pos].keyp = keyp;
761 }
762
763 Source init_winner(const Source& root) {
764 if (root >= k_)
765 return root;
766
767 Source left = init_winner(2 * root);
768 Source right = init_winner(2 * root + 1);
769 if (!cmp_(*losers_[right].keyp, *losers_[left].keyp)) {
770 // left one is less or equal
771 losers_[root] = losers_[right];
772 return left;
773 }
774 else {
775 // right one is less
776 losers_[root] = losers_[left];
777 return right;
778 }
779 }
780
781 void init() {
782 if (TLX_UNLIKELY(k_ == 0))
783 return;
784 losers_[0] = losers_[init_winner(1)];
785 }
786};
787
788template <bool Stable /* == false */, typename ValueType,
789 typename Comparator = std::less<ValueType> >
791 : public LoserTreePointerUnguardedBase<ValueType, Comparator>
792{
793public:
795 using Source = typename Super::Source;
796
797protected:
798 using Super::k_;
799 using Super::losers_;
800 using Super::cmp_;
801
802public:
803 LoserTreePointerUnguarded(const Source& k, const ValueType& sentinel,
804 const Comparator& cmp = Comparator())
805 : Super(k, sentinel, cmp) { }
806
807 void delete_min_insert(const ValueType* keyp, bool sup) {
808 using std::swap;
809 assert(sup == (keyp == nullptr));
810 unused(sup);
811
812 Source source = losers_[0].source;
813 for (Source pos = (k_ + source) / 2; pos > 0; pos /= 2) {
814 // the smaller one gets promoted
815 if (cmp_(*losers_[pos].keyp, *keyp)) {
816 // the other one is smaller
817 swap(losers_[pos].source, source);
818 swap(losers_[pos].keyp, keyp);
819 }
820 }
821
822 losers_[0].source = source;
823 losers_[0].keyp = keyp;
824 }
825};
826
827template <typename ValueType, typename Comparator>
828class LoserTreePointerUnguarded</* Stable == */ true, ValueType, Comparator>
829 : public LoserTreePointerUnguardedBase<ValueType, Comparator>
830{
831public:
833 using Source = typename Super::Source;
834
835protected:
836 using Super::k_;
837 using Super::losers_;
838 using Super::cmp_;
839
840public:
841 LoserTreePointerUnguarded(const Source& k, const ValueType& sentinel,
842 const Comparator& cmp = Comparator())
843 : Super(k, sentinel, cmp) { }
844
845 void delete_min_insert(const ValueType* keyp, bool sup) {
846 using std::swap;
847 assert(sup == (keyp == nullptr));
848 unused(sup);
849
850 Source source = losers_[0].source;
851 for (Source pos = (k_ + source) / 2; pos > 0; pos /= 2) {
852 // the smaller one gets promoted, ties are broken by source
853 if (cmp_(*losers_[pos].keyp, *keyp) ||
854 (!cmp_(*keyp, *losers_[pos].keyp) &&
855 losers_[pos].source < source)) {
856 // the other one is smaller
857 swap(losers_[pos].source, source);
858 swap(losers_[pos].keyp, keyp);
859 }
860 }
861
862 losers_[0].source = source;
863 losers_[0].keyp = keyp;
864 }
865};
866
867/******************************************************************************/
868// LoserTreeSwitch selects loser tree by size of value type
869
870template <bool Stable, typename ValueType, typename Comparator,
871 typename Enable = void>
873{
874public:
876};
877
878template <bool Stable, typename ValueType, typename Comparator>
879class LoserTreeSwitch<
880 Stable, ValueType, Comparator,
881 typename std::enable_if<sizeof(ValueType) <= 2 * sizeof(size_t)>::type>
882{
883public:
885};
886
887template <bool Stable, typename ValueType, typename Comparator>
889
890/*----------------------------------------------------------------------------*/
891
892template <bool Stable, typename ValueType, typename Comparator,
893 typename Enable = void>
894class LoserTreeUnguardedSwitch
895{
896public:
897 using Type = LoserTreePointerUnguarded<Stable, ValueType, Comparator>;
898};
899
900template <bool Stable, typename ValueType, typename Comparator>
901class LoserTreeUnguardedSwitch<
902 Stable, ValueType, Comparator,
903 typename std::enable_if<sizeof(ValueType) <= 2 * sizeof(size_t)>::type>
904{
905public:
906 using Type = LoserTreeCopyUnguarded<Stable, ValueType, Comparator>;
907};
908
909template <bool Stable, typename ValueType, typename Comparator>
910using LoserTreeUnguarded =
911 typename LoserTreeUnguardedSwitch<Stable, ValueType, Comparator>::Type;
912
913//! \}
914//! \}
915
916} // namespace tlx
917
918#endif // !TLX_CONTAINER_LOSER_TREE_HEADER
919
920/******************************************************************************/
Guarded loser tree/tournament tree, either copying the whole element into the tree structure,...
Definition: loser_tree.hpp:56
Unguarded loser tree, copying the whole element into the tree structure.
Definition: loser_tree.hpp:530
Guarded loser tree/tournament tree, either copying the whole element into the tree structure,...
Definition: loser_tree.hpp:183
Guarded loser tree, using pointers to the elements instead of copying them into the tree nodes.
Definition: loser_tree.hpp:308
Unguarded loser tree, keeping only pointers to the elements in the tree structure.
Definition: loser_tree.hpp:706
Guarded loser tree, using pointers to the elements instead of copying them into the tree nodes.
Definition: loser_tree.hpp:420
Simpler non-growing vector without initialization.
LoserTreeCopyBase(const Source &k, const Comparator &cmp=Comparator())
Definition: loser_tree.hpp:88
Source ik_
number of nodes
Definition: loser_tree.hpp:548
typename Super::Source Source
Definition: loser_tree.hpp:186
LoserTreePointerUnguardedBase(const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator())
Definition: loser_tree.hpp:733
static constexpr Source invalid_
sentinel for invalid or finished Sources
Definition: loser_tree.hpp:62
LoserTreeCopy(const Source &k, const Comparator &cmp=Comparator())
Definition: loser_tree.hpp:194
LoserTreeCopyUnguardedBase(Source k, const ValueType &sentinel, const Comparator &cmp=Comparator())
Definition: loser_tree.hpp:557
void insert_start(const ValueType *keyp, const Source &source, bool sup)
Initializes the player source with the element key.
Definition: loser_tree.hpp:110
LoserTreePointerBase(LoserTreePointerBase &&)=default
LoserTreePointerUnguarded(const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator())
Definition: loser_tree.hpp:803
bool sup
flag, true iff is a virtual maximum sentinel
Definition: loser_tree.hpp:68
LoserTreePointerUnguardedBase & operator=(const LoserTreePointerUnguardedBase &)=delete
LoserTreePointerBase(const LoserTreePointerBase &)=delete
LoserTreePointer(Source k, const Comparator &cmp=Comparator())
Definition: loser_tree.hpp:431
const ValueType * keyp
pointer to key value of the element in this node
Definition: loser_tree.hpp:322
Source k_
log_2(ik) next greater power of 2
Definition: loser_tree.hpp:550
SimpleVector< Loser > losers_
array containing loser tree nodes – avoid default-constructing losers[].key
Definition: loser_tree.hpp:81
void delete_min_insert(const ValueType *keyp, bool sup)
Definition: loser_tree.hpp:199
Comparator cmp_
the comparator object
Definition: loser_tree.hpp:83
Source source
index of source
Definition: loser_tree.hpp:70
Source min_source()
return the index of the player with the smallest element.
Definition: loser_tree.hpp:100
LoserTreeCopyUnguarded(Source k, const ValueType &sentinel, const Comparator &comp=Comparator())
Definition: loser_tree.hpp:666
bool first_insert_
still have to construct keys
Definition: loser_tree.hpp:85
ValueType key
copy of key value of the element in this node
Definition: loser_tree.hpp:72
LoserTreePointerUnguardedBase(const LoserTreePointerUnguardedBase &other)=delete
LoserTreePointer< Stable, ValueType, Comparator > Type
Definition: loser_tree.hpp:875
LoserTreePointerBase(Source k, const Comparator &cmp=Comparator())
Definition: loser_tree.hpp:335
LoserTreePointerBase & operator=(const LoserTreePointerBase &)=delete
LoserTreeCopyUnguarded(Source k, const ValueType &sentinel, const Comparator &cmp=Comparator())
Definition: loser_tree.hpp:625
const Source ik_
number of nodes
Definition: loser_tree.hpp:76
std::uint32_t Source
size of counters and array indexes
Definition: loser_tree.hpp:59
Source init_winner(const Source &root)
Computes the winner of the competition at player root.
Definition: loser_tree.hpp:140
const Source k_
log_2(ik) next greater power of 2
Definition: loser_tree.hpp:78
#define TLX_UNLIKELY(c)
Definition: likely.hpp:24
static int round_up_to_power_of_two(int i)
does what it says: round up to next power of two
STL namespace.
void swap(CountingPtr< A, D > &a1, CountingPtr< A, D > &a2) noexcept
swap enclosed object with another counting pointer (no reference counts need change)
void unused(Types &&...)
Definition: unused.hpp:20
Internal representation of a loser tree player/node.
Definition: loser_tree.hpp:66
Internal representation of a loser tree player/node.
Definition: loser_tree.hpp:540
Internal representation of a loser tree player/node.
Definition: loser_tree.hpp:318
Internal representation of a loser tree player/node.
Definition: loser_tree.hpp:716
SFINAE enable_if – copy of std::enable_if<> with less extra cruft.
Definition: enable_if.hpp:22