sort.h File Reference

#include <tpie/portability.h>
#include <tpie/sort_manager.h>
#include <tpie/mergeheap.h>
#include <tpie/internal_sort.h>
#include <tpie/progress_indicator_base.h>
#include <tpie/progress_indicator_null.h>
#include <tpie/fractional_progress.h>
#include <tpie/pipelining/merge_sorter.h>
#include <tpie/file_stream.h>
#include <tpie/uncompressed_stream.h>
#include <tpie/sort_deprecated.h>

Go to the source code of this file.

Namespaces
	tpie

Functions
template<typename Stream , typename T , typename Compare >
void	tpie::bits::generic_sort (Stream &instream, Compare comp, progress_indicator_base *indicator)
	Sort elements of a stream in-place using the given STL-style comparator object. More...
template<typename Stream , typename T , typename Compare >
void	tpie::bits::generic_sort (Stream &instream, Stream &outstream, Compare comp, progress_indicator_base *indicator)
template<typename T , typename Compare >
void	tpie::sort (uncompressed_stream< T > &instream, uncompressed_stream< T > &outstream, Compare comp, progress_indicator_base &indicator)
	Sort elements of a stream using the given STL-style comparator object. More...
template<typename T >
void	tpie::sort (uncompressed_stream< T > &instream, uncompressed_stream< T > &outstream, tpie::progress_indicator_base *indicator=NULL)
	Sort elements of a stream using the less-than operator. More...
template<typename T >
void	tpie::sort (file_stream< T > &instream, file_stream< T > &outstream, tpie::progress_indicator_base *indicator=NULL)
	Sort elements of a stream using the less-than operator. More...
template<typename T , typename Compare >
void	tpie::sort (uncompressed_stream< T > &instream, Compare comp, progress_indicator_base &indicator)
	Sort elements of a stream in-place using the given STL-style comparator object. More...
template<typename T , typename Compare >
void	tpie::sort (file_stream< T > &instream, Compare comp, progress_indicator_base &indicator)
	Sort elements of a stream in-place using the given STL-style comparator object. More...
template<typename T >
void	tpie::sort (uncompressed_stream< T > &instream, progress_indicator_base &indicator)
	Sort elements of a stream in-place using the less-than operator. More...
template<typename T >
void	tpie::sort (file_stream< T > &instream, progress_indicator_base &indicator)
template<typename T >
void	tpie::sort (uncompressed_stream< T > &instream)
	Sort elements of a stream in-place using the less-than operator and no progress indicator. More...

Detailed Description

Sorting algorithms.

In-place Variants for Sorting in TPIE:

TPIE can sort given an input stream and output stream, or just an input stream. When just an input stream is specified, the original input elements are deleted the input stream is rewritten with the sorted output elements. If both the input stream and output stream are specified, the original input elements are saved. During sorting, a temporary copy of each element is stored on disk as part of intermediate sorting results. If N is the size on disk of the original input stream, the polymorphs of sorting with both input and output streams use 3N space, whereas if just an input stream is specified, 2N space is used. If the original unsorted input stream is not needed after sorting, it is recommended that users use the sort() polymorph with with just an input stream, to save space and avoid having to maintain both an input and output stream.

Definition in file sort.h.

Function Documentation

generic_sort()

template<typename Stream , typename T , typename Compare >

void tpie::bits::generic_sort	(	Stream &	instream,
		Compare	comp,
		progress_indicator_base *	indicator
	)

Sort elements of a stream in-place using the given STL-style comparator object.

Definition at line 66 of file sort.h.

                                                       {
 
    stream_size_type sz = instream.size();
 
    fractional_progress fp(indicator);
    fractional_subindicator push(fp, "sort", TPIE_FSI, sz, "Write sorted runs");
    fractional_subindicator merge(fp, "sort", TPIE_FSI, sz, "Perform merge heap");
    fractional_subindicator output(fp, "sort", TPIE_FSI, sz, "Write sorted output");
    fp.init(sz);
 
    instream.seek(0);
 
    merge_sorter<T, true, Compare> s(comp);
    s.set_available_memory(get_memory_manager().available());
    s.begin();
    push.init(sz);
    while (instream.can_read()) s.push(instream.read()), push.step();
    push.done();
    s.end();
 
    instream.truncate(0);
    s.calc(merge);
 
    output.init(sz);
    while (s.can_pull()) instream.write(s.pull()), output.step();
    output.done();
    fp.done();
    instream.seek(0);
}