Stream package

Classes
class	stream::basic_runs_creator< Input_, Cmp_, BlockSize_, AllocStr_ >
	Forms sorted runs of data from a stream. More...
class	stream::runs_creator< Input_, Cmp_, BlockSize_, AllocStr_ >
	Forms sorted runs of data from a stream. More...
struct	stream::use_push< ValueType_ >
	Input strategy for runs_creator class. More...
class	stream::runs_creator< use_push< ValueType_ >, Cmp_, BlockSize_, AllocStr_ >
	Forms sorted runs of elements passed in push() method. More...
struct	stream::from_sorted_sequences< ValueType_ >
	Input strategy for runs_creator class. More...
class	stream::runs_creator< from_sorted_sequences< ValueType_ >, Cmp_, BlockSize_, AllocStr_ >
	Forms sorted runs of data taking elements in sorted order (element by element) More...
class	stream::basic_runs_merger< RunsType_, Cmp_, AllocStr_ >
	Merges sorted runs. More...
class	stream::runs_merger< RunsType_, Cmp_, AllocStr_ >
	Merges sorted runs. More...
class	stream::sort< Input_, Cmp_, BlockSize_, AllocStr_, runs_creator_type >
	Produces sorted stream from input stream. More...
class	stream::compute_sorted_runs_type< ValueType_, BlockSize_ >
	Computes sorted runs type from value type and block size. More...
struct	stream::sorted_runs< TriggerEntryType >
	All sorted runs of a sort operation. More...
class	stream::iterator2stream< InputIterator_ >
	A model of stream that retrieves the data from an input iterator For convenience use streamify function instead of direct instantiation of iterator2stream . More...
struct	stream::streamify_traits< InputIterator_ >
	Traits class of streamify function. More...
class	stream::vector_iterator2stream< InputIterator_ >
	A model of stream that retrieves data from an external stxxl::vector iterator. It is more efficient than generic iterator2stream thanks to use of overlapping For convenience use streamify function instead of direct instantiation of vector_iterator2stream . More...
class	stream::vector_iterator2stream_sr< InputIterator_ >
	Version of iterator2stream. Switches between vector_iterator2stream and iterator2stream . More...
class	stream::generator2stream< Generator_, T >
	A model of stream that outputs data from an adaptable generator functor For convenience use streamify function instead of direct instantiation of generator2stream . More...
class	stream::transform< Operation_, Input1_, Input2_, Input3_, Input4_, Input5_, Input6_ >
	Processes (up to) 6 input streams using given operation functor. More...
class	stream::transform< Operation_, Input1_, Stopper, Stopper, Stopper, Stopper, Stopper >
	Processes an input stream using given operation functor. More...
class	stream::transform< Operation_, Input1_, Input2_, Stopper, Stopper, Stopper, Stopper >
	Processes 2 input streams using given operation functor. More...
class	stream::transform< Operation_, Input1_, Input2_, Input3_, Stopper, Stopper, Stopper >
	Processes 3 input streams using given operation functor. More...
class	stream::transform< Operation_, Input1_, Input2_, Input3_, Input4_, Stopper, Stopper >
	Processes 4 input streams using given operation functor. More...
class	stream::transform< Operation_, Input1_, Input2_, Input3_, Input4_, Input5_, Stopper >
	Processes 5 input streams using given operation functor. More...
class	stream::make_tuple< Input1_, Input2_, Input3_, Input4_, Input5_, Input6_ >
	Creates stream of 6-tuples from 6 input streams. More...
class	stream::make_tuple< Input1_, Input2_, Stopper, Stopper, Stopper, Stopper >
	Creates stream of 2-tuples (pairs) from 2 input streams. More...
class	stream::make_tuple< Input1_, Input2_, Input3_, Stopper, Stopper, Stopper >
	Creates stream of 3-tuples from 3 input streams. More...
class	stream::make_tuple< Input1_, Input2_, Input3_, Input4_, Stopper, Stopper >
	Creates stream of 4-tuples from 4 input streams. More...
class	stream::make_tuple< Input1_, Input2_, Input3_, Input4_, Input5_, Stopper >
	Creates stream of 5-tuples from 5 input streams. More...

Functions
template<class RunsType_ , class Cmp_ >
bool	stream::check_sorted_runs (const RunsType_ &sruns, Cmp_ cmp)
	Checker for the sorted runs object created by the runs_creator . More...
template<class InputIterator_ >
iterator2stream< InputIterator_ >	stream::streamify (InputIterator_ begin, InputIterator_ end)
	Input iterator range to stream converter. More...
template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_>
vector_iterator2stream < stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > >	stream::streamify (stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > begin, stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > end, unsigned_type nbuffers=0)
	Input external stxxl::vector iterator range to stream converter It is more efficient than generic input iterator streamify thanks to use of overlapping. More...
template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_>
vector_iterator2stream < stxxl::const_vector_iterator < Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > >	stream::streamify (stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > begin, stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > end, unsigned_type nbuffers=0)
	Input external stxxl::vector const iterator range to stream converter It is more efficient than generic input iterator streamify thanks to use of overlapping. More...
template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_>
vector_iterator2stream_sr < stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > >	stream::streamify_sr (stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > begin, stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > end, unsigned_type nbuffers=0)
	Version of streamify. Switches from vector_iterator2stream to iterator2stream for small ranges. More...
template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_>
vector_iterator2stream_sr < stxxl::const_vector_iterator < Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > >	stream::streamify_sr (stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > begin, stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > end, unsigned_type nbuffers=0)
	Version of streamify. Switches from vector_iterator2stream to iterator2stream for small ranges. More...
template<class OutputIterator_ , class StreamAlgorithm_ >
OutputIterator_	stream::materialize (StreamAlgorithm_ &in, OutputIterator_ out)
	Stores consecutively stream content to an output iterator. More...
template<class OutputIterator_ , class StreamAlgorithm_ >
OutputIterator_	stream::materialize (StreamAlgorithm_ &in, OutputIterator_ outbegin, OutputIterator_ outend)
	Stores consecutively stream content to an output iterator range until end of the stream or end of the iterator range is reached. More...
template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_, class StreamAlgorithm_ >
stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	stream::materialize (StreamAlgorithm_ &in, stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > outbegin, stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > outend, unsigned_type nbuffers=0)
	Stores consecutively stream content to an output stxxl::vector iterator until end of the stream or end of the iterator range is reached. More...
template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_, class StreamAlgorithm_ >
stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	stream::materialize (StreamAlgorithm_ &in, stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ > out, unsigned_type nbuffers=0)
	Stores consecutively stream content to an output stxxl::vector iterator. More...
template<class StreamAlgorithm_ >
void	stream::discard (StreamAlgorithm_ &in)
	Reads stream content and discards it. Useful where you do not need the processed stream anymore, but are just interested in side effects, or just for debugging. More...
template<class Generator_ >
generator2stream< Generator_ >	stream::streamify (Generator_ gen_)
	Adaptable generator to stream converter. More...

Detailed Description

Package that enables pipelining of consequent sorts
and scans of the external data avoiding the saving the intermediate
results on the disk, e.g. the output of a sort can be directly
fed into a scan procedure without the need to save it on a disk.
All components of the package are contained in the \c stxxl::stream
namespace.

   STREAM ALGORITHM CONCEPT (Do not confuse with C++ input/output streams)

//!
//!    struct stream_algorithm // stream, pipe, whatever
//!    {
//!      typedef some_type value_type;
//!
//!      const value_type & operator * () const; // return current element of the stream
//!      stream_algorithm & operator ++ ();      // go to next element. precondition: empty() == false
//!      bool empty() const;                     // return true if end of stream is reached
//!
//!    };
//! 

Function Documentation

template<class RunsType_ , class Cmp_ >

bool stream::check_sorted_runs	(	const RunsType_ &	sruns,
		Cmp_	cmp
	)

Checker for the sorted runs object created by the runs_creator .

Parameters

sruns	sorted runs object
cmp	comparison object used for checking the order of elements in runs

Returns

true if runs are sorted, false otherwise

=

Examples:

stream/test_push_sort.cpp, and stream/test_sorted_runs.cpp.

References wait_all().

template<class StreamAlgorithm_ >

void stream::discard

(

StreamAlgorithm_ &

in

)

Reads stream content and discards it. Useful where you do not need the processed stream anymore, but are just interested in side effects, or just for debugging.

Parameters

in	input stream

template<class OutputIterator_ , class StreamAlgorithm_ >

OutputIterator_ stream::materialize	(	StreamAlgorithm_ &	in,
		OutputIterator_	out
	)

Stores consecutively stream content to an output iterator.

Parameters

in	stream to be stored used as source
out	output iterator used as destination

Returns

value of the output iterator after all increments, i.e. points to the first unwritten value

Precondition

Output (range) is large enough to hold the all elements in the input stream

Examples:

algo/copy_and_sort_file.cpp, algo/test_parallel_sort.cpp, containers/berkeley_db_benchmark.cpp, stream/test_naive_transpose.cpp, and stream/test_stream.cpp.

Referenced by sort().

template<class OutputIterator_ , class StreamAlgorithm_ >

OutputIterator_ stream::materialize	(	StreamAlgorithm_ &	in,
		OutputIterator_	outbegin,
		OutputIterator_	outend
	)

Stores consecutively stream content to an output iterator range until end of the stream or end of the iterator range is reached.

Parameters

in	stream to be stored used as source
outbegin	output iterator used as destination
outend	output end iterator, pointing beyond the output range

Returns

value of the output iterator after all increments, i.e. points to the first unwritten value

Precondition

Output range is large enough to hold the all elements in the input stream

This function is useful when you do not know the length of the stream beforehand.

template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_, class StreamAlgorithm_ >

stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> stream::materialize	(	StreamAlgorithm_ &	in,
		stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	outbegin,
		stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	outend,
		unsigned_type	nbuffers = 0
	)

Stores consecutively stream content to an output stxxl::vector iterator until end of the stream or end of the iterator range is reached.

Parameters

in	stream to be stored used as source
outbegin	output stxxl::vector iterator used as destination
outend	output end iterator, pointing beyond the output range
nbuffers	number of blocks used for overlapped writing (0 is default, which equals to (2 * number_of_disks)

Returns

value of the output iterator after all increments, i.e. points to the first unwritten value

Precondition

Output range is large enough to hold the all elements in the input stream

This function is useful when you do not know the length of the stream beforehand.

template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_, class StreamAlgorithm_ >

stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> stream::materialize	(	StreamAlgorithm_ &	in,
		stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	out,
		unsigned_type	nbuffers = 0
	)

Stores consecutively stream content to an output stxxl::vector iterator.

Parameters

in	stream to be stored used as source
out	output stxxl::vector iterator used as destination
nbuffers	number of blocks used for overlapped writing (0 is default, which equals to (2 * number_of_disks)

Returns

value of the output iterator after all increments, i.e. points to the first unwritten value

Precondition

Output (range) is large enough to hold the all elements in the input stream

template<class InputIterator_ >

iterator2stream<InputIterator_> stream::streamify	(	InputIterator_	begin,
		InputIterator_	end
	)

Input iterator range to stream converter.

Parameters

begin	iterator, pointing to the first value
end	iterator, pointing to the last + 1 position, i.e. beyond the range

Returns

an instance of a stream object

Examples:

algo/copy_and_sort_file.cpp, algo/test_parallel_sort.cpp, stream/test_naive_transpose.cpp, and stream/test_stream.cpp.

Referenced by random_shuffle(), and sort().

template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_>

vector_iterator2stream<stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > stream::streamify	(	stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	begin,
		stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	end,
		unsigned_type	nbuffers = 0
	)

Input external stxxl::vector iterator range to stream converter It is more efficient than generic input iterator streamify thanks to use of overlapping.

Parameters

begin	iterator, pointing to the first value
end	iterator, pointing to the last + 1 position, i.e. beyond the range
nbuffers	number of blocks used for overlapped reading (0 is default, which equals to (2 * number_of_disks)

Returns

an instance of a stream object

template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_>

vector_iterator2stream<stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > stream::streamify	(	stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	begin,
		stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	end,
		unsigned_type	nbuffers = 0
	)

Input external stxxl::vector const iterator range to stream converter It is more efficient than generic input iterator streamify thanks to use of overlapping.

Parameters

begin	const iterator, pointing to the first value
end	const iterator, pointing to the last + 1 position, i.e. beyond the range
nbuffers	number of blocks used for overlapped reading (0 is default, which equals to (2 * number_of_disks)

Returns

an instance of a stream object

template<class Generator_ >

generator2stream<Generator_> stream::streamify

(

Generator_

gen_

)

Adaptable generator to stream converter.

Parameters

gen_	generator object

Returns

an instance of a stream object

template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_>

vector_iterator2stream_sr<stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > stream::streamify_sr	(	stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	begin,
		stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	end,
		unsigned_type	nbuffers = 0
	)

Version of streamify. Switches from vector_iterator2stream to iterator2stream for small ranges.

template<typename Tp_ , typename AllocStr_ , typename SzTp_ , typename DiffTp_ , unsigned BlkSize_, typename PgTp_ , unsigned PgSz_>

vector_iterator2stream_sr<stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > stream::streamify_sr	(	stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	begin,
		stxxl::const_vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >	end,
		unsigned_type	nbuffers = 0
	)

Version of streamify. Switches from vector_iterator2stream to iterator2stream for small ranges.