19 #ifndef TLX_CONTAINER_LOSER_TREE_HEADER
20 #define TLX_CONTAINER_LOSER_TREE_HEADER
53 template <
typename ValueType,
typename Comparator = std::less<ValueType> >
54 class LoserTreeCopyBase
88 const Comparator& cmp = Comparator())
113 assert(sup == (keyp ==
nullptr));
120 for (
Source i = 0; i < 2 *
k_; ++i) {
129 losers_[pos].key = keyp ? *keyp : ValueType();
179 template <
bool Stable ,
typename ValueType,
180 typename Comparator = std::less<ValueType> >
194 const Comparator& cmp = Comparator())
200 assert(sup == (keyp ==
nullptr));
203 ValueType key = keyp ? *keyp : ValueType();
246 template <
typename ValueType,
typename Comparator>
247 class LoserTreeCopy< true, ValueType, Comparator>
248 :
public LoserTreeCopyBase<ValueType, Comparator>
251 using Super = LoserTreeCopyBase<ValueType, Comparator>;
261 const Comparator& cmp = Comparator())
267 assert(sup == (keyp ==
nullptr));
270 ValueType key = keyp ? *keyp : ValueType();
280 losers_[pos].source < source)))) {
305 template <
typename ValueType,
typename Comparator = std::less<ValueType> >
306 class LoserTreePointerBase
321 const ValueType*
keyp;
335 Source k,
const Comparator& cmp = Comparator())
366 assert(sup == (keyp ==
nullptr));
416 template <
bool Stable ,
typename ValueType,
417 typename Comparator = std::less<ValueType> >
435 assert(sup == (keyp ==
nullptr));
476 template <
typename ValueType,
typename Comparator>
477 class LoserTreePointer< true, ValueType, Comparator>
478 :
public LoserTreePointerBase<ValueType, Comparator>
481 using Super = LoserTreePointerBase<ValueType, Comparator>;
495 assert(sup == (keyp ==
nullptr));
499 for (
Source pos = (
k_ + source) / 2; pos > 0; pos /= 2) {
527 template <
typename ValueType,
typename Comparator = std::less<ValueType> >
528 class LoserTreeCopyUnguardedBase
557 const Comparator& cmp = Comparator())
560 for (
Source i = 0; i < 2 *
k_; i++) {
569 "Data underrun in unguarded merging.");
577 assert(sup == (keyp ==
nullptr));
609 template <
bool Stable ,
typename ValueType,
610 typename Comparator = std::less<ValueType> >
611 class LoserTreeCopyUnguarded
612 :
public LoserTreeCopyUnguardedBase<ValueType, Comparator>
615 using Super = LoserTreeCopyUnguardedBase<ValueType, Comparator>;
625 const Comparator& cmp = Comparator())
626 :
Super(k, sentinel, cmp) { }
631 assert(sup == (keyp ==
nullptr));
635 ValueType key = keyp ? *keyp : ValueType();
637 for (
Source pos = (
k_ + source) / 2; pos > 0; pos /= 2) {
651 template <
typename ValueType,
typename Comparator>
652 class LoserTreeCopyUnguarded< true, ValueType, Comparator>
653 :
public LoserTreeCopyUnguardedBase<ValueType, Comparator>
656 using Super = LoserTreeCopyUnguardedBase<ValueType, Comparator>;
666 const Comparator& comp = Comparator())
667 :
Super(k, sentinel, comp) { }
672 assert(sup == (keyp ==
nullptr));
676 ValueType key = keyp ? *keyp : ValueType();
678 for (
Source pos = (
k_ + source) / 2; pos > 0; pos /= 2) {
703 template <
typename ValueType,
typename Comparator = std::less<ValueType> >
704 class LoserTreePointerUnguardedBase
719 const ValueType*
keyp;
733 const Comparator& cmp = Comparator())
755 assert(sup == (keyp ==
nullptr));
787 template <
bool Stable ,
typename ValueType,
788 typename Comparator = std::less<ValueType> >
789 class LoserTreePointerUnguarded
790 :
public LoserTreePointerUnguardedBase<ValueType, Comparator>
793 using Super = LoserTreePointerUnguardedBase<ValueType, Comparator>;
803 const Comparator& cmp = Comparator())
804 :
Super(k, sentinel, cmp) { }
808 assert(sup == (keyp ==
nullptr));
812 for (
Source pos = (
k_ + source) / 2; pos > 0; pos /= 2) {
826 template <
typename ValueType,
typename Comparator>
827 class LoserTreePointerUnguarded< true, ValueType, Comparator>
828 :
public LoserTreePointerUnguardedBase<ValueType, Comparator>
831 using Super = LoserTreePointerUnguardedBase<ValueType, Comparator>;
841 const Comparator& cmp = Comparator())
842 :
Super(k, sentinel, cmp) { }
846 assert(sup == (keyp ==
nullptr));
850 for (
Source pos = (
k_ + source) / 2; pos > 0; pos /= 2) {
854 losers_[pos].source < source)) {
869 template <
bool Stable,
typename ValueType,
typename Comparator,
870 typename Enable =
void>
871 class LoserTreeSwitch
874 using Type = LoserTreePointer<Stable, ValueType, Comparator>;
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>
883 using Type = LoserTreeCopy<Stable, ValueType, Comparator>;
886 template <
bool Stable,
typename ValueType,
typename Comparator>
891 template <
bool Stable,
typename ValueType,
typename Comparator,
892 typename Enable =
void>
893 class LoserTreeUnguardedSwitch
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>
908 template <
bool Stable,
typename ValueType,
typename Comparator>
909 using LoserTreeUnguarded =
910 typename LoserTreeUnguardedSwitch<Stable, ValueType, Comparator>::Type;
917 #endif // !TLX_CONTAINER_LOSER_TREE_HEADER