tlx
|
Guarded loser tree, using pointers to the elements instead of copying them into the tree nodes. More...
#include <loser_tree.hpp>
Classes | |
struct | Loser |
Internal representation of a loser tree player/node. More... |
Public Types | |
using | Source |
size of counters and array indexes |
Public Member Functions | |
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. | |
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 () |
Static Public Attributes | |
static constexpr Source | invalid_ |
sentinel for invalid or finished Sources |
Protected Attributes | |
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 | |
Comparator | cmp_ |
the comparator object |
Guarded loser tree, using pointers to the elements instead of copying them into the tree nodes.
This is a base class for the LoserTreePointer<true> and <false> classes.
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.
Definition at line 307 of file loser_tree.hpp.
using Source |
size of counters and array indexes
Definition at line 311 of file loser_tree.hpp.
|
inlineexplicit |
Definition at line 335 of file loser_tree.hpp.
|
delete |
|
default |
|
inline |
Definition at line 400 of file loser_tree.hpp.
|
inline |
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 380 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 363 of file loser_tree.hpp.
|
inline |
return the index of the player with the smallest element.
Definition at line 351 of file loser_tree.hpp.
|
delete |
|
default |
|
protected |
the comparator object
Definition at line 332 of file loser_tree.hpp.
|
protected |
number of nodes
Definition at line 326 of file loser_tree.hpp.
|
staticconstexpr |
sentinel for invalid or finished Sources
Definition at line 314 of file loser_tree.hpp.
|
protected |
log_2(ik) next greater power of 2
Definition at line 328 of file loser_tree.hpp.
|
protected |
array containing loser tree nodes
Definition at line 330 of file loser_tree.hpp.