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

Public Types

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

Public Member Functions

 LoserTreePointer (Source k, const Comparator &cmp=Comparator())
void delete_min_insert (const ValueType *keyp, bool sup)
Public Member Functions inherited from LoserTreePointerBase< ValueType, Comparator >
 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.
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
Comparator cmp_
 the comparator object
Protected Attributes inherited from LoserTreePointerBase< 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
Comparator cmp_
 the comparator object

Additional Inherited Members

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

Detailed Description

template<typename ValueType, typename Comparator>
class tlx::LoserTreePointer< true, ValueType, Comparator >

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

Unstable 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.

Definition at line 478 of file loser_tree.hpp.

Member Typedef Documentation

◆ Source

template<typename ValueType, typename Comparator>
using Source

Definition at line 483 of file loser_tree.hpp.

◆ Super

template<typename ValueType, typename Comparator>
using Super

Definition at line 482 of file loser_tree.hpp.

Constructor & Destructor Documentation

◆ LoserTreePointer()

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

Definition at line 491 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 494 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


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