stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator > Class Template Reference

Detailed Description

template<typename ValueType, typename Comparator = std::less<ValueType>>
class stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >

Guarded loser tree/tournament tree, either copying the whole element into the tree structure, or looking up the element via the index.

This is a base class for the LoserTreeCopy<true> and <false> classes.

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.

Template Parameters

ValueType	the element type
Comparator	comparator to use for binary comparisons.

Definition at line 44 of file losertree.h.

Inheritance diagram for stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >:

Collaboration diagram for stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >:

Classes
struct	Loser
	Internal representation of a loser tree player/node. More...

Public Types
typedef unsigned int	size_type
	size of counters and array indexes More...
typedef int	source_type
	type of the source field More...

Public Member Functions
	LoserTreeCopyBase (size_type _k, Comparator _comp=std::less< ValueType >())
	~LoserTreeCopyBase ()
source_type	get_min_source ()
	return the index of the player with the smallest element. More...
void	init ()
size_type	init_winner (size_type root)
void	insert_start (const ValueType &key, source_type source, bool sup)
void	print (std::ostream &os)

Protected Attributes
Comparator	comp
	the comparator object More...
bool	first_insert
	still have to construct keys More...
const size_type	ik
	number of nodes More...
const size_type	k
	log_2(ik) next greater power of 2 More...
Loser *	losers
	array containing loser tree nodes More...

Member Typedef Documentation

template<typename ValueType, typename Comparator = std::less<ValueType>>

typedef unsigned int stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >::size_type

size of counters and array indexes

Definition at line 48 of file losertree.h.

template<typename ValueType, typename Comparator = std::less<ValueType>>

typedef int stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >::source_type

type of the source field

Definition at line 50 of file losertree.h.

Constructor & Destructor Documentation

template<typename ValueType, typename Comparator = std::less<ValueType>>

stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >::LoserTreeCopyBase ( size_type  _k, Comparator  _comp = std::less<ValueType>()  )

inline

Definition at line 76 of file losertree.h.

References stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >::Loser::sup.

template<typename ValueType, typename Comparator = std::less<ValueType>>

stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >::~LoserTreeCopyBase ( )

inline

Definition at line 93 of file losertree.h.

Member Function Documentation

template<typename ValueType, typename Comparator = std::less<ValueType>>

source_type stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >::get_min_source ( )

inline

return the index of the player with the smallest element.

Definition at line 108 of file losertree.h.

template<typename ValueType, typename Comparator = std::less<ValueType>>

void stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >::init ( )

inline

Definition at line 169 of file losertree.h.

template<typename ValueType, typename Comparator = std::less<ValueType>>

size_type stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >::init_winner ( size_type  root )

inline

Computes the winner of the competition at player root. Called recursively (starting at 0) to build the initial tree.

Parameters

root	index of the game to start.

Definition at line 145 of file losertree.h.

template<typename ValueType, typename Comparator = std::less<ValueType>>

void stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >::insert_start ( const ValueType &  key, source_type  source, bool  sup  )

inline

Initializes the player source with the element key.

Parameters

key	the element to insert
source	index of the player
sup	flag that determines whether the value to insert is an explicit supremum sentinel.

Definition at line 121 of file losertree.h.

References UNLIKELY.

template<typename ValueType, typename Comparator = std::less<ValueType>>

void stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >::print ( std::ostream &  os )

inline

Definition at line 101 of file losertree.h.

Member Data Documentation

template<typename ValueType, typename Comparator = std::less<ValueType>>

Comparator stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >::comp

protected

the comparator object

Definition at line 71 of file losertree.h.

template<typename ValueType, typename Comparator = std::less<ValueType>>

bool stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >::first_insert

protected

still have to construct keys

Definition at line 73 of file losertree.h.

template<typename ValueType, typename Comparator = std::less<ValueType>>

const size_type stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >::ik

protected

number of nodes

Definition at line 65 of file losertree.h.

template<typename ValueType, typename Comparator = std::less<ValueType>>

const size_type stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >::k

protected

log_2(ik) next greater power of 2

Definition at line 67 of file losertree.h.

template<typename ValueType, typename Comparator = std::less<ValueType>>

Loser* stxxl::parallel::LoserTreeCopyBase< ValueType, Comparator >::losers

protected

array containing loser tree nodes

Definition at line 69 of file losertree.h.

---

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

• include/stxxl/bits/parallel/losertree.h