ami_sort.h

Go to the documentation of this file.

/****************************************************************************
 * 
 *  MODULE:     iostream
 *

 *  COPYRIGHT (C) 2007 Laura Toma
 *   
 * 

 *  Iostream is a library that implements streams, external memory
 *  sorting on streams, and an external memory priority queue on
 *  streams. These are the fundamental components used in external
 *  memory algorithms.  

 * Credits: The library was developed by Laura Toma.  The kernel of
 * class STREAM is based on the similar class existent in the GPL TPIE
 * project developed at Duke University. The sorting and priority
 * queue have been developed by Laura Toma based on communications
 * with Rajiv Wickremesinghe. The library was developed as part of
 * porting Terraflow to GRASS in 2001.  PEARL upgrades in 2003 by
 * Rajiv Wickremesinghe as part of the Terracost project.

 * 
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *

 *  This program 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
 *  General Public License for more details.
 *  **************************************************************************/


#ifndef _AMI_SORT_H
#define _AMI_SORT_H

#include "ami_sort_impl.h"

#define SORT_DEBUG if(0)


/* ---------------------------------------------------------------------- */

// A version of AMI_sort that takes an input streamof elements of type
// T, creates an output stream and and uses the < operator to sort

// instream is allocated;  *outstream is created
// template<class T>
// AMI_err 
// AMI_sort(AMI_STREAM<T> *instream, AMI_STREAM<T> **outstream) {

//   cout << "Not implemented yet!\n";
//   exit(1);
//   return AMI_ERROR_NO_ERROR;
// }



/* ---------------------------------------------------------------------- */

// A version of AMI_sort that takes an input stream of elements of
// type T, creates an output stream, and a user-specified comparison
// function

// instream is allocated;  *outstream is created
// template<class T>
// AMI_err AMI_sort(AMI_STREAM<T> *instream, AMI_STREAM<T> **outstream,
//                  int (*cmp)(const T&, const  T&)) {

//   cout << "Not implemented yet!\n";
//   exit(1);
//   return AMI_ERROR_NO_ERROR;
// }



/* ---------------------------------------------------------------------- */
// A version of AMI_sort that takes an input stream of elements of
// type T, creates an output stream, and a user-specified comparison
// object. 

//The comparison object "cmp", of (user-defined) class represented by
//CMPR, must have a member function called "compare" which is used for
//sorting the input stream.




//  create  *outstream 
template<class T, class Compare>
AMI_err 
AMI_sort(AMI_STREAM<T> *instream, AMI_STREAM<T> **outstream, Compare *cmp, 
         int deleteInputStream = 0)
{
  char* name=NULL;
  queue<char*>* runList;
  off_t instreamLength;

  assert(instream && outstream && cmp); 
  instreamLength = instream->stream_len();

  if (instreamLength == 0) {
    *outstream = new AMI_STREAM<T>();
    if (deleteInputStream) {
      delete instream;
    }
    return AMI_ERROR_NO_ERROR;
  }
  
  SORT_DEBUG {
    instream->name(&name);
    cout << "AMI_sort: sorting stream" << name <<", len=" 
         << instreamLength << endl;
    delete name;
    MM_manager.print();
  }
  
  //run formation
  runList = runFormation(instream, cmp);
  assert(runList); 

  if (deleteInputStream) {
    delete instream;
  }

  if(runList->length() == 0) {
    /* self-check */
    fprintf(stderr, "ami_sort: Error - no runs created!\n");
    instream->name(&name);
    cout << "ami_sort: instream = " << name << endl;
    exit(1);
    /* no input... */
    /* *outstream = new AMI_STREAM<T>(); */

  } else if(runList->length() == 1) {    
    //if 1 run only
    runList->dequeue(&name);
    //printf("SORT: %s\n", name); fflush(stdout); 
    *outstream = new AMI_STREAM<T>(name);
    delete name; //should be safe, stream makes its own copy
    
  } else {                                              
    /* many runs */
    *outstream = multiMerge<T,Compare>(runList,  cmp);
    //i thought the templates are not needed in the call, but seems to
    //help the compiler..laura
  }

  assert(runList->length() == 0);
  delete runList;
  
  SORT_DEBUG {
    cout << "AMI_sort: done" << endl << endl;
    MM_manager.print();
  }

  assert(*outstream);  
  assert((*outstream)->stream_len() == instreamLength);
  return AMI_ERROR_NO_ERROR;
  
}



template<class  T, class Compare>
int
isSorted(AMI_STREAM<T> *str, Compare cmp) {
  T *prev, *crt;
  AMI_err ae;   

  assert(str);
  str->seek(0);
  
  if (str->stream_len() <2) return 1;
  
  ae = str->read_item(&crt);
  cout << "reading: " << *crt << endl;
  prev = new T (*crt);
  ae = str->read_item(&crt);
  while (ae == AMI_ERROR_NO_ERROR) {
    cout << "reading: " << *crt << endl;
    if (cmp.compare(*prev, *crt) != -1)
      assert(0);
      return 0;
    prev = crt;
    ae = str->read_item(&crt);
  }
  return 1;
}
             
                          
#endif // _AMI_SORT_H