tlx
|
Loser/Tournament tree variants. More...
Classes | |
struct | LoserTreeCopyBase< ValueType, Comparator >::Loser |
Internal representation of a loser tree player/node. More... | |
class | LoserTreeCopyBase< ValueType, Comparator > |
Guarded loser tree/tournament tree, either copying the whole element into the tree structure, or looking up the element via the index. More... | |
class | LoserTreeCopy< Stable, ValueType, Comparator > |
Guarded loser tree/tournament tree, either copying the whole element into the tree structure, or looking up the element via the index. More... | |
class | LoserTreeCopy< true, ValueType, Comparator > |
Guarded loser tree/tournament tree, either copying the whole element into the tree structure, or looking up the element via the index. More... | |
struct | LoserTreePointerBase< ValueType, Comparator >::Loser |
Internal representation of a loser tree player/node. More... | |
class | LoserTreePointerBase< ValueType, Comparator > |
Guarded loser tree, using pointers to the elements instead of copying them into the tree nodes. More... | |
class | LoserTreePointer< Stable, ValueType, Comparator > |
Guarded loser tree, using pointers to the elements instead of copying them into the tree nodes. More... | |
class | LoserTreePointer< true, ValueType, Comparator > |
Guarded loser tree, using pointers to the elements instead of copying them into the tree nodes. More... | |
struct | LoserTreeCopyUnguardedBase< ValueType, Comparator >::Loser |
Internal representation of a loser tree player/node. More... | |
class | LoserTreeCopyUnguardedBase< ValueType, Comparator > |
Unguarded loser tree, copying the whole element into the tree structure. More... | |
class | LoserTreeCopyUnguarded< Stable, ValueType, Comparator > |
class | LoserTreeCopyUnguarded< true, ValueType, Comparator > |
struct | LoserTreePointerUnguardedBase< ValueType, Comparator >::Loser |
Internal representation of a loser tree player/node. More... | |
class | LoserTreePointerUnguardedBase< ValueType, Comparator > |
Unguarded loser tree, keeping only pointers to the elements in the tree structure. More... | |
class | LoserTreePointerUnguarded< Stable, ValueType, Comparator > |
class | LoserTreePointerUnguarded< true, ValueType, Comparator > |
class | LoserTreeSwitch< Stable, ValueType, Comparator, Enable > |
Typedefs | |
using | Source = uint32_t |
size of counters and array indexes More... | |
using | Super = LoserTreeCopyBase< ValueType, Comparator > |
using | Source = typename Super::Source |
using | Super = LoserTreeCopyBase< ValueType, Comparator > |
using | Source = typename Super::Source |
using | Source = uint32_t |
size of counters and array indexes More... | |
using | Super = LoserTreePointerBase< ValueType, Comparator > |
using | Source = typename Super::Source |
using | Super = LoserTreePointerBase< ValueType, Comparator > |
using | Source = typename Super::Source |
using | Source = uint32_t |
size of counters and array indexes More... | |
using | Super = LoserTreeCopyUnguardedBase< ValueType, Comparator > |
using | Source = typename Super::Source |
using | Super = LoserTreeCopyUnguardedBase< ValueType, Comparator > |
using | Source = typename Super::Source |
using | Source = uint32_t |
size of counters and array indexes More... | |
using | Super = LoserTreePointerUnguardedBase< ValueType, Comparator > |
using | Source = typename Super::Source |
using | Super = LoserTreePointerUnguardedBase< ValueType, Comparator > |
using | Source = typename Super::Source |
using | Type = LoserTreePointer< Stable, ValueType, Comparator > |
Functions | |
LoserTreeCopyBase (const Source &k, const Comparator &cmp=Comparator()) | |
Source | min_source () |
return the index of the player with the smallest element. More... | |
void | insert_start (const ValueType *keyp, const Source &source, bool sup) |
Initializes the player source with the element key. More... | |
Source | init_winner (const Source &root) |
Computes the winner of the competition at player root. More... | |
void | init () |
LoserTreeCopy (const Source &k, const Comparator &cmp=Comparator()) | |
void | delete_min_insert (const ValueType *keyp, bool sup) |
LoserTreeCopy (const Source &k, const Comparator &cmp=Comparator()) | |
void | delete_min_insert (const ValueType *keyp, bool sup) |
LoserTreePointerBase (Source k, const Comparator &cmp=Comparator()) | |
LoserTreePointerBase (const LoserTreePointerBase &)=delete | |
LoserTreePointerBase & | operator= (const LoserTreePointerBase &)=delete |
LoserTreePointerBase (LoserTreePointerBase &&)=default | |
LoserTreePointerBase & | operator= (LoserTreePointerBase &&)=default |
Source | min_source () |
return the index of the player with the smallest element. More... | |
void | insert_start (const ValueType *keyp, const Source &source, bool sup) |
Initializes the player source with the element key. More... | |
Source | init_winner (const Source &root) |
Computes the winner of the competition at player root. More... | |
void | init () |
LoserTreePointer (Source k, const Comparator &cmp=Comparator()) | |
void | delete_min_insert (const ValueType *keyp, bool sup) |
LoserTreePointer (Source k, const Comparator &cmp=Comparator()) | |
void | delete_min_insert (const ValueType *keyp, bool sup) |
LoserTreeCopyUnguardedBase (Source k, const ValueType &sentinel, const Comparator &cmp=Comparator()) | |
Source | min_source () |
return the index of the player with the smallest element. More... | |
void | insert_start (const ValueType *keyp, const Source &source, bool sup) |
Source | init_winner (const Source &root) |
void | init () |
LoserTreeCopyUnguarded (Source k, const ValueType &sentinel, const Comparator &cmp=Comparator()) | |
void | delete_min_insert (const ValueType *keyp, bool sup) |
LoserTreeCopyUnguarded (Source k, const ValueType &sentinel, const Comparator &comp=Comparator()) | |
void | delete_min_insert (const ValueType *keyp, bool sup) |
LoserTreePointerUnguardedBase (const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator()) | |
LoserTreePointerUnguardedBase (const LoserTreePointerUnguardedBase &other)=delete | |
LoserTreePointerUnguardedBase & | operator= (const LoserTreePointerUnguardedBase &)=delete |
Source | min_source () |
void | insert_start (const ValueType *keyp, const Source &source, bool sup) |
Source | init_winner (const Source &root) |
void | init () |
LoserTreePointerUnguarded (const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator()) | |
void | delete_min_insert (const ValueType *keyp, bool sup) |
LoserTreePointerUnguarded (const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator()) | |
void | delete_min_insert (const ValueType *keyp, bool sup) |
Variables | |
static constexpr Source | invalid_ |
sentinel for invalid or finished Sources More... | |
bool | sup |
flag, true iff is a virtual maximum sentinel More... | |
Source | source |
index of source More... | |
ValueType | key |
copy of key value of the element in this node More... | |
const Source | ik_ |
number of nodes More... | |
const Source | k_ |
log_2(ik) next greater power of 2 More... | |
SimpleVector< Loser > | losers_ |
array containing loser tree nodes – avoid default-constructing losers[].key More... | |
Comparator | cmp_ |
the comparator object More... | |
bool | first_insert_ |
still have to construct keys More... | |
static constexpr Source | invalid_ |
sentinel for invalid or finished Sources More... | |
Source | source |
index of source More... | |
const ValueType * | keyp |
pointer to key value of the element in this node More... | |
const Source | ik_ |
number of nodes More... | |
const Source | k_ |
log_2(ik) next greater power of 2 More... | |
SimpleVector< Loser > | losers_ |
array containing loser tree nodes More... | |
Comparator | cmp_ |
the comparator object More... | |
static constexpr Source | invalid_ |
sentinel for invalid or finished Sources More... | |
Source | source |
index of source More... | |
ValueType | key |
copy of key value of the element in this node More... | |
Source | ik_ |
number of nodes More... | |
Source | k_ |
log_2(ik) next greater power of 2 More... | |
SimpleVector< Loser > | losers_ |
array containing loser tree nodes More... | |
Comparator | cmp_ |
the comparator object More... | |
static constexpr Source | invalid_ |
sentinel for invalid or finished Sources More... | |
Source | source |
index of source More... | |
const ValueType * | keyp |
copy of key value of the element in this node More... | |
Source | ik_ |
number of nodes More... | |
Source | k_ |
log_2(ik) next greater power of 2 More... | |
SimpleVector< Loser > | losers_ |
array containing loser tree nodes More... | |
Comparator | cmp_ |
the comparator object More... | |
Loser/Tournament tree variants.
using Source = uint32_t |
size of counters and array indexes
Definition at line 74 of file loser_tree.hpp.
using Source = typename Super::Source |
Definition at line 201 of file loser_tree.hpp.
using Source = typename Super::Source |
Definition at line 268 of file loser_tree.hpp.
using Source = uint32_t |
size of counters and array indexes
Definition at line 326 of file loser_tree.hpp.
using Source = typename Super::Source |
Definition at line 438 of file loser_tree.hpp.
using Source = typename Super::Source |
Definition at line 498 of file loser_tree.hpp.
using Source = uint32_t |
size of counters and array indexes
Definition at line 548 of file loser_tree.hpp.
using Source = typename Super::Source |
Definition at line 632 of file loser_tree.hpp.
using Source = typename Super::Source |
Definition at line 673 of file loser_tree.hpp.
using Source = uint32_t |
size of counters and array indexes
Definition at line 724 of file loser_tree.hpp.
using Source = typename Super::Source |
Definition at line 810 of file loser_tree.hpp.
using Source = typename Super::Source |
Definition at line 848 of file loser_tree.hpp.
using Super = LoserTreeCopyBase<ValueType, Comparator> |
Definition at line 200 of file loser_tree.hpp.
using Super = LoserTreeCopyBase<ValueType, Comparator> |
Definition at line 267 of file loser_tree.hpp.
using Super = LoserTreePointerBase<ValueType, Comparator> |
Definition at line 437 of file loser_tree.hpp.
using Super = LoserTreePointerBase<ValueType, Comparator> |
Definition at line 497 of file loser_tree.hpp.
using Super = LoserTreeCopyUnguardedBase<ValueType, Comparator> |
Definition at line 631 of file loser_tree.hpp.
using Super = LoserTreeCopyUnguardedBase<ValueType, Comparator> |
Definition at line 672 of file loser_tree.hpp.
using Super = LoserTreePointerUnguardedBase<ValueType, Comparator> |
Definition at line 809 of file loser_tree.hpp.
using Super = LoserTreePointerUnguardedBase<ValueType, Comparator> |
Definition at line 847 of file loser_tree.hpp.
using Type = LoserTreePointer<Stable, ValueType, Comparator> |
Definition at line 890 of file loser_tree.hpp.
|
inline |
Definition at line 214 of file loser_tree.hpp.
|
inline |
Definition at line 281 of file loser_tree.hpp.
|
inline |
Definition at line 449 of file loser_tree.hpp.
|
inline |
Definition at line 509 of file loser_tree.hpp.
|
inline |
Definition at line 645 of file loser_tree.hpp.
|
inline |
Definition at line 686 of file loser_tree.hpp.
|
inline |
Definition at line 822 of file loser_tree.hpp.
|
inline |
Definition at line 860 of file loser_tree.hpp.
|
inline |
Definition at line 175 of file loser_tree.hpp.
|
inline |
Definition at line 415 of file loser_tree.hpp.
|
inline |
Definition at line 618 of file loser_tree.hpp.
|
inline |
Definition at line 796 of file loser_tree.hpp.
Computes the winner of the competition at player root.
Called recursively (starting at 0) to build the initial tree.
root | index of the game to start. |
Definition at line 155 of file loser_tree.hpp.
Computes the winner of the competition at player root.
Called recursively (starting at 0) to build the initial tree.
root | index of the game to start. |
Definition at line 395 of file loser_tree.hpp.
Definition at line 600 of file loser_tree.hpp.
Definition at line 778 of file loser_tree.hpp.
|
inline |
Initializes the player source with the element key.
keyp | the element to insert |
source | index of the player |
sup | flag that determines whether the value to insert is an explicit supremum sentinel. |
Definition at line 125 of file loser_tree.hpp.
|
inline |
Initializes the player source with the element key.
keyp | the element to insert |
source | index of the player |
sup | flag that determines whether the value to insert is an explicit supremum sentinel. |
Definition at line 378 of file loser_tree.hpp.
|
inline |
Definition at line 589 of file loser_tree.hpp.
|
inline |
Definition at line 767 of file loser_tree.hpp.
|
inlineexplicit |
Definition at line 209 of file loser_tree.hpp.
|
inlineexplicit |
Definition at line 276 of file loser_tree.hpp.
|
inlineexplicit |
Definition at line 103 of file loser_tree.hpp.
|
inline |
Definition at line 640 of file loser_tree.hpp.
|
inline |
Definition at line 681 of file loser_tree.hpp.
|
inline |
Definition at line 572 of file loser_tree.hpp.
|
inlineexplicit |
Definition at line 446 of file loser_tree.hpp.
|
inlineexplicit |
Definition at line 506 of file loser_tree.hpp.
|
delete |
|
default |
|
inlineexplicit |
Definition at line 350 of file loser_tree.hpp.
|
inline |
Definition at line 818 of file loser_tree.hpp.
|
inline |
Definition at line 856 of file loser_tree.hpp.
|
delete |
|
inline |
Definition at line 748 of file loser_tree.hpp.
|
inline |
return the index of the player with the smallest element.
Definition at line 115 of file loser_tree.hpp.
|
inline |
return the index of the player with the smallest element.
Definition at line 366 of file loser_tree.hpp.
|
inline |
return the index of the player with the smallest element.
Definition at line 583 of file loser_tree.hpp.
|
inline |
Definition at line 765 of file loser_tree.hpp.
|
delete |
|
delete |
|
default |
|
protected |
the comparator object
Definition at line 98 of file loser_tree.hpp.
|
protected |
the comparator object
Definition at line 347 of file loser_tree.hpp.
|
protected |
the comparator object
Definition at line 569 of file loser_tree.hpp.
|
protected |
the comparator object
Definition at line 745 of file loser_tree.hpp.
|
protected |
still have to construct keys
Definition at line 100 of file loser_tree.hpp.
|
protected |
number of nodes
Definition at line 91 of file loser_tree.hpp.
|
protected |
number of nodes
Definition at line 341 of file loser_tree.hpp.
|
protected |
number of nodes
Definition at line 563 of file loser_tree.hpp.
|
protected |
number of nodes
Definition at line 739 of file loser_tree.hpp.
|
staticconstexpr |
sentinel for invalid or finished Sources
Definition at line 77 of file loser_tree.hpp.
|
staticconstexpr |
sentinel for invalid or finished Sources
Definition at line 329 of file loser_tree.hpp.
|
staticconstexpr |
sentinel for invalid or finished Sources
Definition at line 551 of file loser_tree.hpp.
|
staticconstexpr |
sentinel for invalid or finished Sources
Definition at line 727 of file loser_tree.hpp.
|
protected |
log_2(ik) next greater power of 2
Definition at line 93 of file loser_tree.hpp.
|
protected |
log_2(ik) next greater power of 2
Definition at line 343 of file loser_tree.hpp.
|
protected |
log_2(ik) next greater power of 2
Definition at line 565 of file loser_tree.hpp.
|
protected |
log_2(ik) next greater power of 2
Definition at line 741 of file loser_tree.hpp.
ValueType key |
copy of key value of the element in this node
Definition at line 87 of file loser_tree.hpp.
ValueType key |
copy of key value of the element in this node
Definition at line 559 of file loser_tree.hpp.
const ValueType* keyp |
pointer to key value of the element in this node
Definition at line 337 of file loser_tree.hpp.
const ValueType* keyp |
copy of key value of the element in this node
Definition at line 735 of file loser_tree.hpp.
|
protected |
array containing loser tree nodes – avoid default-constructing losers[].key
Definition at line 96 of file loser_tree.hpp.
|
protected |
array containing loser tree nodes
Definition at line 345 of file loser_tree.hpp.
|
protected |
array containing loser tree nodes
Definition at line 567 of file loser_tree.hpp.
|
protected |
array containing loser tree nodes
Definition at line 743 of file loser_tree.hpp.
Source source |
index of source
Definition at line 85 of file loser_tree.hpp.
Source source |
index of source
Definition at line 335 of file loser_tree.hpp.
Source source |
index of source
Definition at line 557 of file loser_tree.hpp.
Source source |
index of source
Definition at line 733 of file loser_tree.hpp.
bool sup |
flag, true iff is a virtual maximum sentinel
Definition at line 83 of file loser_tree.hpp.