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 
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  */
179 template <bool Stable /* == false */, typename ValueType,
180  typename Comparator = std::less<ValueType> >
181 class LoserTreeCopy : public LoserTreeCopyBase<ValueType, Comparator>
182 {
183 public:
185  using Source = typename Super::Source;
186 
187 protected:
188  using Super::k_;
189  using Super::losers_;
190  using Super::cmp_;
191 
192 public:
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  */
246 template <typename ValueType, typename Comparator>
247 class LoserTreeCopy</* Stable == */ true, ValueType, Comparator>
248  : public LoserTreeCopyBase<ValueType, Comparator>
249 {
250 public:
252  using Source = typename Super::Source;
253 
254 protected:
255  using Super::k_;
256  using Super::losers_;
257  using Super::cmp_;
258 
259 public:
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  */
305 template <typename ValueType, typename Comparator = std::less<ValueType> >
307 {
308 public:
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 
315 protected:
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 
333 public:
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  */
416 template <bool Stable /* == false */, typename ValueType,
417  typename Comparator = std::less<ValueType> >
418 class LoserTreePointer : public LoserTreePointerBase<ValueType, Comparator>
419 {
420 public:
422  using Source = typename Super::Source;
423 
424 protected:
425  using Super::k_;
426  using Super::losers_;
427  using Super::cmp_;
428 
429 public:
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  */
476 template <typename ValueType, typename Comparator>
477 class LoserTreePointer</* Stable == */ true, ValueType, Comparator>
478  : public LoserTreePointerBase<ValueType, Comparator>
479 {
480 public:
482  using Source = typename Super::Source;
483 
484 protected:
485  using Super::k_;
486  using Super::losers_;
487  using Super::cmp_;
488 
489 public:
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  */
527 template <typename ValueType, typename Comparator = std::less<ValueType> >
529 {
530 public:
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 
537 protected:
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 
555 public:
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 
609 template <bool Stable /* == false */, typename ValueType,
610  typename Comparator = std::less<ValueType> >
612  : public LoserTreeCopyUnguardedBase<ValueType, Comparator>
613 {
614 public:
616  using Source = typename Super::Source;
617 
618 private:
619  using Super::k_;
620  using Super::losers_;
621  using Super::cmp_;
622 
623 public:
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 
651 template <typename ValueType, typename Comparator>
652 class LoserTreeCopyUnguarded</* Stable == */ true, ValueType, Comparator>
653  : public LoserTreeCopyUnguardedBase<ValueType, Comparator>
654 {
655 public:
657  using Source = typename Super::Source;
658 
659 private:
660  using Super::k_;
661  using Super::losers_;
662  using Super::cmp_;
663 
664 public:
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  */
703 template <typename ValueType, typename Comparator = std::less<ValueType> >
705 {
706 public:
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 
713 protected:
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 
731 public:
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 
787 template <bool Stable /* == false */, typename ValueType,
788  typename Comparator = std::less<ValueType> >
790  : public LoserTreePointerUnguardedBase<ValueType, Comparator>
791 {
792 public:
794  using Source = typename Super::Source;
795 
796 protected:
797  using Super::k_;
798  using Super::losers_;
799  using Super::cmp_;
800 
801 public:
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 
826 template <typename ValueType, typename Comparator>
827 class LoserTreePointerUnguarded</* Stable == */ true, ValueType, Comparator>
828  : public LoserTreePointerUnguardedBase<ValueType, Comparator>
829 {
830 public:
832  using Source = typename Super::Source;
833 
834 protected:
835  using Super::k_;
836  using Super::losers_;
837  using Super::cmp_;
838 
839 public:
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 
869 template <bool Stable, typename ValueType, typename Comparator,
870  typename Enable = void>
872 {
873 public:
875 };
876 
877 template <bool Stable, typename ValueType, typename Comparator>
878 class LoserTreeSwitch<
879  Stable, ValueType, Comparator,
880  typename std::enable_if<sizeof(ValueType) <= 2 * sizeof(size_t)>::type>
881 {
882 public:
884 };
885 
886 template <bool Stable, typename ValueType, typename Comparator>
888 
889 /*----------------------------------------------------------------------------*/
890 
891 template <bool Stable, typename ValueType, typename Comparator,
892  typename Enable = void>
893 class LoserTreeUnguardedSwitch
894 {
895 public:
896  using Type = LoserTreePointerUnguarded<Stable, ValueType, Comparator>;
897 };
898 
899 template <bool Stable, typename ValueType, typename Comparator>
900 class LoserTreeUnguardedSwitch<
901  Stable, ValueType, Comparator,
902  typename std::enable_if<sizeof(ValueType) <= 2 * sizeof(size_t)>::type>
903 {
904 public:
905  using Type = LoserTreeCopyUnguarded<Stable, ValueType, Comparator>;
906 };
907 
908 template <bool Stable, typename ValueType, typename Comparator>
909 using LoserTreeUnguarded =
911 
912 //! \}
913 //! \}
914 
915 } // namespace tlx
916 
917 #endif // !TLX_CONTAINER_LOSER_TREE_HEADER
918 
919 /******************************************************************************/
static constexpr Source invalid_
sentinel for invalid or finished Sources
Definition: loser_tree.hpp:61
LoserTreePointer< Stable, ValueType, Comparator > Type
Definition: loser_tree.hpp:874
const ValueType * keyp
pointer to key value of the element in this node
Definition: loser_tree.hpp:321
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:665
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:185
#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:418
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:549
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:139
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:547
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:715
LoserTreePointerUnguarded(const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator())
Definition: loser_tree.hpp:802
LoserTreeCopyUnguarded(Source k, const ValueType &sentinel, const Comparator &cmp=Comparator())
Definition: loser_tree.hpp:624
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:732
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:198
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:334
Guarded loser tree, using pointers to the elements instead of copying them into the tree nodes...
Definition: loser_tree.hpp:306
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:539
LoserTreeCopy(const Source &k, const Comparator &cmp=Comparator())
Definition: loser_tree.hpp:193
Guarded loser tree/tournament tree, either copying the whole element into the tree structure...
Definition: loser_tree.hpp:181
Internal representation of a loser tree player/node.
Definition: loser_tree.hpp:317
LoserTreePointer(Source k, const Comparator &cmp=Comparator())
Definition: loser_tree.hpp:430
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:704
LoserTreeCopyUnguardedBase(Source k, const ValueType &sentinel, const Comparator &cmp=Comparator())
Definition: loser_tree.hpp:556
Unguarded loser tree, copying the whole element into the tree structure.
Definition: loser_tree.hpp:528