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