tlx
Loading...
Searching...
No Matches
LoserTreeCopy< true, 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 LoserTreeCopy< true, ValueType, Comparator >:
LoserTreeCopyBase< ValueType, Comparator > LoserTreeCopyBase< ValueType, Comparator >

Public Types

using Super
using Source
Public Types inherited from LoserTreeCopyBase< ValueType, Comparator >
using Source
 size of counters and array indexes

Public Member Functions

 LoserTreeCopy (const Source &k, const Comparator &cmp=Comparator())
void delete_min_insert (const ValueType *keyp, bool sup)
Public Member Functions inherited from LoserTreeCopyBase< ValueType, Comparator >
 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 ()

Protected Attributes

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
Protected Attributes inherited from LoserTreeCopyBase< ValueType, Comparator >
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

Additional Inherited Members

Static Public Attributes inherited from LoserTreeCopyBase< ValueType, Comparator >
static constexpr Source invalid_
 sentinel for invalid or finished Sources

Detailed Description

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

Stable specialization of LoserTreeCopyBase.

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
ValueTypethe element type
Comparatorcomparator to use for binary comparisons.

Definition at line 248 of file loser_tree.hpp.

Member Typedef Documentation

◆ Source

template<typename ValueType, typename Comparator>
using Source

Definition at line 253 of file loser_tree.hpp.

◆ Super

template<typename ValueType, typename Comparator>
using Super

Definition at line 252 of file loser_tree.hpp.

Constructor & Destructor Documentation

◆ LoserTreeCopy()

template<typename ValueType, typename Comparator>
LoserTreeCopy ( const Source & k,
const Comparator & cmp = Comparator() )
inlineexplicit

Definition at line 261 of file loser_tree.hpp.

Member Function Documentation

◆ delete_min_insert()

template<typename ValueType, typename Comparator>
void delete_min_insert ( const ValueType * keyp,
bool sup )
inline

Definition at line 266 of file loser_tree.hpp.

Member Data Documentation

◆ cmp_

protected

the comparator object

◆ k_

protected

log_2(ik) next greater power of 2

◆ losers_

protected

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


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