libstdc++
__gnu_parallel::LoserTree< stable, T, Comparator > Class Template Reference
Inheritance diagram for __gnu_parallel::LoserTree< stable, T, Comparator >:
Inheritance graph

List of all members.

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
Loserlosers
unsigned int offset

Detailed Description

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.


Member Function Documentation

template<bool stable, typename T , typename Comparator >
void __gnu_parallel::LoserTree< stable, T, Comparator >::delete_min_insert ( 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 ( )
inlineinherited
Returns:
the index of the sequence with the smallest element.

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

Initializes the sequence "source" with the element "key".

Parameters:
keythe element to insert
sourceindex of the source sequence
supflag that determines whether the value to insert is an explicit supremum.

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.


Member Data Documentation

template<typename T , typename Comparator >
unsigned int __gnu_parallel::LoserTreeBase< T, Comparator >::_M_log_k
protectedinherited

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
protectedinherited

Comparator to use.

Definition at line 80 of file losertree.h.

template<typename T , typename Comparator >
bool __gnu_parallel::LoserTreeBase< T, Comparator >::first_insert
protectedinherited

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


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