STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
stxxl::winner_tree< Comparator > Class Template Reference

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_typem_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_playersNumber of fixed players. Fixed players remain at the same index forever, even if they were deactivated in between.
lessThe 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
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
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
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
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
indexThe player whose value has changed.
doneSet 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: