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>
900template <
bool Stable,
typename ValueType,
typename Comparator>
902 Stable, ValueType, Comparator,
903 typename
std::
enable_if<sizeof(ValueType) <= 2 * sizeof(size_t)>::type>
909template <
bool Stable,
typename ValueType,
typename Comparator>
LoserTreeCopyBase(const Source &k, const Comparator &cmp=Comparator())
static constexpr Source invalid_
void insert_start(const ValueType *keyp, const Source &source, bool sup)
Initializes the player source with the element key.
SimpleVector< Loser > losers_
Source min_source()
return the index of the player with the smallest element.
std::uint32_t Source
size of counters and array indexes
Source init_winner(const Source &root)
Computes the winner of the competition at player root.
static constexpr Source invalid_
LoserTreeCopyUnguardedBase(Source k, const ValueType &sentinel, const Comparator &cmp=Comparator())
void insert_start(const ValueType *keyp, const Source &source, bool sup)
SimpleVector< Loser > losers_
Source min_source()
return the index of the player with the smallest element.
std::uint32_t Source
size of counters and array indexes
Source init_winner(const Source &root)
typename Super::Source Source
void delete_min_insert(const ValueType *keyp, bool sup)
LoserTreeCopyUnguarded(Source k, const ValueType &sentinel, const Comparator &comp=Comparator())
LoserTreeCopyUnguardedBase< ValueType, Comparator > Super
typename Super::Source Source
SimpleVector< Loser > losers_
void delete_min_insert(const ValueType *keyp, bool sup)
Comparator cmp_
the comparator object
LoserTreeCopyUnguarded(Source k, const ValueType &sentinel, const Comparator &cmp=Comparator())
LoserTreeCopyUnguardedBase< ValueType, Comparator > Super
typename Super::Source Source
LoserTreeCopy(const Source &k, const Comparator &cmp=Comparator())
LoserTreeCopyBase< ValueType, Comparator > Super
void delete_min_insert(const ValueType *keyp, bool sup)
Guarded loser tree/tournament tree, either copying the whole element into the tree structure,...
typename Super::Source Source
LoserTreeCopy(const Source &k, const Comparator &cmp=Comparator())
SimpleVector< Loser > losers_
LoserTreeCopyBase< ValueType, Comparator > Super
void delete_min_insert(const ValueType *keyp, bool sup)
Comparator cmp_
the comparator object
static constexpr Source invalid_
void insert_start(const ValueType *keyp, const Source &source, bool sup)
Initializes the player source with the element key.
LoserTreePointerBase(LoserTreePointerBase &&)=default
LoserTreePointerBase(const LoserTreePointerBase &)=delete
SimpleVector< Loser > losers_
Source min_source()
return the index of the player with the smallest element.
LoserTreePointerBase(Source k, const Comparator &cmp=Comparator())
LoserTreePointerBase & operator=(const LoserTreePointerBase &)=delete
std::uint32_t Source
size of counters and array indexes
Source init_winner(const Source &root)
Computes the winner of the competition at player root.
LoserTreePointerUnguardedBase(const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator())
static constexpr Source invalid_
void insert_start(const ValueType *keyp, const Source &source, bool sup)
LoserTreePointerUnguardedBase & operator=(const LoserTreePointerUnguardedBase &)=delete
SimpleVector< Loser > losers_
LoserTreePointerUnguardedBase(const LoserTreePointerUnguardedBase &other)=delete
std::uint32_t Source
size of counters and array indexes
Source init_winner(const Source &root)
typename Super::Source Source
LoserTreePointerUnguarded(const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator())
void delete_min_insert(const ValueType *keyp, bool sup)
LoserTreePointerUnguardedBase< ValueType, Comparator > Super
typename Super::Source Source
LoserTreePointerUnguarded(const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator())
SimpleVector< Loser > losers_
void delete_min_insert(const ValueType *keyp, bool sup)
Comparator cmp_
the comparator object
LoserTreePointerUnguardedBase< ValueType, Comparator > Super
typename Super::Source Source
LoserTreePointer(Source k, const Comparator &cmp=Comparator())
void delete_min_insert(const ValueType *keyp, bool sup)
LoserTreePointerBase< ValueType, Comparator > Super
Guarded loser tree, using pointers to the elements instead of copying them into the tree nodes.
typename Super::Source Source
LoserTreePointer(Source k, const Comparator &cmp=Comparator())
SimpleVector< Loser > losers_
void delete_min_insert(const ValueType *keyp, bool sup)
Comparator cmp_
the comparator object
LoserTreePointerBase< ValueType, Comparator > Super
LoserTreeCopy< Stable, ValueType, Comparator > Type
LoserTreePointer< Stable, ValueType, Comparator > Type
LoserTreeCopyUnguarded< Stable, ValueType, Comparator > Type
LoserTreePointerUnguarded< Stable, ValueType, Comparator > Type
Simpler non-growing vector without initialization.
typename LoserTreeSwitch< Stable, ValueType, Comparator >::Type LoserTree
typename LoserTreeUnguardedSwitch< Stable, ValueType, Comparator >::Type LoserTreeUnguarded
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.
bool sup
flag, true iff is a virtual maximum sentinel
Source source
index of source
ValueType key
copy of key value of the element in this node
Internal representation of a loser tree player/node.
Source source
index of source
ValueType key
copy of key value of the element in this node
Internal representation of a loser tree player/node.
const ValueType * keyp
pointer to key value of the element in this node
Source source
index of source
Internal representation of a loser tree player/node.
const ValueType * keyp
copy of key value of the element in this node
Source source
index of source
SFINAE enable_if – copy of std::enable_if<> with less extra cruft.