sort.h

Go to the documentation of this file.

// -*- mode: c++; tab-width: 4; indent-tabs-mode: t; c-file-style: "stroustrup"; -*-
// vi:set ts=4 sts=4 sw=4 noet :
// Copyright 2008-2012, The TPIE development team
// 
// This file is part of TPIE.
// 
// TPIE is free software: you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License as published by the
// Free Software Foundation, either version 3 of the License, or (at your
// option) any later version.
// 
// TPIE is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
// License for more details.
// 
// You should have received a copy of the GNU Lesser General Public License
// along with TPIE.  If not, see <http://www.gnu.org/licenses/>

#ifndef _AMI_SORT_H
#define _AMI_SORT_H


// Get definitions for working with Unix and Windows
#include <tpie/portability.h>

// The typename that actually does the sorting
#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>

namespace tpie {

namespace bits {

template<typename Stream, typename T, typename Compare>
void generic_sort(Stream & instream, Compare comp,
                  progress_indicator_base * indicator) {

    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);
}

template<typename Stream, typename T, typename Compare>
void generic_sort(Stream & instream, Stream & outstream, Compare comp,
                  progress_indicator_base *indicator) {

    if (&instream == &outstream) {
        generic_sort<Stream, T, Compare>(instream, comp, indicator);
        return;
    }

    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();

    s.calc(merge);

    outstream.truncate(0);
    output.init(sz);
    while (s.can_pull()) outstream.write(s.pull()), output.step();
    output.done();
    fp.done();
    outstream.seek(0);
}

}

template<typename T, typename Compare>
void sort(uncompressed_stream<T> &instream, uncompressed_stream<T> &outstream,
          Compare comp, progress_indicator_base & indicator) {
    bits::generic_sort<uncompressed_stream<T>, T, Compare>(instream, outstream, &comp, &indicator);
}

template<typename T>
void sort(uncompressed_stream<T> &instream, uncompressed_stream<T> &outstream,
          tpie::progress_indicator_base* indicator=NULL) {
    std::less<T> comp;
    sort(instream, outstream, comp, indicator);
}

template<typename T>
void sort(file_stream<T> &instream, file_stream<T> &outstream,
          tpie::progress_indicator_base* indicator=NULL) {
    std::less<T> comp;
    bits::generic_sort<file_stream<T>, T>(instream, outstream, comp, indicator);
}


// ********************************************************************
// *                                                                  *
// * Duplicates of the above versions that only use 2x space and      *
// * overwrite the original input stream                              *
// *                                                                  *
// ********************************************************************/

template<typename T, typename Compare>
void sort(uncompressed_stream<T> &instream, Compare comp,
          progress_indicator_base & indicator) {
    sort(instream, instream, comp, &indicator);
}

template<typename T, typename Compare>
void sort(file_stream<T> &instream, Compare comp,
          progress_indicator_base & indicator) {
    bits::generic_sort<file_stream<T>, T>(instream, comp, &indicator);
}

template<typename T>
void sort(uncompressed_stream<T> &instream, 
          progress_indicator_base &indicator) {
    sort(instream, instream, &indicator);
}

template<typename T>
void sort(file_stream<T> &instream,
          progress_indicator_base &indicator) {
    std::less<T> comp;
    sort(instream, comp, indicator);
}

template <typename T>
void sort(uncompressed_stream<T> & instream) {
    sort(instream, instream);
}

}  //  tpie namespace

#include <tpie/sort_deprecated.h>

#endif // _AMI_SORT_H