tlx

Loser/Tournament tree variants. More...

Classes

struct  LoserTreeCopyBase< ValueType, Comparator >::Loser
 Internal representation of a loser tree player/node. More...
 
class  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. More...
 
class  LoserTreeCopy< Stable, ValueType, Comparator >
 Guarded loser tree/tournament tree, either copying the whole element into the tree structure, or looking up the element via the index. More...
 
class  LoserTreeCopy< true, ValueType, Comparator >
 Guarded loser tree/tournament tree, either copying the whole element into the tree structure, or looking up the element via the index. More...
 
struct  LoserTreePointerBase< ValueType, Comparator >::Loser
 Internal representation of a loser tree player/node. More...
 
class  LoserTreePointerBase< ValueType, Comparator >
 Guarded loser tree, using pointers to the elements instead of copying them into the tree nodes. More...
 
class  LoserTreePointer< Stable, ValueType, Comparator >
 Guarded loser tree, using pointers to the elements instead of copying them into the tree nodes. More...
 
class  LoserTreePointer< true, ValueType, Comparator >
 Guarded loser tree, using pointers to the elements instead of copying them into the tree nodes. More...
 
struct  LoserTreeCopyUnguardedBase< ValueType, Comparator >::Loser
 Internal representation of a loser tree player/node. More...
 
class  LoserTreeCopyUnguardedBase< ValueType, Comparator >
 Unguarded loser tree, copying the whole element into the tree structure. More...
 
class  LoserTreeCopyUnguarded< Stable, ValueType, Comparator >
 
class  LoserTreeCopyUnguarded< true, ValueType, Comparator >
 
struct  LoserTreePointerUnguardedBase< ValueType, Comparator >::Loser
 Internal representation of a loser tree player/node. More...
 
class  LoserTreePointerUnguardedBase< ValueType, Comparator >
 Unguarded loser tree, keeping only pointers to the elements in the tree structure. More...
 
class  LoserTreePointerUnguarded< Stable, ValueType, Comparator >
 
class  LoserTreePointerUnguarded< true, ValueType, Comparator >
 
class  LoserTreeSwitch< Stable, ValueType, Comparator, Enable >
 

Typedefs

using Source = uint32_t
 size of counters and array indexes More...
 
using Super = LoserTreeCopyBase< ValueType, Comparator >
 
using Source = typename Super::Source
 
using Super = LoserTreeCopyBase< ValueType, Comparator >
 
using Source = typename Super::Source
 
using Source = uint32_t
 size of counters and array indexes More...
 
using Super = LoserTreePointerBase< ValueType, Comparator >
 
using Source = typename Super::Source
 
using Super = LoserTreePointerBase< ValueType, Comparator >
 
using Source = typename Super::Source
 
using Source = uint32_t
 size of counters and array indexes More...
 
using Super = LoserTreeCopyUnguardedBase< ValueType, Comparator >
 
using Source = typename Super::Source
 
using Super = LoserTreeCopyUnguardedBase< ValueType, Comparator >
 
using Source = typename Super::Source
 
using Source = uint32_t
 size of counters and array indexes More...
 
using Super = LoserTreePointerUnguardedBase< ValueType, Comparator >
 
using Source = typename Super::Source
 
using Super = LoserTreePointerUnguardedBase< ValueType, Comparator >
 
using Source = typename Super::Source
 
using Type = LoserTreePointer< Stable, ValueType, Comparator >
 

Functions

 LoserTreeCopyBase (const Source &k, const Comparator &cmp=Comparator())
 
Source min_source ()
 return the index of the player with the smallest element. More...
 
void insert_start (const ValueType *keyp, const Source &source, bool sup)
 Initializes the player source with the element key. More...
 
Source init_winner (const Source &root)
 Computes the winner of the competition at player root. More...
 
void init ()
 
 LoserTreeCopy (const Source &k, const Comparator &cmp=Comparator())
 
void delete_min_insert (const ValueType *keyp, bool sup)
 
 LoserTreeCopy (const Source &k, const Comparator &cmp=Comparator())
 
void delete_min_insert (const ValueType *keyp, bool sup)
 
 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. More...
 
void insert_start (const ValueType *keyp, const Source &source, bool sup)
 Initializes the player source with the element key. More...
 
Source init_winner (const Source &root)
 Computes the winner of the competition at player root. More...
 
void init ()
 
 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)
 
 LoserTreeCopyUnguardedBase (Source k, const ValueType &sentinel, const Comparator &cmp=Comparator())
 
Source min_source ()
 return the index of the player with the smallest element. More...
 
void insert_start (const ValueType *keyp, const Source &source, bool sup)
 
Source init_winner (const Source &root)
 
void init ()
 
 LoserTreeCopyUnguarded (Source k, const ValueType &sentinel, const Comparator &cmp=Comparator())
 
void delete_min_insert (const ValueType *keyp, bool sup)
 
 LoserTreeCopyUnguarded (Source k, const ValueType &sentinel, const Comparator &comp=Comparator())
 
void delete_min_insert (const ValueType *keyp, bool sup)
 
 LoserTreePointerUnguardedBase (const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator())
 
 LoserTreePointerUnguardedBase (const LoserTreePointerUnguardedBase &other)=delete
 
LoserTreePointerUnguardedBaseoperator= (const LoserTreePointerUnguardedBase &)=delete
 
Source min_source ()
 
void insert_start (const ValueType *keyp, const Source &source, bool sup)
 
Source init_winner (const Source &root)
 
void init ()
 
 LoserTreePointerUnguarded (const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator())
 
void delete_min_insert (const ValueType *keyp, bool sup)
 
 LoserTreePointerUnguarded (const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator())
 
void delete_min_insert (const ValueType *keyp, bool sup)
 

Variables

static constexpr Source invalid_
 sentinel for invalid or finished Sources More...
 
bool sup
 flag, true iff is a virtual maximum sentinel More...
 
Source source
 index of source More...
 
ValueType key
 copy of key value of the element in this node More...
 
const Source ik_
 number of nodes More...
 
const Source k_
 log_2(ik) next greater power of 2 More...
 
SimpleVector< Loserlosers_
 array containing loser tree nodes – avoid default-constructing losers[].key More...
 
Comparator cmp_
 the comparator object More...
 
bool first_insert_
 still have to construct keys More...
 
static constexpr Source invalid_
 sentinel for invalid or finished Sources More...
 
Source source
 index of source More...
 
const ValueType * keyp
 pointer to key value of the element in this node More...
 
const Source ik_
 number of nodes More...
 
const Source k_
 log_2(ik) next greater power of 2 More...
 
SimpleVector< Loserlosers_
 array containing loser tree nodes More...
 
Comparator cmp_
 the comparator object More...
 
static constexpr Source invalid_
 sentinel for invalid or finished Sources More...
 
Source source
 index of source More...
 
ValueType key
 copy of key value of the element in this node More...
 
Source ik_
 number of nodes More...
 
Source k_
 log_2(ik) next greater power of 2 More...
 
SimpleVector< Loserlosers_
 array containing loser tree nodes More...
 
Comparator cmp_
 the comparator object More...
 
static constexpr Source invalid_
 sentinel for invalid or finished Sources More...
 
Source source
 index of source More...
 
const ValueType * keyp
 copy of key value of the element in this node More...
 
Source ik_
 number of nodes More...
 
Source k_
 log_2(ik) next greater power of 2 More...
 
SimpleVector< Loserlosers_
 array containing loser tree nodes More...
 
Comparator cmp_
 the comparator object More...
 

Detailed Description

Loser/Tournament tree variants.

Typedef Documentation

◆ Source [1/12]

using Source = uint32_t

size of counters and array indexes

Definition at line 74 of file loser_tree.hpp.

◆ Source [2/12]

using Source = typename Super::Source

Definition at line 201 of file loser_tree.hpp.

◆ Source [3/12]

using Source = typename Super::Source

Definition at line 268 of file loser_tree.hpp.

◆ Source [4/12]

using Source = uint32_t

size of counters and array indexes

Definition at line 326 of file loser_tree.hpp.

◆ Source [5/12]

using Source = typename Super::Source

Definition at line 438 of file loser_tree.hpp.

◆ Source [6/12]

using Source = typename Super::Source

Definition at line 498 of file loser_tree.hpp.

◆ Source [7/12]

using Source = uint32_t

size of counters and array indexes

Definition at line 548 of file loser_tree.hpp.

◆ Source [8/12]

using Source = typename Super::Source

Definition at line 632 of file loser_tree.hpp.

◆ Source [9/12]

using Source = typename Super::Source

Definition at line 673 of file loser_tree.hpp.

◆ Source [10/12]

using Source = uint32_t

size of counters and array indexes

Definition at line 724 of file loser_tree.hpp.

◆ Source [11/12]

using Source = typename Super::Source

Definition at line 810 of file loser_tree.hpp.

◆ Source [12/12]

using Source = typename Super::Source

Definition at line 848 of file loser_tree.hpp.

◆ Super [1/8]

using Super = LoserTreeCopyBase<ValueType, Comparator>

Definition at line 200 of file loser_tree.hpp.

◆ Super [2/8]

using Super = LoserTreeCopyBase<ValueType, Comparator>

Definition at line 267 of file loser_tree.hpp.

◆ Super [3/8]

using Super = LoserTreePointerBase<ValueType, Comparator>

Definition at line 437 of file loser_tree.hpp.

◆ Super [4/8]

using Super = LoserTreePointerBase<ValueType, Comparator>

Definition at line 497 of file loser_tree.hpp.

◆ Super [5/8]

using Super = LoserTreeCopyUnguardedBase<ValueType, Comparator>

Definition at line 631 of file loser_tree.hpp.

◆ Super [6/8]

using Super = LoserTreeCopyUnguardedBase<ValueType, Comparator>

Definition at line 672 of file loser_tree.hpp.

◆ Super [7/8]

using Super = LoserTreePointerUnguardedBase<ValueType, Comparator>

Definition at line 809 of file loser_tree.hpp.

◆ Super [8/8]

using Super = LoserTreePointerUnguardedBase<ValueType, Comparator>

Definition at line 847 of file loser_tree.hpp.

◆ Type

using Type = LoserTreePointer<Stable, ValueType, Comparator>

Definition at line 890 of file loser_tree.hpp.

Function Documentation

◆ delete_min_insert() [1/8]

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

Definition at line 214 of file loser_tree.hpp.

◆ delete_min_insert() [2/8]

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

Definition at line 281 of file loser_tree.hpp.

◆ delete_min_insert() [3/8]

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

Definition at line 449 of file loser_tree.hpp.

◆ delete_min_insert() [4/8]

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

Definition at line 509 of file loser_tree.hpp.

◆ delete_min_insert() [5/8]

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

Definition at line 645 of file loser_tree.hpp.

◆ delete_min_insert() [6/8]

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

Definition at line 686 of file loser_tree.hpp.

◆ delete_min_insert() [7/8]

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

Definition at line 822 of file loser_tree.hpp.

◆ delete_min_insert() [8/8]

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

Definition at line 860 of file loser_tree.hpp.

◆ init() [1/4]

void init ( )
inline

Definition at line 175 of file loser_tree.hpp.

◆ init() [2/4]

void init ( )
inline

Definition at line 415 of file loser_tree.hpp.

◆ init() [3/4]

void init ( )
inline

Definition at line 618 of file loser_tree.hpp.

◆ init() [4/4]

void init ( )
inline

Definition at line 796 of file loser_tree.hpp.

◆ init_winner() [1/4]

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 155 of file loser_tree.hpp.

◆ init_winner() [2/4]

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 395 of file loser_tree.hpp.

◆ init_winner() [3/4]

Source init_winner ( const Source root)
inline

Definition at line 600 of file loser_tree.hpp.

◆ init_winner() [4/4]

Source init_winner ( const Source root)
inline

Definition at line 778 of file loser_tree.hpp.

◆ insert_start() [1/4]

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 125 of file loser_tree.hpp.

◆ insert_start() [2/4]

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 378 of file loser_tree.hpp.

◆ insert_start() [3/4]

void insert_start ( const ValueType *  keyp,
const Source source,
bool  sup 
)
inline

Definition at line 589 of file loser_tree.hpp.

◆ insert_start() [4/4]

void insert_start ( const ValueType *  keyp,
const Source source,
bool  sup 
)
inline

Definition at line 767 of file loser_tree.hpp.

◆ LoserTreeCopy() [1/2]

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

Definition at line 209 of file loser_tree.hpp.

◆ LoserTreeCopy() [2/2]

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

Definition at line 276 of file loser_tree.hpp.

◆ LoserTreeCopyBase()

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

Definition at line 103 of file loser_tree.hpp.

◆ LoserTreeCopyUnguarded() [1/2]

LoserTreeCopyUnguarded ( Source  k,
const ValueType &  sentinel,
const Comparator &  cmp = Comparator() 
)
inline

Definition at line 640 of file loser_tree.hpp.

◆ LoserTreeCopyUnguarded() [2/2]

LoserTreeCopyUnguarded ( Source  k,
const ValueType &  sentinel,
const Comparator &  comp = Comparator() 
)
inline

Definition at line 681 of file loser_tree.hpp.

◆ LoserTreeCopyUnguardedBase()

LoserTreeCopyUnguardedBase ( Source  k,
const ValueType &  sentinel,
const Comparator &  cmp = Comparator() 
)
inline

Definition at line 572 of file loser_tree.hpp.

◆ LoserTreePointer() [1/2]

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

Definition at line 446 of file loser_tree.hpp.

◆ LoserTreePointer() [2/2]

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

Definition at line 506 of file loser_tree.hpp.

◆ LoserTreePointerBase() [1/3]

LoserTreePointerBase ( const LoserTreePointerBase< ValueType, Comparator > &  )
delete

◆ LoserTreePointerBase() [2/3]

LoserTreePointerBase ( LoserTreePointerBase< ValueType, Comparator > &&  )
default

◆ LoserTreePointerBase() [3/3]

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

Definition at line 350 of file loser_tree.hpp.

◆ LoserTreePointerUnguarded() [1/2]

LoserTreePointerUnguarded ( const Source k,
const ValueType &  sentinel,
const Comparator &  cmp = Comparator() 
)
inline

Definition at line 818 of file loser_tree.hpp.

◆ LoserTreePointerUnguarded() [2/2]

LoserTreePointerUnguarded ( const Source k,
const ValueType &  sentinel,
const Comparator &  cmp = Comparator() 
)
inline

Definition at line 856 of file loser_tree.hpp.

◆ LoserTreePointerUnguardedBase() [1/2]

LoserTreePointerUnguardedBase ( const LoserTreePointerUnguardedBase< ValueType, Comparator > &  other)
delete

◆ LoserTreePointerUnguardedBase() [2/2]

LoserTreePointerUnguardedBase ( const Source k,
const ValueType &  sentinel,
const Comparator &  cmp = Comparator() 
)
inline

Definition at line 748 of file loser_tree.hpp.

◆ min_source() [1/4]

Source min_source ( )
inline

return the index of the player with the smallest element.

Definition at line 115 of file loser_tree.hpp.

◆ min_source() [2/4]

Source min_source ( )
inline

return the index of the player with the smallest element.

Definition at line 366 of file loser_tree.hpp.

◆ min_source() [3/4]

Source min_source ( )
inline

return the index of the player with the smallest element.

Definition at line 583 of file loser_tree.hpp.

◆ min_source() [4/4]

Source min_source ( )
inline

Definition at line 765 of file loser_tree.hpp.

◆ operator=() [1/3]

LoserTreePointerBase& operator= ( const LoserTreePointerBase< ValueType, Comparator > &  )
delete

◆ operator=() [2/3]

LoserTreePointerUnguardedBase& operator= ( const LoserTreePointerUnguardedBase< ValueType, Comparator > &  )
delete

◆ operator=() [3/3]

LoserTreePointerBase& operator= ( LoserTreePointerBase< ValueType, Comparator > &&  )
default

Variable Documentation

◆ cmp_ [1/4]

Comparator cmp_
protected

the comparator object

Definition at line 98 of file loser_tree.hpp.

◆ cmp_ [2/4]

Comparator cmp_
protected

the comparator object

Definition at line 347 of file loser_tree.hpp.

◆ cmp_ [3/4]

Comparator cmp_
protected

the comparator object

Definition at line 569 of file loser_tree.hpp.

◆ cmp_ [4/4]

Comparator cmp_
protected

the comparator object

Definition at line 745 of file loser_tree.hpp.

◆ first_insert_

bool first_insert_
protected

still have to construct keys

Definition at line 100 of file loser_tree.hpp.

◆ ik_ [1/4]

const Source ik_
protected

number of nodes

Definition at line 91 of file loser_tree.hpp.

◆ ik_ [2/4]

const Source ik_
protected

number of nodes

Definition at line 341 of file loser_tree.hpp.

◆ ik_ [3/4]

Source ik_
protected

number of nodes

Definition at line 563 of file loser_tree.hpp.

◆ ik_ [4/4]

Source ik_
protected

number of nodes

Definition at line 739 of file loser_tree.hpp.

◆ invalid_ [1/4]

constexpr Source invalid_
staticconstexpr

sentinel for invalid or finished Sources

Definition at line 77 of file loser_tree.hpp.

◆ invalid_ [2/4]

constexpr Source invalid_
staticconstexpr

sentinel for invalid or finished Sources

Definition at line 329 of file loser_tree.hpp.

◆ invalid_ [3/4]

constexpr Source invalid_
staticconstexpr

sentinel for invalid or finished Sources

Definition at line 551 of file loser_tree.hpp.

◆ invalid_ [4/4]

constexpr Source invalid_
staticconstexpr

sentinel for invalid or finished Sources

Definition at line 727 of file loser_tree.hpp.

◆ k_ [1/4]

const Source k_
protected

log_2(ik) next greater power of 2

Definition at line 93 of file loser_tree.hpp.

◆ k_ [2/4]

const Source k_
protected

log_2(ik) next greater power of 2

Definition at line 343 of file loser_tree.hpp.

◆ k_ [3/4]

Source k_
protected

log_2(ik) next greater power of 2

Definition at line 565 of file loser_tree.hpp.

◆ k_ [4/4]

Source k_
protected

log_2(ik) next greater power of 2

Definition at line 741 of file loser_tree.hpp.

◆ key [1/2]

ValueType key

copy of key value of the element in this node

Definition at line 87 of file loser_tree.hpp.

◆ key [2/2]

ValueType key

copy of key value of the element in this node

Definition at line 559 of file loser_tree.hpp.

◆ keyp [1/2]

const ValueType* keyp

pointer to key value of the element in this node

Definition at line 337 of file loser_tree.hpp.

◆ keyp [2/2]

const ValueType* keyp

copy of key value of the element in this node

Definition at line 735 of file loser_tree.hpp.

◆ losers_ [1/4]

SimpleVector<Loser> losers_
protected

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

Definition at line 96 of file loser_tree.hpp.

◆ losers_ [2/4]

SimpleVector<Loser> losers_
protected

array containing loser tree nodes

Definition at line 345 of file loser_tree.hpp.

◆ losers_ [3/4]

SimpleVector<Loser> losers_
protected

array containing loser tree nodes

Definition at line 567 of file loser_tree.hpp.

◆ losers_ [4/4]

SimpleVector<Loser> losers_
protected

array containing loser tree nodes

Definition at line 743 of file loser_tree.hpp.

◆ source [1/4]

Source source

index of source

Definition at line 85 of file loser_tree.hpp.

◆ source [2/4]

Source source

index of source

Definition at line 335 of file loser_tree.hpp.

◆ source [3/4]

Source source

index of source

Definition at line 557 of file loser_tree.hpp.

◆ source [4/4]

Source source

index of source

Definition at line 733 of file loser_tree.hpp.

◆ sup

bool sup

flag, true iff is a virtual maximum sentinel

Definition at line 83 of file loser_tree.hpp.