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 |
![]() | |
using | Source = uint32_t |
size of counters and array indexes | |
Public Member Functions | |
LoserTreeCopy (const Source &k, const Comparator &cmp=Comparator()) | |
void | delete_min_insert (const ValueType *keyp, bool sup) |
![]() | |
LoserTreeCopyBase (const Source &k, const Comparator &cmp=Comparator()) | |
Source | min_source () |
return the index of the player with the smallest element. | |
void | insert_start (const ValueType *keyp, const Source &source, bool sup) |
Initializes the player source with the element key. | |
Source | init_winner (const Source &root) |
Computes the winner of the competition at player root. | |
void | init () |
Additional Inherited Members | |
![]() | |
static constexpr Source | invalid_ |
sentinel for invalid or finished Sources | |
![]() | |
const Source | ik_ |
number of nodes | |
const Source | k_ |
log_2(ik) next greater power of 2 | |
SimpleVector< Loser > | losers_ |
array containing loser tree nodes – avoid default-constructing losers[].key | |
Comparator | cmp_ |
the comparator object | |
bool | first_insert_ |
still have to construct keys | |
Guarded loser tree/tournament tree, either copying the whole element into the tree structure, or looking up the element via the index.
Stable 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 248 of file loser_tree.hpp.