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

List of all members.

Classes

struct  Loser
 Internal representation of a LoserTree element. More...

Public Member Functions

int get_min_source ()
void insert_start (const T &key, int source, bool sup)
 LoserTreeBase (unsigned int _k, Comparator _comp)
 ~LoserTreeBase ()

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<typename T, typename Comparator>
class __gnu_parallel::LoserTreeBase< T, Comparator >

Guarded loser/tournament tree.

The smallest element is at the top.

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.

Parameters:
Tthe element type
Comparatorthe comparator to use, defaults to std::less<T>

Definition at line 57 of file losertree.h.


Constructor & Destructor Documentation

template<typename T , typename Comparator >
__gnu_parallel::LoserTreeBase< T, Comparator >::LoserTreeBase ( unsigned int  _k,
Comparator  _comp 
)
inline

The constructor.

Parameters:
_kThe number of sequences to merge.
_compThe comparator to use.

Definition at line 96 of file losertree.h.

References __gnu_parallel::__log2(), __gnu_parallel::LoserTreeBase< T, Comparator >::_M_log_k, __gnu_parallel::LoserTreeBase< T, Comparator >::first_insert, and __gnu_parallel::LoserTreeBase< T, Comparator >::losers.

template<typename T , typename Comparator >
__gnu_parallel::LoserTreeBase< T, Comparator >::~LoserTreeBase ( )
inline

The destructor.

Definition at line 119 of file losertree.h.

References __gnu_parallel::LoserTreeBase< T, Comparator >::losers.


Member Function Documentation

template<typename T , typename Comparator >
int __gnu_parallel::LoserTreeBase< T, Comparator >::get_min_source ( )
inline
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 
)
inline

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
protected

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

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

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: