tlx
Loading...
Searching...
No Matches
LoserTreeCopyBase< ValueType, Comparator > Class Template Reference

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>

Inheritance diagram for LoserTreeCopyBase< ValueType, Comparator >:
LoserTreeCopy< Stable, ValueType, Comparator >

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

 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 ()
 

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< Loserlosers_
 array containing loser tree nodes – avoid default-constructing losers[].key
 
Comparator cmp_
 the comparator object
 
bool first_insert_
 still have to construct keys
 

Detailed Description

template<typename ValueType, typename Comparator = std::less<ValueType>>
class tlx::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.

This is a base class for the LoserTreeCopy<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.

Template Parameters
ValueTypethe element type
Comparatorcomparator to use for binary comparisons.

Definition at line 55 of file loser_tree.hpp.

Member Typedef Documentation

◆ Source

template<typename ValueType, typename Comparator = std::less<ValueType>>
using Source

size of counters and array indexes

Definition at line 59 of file loser_tree.hpp.

Constructor & Destructor Documentation

◆ LoserTreeCopyBase()

template<typename ValueType, typename Comparator = std::less<ValueType>>
LoserTreeCopyBase ( const Source & k,
const Comparator & cmp = Comparator() )
inlineexplicit

Definition at line 88 of file loser_tree.hpp.

Member Function Documentation

◆ init()

template<typename ValueType, typename Comparator = std::less<ValueType>>
void init ( )
inline

Definition at line 160 of file loser_tree.hpp.

◆ init_winner()

template<typename ValueType, typename Comparator = std::less<ValueType>>
Source init_winner ( const Source & root)
inline

Computes the winner of the competition at player root.

Called recursively (starting at 0) to build the initial tree.

Parameters
rootindex of the game to start.

Definition at line 140 of file loser_tree.hpp.

◆ insert_start()

template<typename ValueType, typename Comparator = std::less<ValueType>>
void insert_start ( const ValueType * keyp,
const Source & source,
bool sup )
inline

Initializes the player source with the element key.

Parameters
keypthe element to insert
sourceindex of the player
supflag that determines whether the value to insert is an explicit supremum sentinel.

Definition at line 110 of file loser_tree.hpp.

◆ min_source()

template<typename ValueType, typename Comparator = std::less<ValueType>>
Source min_source ( )
inline

return the index of the player with the smallest element.

Definition at line 100 of file loser_tree.hpp.

Member Data Documentation

◆ cmp_

template<typename ValueType, typename Comparator = std::less<ValueType>>
Comparator cmp_
protected

the comparator object

Definition at line 83 of file loser_tree.hpp.

◆ first_insert_

template<typename ValueType, typename Comparator = std::less<ValueType>>
bool first_insert_
protected

still have to construct keys

Definition at line 85 of file loser_tree.hpp.

◆ ik_

template<typename ValueType, typename Comparator = std::less<ValueType>>
const Source ik_
protected

number of nodes

Definition at line 76 of file loser_tree.hpp.

◆ invalid_

template<typename ValueType, typename Comparator = std::less<ValueType>>
Source invalid_
staticconstexpr

sentinel for invalid or finished Sources

Definition at line 62 of file loser_tree.hpp.

◆ k_

template<typename ValueType, typename Comparator = std::less<ValueType>>
const Source k_
protected

log_2(ik) next greater power of 2

Definition at line 78 of file loser_tree.hpp.

◆ losers_

template<typename ValueType, typename Comparator = std::less<ValueType>>
SimpleVector<Loser> losers_
protected

array containing loser tree nodes – avoid default-constructing losers[].key

Definition at line 81 of file loser_tree.hpp.


The documentation for this class was generated from the following file: