tlx
Loading...
Searching...
No Matches
LoserTreePointerUnguardedBase< ValueType, Comparator > Class Template Reference
tlx - C++ Extensions and Utilities » Containers and Data Structures » Loser Trees

Unguarded loser tree, keeping only pointers to the elements in the tree structure. More...

#include <loser_tree.hpp>

Inheritance diagram for LoserTreePointerUnguardedBase< ValueType, Comparator >:
LoserTreePointerUnguarded< Stable, 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

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

Static Public Attributes

static constexpr Source invalid_
 sentinel for invalid or finished Sources

Protected Attributes

Source ik_
 number of nodes
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::LoserTreePointerUnguardedBase< ValueType, Comparator >

Unguarded loser tree, keeping only pointers to the elements in the tree structure.

This is a base class for the LoserTreePointerUnguarded<true> and <false> classes.

No guarding is done, therefore not a single input sequence must run empty. This is a very fast variant.

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

Constructor & Destructor Documentation

◆ LoserTreePointerUnguardedBase() [1/2]

template<typename ValueType, typename Comparator = std::less<ValueType>>
LoserTreePointerUnguardedBase ( const Source & k,
const ValueType & sentinel,
const Comparator & cmp = Comparator() )
inline

Definition at line 733 of file loser_tree.hpp.

◆ LoserTreePointerUnguardedBase() [2/2]

template<typename ValueType, typename Comparator = std::less<ValueType>>
LoserTreePointerUnguardedBase ( const LoserTreePointerUnguardedBase< ValueType, Comparator > & other)
delete

Member Function Documentation

◆ init()

template<typename ValueType, typename Comparator = std::less<ValueType>>
void init ( )
inline

Definition at line 781 of file loser_tree.hpp.

◆ init_winner()

template<typename ValueType, typename Comparator = std::less<ValueType>>
Source init_winner ( const Source & root)
inline

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

Definition at line 752 of file loser_tree.hpp.

◆ min_source()

template<typename ValueType, typename Comparator = std::less<ValueType>>
Source min_source ( )
inline

Definition at line 750 of file loser_tree.hpp.

◆ operator=()

template<typename ValueType, typename Comparator = std::less<ValueType>>
LoserTreePointerUnguardedBase & operator= ( const LoserTreePointerUnguardedBase< ValueType, Comparator > & )
delete

Member Data Documentation

◆ cmp_

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

the comparator object

Definition at line 730 of file loser_tree.hpp.

◆ ik_

template<typename ValueType, typename Comparator = std::less<ValueType>>
Source ik_
protected

number of nodes

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

◆ k_

template<typename ValueType, typename Comparator = std::less<ValueType>>
Source k_
protected

log_2(ik) next greater power of 2

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

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