Stxxl  1.4.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Public Types | Public Member Functions | Private Member Functions | Private Attributes
stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX > Class Template Reference

Loser tree from Knuth, "Sorting and Searching", Section 5.4.1 ! More...

#include <pq_losertree.h>

Inheritance diagram for stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >:
Inheritance graph
[legend]
Collaboration diagram for stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >:
Collaboration graph
[legend]

List of all members.

Public Types

typedef ValTp_ value_type
typedef Cmp_ comparator_type
typedef value_type Element

Public Member Functions

bool is_sentinel (const Element &a)
bool not_sentinel (const Element &a)
 loser_tree ()
 ~loser_tree ()
void init ()
void swap (loser_tree &obj)
void multi_merge (Element *begin, Element *end)
void multi_merge (Element *, unsigned_type length)
unsigned_type mem_cons () const
bool is_space_available () const
void insert_segment (Element *target, unsigned_type length)
unsigned_type size () const

Private Member Functions

unsigned_type initWinner (unsigned_type root)
void update_on_insert (unsigned_type node, const Element &newKey, unsigned_type newIndex, Element *winnerKey, unsigned_type *winnerIndex, unsigned_type *mask)
void deallocate_segment (unsigned_type slot)
void doubleK ()
void compactTree ()
void rebuildLoserTree ()
bool is_segment_empty (unsigned_type slot)
void multi_merge_k (Element *target, unsigned_type length)

Private Attributes

comparator_type cmp
internal_bounded_stack
< unsigned_type, KNKMAX > 
free_slots
unsigned_type size_
unsigned_type logK
unsigned_type k
Element sentinel
Elementcurrent [KNKMAX]
Elementcurrent_end [KNKMAX]
Elementsegment [KNKMAX]
unsigned_type segment_size [KNKMAX]
unsigned_type mem_cons_

Detailed Description

template<class ValTp_, class Cmp_, unsigned KNKMAX>
class stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >

Loser tree from Knuth, "Sorting and Searching", Section 5.4.1 !

!

Parameters:
KNKMAXmaximum arity of loser tree, has to be a power of two

Definition at line 36 of file pq_losertree.h.


Member Typedef Documentation

template<class ValTp_, class Cmp_, unsigned KNKMAX>
typedef Cmp_ stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::comparator_type

Definition at line 40 of file pq_losertree.h.

template<class ValTp_, class Cmp_, unsigned KNKMAX>
typedef value_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::Element

Definition at line 41 of file pq_losertree.h.

template<class ValTp_, class Cmp_, unsigned KNKMAX>
typedef ValTp_ stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::value_type

Definition at line 39 of file pq_losertree.h.


Constructor & Destructor Documentation

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>
stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::loser_tree ( )
template<class ValTp_ , class Cmp_ , unsigned KNKMAX>
stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::~loser_tree ( )

Definition at line 461 of file pq_losertree.h.


Member Function Documentation

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>
void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::compactTree ( ) [private]

Definition at line 357 of file pq_losertree.h.

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>
void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::deallocate_segment ( unsigned_type  slot) [private]

Definition at line 479 of file pq_losertree.h.

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>
void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::doubleK ( ) [private]

Definition at line 326 of file pq_losertree.h.

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>
void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::init ( )
template<class ValTp_, class Cmp_, unsigned KNKMAX>
unsigned_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::initWinner ( unsigned_type  root) [private]
template<class ValTp_ , class Cmp_ , unsigned KNKMAX>
void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::insert_segment ( Element target,
unsigned_type  length 
)

Definition at line 414 of file pq_losertree.h.

Referenced by main().

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>
bool stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::is_segment_empty ( unsigned_type  slot) [inline, private]

Definition at line 681 of file pq_losertree.h.

template<class ValTp_, class Cmp_, unsigned KNKMAX>
bool stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::is_sentinel ( const Element a) [inline]

Definition at line 155 of file pq_losertree.h.

template<class ValTp_, class Cmp_, unsigned KNKMAX>
bool stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::is_space_available ( ) const [inline]

Definition at line 195 of file pq_losertree.h.

template<class ValTp_, class Cmp_, unsigned KNKMAX>
unsigned_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::mem_cons ( ) const [inline]

Definition at line 193 of file pq_losertree.h.

template<class ValTp_, class Cmp_, unsigned KNKMAX>
void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::multi_merge ( Element begin,
Element end 
) [inline]

Definition at line 187 of file pq_losertree.h.

Referenced by main().

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>
void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::multi_merge ( Element target,
unsigned_type  length 
)
template<class ValTp_, class Cmp_, unsigned KNKMAX>
void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::multi_merge_k ( Element target,
unsigned_type  length 
) [private]
template<class ValTp_, class Cmp_, unsigned KNKMAX>
bool stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::not_sentinel ( const Element a) [inline]

Definition at line 159 of file pq_losertree.h.

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>
void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::rebuildLoserTree ( ) [private]

Definition at line 231 of file pq_losertree.h.

template<class ValTp_, class Cmp_, unsigned KNKMAX>
unsigned_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::size ( ) const [inline]

Definition at line 201 of file pq_losertree.h.

Referenced by main().

template<class ValTp_, class Cmp_, unsigned KNKMAX>
void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::swap ( loser_tree< ValTp_, Cmp_, KNKMAX > &  obj) [inline]

Definition at line 169 of file pq_losertree.h.

Referenced by std::swap().

template<class ValTp_, class Cmp_, unsigned KNKMAX>
void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::update_on_insert ( unsigned_type  node,
const Element newKey,
unsigned_type  newIndex,
Element winnerKey,
unsigned_type winnerIndex,
unsigned_type mask 
) [private]

Member Data Documentation

template<class ValTp_, class Cmp_, unsigned KNKMAX>
comparator_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::cmp [private]
template<class ValTp_, class Cmp_, unsigned KNKMAX>
Element* stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::current[KNKMAX] [private]
template<class ValTp_, class Cmp_, unsigned KNKMAX>
Element* stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::current_end[KNKMAX] [private]
template<class ValTp_, class Cmp_, unsigned KNKMAX>
internal_bounded_stack<unsigned_type, KNKMAX> stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::free_slots [private]
template<class ValTp_, class Cmp_, unsigned KNKMAX>
unsigned_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::k [private]
template<class ValTp_, class Cmp_, unsigned KNKMAX>
unsigned_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::logK [private]
template<class ValTp_, class Cmp_, unsigned KNKMAX>
unsigned_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::mem_cons_ [private]
template<class ValTp_, class Cmp_, unsigned KNKMAX>
Element* stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::segment[KNKMAX] [private]
template<class ValTp_, class Cmp_, unsigned KNKMAX>
unsigned_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::segment_size[KNKMAX] [private]
template<class ValTp_, class Cmp_, unsigned KNKMAX>
Element stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::sentinel [private]
template<class ValTp_, class Cmp_, unsigned KNKMAX>
unsigned_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::size_ [private]

The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines