19#ifndef TLX_CONTAINER_LOSER_TREE_HEADER
20#define TLX_CONTAINER_LOSER_TREE_HEADER
53template <
typename ValueType,
typename Comparator = std::less<ValueType> >
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();
179template <
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();
246template <
typename ValueType,
typename Comparator>
261 const Comparator& cmp = Comparator())
267 assert(sup == (keyp ==
nullptr));
270 ValueType key = keyp ? *keyp : ValueType();
276 losers_[pos].source < source)) ||
280 losers_[pos].source < source)))) {
305template <
typename ValueType,
typename Comparator = std::less<ValueType> >
335 Source k,
const Comparator& cmp = Comparator())
366 assert(sup == (keyp ==
nullptr));
416template <
bool Stable ,
typename ValueType,
417 typename Comparator = std::less<ValueType> >
435 assert(sup == (keyp ==
nullptr));
476template <
typename ValueType,
typename Comparator>
495 assert(sup == (keyp ==
nullptr));
499 for (
Source pos = (
k_ + source) / 2; pos > 0; pos /= 2) {
506 losers_[pos].source < source)))) {
527template <
typename ValueType,
typename Comparator = std::less<ValueType> >
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));
609template <
bool Stable ,
typename ValueType,
610 typename Comparator = std::less<ValueType> >
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) {
651template <
typename ValueType,
typename 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) {
681 losers_[pos].source < source)) {
703template <
typename ValueType,
typename Comparator = std::less<ValueType> >
733 const Comparator& cmp = Comparator())
755 assert(sup == (keyp ==
nullptr));
787template <
bool Stable ,
typename ValueType,
788 typename Comparator = std::less<ValueType> >
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) {
826template <
typename ValueType,
typename 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)) {
869template <
bool Stable,
typename ValueType,
typename Comparator,
870 typename Enable =
void>
877template <
bool Stable,
typename ValueType,
typename Comparator>
879 Stable, ValueType, Comparator,
880 typename
std::
enable_if<sizeof(ValueType) <= 2 * sizeof(size_t)>::type>
886template <
bool Stable,
typename ValueType,
typename Comparator>
891template <
bool Stable,
typename ValueType,
typename Comparator,
892 typename Enable =
void>
893class LoserTreeUnguardedSwitch
896 using Type = LoserTreePointerUnguarded<Stable, ValueType, Comparator>;
899template <
bool Stable,
typename ValueType,
typename Comparator>
900class LoserTreeUnguardedSwitch<
901 Stable, ValueType, Comparator,
902 typename
std::enable_if<sizeof(ValueType) <= 2 * sizeof(size_t)>::type>
905 using Type = LoserTreeCopyUnguarded<Stable, ValueType, Comparator>;
908template <
bool Stable,
typename ValueType,
typename Comparator>
909using LoserTreeUnguarded =
910 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.