LoserTreeCopyBase< ValueType, Comparator > Class Template Reference

Guarded loser tree/tournament tree, either copying the whole element into the tree structure, or looking up the element via the index. More...

#include <loser_tree.hpp>

Inheritance diagram for LoserTreeCopyBase< 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
	LoserTreeCopyBase (const Source &k, const Comparator &cmp=Comparator())
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< Loser >	losers_
	array containing loser tree nodes – avoid default-constructing losers[].key
Comparator	cmp_
	the comparator object
bool	first_insert_
	still have to construct keys

Detailed Description

template<typename ValueType, typename Comparator = std::less<ValueType>>
class tlx::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.

This is a base class for the LoserTreeCopy<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.

Template Parameters

ValueType	the element type
Comparator	comparator to use for binary comparisons.

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

Constructor & Destructor Documentation

LoserTreeCopyBase()

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

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

inlineexplicit

Definition at line 88 of file loser_tree.hpp.

Member Function Documentation

init()

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

void init ( )

inline

Definition at line 160 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

root	index of the game to start.

Definition at line 140 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

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.

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

Member Data Documentation

cmp_

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

Comparator cmp_

protected

the comparator object

Definition at line 83 of file loser_tree.hpp.

first_insert_

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

bool first_insert_

protected

still have to construct keys

Definition at line 85 of file loser_tree.hpp.

ik_

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

const Source ik_

protected

number of nodes

Definition at line 76 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 62 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 78 of file loser_tree.hpp.

losers_

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

SimpleVector<Loser> losers_

protected

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

Definition at line 81 of file loser_tree.hpp.

---

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

• tlx/container/loser_tree.hpp