tlx
Loading...
Searching...
No Matches
LoserTreePointer< true, 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 LoserTreePointer< true, ValueType, Comparator >:
LoserTreePointerBase< ValueType, Comparator > LoserTreePointerBase< ValueType, Comparator >

Public Types

using Super
 
using Source
 
using Super
 
using Source
 
- Public Types inherited from LoserTreePointerBase< ValueType, Comparator >
using Source
 size of counters and array indexes
 

Public Member Functions

 LoserTreePointer (Source k, const Comparator &cmp=Comparator())
 
void delete_min_insert (const ValueType *keyp, bool sup)
 
 LoserTreePointer (Source k, const Comparator &cmp=Comparator())
 
void delete_min_insert (const ValueType *keyp, bool sup)
 
- Public Member Functions inherited from LoserTreePointerBase< ValueType, Comparator >
 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 ()
 
 LoserTreePointerBase (Source k, const Comparator &cmp=Comparator())
 
 LoserTreePointerBase (const LoserTreePointerBase &)=delete
 
 LoserTreePointerBase (LoserTreePointerBase &&)=default
 
LoserTreePointerBaseoperator= (const LoserTreePointerBase &)=delete
 
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 ()
 

Protected Attributes

const Source k_
 log_2(ik) next greater power of 2
 
SimpleVector< Loser > losers_
 array containing loser tree nodes
 
Comparator cmp_
 the comparator object
 
const Source k_
 log_2(ik) next greater power of 2
 
SimpleVector< Loser > losers_
 array containing loser tree nodes
 
Comparator cmp_
 the comparator object
 
- Protected Attributes inherited from LoserTreePointerBase< 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
 
Comparator cmp_
 the comparator object
 
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
 

Additional Inherited Members

- Static Public Attributes inherited from LoserTreePointerBase< ValueType, Comparator >
static constexpr Source invalid_
 sentinel for invalid or finished Sources
 
static constexpr Source invalid_
 sentinel for invalid or finished Sources
 

Detailed Description

template<typename ValueType, typename Comparator>
class tlx::LoserTreePointer< true, ValueType, Comparator >

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

Unstable 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.

Definition at line 478 of file loser_tree.hpp.

Member Typedef Documentation

◆ Source [1/2]

using Source

Definition at line 423 of file loser_tree.hpp.

◆ Source [2/2]

template<typename ValueType, typename Comparator>
using Source

Definition at line 483 of file loser_tree.hpp.

◆ Super [1/2]

using Super

Definition at line 422 of file loser_tree.hpp.

◆ Super [2/2]

template<typename ValueType, typename Comparator>
using Super

Definition at line 482 of file loser_tree.hpp.

Constructor & Destructor Documentation

◆ LoserTreePointer() [1/2]

template<typename ValueType, typename Comparator>
LoserTreePointer ( Source k,
const Comparator & cmp = Comparator() )
inlineexplicit

Definition at line 491 of file loser_tree.hpp.

◆ LoserTreePointer() [2/2]

LoserTreePointer ( Source k,
const Comparator & cmp = Comparator() )
inlineexplicit

Definition at line 431 of file loser_tree.hpp.

Member Function Documentation

◆ delete_min_insert() [1/2]

void delete_min_insert ( const ValueType * keyp,
bool sup )
inline

Definition at line 434 of file loser_tree.hpp.

◆ delete_min_insert() [2/2]

template<typename ValueType, typename Comparator>
void delete_min_insert ( const ValueType * keyp,
bool sup )
inline

Definition at line 494 of file loser_tree.hpp.

Member Data Documentation

◆ cmp_ [1/2]

protected

the comparator object

◆ cmp_ [2/2]

Comparator cmp_
protected

the comparator object

Definition at line 428 of file loser_tree.hpp.

◆ k_ [1/2]

protected

log_2(ik) next greater power of 2

◆ k_ [2/2]

const Source k_
protected

log_2(ik) next greater power of 2

Definition at line 426 of file loser_tree.hpp.

◆ losers_ [1/2]

protected

array containing loser tree nodes

◆ losers_ [2/2]

SimpleVector<Loser> losers_
protected

array containing loser tree nodes

Definition at line 427 of file loser_tree.hpp.


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