priority_queue< Config_ > Class Template Reference

External priority queue data structure. More...

#include <priority_queue.h>

Inherits noncopyable.

Collaboration diagram for priority_queue< Config_ >:

List of all members.

Public Types
enum	{   delete_buffer_size = Config::delete_buffer_size, N = Config::N, IntKMAX = Config::IntKMAX, num_int_groups = Config::num_int_groups,   num_ext_groups = Config::num_ext_groups, total_num_groups = Config::num_int_groups + Config::num_ext_groups, BlockSize = Config::BlockSize, ExtKMAX = Config::ExtKMAX }
typedef Config_	Config
typedef Config::value_type	value_type
	The type of object stored in the priority_queue.
typedef Config::comparator_type	comparator_type
	Comparison object.
typedef Config::alloc_strategy_type	alloc_strategy_type
typedef stxxl::uint64	size_type
	An unsigned integral type (64 bit).
typedef typed_block< BlockSize, value_type >	block_type
typedef read_write_pool < block_type >	pool_type
Public Member Functions
	priority_queue (pool_type &pool_)
	Constructs external priority queue object.
	_STXXL_DEPRECATED (priority_queue(prefetch_pool< block_type > &p_pool_, write_pool< block_type > &w_pool_))
	Constructs external priority queue object.
	priority_queue (unsigned_type p_pool_mem, unsigned_type w_pool_mem)
	Constructs external priority queue object.
void	swap (priority_queue &obj)
	swap this priority queue with another one Implementation correctness is questionable.
size_type	size () const
	Returns number of elements contained.
bool	empty () const
	Returns true if queue has no elements.
const value_type &	top () const
	Returns "largest" element.
void	pop ()
	Removes the element at the top.
void	push (const value_type &obj)
	Inserts x into the priority_queue.
unsigned_type	mem_cons () const
	Returns number of bytes consumed by the priority_queue.
Protected Types
typedef priority_queue_local::internal_priority_queue < value_type, std::vector < value_type > , comparator_type >	insert_heap_type
typedef priority_queue_local::loser_tree < value_type, comparator_type, IntKMAX >	int_merger_type
typedef priority_queue_local::ext_merger < block_type, comparator_type, ExtKMAX, alloc_strategy_type >	ext_merger_type
Protected Attributes
int_merger_type	int_mergers [num_int_groups]
pool_type *	pool
bool	pool_owned
ext_merger_type *	ext_mergers
value_type	group_buffers [total_num_groups][N+1]
value_type *	group_buffer_current_mins [total_num_groups]
value_type	delete_buffer [delete_buffer_size+1]
value_type *	delete_buffer_current_min
value_type *	delete_buffer_end
comparator_type	cmp
insert_heap_type	insert_heap
unsigned_type	num_active_groups
size_type	size_

---

Detailed Description

template<class Config_>
class priority_queue< Config_ >

External priority queue data structure.

---

Member Typedef Documentation

template<class Config_ >

typedef Config::comparator_type priority_queue< Config_ >::comparator_type

Comparison object.

template<class Config_ >

typedef stxxl::uint64 priority_queue< Config_ >::size_type

An unsigned integral type (64 bit).

template<class Config_ >

typedef Config::value_type priority_queue< Config_ >::value_type

The type of object stored in the priority_queue.

---

Constructor & Destructor Documentation

template<class Config_ >

priority_queue< Config_ >::priority_queue

(

pool_type &

pool_

)

Constructs external priority queue object.

Parameters:

pool_

pool of blocks that will be used for data writing and prefetching for the disk<->memory transfers happening in the priority queue. Larger pool size helps to speed up operations.

template<class Config_ >

priority_queue< Config_ >::priority_queue	(	unsigned_type	p_pool_mem,
		unsigned_type	w_pool_mem
	)

Constructs external priority queue object.

Parameters:

	p_pool_mem	memory (in bytes) for prefetch pool that will be used for data prefetching for the disk<->memory transfers happening in the priority queue. Larger pool size helps to speed up operations.
	w_pool_mem	memory (in bytes) for buffered write pool that will be used for writing data for the memory<->disk transfers happening in the priority queue. Larger pool size helps to speed up operations.

---

Member Function Documentation

template<class Config_ >

priority_queue< Config_ >::_STXXL_DEPRECATED

(

priority_queue< Config_ >(prefetch_pool< block_type > &p_pool_, write_pool< block_type > &w_pool_)

)

Constructs external priority queue object.

Parameters:

	p_pool_	pool of blocks that will be used for data prefetching for the disk<->memory transfers happening in the priority queue. Larger pool size helps to speed up operations.
	w_pool_	pool of blocks that will be used for writing data for the memory<->disk transfers happening in the priority queue. Larger pool size helps to speed up operations.

template<class Config_ >

bool priority_queue< Config_ >::empty

(

)

const [inline]

Returns true if queue has no elements.

Returns:

true if queue has no elements, false otherwise

References priority_queue< Config_ >::size().

template<class Config_ >

unsigned_type priority_queue< Config_ >::mem_cons

(

)

const [inline]

Returns number of bytes consumed by the priority_queue.

number of bytes consumed by the priority_queue from the internal memory not including pools (see the constructor)

template<class Config_ >

void priority_queue< Config_ >::pop

(

)

[inline]

Removes the element at the top.

Removes the element at the top of the priority_queue, that is, the largest element in the priority_queue. Precondition: empty() is false. Postcondition: size() will be decremented by 1.

References priority_queue_local::internal_priority_queue< _Tp, _Sequence, _Compare >::empty(), priority_queue_local::internal_priority_queue< _Tp, _Sequence, _Compare >::pop(), and priority_queue_local::internal_priority_queue< _Tp, _Sequence, _Compare >::top().

template<class Config_ >

void priority_queue< Config_ >::push

(

const value_type &

obj

)

[inline]

Inserts x into the priority_queue.

Inserts x into the priority_queue. Postcondition: size() will be incremented by 1.

References priority_queue_local::internal_priority_queue< _Tp, _Sequence, _Compare >::empty(), priority_queue_local::internal_priority_queue< _Tp, _Sequence, _Compare >::push(), and priority_queue_local::internal_priority_queue< _Tp, _Sequence, _Compare >::size().

template<class Config_ >

priority_queue< Config_ >::size_type priority_queue< Config_ >::size

(

)

const [inline]

Returns number of elements contained.

Returns:

number of elements contained

References priority_queue_local::internal_priority_queue< _Tp, _Sequence, _Compare >::size().

Referenced by priority_queue< Config_ >::empty().

template<class Config_ >

void priority_queue< Config_ >::swap

(

priority_queue< Config_ > &

obj

)

[inline]

swap this priority queue with another one Implementation correctness is questionable.

template<class Config_ >

const priority_queue< Config_ >::value_type & priority_queue< Config_ >::top

(

)

const [inline]

Returns "largest" element.

Returns a const reference to the element at the top of the priority_queue. The element at the top is guaranteed to be the largest element in the priority queue, as determined by the comparison function Config_::comparator_type (the same as the second parameter of PRIORITY_QUEUE_GENERATOR utility class). That is, for every other element x in the priority_queue, Config_::comparator_type(Q.top(), x) is false. Precondition: empty() is false.

References priority_queue_local::internal_priority_queue< _Tp, _Sequence, _Compare >::empty(), and priority_queue_local::internal_priority_queue< _Tp, _Sequence, _Compare >::top().

---

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

• priority_queue.h