Stxxl  1.3.2
Classes | Functions
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
srunssorted runs object
cmpcomparison 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
ininput stream
template<class OutputIterator_ , class StreamAlgorithm_ >
OutputIterator_ stream::materialize ( StreamAlgorithm_ &  in,
OutputIterator_  out 
)

Stores consecutively stream content to an output iterator.

Parameters
instream to be stored used as source
outoutput 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
instream to be stored used as source
outbeginoutput iterator used as destination
outendoutput 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
instream to be stored used as source
outbeginoutput stxxl::vector iterator used as destination
outendoutput end iterator, pointing beyond the output range
nbuffersnumber 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
instream to be stored used as source
outoutput stxxl::vector iterator used as destination
nbuffersnumber 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
beginiterator, pointing to the first value
enditerator, 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
beginiterator, pointing to the first value
enditerator, pointing to the last + 1 position, i.e. beyond the range
nbuffersnumber 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
beginconst iterator, pointing to the first value
endconst iterator, pointing to the last + 1 position, i.e. beyond the range
nbuffersnumber 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.