Loser Trees

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
LoserTreePointerBase &	operator= (const LoserTreePointerBase &)=delete
	LoserTreePointerBase (LoserTreePointerBase &&)=default
LoserTreePointerBase &	operator= (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
LoserTreePointerUnguardedBase &	operator= (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< Loser >	losers_
	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< Loser >	losers_
	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< Loser >	losers_
	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< Loser >	losers_
	array containing loser tree nodes More...
Comparator	cmp_
	the comparator object More...

Detailed Description

Loser/Tournament tree variants.

Typedef Documentation

using Source = uint32_t

size of counters and array indexes

Definition at line 59 of file loser_tree.hpp.

using Source = typename Super::Source

Definition at line 186 of file loser_tree.hpp.

using Source = typename Super::Source

Definition at line 253 of file loser_tree.hpp.

using Source = uint32_t

size of counters and array indexes

Definition at line 311 of file loser_tree.hpp.

using Source = typename Super::Source

Definition at line 423 of file loser_tree.hpp.

using Source = typename Super::Source

Definition at line 483 of file loser_tree.hpp.

using Source = uint32_t

size of counters and array indexes

Definition at line 533 of file loser_tree.hpp.

using Source = typename Super::Source

Definition at line 617 of file loser_tree.hpp.

using Source = typename Super::Source

Definition at line 658 of file loser_tree.hpp.

using Source = uint32_t

size of counters and array indexes

Definition at line 709 of file loser_tree.hpp.

using Source = typename Super::Source

Definition at line 795 of file loser_tree.hpp.

using Source = typename Super::Source

Definition at line 833 of file loser_tree.hpp.

using Super = LoserTreeCopyBase<ValueType, Comparator>

Definition at line 185 of file loser_tree.hpp.

using Super = LoserTreeCopyBase<ValueType, Comparator>

Definition at line 252 of file loser_tree.hpp.

using Super = LoserTreePointerBase<ValueType, Comparator>

Definition at line 422 of file loser_tree.hpp.

using Super = LoserTreePointerBase<ValueType, Comparator>

Definition at line 482 of file loser_tree.hpp.

using Super = LoserTreeCopyUnguardedBase<ValueType, Comparator>

Definition at line 616 of file loser_tree.hpp.

using Super = LoserTreeCopyUnguardedBase<ValueType, Comparator>

Definition at line 657 of file loser_tree.hpp.

using Super = LoserTreePointerUnguardedBase<ValueType, Comparator>

Definition at line 794 of file loser_tree.hpp.

using Super = LoserTreePointerUnguardedBase<ValueType, Comparator>

Definition at line 832 of file loser_tree.hpp.

using Type = LoserTreePointer<Stable, ValueType, Comparator>

Definition at line 875 of file loser_tree.hpp.

Function Documentation

void delete_min_insert ( const ValueType *  keyp, bool  sup  )

inline

Definition at line 199 of file loser_tree.hpp.

void delete_min_insert ( const ValueType *  keyp, bool  sup  )

inline

Definition at line 266 of file loser_tree.hpp.

void delete_min_insert ( const ValueType *  keyp, bool  sup  )

inline

Definition at line 434 of file loser_tree.hpp.

void delete_min_insert ( const ValueType *  keyp, bool  sup  )

inline

Definition at line 494 of file loser_tree.hpp.

void delete_min_insert ( const ValueType *  keyp, bool  sup  )

inline

Definition at line 630 of file loser_tree.hpp.

void delete_min_insert ( const ValueType *  keyp, bool  sup  )

inline

Definition at line 671 of file loser_tree.hpp.

void delete_min_insert ( const ValueType *  keyp, bool  sup  )

inline

Definition at line 807 of file loser_tree.hpp.

void delete_min_insert ( const ValueType *  keyp, bool  sup  )

inline

Definition at line 845 of file loser_tree.hpp.

void init ( )

inline

Definition at line 160 of file loser_tree.hpp.

void init ( )

inline

Definition at line 400 of file loser_tree.hpp.

void init ( )

inline

Definition at line 603 of file loser_tree.hpp.

void init ( )

inline

Definition at line 781 of file loser_tree.hpp.

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

root	index of the game to start.

Definition at line 140 of file loser_tree.hpp.

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

root	index of the game to start.

Definition at line 380 of file loser_tree.hpp.

Source init_winner ( const Source &  root )

inline

Definition at line 585 of file loser_tree.hpp.

Source init_winner ( const Source &  root )

inline

Definition at line 763 of file loser_tree.hpp.

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

inline

Initializes the player source with the element key.

Parameters

keyp	the element to insert
source	index of the player
sup	flag that determines whether the value to insert is an explicit supremum sentinel.

Definition at line 110 of file loser_tree.hpp.

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

inline

Initializes the player source with the element key.

Parameters

keyp	the element to insert
source	index of the player
sup	flag that determines whether the value to insert is an explicit supremum sentinel.

Definition at line 363 of file loser_tree.hpp.

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

inline

Definition at line 574 of file loser_tree.hpp.

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

inline

Definition at line 752 of file loser_tree.hpp.

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

inlineexplicit

Definition at line 194 of file loser_tree.hpp.

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

inlineexplicit

Definition at line 261 of file loser_tree.hpp.

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

inlineexplicit

Definition at line 88 of file loser_tree.hpp.

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

inline

Definition at line 625 of file loser_tree.hpp.

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

inline

Definition at line 666 of file loser_tree.hpp.

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

inline

Definition at line 557 of file loser_tree.hpp.

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

inlineexplicit

Definition at line 431 of file loser_tree.hpp.

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

inlineexplicit

Definition at line 491 of file loser_tree.hpp.

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

inlineexplicit

Definition at line 335 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 803 of file loser_tree.hpp.

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

inline

Definition at line 841 of file loser_tree.hpp.

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

inline

Definition at line 733 of file loser_tree.hpp.

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

delete

Source min_source ( )

inline

return the index of the player with the smallest element.

Definition at line 100 of file loser_tree.hpp.

Source min_source ( )

inline

return the index of the player with the smallest element.

Definition at line 351 of file loser_tree.hpp.

Source min_source ( )

inline

return the index of the player with the smallest element.

Definition at line 568 of file loser_tree.hpp.

Source min_source ( )

inline

Definition at line 750 of file loser_tree.hpp.

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

delete

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

default

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

delete

Variable Documentation

Comparator cmp_

protected

the comparator object

Definition at line 83 of file loser_tree.hpp.

Comparator cmp_

protected

the comparator object

Definition at line 332 of file loser_tree.hpp.

Comparator cmp_

protected

the comparator object

Definition at line 554 of file loser_tree.hpp.

Comparator cmp_

protected

the comparator object

Definition at line 730 of file loser_tree.hpp.

bool first_insert_

protected

still have to construct keys

Definition at line 85 of file loser_tree.hpp.

const Source ik_

protected

number of nodes

Definition at line 76 of file loser_tree.hpp.

const Source ik_

protected

number of nodes

Definition at line 326 of file loser_tree.hpp.

Source ik_

protected

number of nodes

Definition at line 548 of file loser_tree.hpp.

Source ik_

protected

number of nodes

Definition at line 724 of file loser_tree.hpp.

constexpr Source invalid_

static

sentinel for invalid or finished Sources

Definition at line 62 of file loser_tree.hpp.

constexpr Source invalid_

static

sentinel for invalid or finished Sources

Definition at line 314 of file loser_tree.hpp.

constexpr Source invalid_

static

sentinel for invalid or finished Sources

Definition at line 536 of file loser_tree.hpp.

constexpr Source invalid_

static

sentinel for invalid or finished Sources

Definition at line 712 of file loser_tree.hpp.

const Source k_

protected

log_2(ik) next greater power of 2

Definition at line 78 of file loser_tree.hpp.

const Source k_

protected

log_2(ik) next greater power of 2

Definition at line 328 of file loser_tree.hpp.

Source k_

protected

log_2(ik) next greater power of 2

Definition at line 550 of file loser_tree.hpp.

Source k_

protected

log_2(ik) next greater power of 2

Definition at line 726 of file loser_tree.hpp.

ValueType key

copy of key value of the element in this node

Definition at line 72 of file loser_tree.hpp.

ValueType key

copy of key value of the element in this node

Definition at line 544 of file loser_tree.hpp.

const ValueType* keyp

pointer to key value of the element in this node

Definition at line 322 of file loser_tree.hpp.

const ValueType* keyp

copy of key value of the element in this node

Definition at line 720 of file loser_tree.hpp.

SimpleVector<Loser> losers_

protected

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

Definition at line 81 of file loser_tree.hpp.

SimpleVector<Loser> losers_

protected

array containing loser tree nodes

Definition at line 330 of file loser_tree.hpp.

SimpleVector<Loser> losers_

protected

array containing loser tree nodes

Definition at line 552 of file loser_tree.hpp.

SimpleVector<Loser> losers_

protected

array containing loser tree nodes

Definition at line 728 of file loser_tree.hpp.

Source source

index of source

Definition at line 70 of file loser_tree.hpp.

Source source

index of source

Definition at line 320 of file loser_tree.hpp.

Source source

index of source

Definition at line 542 of file loser_tree.hpp.

Source source

index of source

Definition at line 718 of file loser_tree.hpp.

bool sup

flag, true iff is a virtual maximum sentinel

Definition at line 68 of file loser_tree.hpp.