tlx
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 >:
LoserTreePointer< Stable, ValueType, Comparator > LoserTreePointer< true, 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

 LoserTreePointerBase (Source k, const Comparator &cmp=Comparator())
 
 LoserTreePointerBase (const LoserTreePointerBase &)=delete
 
LoserTreePointerBaseoperator= (const LoserTreePointerBase &)=delete
 
 LoserTreePointerBase (LoserTreePointerBase &&)=default
 
LoserTreePointerBaseoperator= (LoserTreePointerBase &&)=default
 
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< Loserlosers_
 array containing loser tree nodes More...
 
Comparator cmp_
 the comparator object More...
 

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


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