#include <iostream>
#include <iomanip>
#include <math.h>
#include <time.h>
#include <fstream>
#include <cstdlib>

template <typename MyType>
void Sort(MyType &a, MyType &b);
template <typename MyType>
void BubbleSort(MyType *list, int length);

template <typename MyType>
void Merge(MyType *list1, int length1, MyType *list2, int length2);
template <typename MyType>
void MergeSort(MyType *list, int length);

void ReadPasswords(std::ifstream &InFile, std::string *Passwords,
		   int &LineCount, int LongestLine);

int FileLength(std::ifstream &InFile, int &LongestWord);

template <typename MyType>
void PrintList(MyType *list, int n);

int main(void )
{
  std::ifstream InFile;
  std::string InFileName="UserAccount-passwords.txt";

  InFile.open(InFileName.c_str());
  if (InFile.fail() )
  {
    std::cerr << "Error: Cannot open " << InFileName <<
      " for reading." << std::endl;
    exit(1);
  }

  // Need to know the number of lines, and the length of the longest one
  int LineCount, LongestLine;
  LineCount =  FileLength(InFile, LongestLine);
  std::cout  << InFileName << " has " << LineCount << " lines.\n";
  std::cout  << "\tThe longest has " << LongestLine << " characters.\n";
  std::string *Passwords = new std::string [LineCount+1];
  std::string *Copy = new std::string [LineCount+1];
  ReadPasswords(InFile, Passwords, LineCount, LongestLine);

  // We'll check that we can sort this correctly
  for (int i=0; i<5; i++)      Copy[i] = Passwords[i*111];
  std::cout << "     Unsorted: ";   PrintList(Copy, 5);
  BubbleSort(Copy,5);
  std::cout << "Bubble Sorted: ";   PrintList(Copy, 5);
  for (int i=0; i<5; i++)      Copy[i] = Passwords[i*111];
  MergeSort(Copy,5);
  std::cout << " Merge Sorted: ";   PrintList(Copy, 5);

  clock_t start;
  double diff, diff_seconds, C_bubble, C_merge;

//  TEST BUBBLE SORT
  std::cout << std::setw(50) << std::setfill('|') << '|' << std::endl;
  std::cout << std::setw(20) << std::setfill(' ') << ' ' << "Bubble Sort" <<std::endl;
  std::cout.precision(4); // Want numbers to 4 digits
  for (int n=1000; n<=32000; n*=2) {
    for (int i=0; i<n; i++)
      Copy[i] = Passwords[i];

    start=clock();
    BubbleSort(Copy,n);
    diff = (double)(clock()-start);
    diff_seconds = diff/CLOCKS_PER_SEC;
    C_bubble = diff_seconds/( (double)(n*n));
    std::cout << "Bubble: n =  " << std::setw(7) << n << " took "
	      << diff_seconds << std::setw(10) << " seconds. C="
	      << C_bubble << std::endl;
  }
  int BigN = 32e6;
  std::cout << "Taking C = " << C_bubble << ", sorting list of length " << BigN <<
    " would take " << std::endl;
  std::cout << "\t   " << C_bubble*BigN*BigN << " seconds," << std::endl;
  std::cout << "\t = " << C_bubble*BigN*BigN/60       << " minutes" << std::endl;
  std::cout << "\t = " << C_bubble*BigN*BigN/60/60    << " hours" << std::endl;
  std::cout << "\t = " << C_bubble*BigN*BigN/60/60/24 << " days." << std::endl;
  std::cout << std::endl;

  // ------------------------------------------------
  // MERGE SORT
  std::cout << std::setw(50) << std::setfill('|') << '|' << std::endl;
  std::cout << std::setw(20) << std::setfill(' ') << ' ' << "Merge Sort"
	    <<std::endl;

  for (int n=50000; n<=32*50000; n*=2) {
    for (int i=0; i<n; i++)
      Copy[i] = Passwords[i];
    start=clock();
    MergeSort(Copy,n);
    diff = (double)(clock()-start);
    diff_seconds = diff/CLOCKS_PER_SEC;
    C_merge= diff_seconds/( (double)(n*log2(n)));
    std::cout << "Merge: n =  " << std::setw(7) << n << " took "
	      << diff_seconds << std::setw(10) << " seconds. C="
	      << C_merge << std::endl;
  }
  std::cout << "Taking C = " << C_merge << ", sorting list of length " << BigN <<
    " would take " << std::endl;
  std::cout << "\t   " << C_merge*BigN*log2(BigN)    << " seconds" << std::endl;
  std::cout << "\t = " << C_merge*BigN*log2(BigN)/60 << " minutes" << std::endl;
  std::cout << "\t = " << C_merge*BigN*log2(BigN)/60/60    << " hours" << std::endl;
  std::cout << "\t = " << C_merge*BigN*log2(BigN)/60/60/24 << " days." << std::endl;

  delete [] Passwords;
  delete [] Copy;

  return(0);
}

// Merge two lists:  list1 and list2, of length length1 and length2,
//   respectively
// Assume that the two lists are already sorted.
// Store result in the pre-allocated Merged
template <typename MyType>
void Merge(MyType *list1, int length1,
	   MyType *list2, int length2,  MyType *Merged)
{
  int i=0, j=0;
  for (int k=0; k<length1+length2; k++)
    if ( (i != length1) && ((j==length2)
			    || (list1[i] <= list2[j])) )
    {
      Merged[k] = list1[i];
      i++;
    }
    else
    {
      Merged[k] = list2[j];
      j++;
    }
}

// MergeSort list:
//   - if list is of length 1, return
//   - otherwise: split, sort, merge, return
template <typename MyType>
void MergeSort(MyType *list, int length)
{
  if (length <=1)
    return;
  else
  {
    int m;
    m = (int)floor((double)length/2.0);
    MyType *list1 = new MyType [m];
    MyType *list2 = new MyType [length-m];
    for (int i=0; i<m; i++)
      list1[i]=list[i];
    for (int i=0; i<length-m; i++)
      list2[i]=list[m+i];
    MergeSort(list1, m);
    MergeSort(list2, length-m);
    Merge(list1, m, list2, length-m, list);
    delete [] list1;
    delete [] list2;
  }
}


template <typename MyType>
void PrintList(MyType *x, int n)
{
  for (int i=0; i<n; i++)
    std::cout << std::setw(4) << x[i] << "  ";
  std::cout << std::endl;
}

int FileLength(std::ifstream &InFile, int &LongestLine)
{
  // Rewind to the start of the file
  InFile.clear();
  InFile.seekg(std::ios::beg);

  char c;
  InFile.get( c );
  int LineCount=0, ThisLineLength=0;
  while( ! InFile.eof() )
  {
    if (c != '\n')
      ThisLineLength++;
    else
    {
      LineCount++;
      if (LongestLine<ThisLineLength)
	LongestLine = ThisLineLength;
      ThisLineLength=0;
    }
    InFile.get( c );
  }

  // Rewind
  InFile.clear();
  InFile.seekg(std::ios::beg);

  return(LineCount);
}



// Read each line from the file. Store in Passwords.
// Updated LineCount (ignore blank lines)
void ReadPasswords(std::ifstream &InFile, std::string *Passwords,
		   int &LineCount, int LongestLine)
{
  int WordsRead=0;
  char *c_string_word = new char [LongestLine+1];
  for (int Line=0; Line < LineCount; Line++)
  {
    InFile.getline(c_string_word, LongestLine+1);
    Passwords[Line] = c_string_word;
    if (Passwords[Line].length() == 0) // that was a blank line
    {
      Line--;
      LineCount--;
    }
    else
      WordsRead++;
  }
  LineCount = WordsRead;
  delete [] c_string_word;
}


// Arguments: two variables of type MyType
// return value: void
// Does: Sorts a and b so that a<=b.
template <typename MyType>
void Sort(MyType &a, MyType &b) {
  MyType tmp=a;
  if (a>b)
  {
    a=b;
    b=tmp;
  }
}

// Arguments: an array of generic type and its length
// return value: void
// Does: Sorts the 1st n elements of x
template <typename MyType>
void BubbleSort(MyType *x, int n) {
  int i, k;
  for (i=n-1; i>1; i--)
    for (k=0; k<i; k++)
      Sort(x[k], x[k+1]);
}