__gnu_parallel::_LoserTree< __stable, _Tp, _Compare > Class Template Reference

Stable _LoserTree variant. More...

#include <parallel/losertree.h>

Inheritance diagram for __gnu_parallel::_LoserTree< __stable, _Tp, _Compare >:

Public Member Functions
	_LoserTree (unsigned int __k, _Compare __comp)
unsigned int	__init_winner (unsigned int __root)
void	__init ()
void	__delete_min_insert (_Tp __key, bool __sup)
	Delete the smallest element and insert a new element from the previously smallest element's sequence. More...
Public Member Functions inherited from __gnu_parallel::_LoserTreeBase< _Tp, _Compare >
	_LoserTreeBase (unsigned int __k, _Compare __comp)
	The constructor. More...
	~_LoserTreeBase ()
	The destructor. More...
void	__insert_start (const _Tp &__key, int __source, bool __sup)
	Initializes the sequence "_M_source" with the element "__key". More...
int	__get_min_source ()

Private Types
typedef _LoserTreeBase< _Tp, _Compare >	_Base

Additional Inherited Members
Protected Attributes inherited from __gnu_parallel::_LoserTreeBase< _Tp, _Compare >
unsigned int	_M_ik
unsigned int	_M_k
unsigned int	_M_offset
unsigned int	_M_log_k
_Loser *	_M_losers
	_LoserTree __elements. More...
_Compare	_M_comp
	_Compare to use. More...
bool	_M_first_insert
	State flag that determines whether the _LoserTree is empty. More...

Detailed Description

template<bool __stable, typename _Tp, typename _Compare>
class __gnu_parallel::_LoserTree< __stable, _Tp, _Compare >

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.

Member Typedef Documentation

template<bool __stable, typename _Tp , typename _Compare >

typedef _LoserTreeBase<_Tp, _Compare> __gnu_parallel::_LoserTree< __stable, _Tp, _Compare >::_Base

private

Constructor & Destructor Documentation

template<bool __stable, typename _Tp , typename _Compare >

__gnu_parallel::_LoserTree< __stable, _Tp, _Compare >::_LoserTree ( unsigned int  __k, _Compare  __comp  )

inline

      : _Base::_LoserTreeBase(__k, __comp)
      { }

Member Function Documentation

template<bool __stable, typename _Tp , typename _Compare >

void __gnu_parallel::_LoserTree< __stable, _Tp, _Compare >::__delete_min_insert ( _Tp  __key, bool  __sup  )

inline

Delete the smallest element and insert a new element from the previously smallest element's sequence.

This implementation is stable.

      {
        using std::swap;
#if _GLIBCXX_ASSERTIONS
    // no dummy sequence can ever be at the top!
    _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
#endif

    int __source = _M_losers[0]._M_source;
    for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
         __pos /= 2)
      {
        // The smaller one gets promoted, ties are broken by _M_source.
        if ((__sup && (!_M_losers[__pos]._M_sup
               || _M_losers[__pos]._M_source < __source))
        || (!__sup && !_M_losers[__pos]._M_sup
            && ((_M_comp(_M_losers[__pos]._M_key, __key))
            || (!_M_comp(__key, _M_losers[__pos]._M_key)
                && _M_losers[__pos]._M_source < __source))))
          {
        // The other one is smaller.
        std::swap(_M_losers[__pos]._M_sup, __sup);
        std::swap(_M_losers[__pos]._M_source, __source);
        swap(_M_losers[__pos]._M_key, __key);
          }
      }

    _M_losers[0]._M_sup = __sup;
    _M_losers[0]._M_source = __source;
    _M_losers[0]._M_key = __key;
      }

template<bool __stable, typename _Tp , typename _Compare >

void __gnu_parallel::_LoserTree< __stable, _Tp, _Compare >::__init ( )

inline

      { _M_losers[0] = _M_losers[__init_winner(1)]; }

template<bool __stable, typename _Tp , typename _Compare >

unsigned int __gnu_parallel::_LoserTree< __stable, _Tp, _Compare >::__init_winner ( unsigned int  __root )

inline

      {
    if (__root >= _M_k)
      return __root;
    else
      {
        unsigned int __left = __init_winner(2 * __root);
        unsigned int __right = __init_winner(2 * __root + 1);
        if (_M_losers[__right]._M_sup
        || (!_M_losers[__left]._M_sup
            && !_M_comp(_M_losers[__right]._M_key,
                _M_losers[__left]._M_key)))
          {
        // Left one is less or equal.
        _M_losers[__root] = _M_losers[__right];
        return __left;
          }
        else
          {
        // Right one is less.
        _M_losers[__root] = _M_losers[__left];
        return __right;
          }
      }
      }

---

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

• GCC4/inc/parallel/losertree.h