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 = uint32_t
	size of counters and array indexes More...

Public Member 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 ()

Static Public Attributes
static constexpr Source	invalid_
	sentinel for invalid or finished Sources More...

Protected Attributes
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...

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.

---

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

• tlx/container/loser_tree.hpp