STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
stxxl::ppq_local::internal_array< ValueType > Class Template Reference

Detailed Description

template<class ValueType>
class stxxl::ppq_local::internal_array< ValueType >

Internal arrays store a sorted sequence of values in RAM, which will be merged together into the deletion buffer when it needs to be refilled.

Internal arrays are constructed from the insertions heaps when they overflow.

Definition at line 275 of file parallel_priority_queue.h.

+ Inheritance diagram for stxxl::ppq_local::internal_array< ValueType >:
+ Collaboration diagram for stxxl::ppq_local::internal_array< ValueType >:

Public Types

typedef ppq_iterator< value_typeiterator
 
typedef ValueType value_type
 

Public Member Functions

 internal_array ()
 Default constructor. Don't use this directy. Needed for regrowing in surrounding vector. More...
 
 internal_array (std::vector< value_type > &values, unsigned_type min_index=0, unsigned_type level=0)
 Constructor which takes a value vector. The value vector is empty afterwards. More...
 
iterator begin () const
 Begin iterator. More...
 
size_t capacity () const
 Returns the initial size of the array. More...
 
bool empty () const
 Returns if the array has run empty. More...
 
iterator end () const
 End iterator. More...
 
size_t get_max_index () const
 The index of the largest element in the array. More...
 
const value_typeget_min () const
 The currently smallest element in the array. More...
 
size_t get_min_index () const
 The index of the currently smallest element in the array. More...
 
void inc_min (size_t diff=1)
 Use inc_min(diff) if multiple values have been extracted. More...
 
size_t int_memory () const
 Return the amount of internal memory used by the array. More...
 
unsigned_type level () const
 Returns the level (group number) of the array. More...
 
void make_empty ()
 Make this array empty. More...
 
value_typeoperator[] (size_t i)
 Random access operator. More...
 
size_t size () const
 Returns the current size of the array. More...
 
void swap (internal_array &o)
 Swap internal_array with another one. More...
 

Static Public Member Functions

static size_t int_memory (size_t capacity)
 Return the amount of internal memory used by an array with the capacity in number of items. More...
 

Protected Types

typedef
iterator::block_pointers_type 
block_pointers_type
 

Protected Attributes

block_pointers_type m_block_pointers
 Begin and end pointers of the array This is used by the iterator. More...
 
unsigned_type m_level
 Level of internal array (Sander's PQ: group number) More...
 
unsigned_type m_min_index
 Index of the current head. More...
 
std::vector< value_typem_values
 Contains the items of the sorted sequence. More...
 

Friends

void swap (internal_array &a, internal_array &b)
 Swap internal_array with another one. More...
 

Additional Inherited Members

- Private Member Functions inherited from stxxl::noncopyable
 noncopyable ()
 

Member Typedef Documentation

template<class ValueType >
typedef iterator::block_pointers_type stxxl::ppq_local::internal_array< ValueType >::block_pointers_type
protected

Definition at line 282 of file parallel_priority_queue.h.

template<class ValueType >
typedef ppq_iterator<value_type> stxxl::ppq_local::internal_array< ValueType >::iterator

Definition at line 279 of file parallel_priority_queue.h.

template<class ValueType >
typedef ValueType stxxl::ppq_local::internal_array< ValueType >::value_type

Definition at line 278 of file parallel_priority_queue.h.

Constructor & Destructor Documentation

template<class ValueType >
stxxl::ppq_local::internal_array< ValueType >::internal_array ( )
inline

Default constructor. Don't use this directy. Needed for regrowing in surrounding vector.

Definition at line 300 of file parallel_priority_queue.h.

template<class ValueType >
stxxl::ppq_local::internal_array< ValueType >::internal_array ( std::vector< value_type > &  values,
unsigned_type  min_index = 0,
unsigned_type  level = 0 
)
inline

Constructor which takes a value vector. The value vector is empty afterwards.

Definition at line 304 of file parallel_priority_queue.h.

References STXXL_ASSERT.

Member Function Documentation

template<class ValueType >
iterator stxxl::ppq_local::internal_array< ValueType >::begin ( ) const
inline

Begin iterator.

Definition at line 406 of file parallel_priority_queue.h.

template<class ValueType >
size_t stxxl::ppq_local::internal_array< ValueType >::capacity ( ) const
inline

Returns the initial size of the array.

Definition at line 381 of file parallel_priority_queue.h.

template<class ValueType >
bool stxxl::ppq_local::internal_array< ValueType >::empty ( ) const
inline
template<class ValueType >
iterator stxxl::ppq_local::internal_array< ValueType >::end ( ) const
inline

End iterator.

Definition at line 413 of file parallel_priority_queue.h.

template<class ValueType >
size_t stxxl::ppq_local::internal_array< ValueType >::get_max_index ( ) const
inline

The index of the largest element in the array.

Definition at line 357 of file parallel_priority_queue.h.

template<class ValueType >
const value_type& stxxl::ppq_local::internal_array< ValueType >::get_min ( ) const
inline

The currently smallest element in the array.

Definition at line 345 of file parallel_priority_queue.h.

template<class ValueType >
size_t stxxl::ppq_local::internal_array< ValueType >::get_min_index ( ) const
inline

The index of the currently smallest element in the array.

Definition at line 351 of file parallel_priority_queue.h.

template<class ValueType >
void stxxl::ppq_local::internal_array< ValueType >::inc_min ( size_t  diff = 1)
inline

Use inc_min(diff) if multiple values have been extracted.

Definition at line 339 of file parallel_priority_queue.h.

template<class ValueType >
static size_t stxxl::ppq_local::internal_array< ValueType >::int_memory ( size_t  capacity)
inlinestatic

Return the amount of internal memory used by an array with the capacity in number of items.

Definition at line 394 of file parallel_priority_queue.h.

Referenced by stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::add_as_internal_array().

template<class ValueType >
size_t stxxl::ppq_local::internal_array< ValueType >::int_memory ( ) const
inline

Return the amount of internal memory used by the array.

Definition at line 400 of file parallel_priority_queue.h.

template<class ValueType >
unsigned_type stxxl::ppq_local::internal_array< ValueType >::level ( ) const
inline

Returns the level (group number) of the array.

Definition at line 387 of file parallel_priority_queue.h.

template<class ValueType >
void stxxl::ppq_local::internal_array< ValueType >::make_empty ( )
inline

Make this array empty.

Definition at line 369 of file parallel_priority_queue.h.

template<class ValueType >
value_type& stxxl::ppq_local::internal_array< ValueType >::operator[] ( size_t  i)
inline

Random access operator.

Definition at line 333 of file parallel_priority_queue.h.

template<class ValueType >
size_t stxxl::ppq_local::internal_array< ValueType >::size ( ) const
inline

Returns the current size of the array.

Definition at line 375 of file parallel_priority_queue.h.

Friends And Related Function Documentation

template<class ValueType >
void swap ( internal_array< ValueType > &  a,
internal_array< ValueType > &  b 
)
friend

Swap internal_array with another one.

Definition at line 327 of file parallel_priority_queue.h.

Member Data Documentation

template<class ValueType >
block_pointers_type stxxl::ppq_local::internal_array< ValueType >::m_block_pointers
protected

Begin and end pointers of the array This is used by the iterator.

Definition at line 295 of file parallel_priority_queue.h.

Referenced by stxxl::ppq_local::internal_array< ValueType >::swap().

template<class ValueType >
unsigned_type stxxl::ppq_local::internal_array< ValueType >::m_level
protected

Level of internal array (Sander's PQ: group number)

Definition at line 291 of file parallel_priority_queue.h.

Referenced by stxxl::ppq_local::internal_array< ValueType >::swap().

template<class ValueType >
unsigned_type stxxl::ppq_local::internal_array< ValueType >::m_min_index
protected

Index of the current head.

Definition at line 288 of file parallel_priority_queue.h.

Referenced by stxxl::ppq_local::internal_array< ValueType >::swap().

template<class ValueType >
std::vector<value_type> stxxl::ppq_local::internal_array< ValueType >::m_values
protected

Contains the items of the sorted sequence.

Definition at line 285 of file parallel_priority_queue.h.

Referenced by stxxl::ppq_local::internal_array< ValueType >::swap().


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