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