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 |
using | Source |
Public Types inherited from LoserTreeCopyBase< ValueType, Comparator > | |
using | Source |
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) |
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. | |
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 () |
Protected Attributes | |
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 | |
Protected Attributes inherited from LoserTreeCopyBase< ValueType, Comparator > | |
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 |
Additional Inherited Members | |
Static Public Attributes inherited from LoserTreeCopyBase< ValueType, Comparator > | |
static constexpr Source | invalid_ |
sentinel for invalid or finished Sources |
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.
using Source |
Definition at line 253 of file loser_tree.hpp.
using Super |
Definition at line 252 of file loser_tree.hpp.
|
inlineexplicit |
Definition at line 261 of file loser_tree.hpp.
|
inline |
Definition at line 266 of file loser_tree.hpp.
|
protected |
the comparator object
|
protected |
log_2(ik) next greater power of 2
|
protected |
array containing loser tree nodes – avoid default-constructing losers[].key