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 >:

Collaboration diagram for stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >:

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
Element *	current [KNKMAX]
Element *	current_end [KNKMAX]
Element *	segment [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:

KNKMAX

maximum 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

(

)

Definition at line 206 of file pq_losertree.h.

References stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::current, stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::current_end, stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::free_slots, stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::init(), stxxl::priority_queue_local::internal_bounded_stack< Tp_, max_size_ >::push(), stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::segment, and stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::sentinel.

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

(

)

Definition at line 218 of file pq_losertree.h.

Referenced by stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::loser_tree(), and main().

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
	)

Definition at line 504 of file pq_losertree.h.

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

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]

Definition at line 52 of file pq_losertree.h.

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

template<class ValTp_, class Cmp_, unsigned KNKMAX>

Element* stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::current[KNKMAX] [private]

Definition at line 71 of file pq_losertree.h.

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

template<class ValTp_, class Cmp_, unsigned KNKMAX>

Element* stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::current_end[KNKMAX] [private]

Definition at line 72 of file pq_losertree.h.

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

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]

Definition at line 54 of file pq_losertree.h.

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

template<class ValTp_, class Cmp_, unsigned KNKMAX>

unsigned_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::k [private]

Definition at line 58 of file pq_losertree.h.

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

template<class ValTp_, class Cmp_, unsigned KNKMAX>

unsigned_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::logK [private]

Definition at line 57 of file pq_losertree.h.

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

template<class ValTp_, class Cmp_, unsigned KNKMAX>

unsigned_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::mem_cons_ [private]

Definition at line 76 of file pq_losertree.h.

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

template<class ValTp_, class Cmp_, unsigned KNKMAX>

Element* stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::segment[KNKMAX] [private]

Definition at line 73 of file pq_losertree.h.

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

template<class ValTp_, class Cmp_, unsigned KNKMAX>

unsigned_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::segment_size[KNKMAX] [private]

Definition at line 74 of file pq_losertree.h.

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

template<class ValTp_, class Cmp_, unsigned KNKMAX>

Element stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::sentinel [private]

Definition at line 60 of file pq_losertree.h.

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

template<class ValTp_, class Cmp_, unsigned KNKMAX>

unsigned_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::size_ [private]

Definition at line 56 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