// Program WordList creates a list of unique words from 
// input file  book.in and writes them with frequency 
// count to the file words.out.

#include <fstream>
#include <cstdlib>
#include <iostream>
#include <cctype>
using namespace std;

const int MAX_CHARS = 200;

enum RelationType {LESS, EQUAL, GREATER};

class StrType
{
public:

  StrType();

  void GetStringFile(bool skip, std::ifstream& inFile);
  //Post: If the number of allowable characters exceeds
  //      MAX_CHARS, the remaining allowable characters have been
  //      read and discarded.

  void PrintToFile(bool newLine, std::ofstream& outFile);

  RelationType ComparedTo(const StrType& )const;
  //Precondition:  Self and otherString have been initialized.
  // Postcondition:  Function value 
  //                        = LESS    if self comes before otherString
  //                        = GREATER if self comes after otherString;
  //                        = EQUAL   if self and otherString are equal


  int LengthIs();

private:
  char letters[MAX_CHARS + 1];
};



struct WordType
{
  StrType word;
  int count;
};

struct TreeNode
{
  WordType info;
  TreeNode * left;
  TreeNode * right;
};

void PrintTree(TreeNode*, std::ofstream&);
// Prints the words in the tree and their frequency counts.

void IncrementOrInsert(TreeNode*&, StrType);
// Increments the frequency count if the string is in the tree
// or inserts the string if it is not there.

int main()
{
  using namespace std;
  TreeNode* tree = NULL;
  ifstream inFile;
  ofstream outFile;
  StrType string;
  inFile.open("history.in");
  outFile.open("words.dat");
  string.GetStringFile(true, inFile);

  while (inFile)
  {    
    if (string.LengthIs() > 2)
      IncrementOrInsert(tree, string);
    string.GetStringFile(true, inFile);
  }
  PrintTree(tree, outFile);
  return 0;
}

void IncrementOrInsert(TreeNode*& tree, StrType string)
{
  if (tree == NULL)
  {
    tree = new TreeNode;
    tree->info.word = string;
    tree->info.count = 1;
    tree->left = NULL;
    tree->right = NULL;
  }
  else
  {
    switch (tree->info.word.ComparedTo(string))
    {
      case EQUAL   :  tree->info.count++; 
                      break;
      case GREATER :  IncrementOrInsert(tree->left, string); 
                      break;
      case LESS    :  IncrementOrInsert(tree->right, string);
                      break;
      default : cout << "error";            
    }
  }
}

void PrintTree(TreeNode* tree, std::ofstream& outFile)
{
  if ( !(tree == NULL))
  {
    PrintTree(tree->left, outFile);
    tree->info.word.PrintToFile(true, outFile);
    outFile << ": " << tree->info.count;
    PrintTree(tree->right, outFile);
  }
}

int StrType::LengthIs()
{
  return std::strlen(letters);
}

void StrType::PrintToFile(bool newLine, std::ofstream& outFile)
{
  if (newLine)
    outFile  << std::endl;
  outFile  << letters;
}

StrType::StrType()
{
  letters[0] = '\0';
}


void StrType::GetStringFile(bool skip, std::ifstream& inFile)
{
 
  using namespace std;
  char letter;
  int count = 0;

  if (skip)
  {
    inFile.get(letter);
    while (!isalnum(letter) && inFile)
      inFile.get(letter);
  }
  else
    inFile.get(letter);
  if (!inFile || !isalnum(letter))
    letters[0] = '\0';
  else
  {
    do
    {
      letters[count] = letter;
      count++;
      inFile.get(letter);
    } while (isalnum(letter) && inFile && (count < MAX_CHARS));
    letters[count] = '\0';

    // Skip extra characters if necessary.
    if (count == MAX_CHARS)
      do
      {
        inFile.get(letter);
      } while (isalnum(letter) && inFile);

  }
}

RelationType StrType::ComparedTo(const StrType& local) const
//Precondition:  Self and otherString have been initialized.
// Postcondition:  Function value 
//                        = LESS    if self comes before otherString
//                        = GREATER if self comes after otherString;
//                        = EQUAL   if self and otherString are equal

{
  int comp;
  comp = std::strcmp(letters, local.letters);

  if( comp == 0 )
 
    return EQUAL;

  else if( comp  <  0)
 
    return 	LESS;
 
  else
    return GREATER;

}