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