stxxl::ppq_local::minima_tree< ParentType > Class Template Reference

Detailed Description

template<class ParentType>
class stxxl::ppq_local::minima_tree< ParentType >

The minima_tree contains minima from all sources inside the PPQ.

It contains four substructures: winner trees for insertion heaps, internal and external arrays, each containing the minima from all currently allocated structures. These three sources, plus the deletion buffer are combined using a "head" inner tree containing only up to four item.

Definition at line 1577 of file parallel_priority_queue.h.

Inheritance diagram for stxxl::ppq_local::minima_tree< ParentType >:

Collaboration diagram for stxxl::ppq_local::minima_tree< ParentType >:

Classes
struct	head_comp
	WinnerTree-Comparator for the head winner tree. It accesses all relevant data structures from the priority queue. More...
struct	heaps_comp
	Comparator for the insertion heaps winner tree. More...
struct	ia_comp
	Comparator for the internal arrays winner tree. More...

Public Types
typedef parent_type::inv_compare_type	compare_type
typedef parent_type::external_arrays_type	eas_type
typedef parent_type::internal_arrays_type	ias_type
typedef ParentType	parent_type
typedef parent_type::proc_vector_type	proc_vector_type
typedef minima_tree< ParentType >	self_type
enum	Types { HEAP = 0, IA = 1, EB = 2, TYPE_ERROR = 3 }
	Entries in the head winner tree. More...
typedef parent_type::value_type	value_type

Public Member Functions
	minima_tree (parent_type &parent)
	Construct the tree of minima sources. More...
void	add_internal_array (unsigned index)
	Add a newly created internal array to the minima tree. More...
void	clear_heaps ()
	Remove all insertion heaps from the minima tree. More...
void	clear_internal_arrays ()
	Remove all internal arrays from the minima tree. More...
void	deactivate_extract_buffer ()
	Remove the extract buffer from the minima tree. More...
void	deactivate_heap (unsigned index)
	Remove an insertion heap from the minima tree. More...
void	deactivate_internal_array (unsigned index)
	Remove an internal array from the minima tree. More...
size_t	ia_slots () const
	Return size of internal arrays minima tree. More...
void	print_stats () const
	Prints statistical data. More...
void	rebuild_internal_arrays ()
std::string	to_string () const
	Returns a readable representation of the winner tree as string. More...
std::pair< unsigned, unsigned >	top ()
	Return smallest items of head winner tree. More...
void	update_extract_buffer ()
	Update minima tree after an item of the extract buffer was removed. More...
void	update_heap (int_type index)
	Update minima tree after an item from the heap index was removed. More...
void	update_internal_array (unsigned index)
	Update minima tree after an item from an internal array was removed. More...

Static Public Attributes
static const unsigned	initial_ea_size = 2
static const unsigned	initial_ia_size = 2

Protected Attributes
const compare_type &	m_compare
	value_type comparator More...
winner_tree< head_comp >	m_head
	The winner trees. More...
head_comp	m_head_comp
	Comperator instances. More...
winner_tree< heaps_comp >	m_heaps
heaps_comp	m_heaps_comp
winner_tree< ia_comp >	m_ia
ia_comp	m_ia_comp
parent_type &	m_parent
	The priority queue. More...

Member Typedef Documentation

template<class ParentType>

typedef parent_type::inv_compare_type stxxl::ppq_local::minima_tree< ParentType >::compare_type

Definition at line 1583 of file parallel_priority_queue.h.

template<class ParentType>

typedef parent_type::external_arrays_type stxxl::ppq_local::minima_tree< ParentType >::eas_type

Definition at line 1587 of file parallel_priority_queue.h.

template<class ParentType>

typedef parent_type::internal_arrays_type stxxl::ppq_local::minima_tree< ParentType >::ias_type

Definition at line 1586 of file parallel_priority_queue.h.

template<class ParentType>

typedef ParentType stxxl::ppq_local::minima_tree< ParentType >::parent_type

Definition at line 1580 of file parallel_priority_queue.h.

template<class ParentType>

typedef parent_type::proc_vector_type stxxl::ppq_local::minima_tree< ParentType >::proc_vector_type

Definition at line 1585 of file parallel_priority_queue.h.

template<class ParentType>

typedef minima_tree<ParentType> stxxl::ppq_local::minima_tree< ParentType >::self_type

Definition at line 1581 of file parallel_priority_queue.h.

template<class ParentType>

typedef parent_type::value_type stxxl::ppq_local::minima_tree< ParentType >::value_type

Definition at line 1584 of file parallel_priority_queue.h.

Member Enumeration Documentation

template<class ParentType>

enum stxxl::ppq_local::minima_tree::Types

Entries in the head winner tree.

Enumerator
HEAP
IA
EB
TYPE_ERROR

Definition at line 1688 of file parallel_priority_queue.h.

Constructor & Destructor Documentation

template<class ParentType>

stxxl::ppq_local::minima_tree< ParentType >::minima_tree ( parent_type &  parent )

inline

Construct the tree of minima sources.

Definition at line 1696 of file parallel_priority_queue.h.

Member Function Documentation

template<class ParentType>

void stxxl::ppq_local::minima_tree< ParentType >::add_internal_array ( unsigned  index )

inline

Add a newly created internal array to the minima tree.

Definition at line 1748 of file parallel_priority_queue.h.

template<class ParentType>

void stxxl::ppq_local::minima_tree< ParentType >::clear_heaps ( )

inline

Remove all insertion heaps from the minima tree.

Definition at line 1781 of file parallel_priority_queue.h.

template<class ParentType>

void stxxl::ppq_local::minima_tree< ParentType >::clear_internal_arrays ( )

inline

Remove all internal arrays from the minima tree.

Definition at line 1788 of file parallel_priority_queue.h.

template<class ParentType>

void stxxl::ppq_local::minima_tree< ParentType >::deactivate_extract_buffer ( )

inline

Remove the extract buffer from the minima tree.

Definition at line 1765 of file parallel_priority_queue.h.

template<class ParentType>

void stxxl::ppq_local::minima_tree< ParentType >::deactivate_heap ( unsigned  index )

inline

Remove an insertion heap from the minima tree.

Definition at line 1755 of file parallel_priority_queue.h.

template<class ParentType>

void stxxl::ppq_local::minima_tree< ParentType >::deactivate_internal_array ( unsigned  index )

inline

Remove an internal array from the minima tree.

Definition at line 1771 of file parallel_priority_queue.h.

template<class ParentType>

size_t stxxl::ppq_local::minima_tree< ParentType >::ia_slots ( ) const

inline

Return size of internal arrays minima tree.

Definition at line 1808 of file parallel_priority_queue.h.

template<class ParentType>

void stxxl::ppq_local::minima_tree< ParentType >::print_stats ( ) const

inline

Prints statistical data.

Definition at line 1824 of file parallel_priority_queue.h.

template<class ParentType>

void stxxl::ppq_local::minima_tree< ParentType >::rebuild_internal_arrays ( )

inline

Definition at line 1794 of file parallel_priority_queue.h.

template<class ParentType>

std::string stxxl::ppq_local::minima_tree< ParentType >::to_string ( ) const

inline

Returns a readable representation of the winner tree as string.

Definition at line 1814 of file parallel_priority_queue.h.

template<class ParentType>

std::pair<unsigned, unsigned> stxxl::ppq_local::minima_tree< ParentType >::top ( )

inline

Return smallest items of head winner tree.

Definition at line 1711 of file parallel_priority_queue.h.

template<class ParentType>

void stxxl::ppq_local::minima_tree< ParentType >::update_extract_buffer ( )

inline

Update minima tree after an item of the extract buffer was removed.

Definition at line 1735 of file parallel_priority_queue.h.

template<class ParentType>

void stxxl::ppq_local::minima_tree< ParentType >::update_heap ( int_type  index )

inline

Update minima tree after an item from the heap index was removed.

Definition at line 1728 of file parallel_priority_queue.h.

template<class ParentType>

void stxxl::ppq_local::minima_tree< ParentType >::update_internal_array ( unsigned  index )

inline

Update minima tree after an item from an internal array was removed.

Definition at line 1741 of file parallel_priority_queue.h.

Member Data Documentation

template<class ParentType>

const unsigned stxxl::ppq_local::minima_tree< ParentType >::initial_ea_size = 2

static

Definition at line 1590 of file parallel_priority_queue.h.

template<class ParentType>

const unsigned stxxl::ppq_local::minima_tree< ParentType >::initial_ia_size = 2

static

Definition at line 1589 of file parallel_priority_queue.h.

template<class ParentType>

const compare_type& stxxl::ppq_local::minima_tree< ParentType >::m_compare

protected

value_type comparator

Definition at line 1674 of file parallel_priority_queue.h.

template<class ParentType>

winner_tree<head_comp> stxxl::ppq_local::minima_tree< ParentType >::m_head

protected

The winner trees.

Definition at line 1682 of file parallel_priority_queue.h.

template<class ParentType>

head_comp stxxl::ppq_local::minima_tree< ParentType >::m_head_comp

protected

Comperator instances.

Definition at line 1677 of file parallel_priority_queue.h.

template<class ParentType>

winner_tree<heaps_comp> stxxl::ppq_local::minima_tree< ParentType >::m_heaps

protected

Definition at line 1683 of file parallel_priority_queue.h.

template<class ParentType>

heaps_comp stxxl::ppq_local::minima_tree< ParentType >::m_heaps_comp

protected

Definition at line 1678 of file parallel_priority_queue.h.

template<class ParentType>

winner_tree<ia_comp> stxxl::ppq_local::minima_tree< ParentType >::m_ia

protected

Definition at line 1684 of file parallel_priority_queue.h.

template<class ParentType>

ia_comp stxxl::ppq_local::minima_tree< ParentType >::m_ia_comp

protected

Definition at line 1679 of file parallel_priority_queue.h.

template<class ParentType>

parent_type& stxxl::ppq_local::minima_tree< ParentType >::m_parent

protected

The priority queue.

Definition at line 1671 of file parallel_priority_queue.h.

---

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

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