/****************************************************************************
* NAME: Clark Sullivan Erfurt
* COURSE: 2437.002
* LAB: 10
* LAB  OUT:   November 25, 2003
* DATE DUE:   December  5, 2003
*
* Purpose: 
*          
* Input:   
*
* Output:  
**************************************************************************/

/****************
*  Header files
****************/
#include <iostream>  // input/output stream (cout, cin)
#include <fstream>   // file stream for input/output
#include <string>    //
using namespace std; // Location of classes & function 
                     // defined in standard libraries

/**************
*  Structure
**************/
struct Records   // Structures of Records
{
   int id;
   string name;
   string city;
};


/***********************
*  Function Prototypes
***********************/
void OpenFiles(fstream &, fstream &);
void GetRecords(Records[], istream &);
void PrintRecords(Records[], ostream &); 
void HeapSort(Records[], Records[], ostream &);
void reheapUp(Records[] , int);
void reheapDown(Records[], int, int);
void QuickSort(Records[], int, int);
void medianLeft(Records[], int, int);
void QuickInsertion(Records[], int, int);
void ShellSort(Records[], int);

/******************
*  Main Function
******************/
int main()
{
   Records records[50], temp[50];
   fstream DataIn;       // Used to input information from lab10.dat
   fstream DataOut;      // Used to output information to lab10.out   

   OpenFiles(DataIn, DataOut);
   GetRecords(records, DataIn);
   
   DataOut << "\n Original list from the file:\n\n";
   PrintRecords(records, DataOut); 
   cout << "\n\n\n";
   
   HeapSort(records, temp, DataOut);
   DataOut << "\n\n\n Heap Sort from the original list:\n\n";
   PrintRecords(temp, DataOut); 

    for(int walker = 0; walker < 50; walker++)
      temp[walker] = records[walker];
   QuickSort(temp, 0, 49);
   DataOut << "\n\n\n Quick Sort from the original list:\n\n";
   PrintRecords(temp, DataOut); 

    for(int walker = 0; walker < 50; walker++)
      temp[walker] = records[walker];
   ShellSort(temp, 49);
   DataOut << "\n\n\n Shell Sort from the original list:\n\n";
   PrintRecords(temp, DataOut); 

   //system("PAUSE"); // remove later
   DataIn.close();
   DataOut.close();
} // End of Main Function

/***********************************************************
* OpenFiles()                                              *
*                                                          *
* Precondition: istream DataIn and ostream DataOut         *
*               is declared.                               *
*                                                          *
* Postcondition: Two files, lab10.out and lab10.dat is     *
*                opened.                                   *
***********************************************************/
void OpenFiles(fstream &DataIn, fstream &DataOut)
{
   DataIn.open("lab10.dat", ios::in); //Opening input file
   if (!DataIn)
   {
      cout << "\n Error opening file 'lab10.dat'\n";
      exit (100);
   }
   cout << "\n\n Opening lab10.dat successful.\n";

   DataOut.open("lab10.out", ios::out); //Opening output file
   if (!DataOut)
   {
      cout << "\n Error opening file 'lab10.out'\n";
      exit (100);
   }
   cout << " Opening lab10.out successful.\n\n";
}

void GetRecords(Records records[], istream &DataIn)
{
   int x = 0;
   string aline;
   
   DataIn >> records[x].id;
   while (!DataIn.eof())
   {
      getline(DataIn, aline);
      records[x].name.assign(aline, 1, 13);
      records[x].city.assign(aline, 14, 14);
      x++;
      DataIn >> records[x].id;
   }
}

void PrintRecords(Records temp[], ostream &DataOut) // TESTING 
{
   int x = 0;

   do
   {
      cout << " ";
      cout << temp[x].id << " ";
      cout << temp[x].name << " ";
      cout << temp[x].city << " ";
      cout << endl;
      x++;
   }while(x != 50);

   x = 0;
   DataOut << " ID      Name          City\n"
           << " === ============ ==============\n";
   do
   {
      DataOut << " ";
      DataOut << temp[x].id << " ";
      DataOut << temp[x].name << " ";
      DataOut << temp[x].city << " ";
      DataOut << endl;
      x++;
   }while(x != 50);
}

//
void HeapSort(Records records[], Records heap[], ostream &DataOut) 
{                 
   Records holdData;                               
   int walker = 0;
   int sorted;
   

   for(walker = 0; walker < 50; walker++) 
      heap[walker] = records[walker];

   walker = 0;
   while (walker < 50)
   {
      reheapUp(heap, walker);
      walker++;
   }

   sorted = walker - 1;
   while (sorted >= 0)
   {
      holdData     = heap[0];
      heap[0]      = heap[sorted];
      heap[sorted] = holdData;
      sorted--;
      reheapDown(heap, 0, sorted);
   }
}

// function call from HeapSort --
void reheapUp(Records heap[], int walker)
{
   int parent;
   Records hold;  // used to swap the structure contents

   if(walker)
   {
      parent = (walker - 1) / 2;
      if (heap[walker].id > heap[parent].id)
      {
         hold         = heap[parent];  // 
         heap[parent] = heap[walker];  // swap
         heap[walker] = hold;          //
         reheapUp(heap, parent);
      }
   }
}

// function call from HeapSort --
void reheapDown(Records heap[], int root, int last)
{
   Records hold;
   Records leftKey;
   Records rightKey;
   Records largeChildKey;
   int largeChildIndex;
   
   if (root * 2 + 1 <= last)
   {
      leftKey   = heap[root * 2 + 1];
      if ((root * 2 + 2) <= last)
           rightKey = heap[root * 2 + 2];
      else
           rightKey.id = -1;

      // Determine which child is larger
      if (leftKey.id > rightKey.id)
      {
         largeChildKey   = leftKey;
         largeChildIndex = root * 2 + 1;
      }
      else
      {
         largeChildKey   = rightKey;
         largeChildIndex = root * 2 + 2;
      }

      // Test if root > larger subtree
      if (heap[root].id < largeChildKey.id)
      {
         hold                  = heap[root];
         heap[root]            = heap[largeChildIndex];
         heap[largeChildIndex] = hold;
         reheapDown(heap, largeChildIndex, last);
      }
   }
}

// here we go...
void QuickSort(Records quick[], int left, int right)
{
   Records hold;
   Records pivot;
   int sortLeft;
   int sortRight;

   if((right - left) > 4)
   {
      medianLeft(quick, left, right);
      pivot     = quick[left];
      sortLeft  = left + 1;
      sortRight = right;

      while (sortLeft <= sortRight)
      {
         while (quick[sortLeft].id < pivot.id)
            sortLeft++;

         while (quick[sortRight].id >= pivot.id)
            sortRight--;

         if (sortLeft <= sortRight)
         {
            hold             = quick[sortLeft];
            quick[sortLeft]  = quick[sortRight];
            quick[sortRight] = hold;
            sortLeft++;
            sortRight--;
         }
      }

      // Prepare for next phase
      quick[left] = quick[sortLeft - 1];
      quick[sortLeft - 1] = pivot;

      if (left < sortRight)
          QuickSort(quick, left, sortRight -1);
      if (sortLeft < right)
          QuickSort(quick, sortLeft, right);
   }
   else
      QuickInsertion(quick, left, right);
   return;
}

// function call from QuickSort...
void medianLeft(Records quick[], int left, int right)
{
   int mid;
   Records hold;

   // Rearrange quick[] so median is in the middle location
   mid = (left + right) / 2;
   if (quick[left].id > quick[mid].id)
   {
      hold        = quick[left];
      quick[left] = quick[mid];
      quick[mid]  = hold;
   }
   if (quick[left].id > quick[right].id)
   {
      hold        = quick[left];
      quick[left] = quick[right];
      quick[right]  = hold;
   }
   if (quick[mid].id > quick[right].id)
   {
      hold        = quick[mid];
      quick[mid] = quick[right];
      quick[right]  = hold;
   }
   // Median is in middle. Exchange with left.
   hold        = quick[left];
   quick[left] = quick[mid];
   quick[mid]  = hold;

   return;
}

void QuickInsertion(Records quick[], int first, int last)
{
   Records hold;
   int     current;
   int     walker;

   for (current = first + 1; current <= last; current++)
   {
      hold   = quick[current];
      walker = current - 1;
      while(walker >= first && hold.id < quick[walker].id)
      {
         quick[walker + 1] = quick[walker];
         walker--;
      }
      quick[walker + 1] = hold;
   }
   return;
}

// Finally... here we go... again.
void ShellSort(Records shell[], int last)
{
   Records hold;
   int incre;
   int curr;
   int walker;

   incre = last / 2;
   while(incre != 0)
   {
      for (curr = incre; curr <= last; curr++)
      {
         hold = shell[curr];
         walker = curr - incre;
         while (walker >= 0 && hold.id < shell[walker].id)
         {
            shell[walker + incre] = shell[walker];
            walker = (walker - incre);
         }
         shell[walker + incre] = hold;
      }
      incre = incre / 2;
   }
}