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>
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,...
Unguarded loser tree, copying the whole element into the tree structure.
Guarded loser tree/tournament tree, either copying the whole element into the tree structure,...
Guarded loser tree, using pointers to the elements instead of copying them into the tree nodes.
Unguarded loser tree, keeping only pointers to the elements in the tree structure.
Guarded loser tree, using pointers to the elements instead of copying them into the tree nodes.
Simpler non-growing vector without initialization.
LoserTreeCopyBase(const Source &k, const Comparator &cmp=Comparator())
Source ik_
number of nodes
typename Super::Source Source
LoserTreePointerUnguardedBase(const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator())
static constexpr Source invalid_
sentinel for invalid or finished Sources
LoserTreeCopy(const Source &k, const Comparator &cmp=Comparator())
LoserTreeCopyUnguardedBase(Source k, const ValueType &sentinel, const Comparator &cmp=Comparator())
void insert_start(const ValueType *keyp, const Source &source, bool sup)
Initializes the player source with the element key.
LoserTreePointerBase(LoserTreePointerBase &&)=default
LoserTreePointerUnguarded(const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator())
bool sup
flag, true iff is a virtual maximum sentinel
LoserTreePointerUnguardedBase & operator=(const LoserTreePointerUnguardedBase &)=delete
LoserTreePointerBase(const LoserTreePointerBase &)=delete
LoserTreePointer(Source k, const Comparator &cmp=Comparator())
const ValueType * keyp
pointer to key value of the element in this node
Source k_
log_2(ik) next greater power of 2
SimpleVector< Loser > losers_
array containing loser tree nodes – avoid default-constructing losers[].key
void delete_min_insert(const ValueType *keyp, bool sup)
Comparator cmp_
the comparator object
Source source
index of source
Source min_source()
return the index of the player with the smallest element.
LoserTreeCopyUnguarded(Source k, const ValueType &sentinel, const Comparator &comp=Comparator())
bool first_insert_
still have to construct keys
ValueType key
copy of key value of the element in this node
LoserTreePointerUnguardedBase(const LoserTreePointerUnguardedBase &other)=delete
LoserTreePointer< Stable, ValueType, Comparator > Type
LoserTreePointerBase(Source k, const Comparator &cmp=Comparator())
LoserTreePointerBase & operator=(const LoserTreePointerBase &)=delete
LoserTreeCopyUnguarded(Source k, const ValueType &sentinel, const Comparator &cmp=Comparator())
const Source ik_
number of nodes
std::uint32_t Source
size of counters and array indexes
Source init_winner(const Source &root)
Computes the winner of the competition at player root.
const Source k_
log_2(ik) next greater power of 2
#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.
Internal representation of a loser tree player/node.
Internal representation of a loser tree player/node.
Internal representation of a loser tree player/node.
SFINAE enable_if – copy of std::enable_if<> with less extra cruft.
Definition enable_if.hpp:22