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.
T | the element type | |
Comparator | the comparator to use, defaults to std::less<T> |
Definition at line 63 of file losertree.h.
__gnu_parallel::LoserTreeBase< T, Comparator >::LoserTreeBase | ( | unsigned int | _k, | |
Comparator | _comp | |||
) | [inline] |
The constructor.
_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.
__gnu_parallel::LoserTreeBase< T, Comparator >::~LoserTreeBase | ( | ) | [inline] |
The destructor.
Definition at line 125 of file losertree.h.
References __gnu_parallel::LoserTreeBase< T, Comparator >::losers.
int __gnu_parallel::LoserTreeBase< T, Comparator >::get_min_source | ( | ) | [inline] |
Definition at line 158 of file losertree.h.
References __gnu_parallel::LoserTreeBase< T, Comparator >::losers, and __gnu_parallel::LoserTreeBase< T, Comparator >::Loser::source.
void __gnu_parallel::LoserTreeBase< T, Comparator >::insert_start | ( | const T & | key, | |
int | source, | |||
bool | sup | |||
) | [inline] |
Initializes the sequence "source" with the element "key".
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.
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().
Comparator __gnu_parallel::LoserTreeBase< T, Comparator >::comp [protected] |
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().
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().