tlx
|
Guarded loser tree/tournament tree, either copying the whole element into the tree structure, or looking up the element via the index. More...
#include <loser_tree.hpp>
Public Types | |
using | Super = LoserTreeCopyBase< ValueType, Comparator > |
using | Source = typename Super::Source |
Public Types inherited from LoserTreeCopyBase< ValueType, Comparator > | |
using | Source = uint32_t |
size of counters and array indexes More... | |
Public Member Functions | |
LoserTreeCopy (const Source &k, const Comparator &cmp=Comparator()) | |
void | delete_min_insert (const ValueType *keyp, bool sup) |
Public Member Functions inherited from LoserTreeCopyBase< ValueType, Comparator > | |
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 () |
Additional Inherited Members | |
Static Public Attributes inherited from LoserTreeCopyBase< ValueType, Comparator > | |
static constexpr Source | invalid_ |
sentinel for invalid or finished Sources More... | |
Protected Attributes inherited from LoserTreeCopyBase< ValueType, Comparator > | |
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... | |
Guarded loser tree/tournament tree, either copying the whole element into the tree structure, or looking up the element via the index.
Unstable specialization of LoserTreeCopyBase.
Guarding is done explicitly through one flag sup per element, inf is not needed due to a better initialization routine. This is a well-performing variant.
ValueType | the element type |
Comparator | comparator to use for binary comparisons. |
Definition at line 182 of file loser_tree.hpp.