stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity > Class Template Reference

Detailed Description

template<class ValueType, class CompareType, unsigned MaxArity>
class stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >

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

Parameters

MaxArity

maximum arity of loser tree, has to be a power of two

Definition at line 38 of file pq_losertree.h.

Inheritance diagram for stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >:

Collaboration diagram for stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >:

Public Types
enum	{ max_arity = MaxArity }
typedef CompareType	comparator_type
typedef value_type	Element
typedef ValueType	value_type

Public Member Functions
	loser_tree ()
	~loser_tree ()
void	init ()
void	insert_segment (Element *target, unsigned_type length)
	insert segment beginning at target More...
bool	is_sentinel (const Element &a)
bool	is_space_available () const
unsigned_type	mem_cons () const
void	multi_merge (Element *begin, Element *end)
void	multi_merge (Element *, unsigned_type length)
bool	not_sentinel (const Element &a)
unsigned_type	size () const
void	swap (loser_tree &obj)

Private Member Functions
void	compactTree ()
void	deallocate_segment (unsigned_type slot)
void	doubleK ()
unsigned_type	initWinner (unsigned_type root)
bool	is_segment_empty (unsigned_type slot)
void	multi_merge_k (Element *target, unsigned_type length)
void	rebuildLoserTree ()
void	update_on_insert (unsigned_type node, const Element &newKey, unsigned_type newIndex, Element *winnerKey, unsigned_type *winnerIndex, unsigned_type *mask)
Private Member Functions inherited from stxxl::noncopyable
	noncopyable ()

Private Attributes
comparator_type	cmp
Element *	current [MaxArity]
Element *	current_end [MaxArity]
internal_bounded_stack < unsigned_type, MaxArity >	free_slots
unsigned_type	k
unsigned_type	logK
unsigned_type	mem_cons_
Element *	segment [MaxArity]
unsigned_type	segment_size [MaxArity]
Element	sentinel
unsigned_type	size_

Member Typedef Documentation

template<class ValueType, class CompareType, unsigned MaxArity>

typedef CompareType stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::comparator_type

Definition at line 42 of file pq_losertree.h.

template<class ValueType, class CompareType, unsigned MaxArity>

typedef value_type stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::Element

Definition at line 43 of file pq_losertree.h.

template<class ValueType, class CompareType, unsigned MaxArity>

typedef ValueType stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::value_type

Definition at line 41 of file pq_losertree.h.

Member Enumeration Documentation

template<class ValueType, class CompareType, unsigned MaxArity>

anonymous enum

Enumerator
max_arity

Definition at line 44 of file pq_losertree.h.

Constructor & Destructor Documentation

template<class ValueType , class CompareType , unsigned MaxArity>

stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::loser_tree

(

)

Definition at line 211 of file pq_losertree.h.

References stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::current, stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::current_end, stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::free_slots, stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::init(), stxxl::priority_queue_local::internal_bounded_stack< ValueType, MaxSize >::push(), stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::segment, and stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::sentinel.

template<class ValueType , class CompareType , unsigned MaxArity>

stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::~loser_tree

(

)

Definition at line 461 of file pq_losertree.h.

References STXXL_VERBOSE1, and STXXL_VERBOSE2.

Member Function Documentation

template<class ValueType , class CompareType , unsigned MaxArity>

void stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::compactTree ( )

private

Definition at line 359 of file pq_losertree.h.

References STXXL_VERBOSE3.

template<class ValueType , class CompareType , unsigned MaxArity>

void stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::deallocate_segment ( unsigned_type  slot )

private

Definition at line 480 of file pq_losertree.h.

References STXXL_VERBOSE2.

template<class ValueType , class CompareType , unsigned MaxArity>

void stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::doubleK ( )

private

Definition at line 329 of file pq_losertree.h.

References STXXL_VERBOSE3.

template<class ValueType , class CompareType , unsigned MaxArity>

void stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::init

(

)

Definition at line 224 of file pq_losertree.h.

Referenced by stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::loser_tree().

template<class ValueType, class CompareType, unsigned MaxArity>

unsigned_type stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::initWinner ( unsigned_type  root )

private

template<class ValueType , class CompareType , unsigned MaxArity>

void stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::insert_segment	(	Element *	target,
		unsigned_type	length
	)

insert segment beginning at target

Definition at line 416 of file pq_losertree.h.

References STXXL_VERBOSE2.

template<class ValueType , class CompareType , unsigned MaxArity>

bool stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::is_segment_empty ( unsigned_type  slot )

inlineprivate

Definition at line 681 of file pq_losertree.h.

template<class ValueType, class CompareType, unsigned MaxArity>

bool stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::is_sentinel ( const Element &  a )

inline

Definition at line 158 of file pq_losertree.h.

template<class ValueType, class CompareType, unsigned MaxArity>

bool stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::is_space_available ( ) const

inline

Definition at line 198 of file pq_losertree.h.

template<class ValueType, class CompareType, unsigned MaxArity>

unsigned_type stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::mem_cons ( ) const

inline

Definition at line 196 of file pq_losertree.h.

template<class ValueType, class CompareType, unsigned MaxArity>

void stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::multi_merge ( Element *  begin, Element *  end  )

inline

Definition at line 190 of file pq_losertree.h.

template<class ValueType , class CompareType , unsigned MaxArity>

void stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::multi_merge	(	Element *	target,
		unsigned_type	length
	)

Definition at line 505 of file pq_losertree.h.

References stxxl::priority_queue_local::merge3_iterator(), stxxl::priority_queue_local::merge4_iterator(), stxxl::priority_queue_local::merge_iterator(), and STXXL_VERBOSE3.

template<class ValueType, class CompareType, unsigned MaxArity>

void stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::multi_merge_k ( Element *  target, unsigned_type  length  )

private

template<class ValueType, class CompareType, unsigned MaxArity>

bool stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::not_sentinel ( const Element &  a )

inline

Definition at line 162 of file pq_losertree.h.

template<class ValueType , class CompareType , unsigned MaxArity>

void stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::rebuildLoserTree ( )

private

Definition at line 236 of file pq_losertree.h.

template<class ValueType, class CompareType, unsigned MaxArity>

unsigned_type stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::size ( ) const

inline

Definition at line 206 of file pq_losertree.h.

template<class ValueType, class CompareType, unsigned MaxArity>

void stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::swap ( loser_tree< ValueType, CompareType, MaxArity > &  obj )

inline

Definition at line 172 of file pq_losertree.h.

template<class ValueType, class CompareType, unsigned MaxArity>

void stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::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 ValueType, class CompareType, unsigned MaxArity>

comparator_type stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::cmp

private

Definition at line 55 of file pq_losertree.h.

Referenced by stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().

template<class ValueType, class CompareType, unsigned MaxArity>

Element* stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::current[MaxArity]

private

Definition at line 74 of file pq_losertree.h.

Referenced by stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::loser_tree(), and stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().

template<class ValueType, class CompareType, unsigned MaxArity>

Element* stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::current_end[MaxArity]

private

Definition at line 75 of file pq_losertree.h.

Referenced by stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::loser_tree(), and stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().

template<class ValueType, class CompareType, unsigned MaxArity>

internal_bounded_stack<unsigned_type, MaxArity> stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::free_slots

private

Definition at line 57 of file pq_losertree.h.

Referenced by stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::loser_tree(), and stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().

template<class ValueType, class CompareType, unsigned MaxArity>

unsigned_type stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::k

private

Definition at line 61 of file pq_losertree.h.

Referenced by stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().

template<class ValueType, class CompareType, unsigned MaxArity>

unsigned_type stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::logK

private

Definition at line 60 of file pq_losertree.h.

Referenced by stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().

template<class ValueType, class CompareType, unsigned MaxArity>

unsigned_type stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::mem_cons_

private

Definition at line 79 of file pq_losertree.h.

Referenced by stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().

template<class ValueType, class CompareType, unsigned MaxArity>

Element* stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::segment[MaxArity]

private

Definition at line 76 of file pq_losertree.h.

Referenced by stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::loser_tree(), and stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().

template<class ValueType, class CompareType, unsigned MaxArity>

unsigned_type stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::segment_size[MaxArity]

private

Definition at line 77 of file pq_losertree.h.

Referenced by stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().

template<class ValueType, class CompareType, unsigned MaxArity>

Element stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::sentinel

private

Definition at line 63 of file pq_losertree.h.

Referenced by stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::loser_tree(), and stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().

template<class ValueType, class CompareType, unsigned MaxArity>

unsigned_type stxxl::priority_queue_local::loser_tree< ValueType, CompareType, MaxArity >::size_

private

Definition at line 59 of file pq_losertree.h.

Referenced by stxxl::priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX >::swap().

---

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

• include/stxxl/bits/containers/pq_losertree.h