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

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

template <typename MyType>
void MergeSort(MyType *list, unsigned int length);

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

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

void Insert(std::string *Top10, unsigned int *Top10Freq,
	    std::string NewString, unsigned int NewCount);

void PrintTop10(std::string *list, unsigned int *count);

int main(void )
{
  std::ifstream InFile;
  std::string InFileName="UserAccount-1e4.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
  unsigned int LineCount=0, 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];
  ReadPasswords(InFile, Passwords, LineCount, LongestLine);

//  Now sort all the words
  std::cout << "Sorting ... ";
  MergeSort(Passwords, LineCount);
  std::cout << "\n-------------\nFirst 5 words sorted are: " << std::endl;
  for (int Line=0; Line < 5; Line++)
    std::cout << Passwords[Line] << std::endl;


// Find the most frequently occuring word.
//   - create a new list of unique words
//   - a corresponding count of the number on instances.

  std::string *UniqueWords = new std::string [LineCount+1];
  unsigned int *WordFreq  = new unsigned int [LineCount+1];
  unsigned int UniqueWordsFound;

// The first one can't already be on the list
  UniqueWords[0] = Passwords[0];
  WordFreq[0] = 1;
  UniqueWordsFound=1;

  for (unsigned int i=0; i<LineCount; i++)
  {
    if (Passwords[i] !=  UniqueWords[UniqueWordsFound-1])
    { // We have found a new word
      UniqueWords[UniqueWordsFound] = Passwords[i];
      WordFreq[UniqueWordsFound] = 1;
      UniqueWordsFound++;
    }
    else
      WordFreq[UniqueWordsFound-1]++;
  }

  // Now find the top 10
  std::string Top10[10];
  unsigned int Top10Freq[10];
  // Insert the 1st into list and set rest to 0
  Top10[0]=UniqueWords[0];
  Top10Freq[0]=WordFreq[0];
  for (int i=1; i<10; i++)
  {
    Top10[i]="";
    Top10Freq[i]=0;
  }
// See if this is at least as freq as the 10th most
  for (unsigned int i=1; i<UniqueWordsFound; i++)
    if (WordFreq[i] > Top10Freq[9])
      Insert(Top10, Top10Freq, UniqueWords[i], WordFreq[i]);

  // Now, output top 10
  std::cout << "Finished. Top 10 is " << std::endl;
  PrintTop10(Top10, Top10Freq);

  delete [] Passwords;
  delete [] UniqueWords;
  delete [] WordFreq;

  InFile.close();

  return(0);
}

// Return the number of lines in the file. Also set length of longest line
int FileLength(std::ifstream &InFile, unsigned int &LongestLine)
{
  InFile.clear();
  InFile.seekg(std::ios::beg); // Rewind to the start of the file

  char c;
  InFile.get( c );
  unsigned int LineCount=0, ThisLineLength=0;
  LongestLine=0;
  while( ! InFile.eof() )
  {
    if (c != '\n')
      ThisLineLength++;
    else
    {
      LineCount++;
      if (LongestLine<ThisLineLength)
	LongestLine = ThisLineLength;
      ThisLineLength=0;
    }
    InFile.get( c );
  }
  InFile.clear();
  InFile.seekg(std::ios::beg);    // Rewind
  return(LineCount);
}

// Function ReadPasswords()
// Arguments: (std::ifstream) open input file stream &InFile,
//            (std::string *) array of Passwords,
//            (unsigned int) Number lines to read,
//            (unsigned int) length of longest line
// returns:   void
// Does:      Read each line from the file. Store in Passwords.
void ReadPasswords(std::ifstream &InFile, std::string *Passwords,
		   unsigned int &LineCount, unsigned int LongestLine)
{
  int WordsRead=0;
  char *c_string_word = new char [LongestLine+1];
  for (unsigned 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--;
    else
      WordsRead++;
  }
  LineCount = WordsRead;
  delete [] c_string_word;
}

// Function Merge()
// Arguments: (MyType) array list1 of (unsigned int) length length1,
//            (MyType) array list2 of (unsigned int) length length2,
//            (MyType) array Merged
// Returns:   void
// Does:      assuming that the two lists are already sorted, merge
//            these into a sing le sorted list called Merged. Assume
//            memory has been allocated for Merged
template <typename MyType>
void Merge(MyType *list1, unsigned int length1,
	   MyType *list2, unsigned int length2,  MyType *Merged)
{
  unsigned int i=0, j=0;
  for (unsigned 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++;
    }
}

// Function MergeSort()
// Arguments: (MyType) array list of (unsigned int) length length
// Returns:   void
// Does:      Applies Merge Sort algorithm to sort entries in array.
//            If the list of length 1, return
//            Else {split, sort, merge, return}
template <typename MyType>
void MergeSort(MyType *list, unsigned int length)
{
  if (length <=1)
    return;
  else
  {
    unsigned int m;
    m = (unsigned int)floor((double)length/2.0);
    MyType *list1 = new MyType [m];
    MyType *list2 = new MyType [length-m];
    for (unsigned int i=0; i<m; i++)
      list1[i]=list[i];
    for (unsigned 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;
  }
}


// Insert NewString into the list Top10, ordered by
// NewCount in Top10Freq, bumping anything if needed
void  Insert(std::string *Top10, unsigned int *Top10Freq,
	     std::string NewString, unsigned int NewCount)
{
  if (NewCount <= Top10Freq[9])
    std::cerr << "Error: new entry would not make top 10" << std::endl;
  else
  {
    Top10[9]=NewString;
    Top10Freq[9]=NewCount;
    for (int i=8; i>=0; i--)
    {
      if (Top10Freq[i]<NewCount)
      {
	Top10[i+1] = Top10[i];
	Top10Freq[i+1] = Top10Freq[i];
	Top10[i]=NewString;
	Top10Freq[i]=NewCount;
      }
    }
  }
}

void PrintTop10(std::string *list, unsigned int *count)
{
  for (unsigned int i=0; i<10; i++)
  {
    std::cout.width(15);
    std::cout << list[i];
    std::cout.width(8);
    std::cout << count[i] << std::endl;
  }
}