LoserTreePointerBase< 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 LoserTreePointerBase< 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
	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.
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
Comparator	cmp_
	the comparator object

Detailed Description

template<typename ValueType, typename Comparator = std::less<ValueType>>
class tlx::LoserTreePointerBase< ValueType, Comparator >

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

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

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

Constructor & Destructor Documentation

LoserTreePointerBase() [1/3]

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

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

inlineexplicit

Definition at line 335 of file loser_tree.hpp.

LoserTreePointerBase() [2/3]

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

LoserTreePointerBase ( const LoserTreePointerBase< ValueType, Comparator > & )

delete

LoserTreePointerBase() [3/3]

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

LoserTreePointerBase ( LoserTreePointerBase< ValueType, Comparator > && )

default

Member Function Documentation

init()

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

void init ( )

inline

Definition at line 400 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 380 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 363 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 351 of file loser_tree.hpp.

operator=() [1/2]

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

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

delete

operator=() [2/2]

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

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

default

Member Data Documentation

cmp_

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

Comparator cmp_

protected

the comparator object

Definition at line 332 of file loser_tree.hpp.

ik_

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

const Source ik_

protected

number of nodes

Definition at line 326 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 314 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 328 of file loser_tree.hpp.

losers_

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

SimpleVector<Loser> losers_

protected

array containing loser tree nodes

Definition at line 330 of file loser_tree.hpp.

---

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

• tlx/container/loser_tree.hpp