__gnu_parallel::losertreebase(3)
NAME
__gnu_parallel::LoserTreeBase
SYNOPSIS
Inherited by __gnu_parallel::LoserTree< stable, T, Comparator >, and __gnu_parallel::LoserTree< false, T, Comparator >.
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 wellperforming variant. - Parameters:
T the element type
Comparator the comparator to use, defaults to std::less<T> - Definition at line 63 of file losertree.h.
- 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
Loser * losers
unsigned int offset - Classes
- struct Loser
Internal representation of a LoserTree element.
Constructor & Destructor Documentation
- template<typename T, typename Comparator> __gnu_parallel::LoserTreeBase< T,
- Comparator >::LoserTreeBase (unsigned int _k, Comparator _comp)
[inline]
The constructor. - Parameters:
_k The number of sequences to merge.
_comp The comparator to use. - Definition at line 102 of file losertree.h.
- References __gnu_parallel::LoserTreeBase< T, Comparator >::_M_log_k,
__gnu_parallel::LoserTreeBase< T, Comparator >::first_insert,
__gnu_parallel::log2(), and __gnu_parallel::LoserTreeBase< T,
Comparator >::losers. - template<typename T, typename Comparator> __gnu_parallel::LoserTreeBase< T,
- Comparator >::~LoserTreeBase () [inline] The destructor.
- Definition at line 125 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 158 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:
key the element to insert
source index of the source sequence
sup flag that determines whether the value to insert is an explicit supremum. - Definition at line 137 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 80 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 86 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 93 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] LoserTree elements.
- Definition at line 83 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().
Author
- Generated automatically by Doxygen for libstdc++ from the source code.