19#ifndef TLX_CONTAINER_LOSER_TREE_HEADER
20#define TLX_CONTAINER_LOSER_TREE_HEADER
54template <
typename ValueType,
typename Comparator = std::less<ValueType> >
89 const Comparator& cmp = Comparator())
114 assert(sup == (keyp ==
nullptr));
121 for (
Source i = 0; i < 2 *
k_; ++i) {
130 losers_[pos].key = keyp ? *keyp : ValueType();
180template <
bool Stable ,
typename ValueType,
181 typename Comparator = std::less<ValueType> >
195 const Comparator& cmp = Comparator())
201 assert(sup == (keyp ==
nullptr));
204 ValueType key = keyp ? *keyp : ValueType();
247template <
typename ValueType,
typename Comparator>
262 const Comparator& cmp = Comparator())
268 assert(sup == (keyp ==
nullptr));
271 ValueType key = keyp ? *keyp : ValueType();
277 losers_[pos].source < source)) ||
281 losers_[pos].source < source)))) {
306template <
typename ValueType,
typename Comparator = std::less<ValueType> >
336 Source k,
const Comparator& cmp = Comparator())
367 assert(sup == (keyp ==
nullptr));
417template <
bool Stable ,
typename ValueType,
418 typename Comparator = std::less<ValueType> >
436 assert(sup == (keyp ==
nullptr));
477template <
typename ValueType,
typename Comparator>
496 assert(sup == (keyp ==
nullptr));
500 for (
Source pos = (
k_ + source) / 2; pos > 0; pos /= 2) {
507 losers_[pos].source < source)))) {
528template <
typename ValueType,
typename Comparator = std::less<ValueType> >
558 const Comparator& cmp = Comparator())
561 for (
Source i = 0; i < 2 *
k_; i++) {
570 "Data underrun in unguarded merging.");
578 assert(sup == (keyp ==
nullptr));
610template <
bool Stable ,
typename ValueType,
611 typename Comparator = std::less<ValueType> >
626 const Comparator& cmp = Comparator())
627 :
Super(k, sentinel, cmp) { }
632 assert(sup == (keyp ==
nullptr));
636 ValueType key = keyp ? *keyp : ValueType();
638 for (
Source pos = (
k_ + source) / 2; pos > 0; pos /= 2) {
652template <
typename ValueType,
typename Comparator>
667 const Comparator& comp = Comparator())
668 :
Super(k, sentinel, comp) { }
673 assert(sup == (keyp ==
nullptr));
677 ValueType key = keyp ? *keyp : ValueType();
679 for (
Source pos = (
k_ + source) / 2; pos > 0; pos /= 2) {
682 losers_[pos].source < source)) {
704template <
typename ValueType,
typename Comparator = std::less<ValueType> >
734 const Comparator& cmp = Comparator())
756 assert(sup == (keyp ==
nullptr));
788template <
bool Stable ,
typename ValueType,
789 typename Comparator = std::less<ValueType> >
804 const Comparator& cmp = Comparator())
805 :
Super(k, sentinel, cmp) { }
809 assert(sup == (keyp ==
nullptr));
813 for (
Source pos = (
k_ + source) / 2; pos > 0; pos /= 2) {
827template <
typename ValueType,
typename Comparator>
842 const Comparator& cmp = Comparator())
843 :
Super(k, sentinel, cmp) { }
847 assert(sup == (keyp ==
nullptr));
851 for (
Source pos = (
k_ + source) / 2; pos > 0; pos /= 2) {
855 losers_[pos].source < source)) {
870template <
bool Stable,
typename ValueType,
typename Comparator,
871 typename Enable =
void>
878template <
bool Stable,
typename ValueType,
typename Comparator>
880 Stable, ValueType, Comparator,
881 typename
std::
enable_if<sizeof(ValueType) <= 2 * sizeof(size_t)>::type>
887template <
bool Stable,
typename ValueType,
typename Comparator>
892template <
bool Stable,
typename ValueType,
typename Comparator,
893 typename Enable =
void>
894class LoserTreeUnguardedSwitch
897 using Type = LoserTreePointerUnguarded<Stable, ValueType, Comparator>;
900template <
bool Stable,
typename ValueType,
typename Comparator>
901class LoserTreeUnguardedSwitch<
902 Stable, ValueType, Comparator,
903 typename
std::enable_if<sizeof(ValueType) <= 2 * sizeof(size_t)>::type>
906 using Type = LoserTreeCopyUnguarded<Stable, ValueType, Comparator>;
909template <
bool Stable,
typename ValueType,
typename Comparator>
910using LoserTreeUnguarded =
911 typename LoserTreeUnguardedSwitch<Stable, ValueType, Comparator>::Type;
Guarded loser tree/tournament tree, either copying the whole element into the tree structure,...
Unguarded loser tree, copying the whole element into the tree structure.
Guarded loser tree/tournament tree, either copying the whole element into the tree structure,...
Guarded loser tree, using pointers to the elements instead of copying them into the tree nodes.
Unguarded loser tree, keeping only pointers to the elements in the tree structure.
Guarded loser tree, using pointers to the elements instead of copying them into the tree nodes.
Simpler non-growing vector without initialization.
LoserTreeCopyBase(const Source &k, const Comparator &cmp=Comparator())
Source ik_
number of nodes
typename Super::Source Source
LoserTreePointerUnguardedBase(const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator())
uint32_t Source
size of counters and array indexes
static constexpr Source invalid_
sentinel for invalid or finished Sources
LoserTreeCopy(const Source &k, const Comparator &cmp=Comparator())
LoserTreeCopyUnguardedBase(Source k, const ValueType &sentinel, const Comparator &cmp=Comparator())
void insert_start(const ValueType *keyp, const Source &source, bool sup)
Initializes the player source with the element key.
LoserTreePointerBase(LoserTreePointerBase &&)=default
LoserTreePointerUnguarded(const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator())
bool sup
flag, true iff is a virtual maximum sentinel
LoserTreePointerUnguardedBase & operator=(const LoserTreePointerUnguardedBase &)=delete
LoserTreePointerBase(const LoserTreePointerBase &)=delete
LoserTreePointer(Source k, const Comparator &cmp=Comparator())
const ValueType * keyp
pointer to key value of the element in this node
Source k_
log_2(ik) next greater power of 2
SimpleVector< Loser > losers_
array containing loser tree nodes – avoid default-constructing losers[].key
void delete_min_insert(const ValueType *keyp, bool sup)
Comparator cmp_
the comparator object
Source source
index of source
Source min_source()
return the index of the player with the smallest element.
LoserTreeCopyUnguarded(Source k, const ValueType &sentinel, const Comparator &comp=Comparator())
bool first_insert_
still have to construct keys
ValueType key
copy of key value of the element in this node
LoserTreePointerUnguardedBase(const LoserTreePointerUnguardedBase &other)=delete
LoserTreePointer< Stable, ValueType, Comparator > Type
LoserTreePointerBase(Source k, const Comparator &cmp=Comparator())
LoserTreePointerBase & operator=(const LoserTreePointerBase &)=delete
LoserTreeCopyUnguarded(Source k, const ValueType &sentinel, const Comparator &cmp=Comparator())
const Source ik_
number of nodes
Source init_winner(const Source &root)
Computes the winner of the competition at player root.
const Source k_
log_2(ik) next greater power of 2
static int round_up_to_power_of_two(int i)
does what it says: round up to next power of two
void swap(CountingPtr< A, D > &a1, CountingPtr< A, D > &a2) noexcept
swap enclosed object with another counting pointer (no reference counts need change)
Internal representation of a loser tree player/node.
Internal representation of a loser tree player/node.
Internal representation of a loser tree player/node.
Internal representation of a loser tree player/node.
SFINAE enable_if – copy of std::enable_if<> with less extra cruft.