Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Loser Trees
+ Collaboration diagram for Loser Trees:

Classes

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

Typedefs

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

Functions

 LoserTreeCopy (const Source &k, const Comparator &cmp=Comparator())
 
 LoserTreeCopy (const Source &k, const Comparator &cmp=Comparator())
 
 LoserTreeCopyBase (const Source &k, const Comparator &cmp=Comparator())
 
 LoserTreeCopyUnguarded (Source k, const ValueType &sentinel, const Comparator &cmp=Comparator())
 
 LoserTreeCopyUnguarded (Source k, const ValueType &sentinel, const Comparator &comp=Comparator())
 
 LoserTreeCopyUnguardedBase (Source k, const ValueType &sentinel, const Comparator &cmp=Comparator())
 
 LoserTreePointer (Source k, const Comparator &cmp=Comparator())
 
 LoserTreePointer (Source k, const Comparator &cmp=Comparator())
 
 LoserTreePointerBase (Source k, const Comparator &cmp=Comparator())
 
 LoserTreePointerBase (const LoserTreePointerBase &)=delete
 
 LoserTreePointerBase (LoserTreePointerBase &&)=default
 
 LoserTreePointerUnguarded (const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator())
 
 LoserTreePointerUnguarded (const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator())
 
 LoserTreePointerUnguardedBase (const Source &k, const ValueType &sentinel, const Comparator &cmp=Comparator())
 
 LoserTreePointerUnguardedBase (const LoserTreePointerUnguardedBase &other)=delete
 
void delete_min_insert (const ValueType *keyp, bool sup)
 
void delete_min_insert (const ValueType *keyp, bool sup)
 
void delete_min_insert (const ValueType *keyp, bool sup)
 
void delete_min_insert (const ValueType *keyp, bool sup)
 
void delete_min_insert (const ValueType *keyp, bool sup)
 
void delete_min_insert (const ValueType *keyp, bool sup)
 
void delete_min_insert (const ValueType *keyp, bool sup)
 
void delete_min_insert (const ValueType *keyp, bool sup)
 
void init ()
 
void init ()
 
void init ()
 
void init ()
 
Source init_winner (const Source &root)
 Computes the winner of the competition at player root. More...
 
Source init_winner (const Source &root)
 Computes the winner of the competition at player root. More...
 
Source init_winner (const Source &root)
 
Source init_winner (const Source &root)
 
void insert_start (const ValueType *keyp, const Source &source, bool sup)
 Initializes the player source with the element key. More...
 
void insert_start (const ValueType *keyp, const Source &source, bool sup)
 Initializes the player source with the element key. More...
 
void insert_start (const ValueType *keyp, const Source &source, bool sup)
 
void insert_start (const ValueType *keyp, const Source &source, bool sup)
 
Source min_source ()
 return the index of the player with the smallest element. More...
 
Source min_source ()
 return the index of the player with the smallest element. More...
 
Source min_source ()
 return the index of the player with the smallest element. More...
 
Source min_source ()
 
LoserTreePointerBase & operator= (const LoserTreePointerBase &)=delete
 
LoserTreePointerBase & operator= (LoserTreePointerBase &&)=default
 
LoserTreePointerUnguardedBase & operator= (const LoserTreePointerUnguardedBase &)=delete
 

Variables

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

Detailed Description

Loser/Tournament tree variants

Typedef Documentation

using Source = uint32_t

size of counters and array indexes

Definition at line 58 of file loser_tree.hpp.

using Source = typename Super::Source

Definition at line 179 of file loser_tree.hpp.

using Source = typename Super::Source

Definition at line 246 of file loser_tree.hpp.

using Source = uint32_t

size of counters and array indexes

Definition at line 304 of file loser_tree.hpp.

using Source = typename Super::Source

Definition at line 410 of file loser_tree.hpp.

using Source = typename Super::Source

Definition at line 470 of file loser_tree.hpp.

using Source = uint32_t

size of counters and array indexes

Definition at line 520 of file loser_tree.hpp.

using Source = typename Super::Source

Definition at line 598 of file loser_tree.hpp.

using Source = typename Super::Source

Definition at line 639 of file loser_tree.hpp.

using Source = uint32_t

size of counters and array indexes

Definition at line 688 of file loser_tree.hpp.

using Source = typename Super::Source

Definition at line 768 of file loser_tree.hpp.

using Source = typename Super::Source

Definition at line 806 of file loser_tree.hpp.

using Super = LoserTreeCopyBase<ValueType, Comparator>

Definition at line 178 of file loser_tree.hpp.

using Super = LoserTreeCopyBase<ValueType, Comparator>

Definition at line 245 of file loser_tree.hpp.

using Super = LoserTreePointerBase<ValueType, Comparator>

Definition at line 409 of file loser_tree.hpp.

using Super = LoserTreePointerBase<ValueType, Comparator>

Definition at line 469 of file loser_tree.hpp.

using Super = LoserTreeCopyUnguardedBase<ValueType, Comparator>

Definition at line 597 of file loser_tree.hpp.

using Super = LoserTreeCopyUnguardedBase<ValueType, Comparator>

Definition at line 638 of file loser_tree.hpp.

using Super = LoserTreePointerUnguardedBase<ValueType, Comparator>

Definition at line 767 of file loser_tree.hpp.

using Super = LoserTreePointerUnguardedBase<ValueType, Comparator>

Definition at line 805 of file loser_tree.hpp.

using Type = LoserTreePointer<Stable, ValueType, Comparator>

Definition at line 848 of file loser_tree.hpp.

Function Documentation

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

Definition at line 187 of file loser_tree.hpp.

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

Definition at line 254 of file loser_tree.hpp.

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

Definition at line 606 of file loser_tree.hpp.

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

Definition at line 647 of file loser_tree.hpp.

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

Definition at line 418 of file loser_tree.hpp.

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

Definition at line 478 of file loser_tree.hpp.

LoserTreePointerBase ( const LoserTreePointerBase< ValueType, Comparator > &  )
delete
LoserTreePointerBase ( LoserTreePointerBase< ValueType, Comparator > &&  )
default
LoserTreePointerUnguarded ( const Source k,
const ValueType &  sentinel,
const Comparator &  cmp = Comparator() 
)
inline

Definition at line 776 of file loser_tree.hpp.

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

Definition at line 814 of file loser_tree.hpp.

LoserTreePointerUnguardedBase ( const LoserTreePointerUnguardedBase< ValueType, Comparator > &  other)
delete
void delete_min_insert ( const ValueType *  keyp,
bool  sup 
)
inline
void delete_min_insert ( const ValueType *  keyp,
bool  sup 
)
inline
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 137 of file loser_tree.hpp.

References LoserTreeCopyBase< ValueType, Comparator >::cmp_, LoserTreeCopyBase< ValueType, Comparator >::k_, and LoserTreeCopyBase< ValueType, Comparator >::losers_.

Referenced by LoserTreeCopyBase< ValueType, Comparator >::init().

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

References LoserTreePointerBase< ValueType, Comparator >::cmp_, LoserTreePointerBase< ValueType, Comparator >::k_, and LoserTreePointerBase< ValueType, Comparator >::losers_.

Referenced by LoserTreePointerBase< ValueType, Comparator >::init().

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

References LoserTreeCopyBase< ValueType, Comparator >::first_insert_, LoserTreeCopyBase< ValueType, Comparator >::k_, LoserTreeCopyBase< ValueType, Comparator >::losers_, and TLX_UNLIKELY.

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

References LoserTreePointerBase< ValueType, Comparator >::k_, LoserTreePointerBase< ValueType, Comparator >::losers_, and tlx::unused().

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

return the index of the player with the smallest element.

Definition at line 99 of file loser_tree.hpp.

References LoserTreeCopyBase< ValueType, Comparator >::losers_.

Source min_source ( )
inline

return the index of the player with the smallest element.

Definition at line 344 of file loser_tree.hpp.

References LoserTreePointerBase< ValueType, Comparator >::invalid_, and LoserTreePointerBase< ValueType, Comparator >::losers_.

Source min_source ( )
inline

return the index of the player with the smallest element.

Definition at line 555 of file loser_tree.hpp.

References LoserTreeCopyUnguardedBase< ValueType, Comparator >::invalid_, and LoserTreeCopyUnguardedBase< ValueType, Comparator >::losers_.

Source min_source ( )
inline
LoserTreePointerBase& operator= ( const LoserTreePointerBase< ValueType, Comparator > &  )
delete
LoserTreePointerBase& operator= ( LoserTreePointerBase< ValueType, Comparator > &&  )
default
LoserTreePointerUnguardedBase& operator= ( const LoserTreePointerUnguardedBase< ValueType, Comparator > &  )
delete

Variable Documentation

bool first_insert_
protected

still have to construct keys

Definition at line 84 of file loser_tree.hpp.

Referenced by LoserTreeCopyBase< ValueType, Comparator >::insert_start().

const Source ik_
protected

number of nodes

Definition at line 75 of file loser_tree.hpp.

Referenced by LoserTreeCopyBase< ValueType, Comparator >::LoserTreeCopyBase().

const Source ik_
protected

number of nodes

Definition at line 319 of file loser_tree.hpp.

Referenced by LoserTreePointerBase< ValueType, Comparator >::LoserTreePointerBase().

Source ik_
protected

number of nodes

Definition at line 535 of file loser_tree.hpp.

Source ik_
protected
constexpr Source invalid_ = Source(-1)
static

sentinel for invalid or finished Sources

Definition at line 61 of file loser_tree.hpp.

Referenced by LoserTreeCopyBase< ValueType, Comparator >::LoserTreeCopyBase().

constexpr Source invalid_ = Source(-1)
static
constexpr Source invalid_ = Source(-1)
static
constexpr Source invalid_ = Source(-1)
static

sentinel for invalid or finished Sources

Definition at line 691 of file loser_tree.hpp.

Referenced by LoserTreePointerUnguardedBase< ValueType, Comparator >::LoserTreePointerUnguardedBase().

ValueType key

copy of key value of the element in this node

Definition at line 71 of file loser_tree.hpp.

ValueType key

copy of key value of the element in this node

Definition at line 531 of file loser_tree.hpp.

const ValueType* keyp

pointer to key value of the element in this node

Definition at line 315 of file loser_tree.hpp.

const ValueType* keyp

copy of key value of the element in this node

Definition at line 699 of file loser_tree.hpp.

Source source

index of source

Definition at line 69 of file loser_tree.hpp.

Source source

index of source

Definition at line 313 of file loser_tree.hpp.

Source source

index of source

Definition at line 529 of file loser_tree.hpp.

Source source

index of source

Definition at line 697 of file loser_tree.hpp.

bool sup

flag, true iff is a virtual maximum sentinel

Definition at line 67 of file loser_tree.hpp.