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

Guarded loser tree, using pointers to the elements instead of copying them into the tree nodes. More...

#include <loser_tree.hpp>

Inheritance diagram for LoserTreePointerBase< ValueType, Comparator >:
LoserTreePointer< 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

 LoserTreePointerBase (Source k, const Comparator &cmp=Comparator())
 
 LoserTreePointerBase (const LoserTreePointerBase &)=delete
 
LoserTreePointerBaseoperator= (const LoserTreePointerBase &)=delete
 
 LoserTreePointerBase (LoserTreePointerBase &&)=default
 
LoserTreePointerBaseoperator= (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< Loserlosers_
 array containing loser tree nodes
 
Comparator cmp_
 the comparator object
 

Detailed Description

template<typename ValueType, typename Comparator = std::less<ValueType>>
class tlx::LoserTreePointerBase< ValueType, Comparator >

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.

Member Typedef Documentation

◆ Source

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

size of counters and array indexes

Definition at line 311 of file loser_tree.hpp.

Constructor & Destructor Documentation

◆ LoserTreePointerBase() [1/3]

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

Definition at line 335 of file loser_tree.hpp.

◆ LoserTreePointerBase() [2/3]

template<typename ValueType, typename Comparator = std::less<ValueType>>
LoserTreePointerBase ( const LoserTreePointerBase< ValueType, Comparator > & )
delete

◆ LoserTreePointerBase() [3/3]

template<typename ValueType, typename Comparator = std::less<ValueType>>
LoserTreePointerBase ( LoserTreePointerBase< ValueType, Comparator > && )
default

Member Function Documentation

◆ init()

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

Definition at line 400 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 380 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 363 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 351 of file loser_tree.hpp.

◆ operator=() [1/2]

template<typename ValueType, typename Comparator = std::less<ValueType>>
LoserTreePointerBase & operator= ( const LoserTreePointerBase< ValueType, Comparator > & )
delete

◆ operator=() [2/2]

template<typename ValueType, typename Comparator = std::less<ValueType>>
LoserTreePointerBase & operator= ( LoserTreePointerBase< ValueType, Comparator > && )
default

Member Data Documentation

◆ cmp_

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

the comparator object

Definition at line 332 of file loser_tree.hpp.

◆ ik_

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

number of nodes

Definition at line 326 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 314 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 328 of file loser_tree.hpp.

◆ losers_

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

array containing loser tree nodes

Definition at line 330 of file loser_tree.hpp.


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