Public Member Functions¶

void delete_min_insert (T key, bool sup)
int get_min_source ()
void init ()
unsigned int init_winner (unsigned int root)
void insert_start (const T &key, int source, bool sup)
LoserTree (unsigned int _k, Comparator _comp)

Protected Attributes¶

unsigned int _M_log_k
Comparator comp
bool first_insert
unsigned int ik
unsigned int k
Loser * losers
unsigned int offset

template<bool stable, typename T, typename Comparator> class __gnu_parallel::LoserTree< stable, T, Comparator >¶

Stable LoserTree variant.

Provides the stable implementations of insert_start, init_winner, init and delete_min_insert.

Unstable variant is done using partial specialisation below.

Definition at line 165 of file losertree.h.

template<bool stable, typename T , typename Comparator > void __gnu_parallel::LoserTree< stable, T, Comparator >::delete_min_insert (T key, bool sup) [inline]¶

Delete the smallest element and insert a new element from the previously smallest element's sequence. This implementation is stable.

Definition at line 215 of file losertree.h.

template<typename T , typename Comparator > int __gnu_parallel::LoserTreeBase< T, Comparator >::get_min_source () [inline, inherited] Returns:¶

Definition at line 152 of file losertree.h.

References __gnu_parallel::LoserTreeBase< T, Comparator >::losers, and __gnu_parallel::LoserTreeBase< T, Comparator >::Loser::source.

template<typename T , typename Comparator > void __gnu_parallel::LoserTreeBase< T, Comparator >::insert_start (const T & key, int source, bool sup) [inline, inherited]¶

Initializes the sequence 'source' with the element 'key'. Parameters:

Definition at line 131 of file losertree.h.

References __gnu_parallel::LoserTreeBase< T, Comparator >::first_insert, __gnu_parallel::LoserTreeBase< T, Comparator >::Loser::key, __gnu_parallel::LoserTreeBase< T, Comparator >::losers, __gnu_parallel::LoserTreeBase< T, Comparator >::Loser::source, and __gnu_parallel::LoserTreeBase< T, Comparator >::Loser::sup.

template<typename T , typename Comparator > unsigned int __gnu_parallel::LoserTreeBase< T, Comparator >::_M_log_k [protected, inherited] log_2{k}¶

Definition at line 74 of file losertree.h.

Referenced by __gnu_parallel::LoserTreeBase< T, Comparator >::LoserTreeBase().

template<typename T , typename Comparator > Comparator __gnu_parallel::LoserTreeBase< T, Comparator >::comp [protected, inherited]¶

Comparator to use.

Definition at line 80 of file losertree.h.

template<typename T , typename Comparator > bool __gnu_parallel::LoserTreeBase< T, Comparator >::first_insert [protected, inherited]¶

State flag that determines whether the LoserTree is empty. Only used for building the LoserTree.

Definition at line 87 of file losertree.h.

Referenced by __gnu_parallel::LoserTreeBase< T, Comparator >::insert_start(), and __gnu_parallel::LoserTreeBase< T, Comparator >::LoserTreeBase().

template<typename T , typename Comparator > Loser* __gnu_parallel::LoserTreeBase< T, Comparator >::losers [protected, inherited]¶

LoserTree elements.

Definition at line 77 of file losertree.h.

Referenced by __gnu_parallel::LoserTreeBase< T, Comparator >::get_min_source(), __gnu_parallel::LoserTreeBase< T, Comparator >::insert_start(), __gnu_parallel::LoserTreeBase< T, Comparator >::LoserTreeBase(), and __gnu_parallel::LoserTreeBase< T, Comparator >::~LoserTreeBase().