stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ > Class Template Reference

Forms sorted runs of data from a stream. More...

#include <sort_stream.h>

Inheritance diagram for stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >:

Collaboration diagram for stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >:

List of all members.

Public Types
typedef Input_	input_type
typedef CompareType_	cmp_type
typedef AllocStr_	allocation_strategy_type
typedef Input_::value_type	value_type
typedef typed_block < BlockSize_, value_type >	block_type
typedef sort_helper::trigger_entry < block_type >	trigger_entry_type
typedef sorted_runs < trigger_entry_type, cmp_type >	sorted_runs_data_type
typedef sorted_runs_data_type::run_type	run_type
typedef counting_ptr < sorted_runs_data_type >	sorted_runs_type
Public Member Functions
	basic_runs_creator (Input_ &input, CompareType_ cmp, unsigned_type memory_to_use)
	Create the object.
sorted_runs_type &	result ()
	Returns the sorted runs object.
Static Public Attributes
static const unsigned	block_size = BlockSize_
Protected Attributes
Input_ &	m_input
CompareType_	m_cmp
	reference to the input stream
Private Member Functions
unsigned_type	fetch (block_type *blocks, unsigned_type first_idx, unsigned_type last_idx)
	true iff result is already computed (used in 'result()' method)
void	fill_with_max_value (block_type *blocks, unsigned_type num_blocks, unsigned_type first_idx)
	fill the rest of the block with max values
void	sort_run (block_type *run, unsigned_type elements)
	Sort a specific run, contained in a sequences of blocks.
void	compute_result ()
	Finish the results, i. e. create all runs.
Private Attributes
sorted_runs_type	m_result
	comparator used to sort block groups
unsigned_type	m_memsize
	stores the result (sorted runs) as smart pointer
bool	m_result_computed
	memory for internal use in blocks

---

Detailed Description

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>
class stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >

Forms sorted runs of data from a stream.

Template Parameters:

Input_	type of the input stream
CompareType_	type of comparison object used for sorting the runs
BlockSize_	size of blocks used to store the runs (in bytes)
AllocStr_	functor that defines allocation strategy for the runs

Definition at line 54 of file sort_stream.h.

---

Member Typedef Documentation

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef AllocStr_ stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::allocation_strategy_type

Definition at line 60 of file sort_stream.h.

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef typed_block<BlockSize_, value_type> stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::block_type

Reimplemented in stxxl::stream::runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >, and stxxl::stream::runs_creator< stream::use_push< ValueType >, cmp_type, block_size, alloc_strategy_type >.

Definition at line 64 of file sort_stream.h.

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef CompareType_ stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::cmp_type

Reimplemented in stxxl::stream::runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >, and stxxl::stream::runs_creator< stream::use_push< ValueType >, cmp_type, block_size, alloc_strategy_type >.

Definition at line 58 of file sort_stream.h.

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef Input_ stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::input_type

Definition at line 57 of file sort_stream.h.

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef sorted_runs_data_type::run_type stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::run_type

Definition at line 67 of file sort_stream.h.

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef sorted_runs<trigger_entry_type,cmp_type> stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::sorted_runs_data_type

Reimplemented in stxxl::stream::runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >, and stxxl::stream::runs_creator< stream::use_push< ValueType >, cmp_type, block_size, alloc_strategy_type >.

Definition at line 66 of file sort_stream.h.

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef counting_ptr<sorted_runs_data_type> stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::sorted_runs_type

Reimplemented in stxxl::stream::runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >, and stxxl::stream::runs_creator< stream::use_push< ValueType >, cmp_type, block_size, alloc_strategy_type >.

Definition at line 68 of file sort_stream.h.

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef sort_helper::trigger_entry<block_type> stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::trigger_entry_type

Definition at line 65 of file sort_stream.h.

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

typedef Input_::value_type stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::value_type

Reimplemented in stxxl::stream::runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >, and stxxl::stream::runs_creator< stream::use_push< ValueType >, cmp_type, block_size, alloc_strategy_type >.

Definition at line 63 of file sort_stream.h.

---

Constructor & Destructor Documentation

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::basic_runs_creator	(	Input_ &	input,
		CompareType_	cmp,
		unsigned_type	memory_to_use
	)		[inline]

Create the object.

Parameters:

i	input stream
c	comparator object
memory_to_use	memory amount that is allowed to used by the sorter in bytes

Definition at line 126 of file sort_stream.h.

---

Member Function Documentation

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

unsigned_type stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::fetch	(	block_type *	blocks,
		unsigned_type	first_idx,
		unsigned_type	last_idx
	)		[inline, private]

true iff result is already computed (used in 'result()' method)

Fetch data from input into blocks[first_idx,last_idx).

Definition at line 81 of file sort_stream.h.

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

void stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::fill_with_max_value	(	block_type *	blocks,
		unsigned_type	num_blocks,
		unsigned_type	first_idx
	)		[inline, private]

fill the rest of the block with max values

Definition at line 96 of file sort_stream.h.

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

sorted_runs_type& stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::result

(

)

[inline]

Returns the sorted runs object.

Returns:

Sorted runs object. The result is computed lazily, i.e. on the first call

Remarks:

Returned object is intended to be used by runs_merger object as input

Definition at line 143 of file sort_stream.h.

Referenced by main().

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

void stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::sort_run	(	block_type *	run,
		unsigned_type	elements
	)		[inline, private]

Sort a specific run, contained in a sequences of blocks.

Definition at line 111 of file sort_stream.h.

---

Member Data Documentation

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

const unsigned stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::block_size = BlockSize_ [static]

Definition at line 59 of file sort_stream.h.

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

CompareType_ stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::m_cmp [protected]

reference to the input stream

Definition at line 72 of file sort_stream.h.

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

Input_& stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::m_input [protected]

Definition at line 71 of file sort_stream.h.

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

unsigned_type stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::m_memsize [private]

stores the result (sorted runs) as smart pointer

Definition at line 77 of file sort_stream.h.

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

sorted_runs_type stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::m_result [private]

comparator used to sort block groups

Definition at line 76 of file sort_stream.h.

template<class Input_, class CompareType_, unsigned BlockSize_ = STXXL_DEFAULT_BLOCK_SIZE(typename Input_::value_type), class AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY>

bool stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::m_result_computed [private]

memory for internal use in blocks

Definition at line 78 of file sort_stream.h.

---

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

• include/stxxl/bits/stream/sort_stream.h