STXXL  1.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
stxxl::priority_queue< ConfigType > Class Template Reference

Detailed Description

template<class ConfigType>
class stxxl::priority_queue< ConfigType >

External priority queue data structure
Introduction to priority queue container: see STXXL Priority Queue tutorial.
Design and Internals of priority queue container: see Priority Queue.

Examples:
examples/containers/pqueue1.cpp, and examples/containers/pqueue2.cpp.

Definition at line 98 of file priority_queue.h.

+ Inheritance diagram for stxxl::priority_queue< ConfigType >:
+ Collaboration diagram for stxxl::priority_queue< ConfigType >:

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::alloc_strategy_type alloc_strategy_type
 
typedef typed_block< BlockSize,
value_type
block_type
 Type of the block used in disk-memory transfers. More...
 
typedef Config::comparator_type comparator_type
 Comparison object. More...
 
typedef ConfigType Config
 
typedef read_write_pool
< block_type
pool_type
 
typedef stxxl::uint64 size_type
 An unsigned integral type (64 bit). More...
 
typedef Config::value_type value_type
 The type of object stored in the priority_queue. More...
 

Public Member Functions

Constructors/Destructors
 priority_queue (pool_type &pool_)
 Constructs external priority queue object. More...
 
 priority_queue (prefetch_pool< block_type > &p_pool_, write_pool< block_type > &w_pool_)
 Constructs external priority queue object. More...
 
 priority_queue (unsigned_type p_pool_mem, unsigned_type w_pool_mem)
 Constructs external priority queue object. More...
 
virtual ~priority_queue ()
 
Capacity
size_type size () const
 Returns number of elements contained. More...
 
bool empty () const
 Returns true if queue has no elements. More...
 
Operators
const value_typetop () const
 Returns "largest" element. More...
 
Modifiers
void pop ()
 Removes the element at the top. More...
 
void push (const value_type &obj)
 Inserts x into the priority_queue. More...
 
Miscellaneous
unsigned_type mem_cons () const
 Number of bytes consumed by the priority_queue from the internal memory not including pools (see the constructor) More...
 
void dump_sizes () const
 
void dump_params () const
 

Protected Types

typedef
priority_queue_local::ext_merger
< block_type, comparator_type,
ExtKMAX, alloc_strategy_type
ext_merger_type
 
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
 

Protected Attributes

comparator_type cmp
 
value_type delete_buffer [delete_buffer_size+1]
 
value_typedelete_buffer_current_min
 
value_typedelete_buffer_end
 
ext_merger_type ** ext_mergers
 
value_typegroup_buffer_current_mins [total_num_groups]
 
value_type group_buffers [total_num_groups][N+1]
 
insert_heap_type insert_heap
 
int_merger_type int_mergers [num_int_groups]
 
unsigned_type num_active_groups
 
pool_typepool
 
bool pool_owned
 
size_type size_
 

Private Member Functions

unsigned_type current_delete_buffer_size () const
 
unsigned_type current_group_buffer_size (unsigned_type i) const
 
void empty_insert_heap ()
 
value_type get_supremum () const
 
void init ()
 
unsigned_type make_space_available (unsigned_type level)
 
void refill_delete_buffer ()
 
size_type refill_group_buffer (unsigned_type k)
 
- Private Member Functions inherited from stxxl::noncopyable
 noncopyable ()
 

Member Typedef Documentation

template<class ConfigType>
typedef Config::alloc_strategy_type stxxl::priority_queue< ConfigType >::alloc_strategy_type

Definition at line 118 of file priority_queue.h.

template<class ConfigType>
typedef typed_block<BlockSize, value_type> stxxl::priority_queue< ConfigType >::block_type

Type of the block used in disk-memory transfers.

Definition at line 122 of file priority_queue.h.

template<class ConfigType>
typedef Config::comparator_type stxxl::priority_queue< ConfigType >::comparator_type

Comparison object.

Definition at line 117 of file priority_queue.h.

template<class ConfigType>
typedef ConfigType stxxl::priority_queue< ConfigType >::Config

Definition at line 101 of file priority_queue.h.

Definition at line 138 of file priority_queue.h.

template<class ConfigType>
typedef priority_queue_local::internal_priority_queue<value_type, std::vector<value_type>, comparator_type> stxxl::priority_queue< ConfigType >::insert_heap_type
protected

Definition at line 127 of file priority_queue.h.

template<class ConfigType>
typedef priority_queue_local::loser_tree< value_type, comparator_type, IntKMAX> stxxl::priority_queue< ConfigType >::int_merger_type
protected

Definition at line 132 of file priority_queue.h.

template<class ConfigType>
typedef read_write_pool<block_type> stxxl::priority_queue< ConfigType >::pool_type

Definition at line 123 of file priority_queue.h.

template<class ConfigType>
typedef stxxl::uint64 stxxl::priority_queue< ConfigType >::size_type

An unsigned integral type (64 bit).

Definition at line 120 of file priority_queue.h.

template<class ConfigType>
typedef Config::value_type stxxl::priority_queue< ConfigType >::value_type

The type of object stored in the priority_queue.

Definition at line 115 of file priority_queue.h.

Member Enumeration Documentation

template<class ConfigType>
anonymous enum
Enumerator
delete_buffer_size 
N 
IntKMAX 
num_int_groups 
num_ext_groups 
total_num_groups 
BlockSize 
ExtKMAX 

Definition at line 102 of file priority_queue.h.

Constructor & Destructor Documentation

template<class ConfigType >
stxxl::priority_queue< ConfigType >::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.

Definition at line 377 of file priority_queue.h.

References stxxl::priority_queue< ConfigType >::init(), and STXXL_VERBOSE_PQ.

template<class ConfigType >
stxxl::priority_queue< ConfigType >::priority_queue ( 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.

Definition at line 390 of file priority_queue.h.

References stxxl::priority_queue< ConfigType >::init(), and STXXL_VERBOSE_PQ.

template<class ConfigType >
stxxl::priority_queue< ConfigType >::priority_queue ( unsigned_type  p_pool_mem,
unsigned_type  w_pool_mem 
)

Constructs external priority queue object.

Parameters
p_pool_memmemory (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_memmemory (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.

Definition at line 402 of file priority_queue.h.

References stxxl::priority_queue< ConfigType >::init(), and STXXL_VERBOSE_PQ.

template<class ConfigType >
stxxl::priority_queue< ConfigType >::~priority_queue ( )
virtual

Definition at line 436 of file priority_queue.h.

References STXXL_VERBOSE_PQ.

Member Function Documentation

template<class ConfigType>
unsigned_type stxxl::priority_queue< ConfigType >::current_delete_buffer_size ( ) const
inlineprivate

Definition at line 175 of file priority_queue.h.

template<class ConfigType>
unsigned_type stxxl::priority_queue< ConfigType >::current_group_buffer_size ( unsigned_type  i) const
inlineprivate

Definition at line 176 of file priority_queue.h.

template<class ConfigType >
void stxxl::priority_queue< ConfigType >::dump_params ( ) const

Definition at line 837 of file priority_queue.h.

References STXXL_MSG.

template<class ConfigType >
void stxxl::priority_queue< ConfigType >::dump_sizes ( ) const

Definition at line 811 of file priority_queue.h.

References STXXL_MSG.

template<class ConfigType>
bool stxxl::priority_queue< ConfigType >::empty ( ) const
inline

Returns true if queue has no elements.

Returns
true if queue has no elements, false otherwise

Definition at line 257 of file priority_queue.h.

template<class ConfigType >
void stxxl::priority_queue< ConfigType >::empty_insert_heap ( )
private
template<class ConfigType>
value_type stxxl::priority_queue< ConfigType >::get_supremum ( ) const
inlineprivate

Definition at line 174 of file priority_queue.h.

template<class ConfigType >
void stxxl::priority_queue< ConfigType >::init ( )
private
template<class ConfigType>
unsigned_type stxxl::priority_queue< ConfigType >::mem_cons ( ) const
inline

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

Definition at line 300 of file priority_queue.h.

template<class ConfigType >
void stxxl::priority_queue< ConfigType >::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.

Definition at line 345 of file priority_queue.h.

template<class ConfigType >
void stxxl::priority_queue< ConfigType >::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.

Definition at line 362 of file priority_queue.h.

References stxxl::priority_queue< ConfigType >::push().

Referenced by stxxl::priority_queue< ConfigType >::push().

template<class ConfigType >
priority_queue< ConfigType >::size_type stxxl::priority_queue< ConfigType >::refill_group_buffer ( unsigned_type  k)
private

Definition at line 452 of file priority_queue.h.

References stxxl::is_sorted(), STXXL_MSG, and STXXL_VERBOSE_PQ.

template<class ConfigType >
priority_queue< ConfigType >::size_type stxxl::priority_queue< ConfigType >::size ( ) const
inline

Returns number of elements contained.

Returns
number of elements contained

Definition at line 324 of file priority_queue.h.

References stxxl::priority_queue< ConfigType >::size().

Referenced by stxxl::priority_queue< ConfigType >::size().

template<class ConfigType >
const priority_queue< ConfigType >::value_type & stxxl::priority_queue< ConfigType >::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 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, comparator_type(Q.top(), x) is false. Precondition: empty() is false.

Definition at line 333 of file priority_queue.h.

References stxxl::priority_queue< ConfigType >::top().

Referenced by stxxl::priority_queue< ConfigType >::top().

Member Data Documentation

template<class ConfigType>
comparator_type stxxl::priority_queue< ConfigType >::cmp
protected

Definition at line 154 of file priority_queue.h.

template<class ConfigType>
value_type stxxl::priority_queue< ConfigType >::delete_buffer[delete_buffer_size+1]
protected

Definition at line 150 of file priority_queue.h.

template<class ConfigType>
value_type* stxxl::priority_queue< ConfigType >::delete_buffer_current_min
protected

Definition at line 151 of file priority_queue.h.

template<class ConfigType>
value_type* stxxl::priority_queue< ConfigType >::delete_buffer_end
protected

Definition at line 152 of file priority_queue.h.

template<class ConfigType>
ext_merger_type** stxxl::priority_queue< ConfigType >::ext_mergers
protected

Definition at line 143 of file priority_queue.h.

template<class ConfigType>
value_type* stxxl::priority_queue< ConfigType >::group_buffer_current_mins[total_num_groups]
protected

Definition at line 147 of file priority_queue.h.

template<class ConfigType>
value_type stxxl::priority_queue< ConfigType >::group_buffers[total_num_groups][N+1]
protected

Definition at line 146 of file priority_queue.h.

template<class ConfigType>
insert_heap_type stxxl::priority_queue< ConfigType >::insert_heap
protected

Definition at line 157 of file priority_queue.h.

template<class ConfigType>
int_merger_type stxxl::priority_queue< ConfigType >::int_mergers[num_int_groups]
protected

Definition at line 140 of file priority_queue.h.

template<class ConfigType>
unsigned_type stxxl::priority_queue< ConfigType >::num_active_groups
protected

Definition at line 160 of file priority_queue.h.

template<class ConfigType>
pool_type* stxxl::priority_queue< ConfigType >::pool
protected

Definition at line 141 of file priority_queue.h.

template<class ConfigType>
bool stxxl::priority_queue< ConfigType >::pool_owned
protected

Definition at line 142 of file priority_queue.h.

template<class ConfigType>
size_type stxxl::priority_queue< ConfigType >::size_
protected

Definition at line 163 of file priority_queue.h.


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