Detailed Description

template<typename Comparator>
class stxxl::winner_tree< Comparator >

The class winner_tree is a binary tournament tree.

There are n=2^k so called players which compete for the winning position. The winner is the smallest one regarding the comparator m_less. Each player is identified with it's index. The comparator should use this index in order to compare the actual values.

A change of one players value results in O(log n) operations. The winner can be determined in O(1) operations.

There is a number of fixed players which remain at the same index forever, even if they were deactivated in between. Additionally any number of players can be added dynamically. They are assigned to a free slot and if one gets removed the slot will be marked free again.

Definition at line 42 of file winner_tree.h.

Inheritance diagram for stxxl::winner_tree< Comparator >:

Collaboration diagram for stxxl::winner_tree< Comparator >:

Classes
struct	stats_type
	Collection of stats from the winner_tree. More...

Public Member Functions
	winner_tree (unsigned_type num_players, Comparator &less)

void	activate_player (unsigned_type index)
	activate one of the static players or add a new one and replay More...

void	activate_without_replay (unsigned_type index)
	activate a player and resize if necessary More...

void	clear ()
	Deactivate all players. More...

void	deactivate_player (unsigned_type index)
	deactivate a player and replay. More...

void	deactivate_player_step (unsigned_type index)

void	deactivate_without_replay (unsigned_type index)
	deactivate a player More...

void	double_num_slots ()
	Doubles the number of slots and adapts the tree so it's a valid winner tree again. More...

bool	empty () const
	Returns if all players are deactivated. More...

void	notify_change (unsigned_type index)
	Notify that the value of the player at index has changed. More...

size_t	num_slots () const
	Return the current number of slots. More...

void	print_stats () const
	Print statistical data. More...

void	rebuild ()
	Build from winner tree from scratch. More...

void	replay_on_change (unsigned_type index, bool done=false)

void	replay_on_deactivations (unsigned_type index)
	Replay after the player at index has been deactivated. More...

void	replay_on_pop ()
	Replay after the value of the winning player has changed. More...

void	resize (unsigned_type num_players)

void	resize_and_clear (unsigned_type num_players)
	Deactivate all players and resize the tree. More...

void	resize_and_rebuild (unsigned_type num_players)

std::string	to_string () const
	Returns a readable representation of the winner tree as string. More...

unsigned_type	top () const
	Returns the winner. Remember running replay_on_pop() if the value of the winner changes. More...

Protected Types
typedef fake_timer	stats_timer
	Defines if statistics are gathered: fake_timer or timer. More...

Protected Attributes
const unsigned_type	invalid_key = std::numeric_limits<unsigned_type>::max()

Comparator &	m_less
	the comparator object of this tree More...

unsigned_type	m_num_slots
	number of slots for the players (2^k) More...

stats_type	m_stats
	Collection of stats from the winner_tree. More...

std::vector< unsigned_type >	m_tree
	the binary tree of size 2^(k+1)-1 More...

Member Typedef Documentation

template<typename Comparator>

typedef fake_timer stxxl::winner_tree< Comparator >::stats_timer

protected

Defines if statistics are gathered: fake_timer or timer.

Definition at line 55 of file winner_tree.h.

Constructor & Destructor Documentation

template<typename Comparator>

stxxl::winner_tree< Comparator >::winner_tree	(	unsigned_type	num_players,
		Comparator &	less
	)

inline

Constructor. Reserves space, registers free slots. No games are played here! All players and slots are deactivated in the beginning.

Parameters

num_players	Number of fixed players. Fixed players remain at the same index forever, even if they were deactivated in between.
less	The comparator. It should use two given indices, compare the corresponding values and return the index of one with the smaller value.

Definition at line 88 of file winner_tree.h.

Member Function Documentation

template<typename Comparator>

void stxxl::winner_tree< Comparator >::activate_player ( unsigned_type index )

inline

activate one of the static players or add a new one and replay

Definition at line 99 of file winner_tree.h.

template<typename Comparator>

void stxxl::winner_tree< Comparator >::activate_without_replay ( unsigned_type index )

inline

activate a player and resize if necessary

Definition at line 108 of file winner_tree.h.

Referenced by stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::check_external_level().

template<typename Comparator>

void stxxl::winner_tree< Comparator >::clear ( )

inline

Deactivate all players.

Definition at line 277 of file winner_tree.h.

template<typename Comparator>

void stxxl::winner_tree< Comparator >::deactivate_player ( unsigned_type index )

inline

deactivate a player and replay.

Definition at line 125 of file winner_tree.h.

Referenced by stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::check_external_level().

template<typename Comparator>

void stxxl::winner_tree< Comparator >::deactivate_player_step ( unsigned_type index )

inline

deactivate one player in a batch of deactivations run replay_on_deactivation() afterwards. If there are multiple consecutive removes you should run deactivate_player_step() for all of them first and afterwards run replay_on_deactivation() for each one of them.

Definition at line 138 of file winner_tree.h.

template<typename Comparator>

void stxxl::winner_tree< Comparator >::deactivate_without_replay ( unsigned_type index )

inline

deactivate a player

Definition at line 117 of file winner_tree.h.

Referenced by stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::check_external_level().

template<typename Comparator>

void stxxl::winner_tree< Comparator >::double_num_slots ( )

inline

Doubles the number of slots and adapts the tree so it's a valid winner tree again.

Definition at line 245 of file winner_tree.h.

template<typename Comparator>

bool stxxl::winner_tree< Comparator >::empty ( ) const

inline

Returns if all players are deactivated.

Definition at line 182 of file winner_tree.h.

template<typename Comparator>

void stxxl::winner_tree< Comparator >::notify_change ( unsigned_type index )

inline

Notify that the value of the player at index has changed.

Definition at line 168 of file winner_tree.h.

template<typename Comparator>

size_t stxxl::winner_tree< Comparator >::num_slots ( ) const

inline

Return the current number of slots.

Definition at line 188 of file winner_tree.h.

template<typename Comparator>

void stxxl::winner_tree< Comparator >::print_stats ( ) const

inline

Print statistical data.

Definition at line 357 of file winner_tree.h.

template<typename Comparator>

void stxxl::winner_tree< Comparator >::rebuild ( )

inline

Build from winner tree from scratch.

Definition at line 309 of file winner_tree.h.

Referenced by stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::check_external_level().

template<typename Comparator>

void stxxl::winner_tree< Comparator >::replay_on_change	(	unsigned_type	index,
		bool	done = `false`
	)

inline

Replays all games the player with the given index is involved in. This corresponds to the path from leaf [index] to root. If only the value of player [index] has changed the result is a valid winner tree.

Parameters

index	The player whose value has changed.
done	Set done to true if the player has been deactivated or removed. All games will be lost then.

Definition at line 210 of file winner_tree.h.

Referenced by stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::check_external_level().

template<typename Comparator>

void stxxl::winner_tree< Comparator >::replay_on_deactivations ( unsigned_type index )

inline

Replay after the player at index has been deactivated.

Definition at line 160 of file winner_tree.h.

template<typename Comparator>

void stxxl::winner_tree< Comparator >::replay_on_pop ( )

inline

Replay after the value of the winning player has changed.

Definition at line 194 of file winner_tree.h.

template<typename Comparator>

void stxxl::winner_tree< Comparator >::resize ( unsigned_type num_players )

inline

Definition at line 282 of file winner_tree.h.

template<typename Comparator>

void stxxl::winner_tree< Comparator >::resize_and_clear ( unsigned_type num_players )

inline

Deactivate all players and resize the tree.

Definition at line 290 of file winner_tree.h.

template<typename Comparator>

void stxxl::winner_tree< Comparator >::resize_and_rebuild ( unsigned_type num_players )

inline

Definition at line 296 of file winner_tree.h.

template<typename Comparator>

std::string stxxl::winner_tree< Comparator >::to_string ( ) const

inline

Returns a readable representation of the winner tree as string.

Definition at line 336 of file winner_tree.h.

template<typename Comparator>

unsigned_type stxxl::winner_tree< Comparator >::top ( ) const

inline

Returns the winner. Remember running replay_on_pop() if the value of the winner changes.

Definition at line 176 of file winner_tree.h.

Referenced by stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::check_external_level().

Member Data Documentation

template<typename Comparator>

const unsigned_type stxxl::winner_tree< Comparator >::invalid_key = std::numeric_limits<unsigned_type>::max()

protected

Definition at line 75 of file winner_tree.h.

template<typename Comparator>

Comparator& stxxl::winner_tree< Comparator >::m_less

protected

the comparator object of this tree

Definition at line 49 of file winner_tree.h.

template<typename Comparator>

unsigned_type stxxl::winner_tree< Comparator >::m_num_slots

protected

number of slots for the players (2^k)

Definition at line 52 of file winner_tree.h.

template<typename Comparator>

stats_type stxxl::winner_tree< Comparator >::m_stats

protected

Collection of stats from the winner_tree.

Definition at line 73 of file winner_tree.h.

template<typename Comparator>

std::vector<unsigned_type> stxxl::winner_tree< Comparator >::m_tree

protected

the binary tree of size 2^(k+1)-1

Definition at line 46 of file winner_tree.h.

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

include/stxxl/bits/common/winner_tree.h

Detailed Description

template<typename Comparator> class stxxl::winner_tree< Comparator >

Classes

Public Member Functions

Protected Types

Protected Attributes

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename Comparator>
class stxxl::winner_tree< Comparator >