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 51 of file 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 >:

Public Types
typedef AllocStr	allocation_strategy_type

typedef typed_block< BlockSize, value_type >	block_type

typedef CompareType	cmp_type

typedef element_iterator_traits < block_type, external_size_type > ::element_iterator	element_iterator

typedef Input	input_type

typedef sorted_runs_data_type::run_type	run_type

typedef sorted_runs < trigger_entry_type, cmp_type >	sorted_runs_data_type

typedef counting_ptr < sorted_runs_data_type >	sorted_runs_type

typedef sort_helper::trigger_entry < block_type >	trigger_entry_type

typedef Input::value_type	value_type

Public Member Functions
	basic_runs_creator (Input &input, CompareType cmp, unsigned_type memory_to_use)
	Create the object. More...

sorted_runs_type &	result ()
	Returns the sorted runs object. More...

Static Public Attributes
static const unsigned	block_size = BlockSize

Protected Attributes
CompareType	m_cmp
	comparator used to sort block groups More...

Input &	m_input
	reference to the input stream More...

Private Member Functions
void	compute_result ()
	Finish the results, i. e. create all runs. More...

unsigned_type	fetch (block_type *blocks, unsigned_type first_idx, unsigned_type last_idx)
	Fetch data from input into blocks[first_idx,last_idx). More...

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 More...

void	sort_run (block_type *run, unsigned_type elements)
	Sort a specific run, contained in a sequences of blocks. More...

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

Private Attributes
unsigned_type	m_memsize
	memory for internal use in blocks More...

sorted_runs_type	m_result
	stores the result (sorted runs) as smart pointer More...

bool	m_result_computed
	true iff result is already computed (used in 'result()' method) More...

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 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 typed_block<BlockSize, value_type> stxxl::stream::basic_runs_creator< Input, CompareType, BlockSize, AllocStr >::block_type

Definition at line 61 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

Definition at line 55 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 element_iterator_traits<block_type, external_size_type>::element_iterator stxxl::stream::basic_runs_creator< Input, CompareType, BlockSize, AllocStr >::element_iterator

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 Input stxxl::stream::basic_runs_creator< Input, CompareType, BlockSize, AllocStr >::input_type

Definition at line 54 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 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 sorted_runs<trigger_entry_type, cmp_type> stxxl::stream::basic_runs_creator< Input, CompareType, BlockSize, AllocStr >::sorted_runs_data_type

Definition at line 63 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

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 sort_helper::trigger_entry<block_type> stxxl::stream::basic_runs_creator< Input, CompareType, BlockSize, AllocStr >::trigger_entry_type

Definition at line 62 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

Definition at line 60 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

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

Definition at line 130 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
	)

inlineprivate

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

Definition at line 84 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
	)

inlineprivate

fill the rest of the block with max values

Definition at line 99 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 150 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 >::sort_run	(	block_type *	run,
		unsigned_type	elements
	)

inlineprivate

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

Definition at line 114 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 56 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

comparator used to sort block groups

Definition at line 73 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

reference to the input stream

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

memory for internal use in blocks

Definition at line 79 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

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>

bool stxxl::stream::basic_runs_creator< Input, CompareType, BlockSize, AllocStr >::m_result_computed

private

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

Definition at line 81 of file sort_stream.h.

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

include/stxxl/bits/stream/sort_stream.h

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 >

Public Types

Public Member Functions

Static Public Attributes

Protected Attributes

Private Member Functions

Private Attributes

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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 >