#include <iostream>
#include <fstream>
#include <string>
#include <list>
#include <iomanip>

using namespace std;

// File Descriptors
ofstream outfile;
ifstream infile;

// Class Definitions
class TreeNode
{
    typedef string valueType;
    private:
        TreeNode* root;         //  The tree's root node's pointer
        TreeNode* Lchild;       // Points to this node's left child
        TreeNode* Rchild;       // Points to this node's right child
        valueType word;         // Holds the word
        int counter;            // Holds the number of occurences of the word
    public:
        // Constructer
      TreeNode()
      {
        root = NULL;                // Root is not pointing to anything yet
        counter = 0;                // No words counted yet
      }
      TreeNode* insert(TreeNode *root, valueType);  // Adds a word to the bst
      TreeNode* search(TreeNode* r, valueType);     // Searches for instances of each word
      TreeNode* get_root()          // Returns the root of the class
      { return root;}
      valueType get_word()          // Returns the word in current node
      { return word;}
      int get_counter()             // Returns the counter of current node
      { return counter;}
      void print(TreeNode*);        // Prints out each word along with it's count and frequency
      TreeNode* myNewNode();        // Creates a new pointer to a new node in the bst
};


// Prototypes
int OpenOutput();
int OpenInput();
void PrintHeader();

int main()
{
    OpenOutput();
    OpenInput();
    PrintHeader();

    string word;                    // Declare variable to hold each word from infile
    //TreeNode* root = NULL;          // Declare a pointer of type TreeNode that points to our tree
    TreeNode tree;                  // Declare an object of type TreeNode to start a tree
    //tree.myNewNode();               // Create a node for root to point to
    infile >> word;
    while (infile)
    {
       tree.insert(tree.get_root(), word);  // Insert word into tree
       infile >>  word;                     // Get next word

       // Display each word with total # of occurrences and % of input file
       cout << "Word: " << setw(16) << tree.get_word() << setw(10) << "  Absolute: "
            << tree.get_counter() << setw(11) << "Relative: " << endl;
       outfile << "Word: " << setw(16) << tree.get_word() << setw(10) << "  Absolute: "
               << tree.get_counter() << setw(11) << "Relative: "<< endl;

    }

    return 0;
}

// Funtion Definitions
// *********************************************************************
TreeNode* TreeNode::myNewNode()
{
    TreeNode* temp = NULL;          // New pointer, points to nothing
    temp = new TreeNode;            // Points to a newly created node
    //.temp->word = NULL;              // Empty value in word section
    temp->Lchild = NULL;            // There are no left children yet to point to
    temp->Rchild = NULL;            // There are no right children yet to point to
    temp->counter = 0;              // There are no words to count yet
    return temp;
}

// *********************************************************************
//TreeNode* TreeNode::insert(TreeNode* r, valueType v)    // Adds a word to the bst
TreeNode* TreeNode::insert(TreeNode *root, valueType v)    // Adds a word to the bst

{
    TreeNode* parent;       // Points to parent node
    TreeNode* temp;         // Temporary holding place

    if (root == NULL)       // If we don't have a tree yet
    {
        root = myNewNode(); // This starts us off
        word = v;           // Put passed in word into tree node
        counter = counter + 1;// Increment that word's counter
        return root;        // Get out of function
    }
    while (root != NULL)    // While we do have a tree
    {                       // Search for where to put new value
        if(v < word)        // If new word is less than root's word
        {
            parent = root;  // Make the root a parent
            root = Lchild;  // Move down left tree
            counter = counter + 1;
        }
        else if (v > word)  // If new word is greater than root word
        {
            parent = root;  // Make the root a parent
            root = Rchild;  // Move down right tree
            counter = counter + 1;
        }
    }
    temp = myNewNode();     // Create a new node
    temp->word = v;         // Fill in the word field

    //  Update left and right parents
    if (v < parent->word)
        parent->Lchild = temp;
    else if (v > parent->word)
        parent->Rchild = temp;
    return root;
}
// *********************************************************************
TreeNode* TreeNode::search(TreeNode* r, valueType val)
{
    while (r != NULL && val != r->word)
    {
        if (val < r->word)
        {
            r = r->Lchild;
        }
        else
        {
            r = r->Rchild;
        }
    }
    if (r->word == val)
    {
        // Update counter for that word
        r->counter = counter + 1;
    }
}

// *********************************************************************
void TreeNode::print(TreeNode*)
{
    if (root == NULL)
        return;
    print(Lchild);
    cout << word;
    print(Rchild);
}

// *********************************************************************
int OpenOutput()
{
    outfile.open("TreesOUT");
    if (!outfile)
    {
        cout << "Error opening output file." << endl << endl;
        outfile << "Error opening output file." << endl << endl;
        return 1;
    }
    else
    cout << "Output file opened correctly." << endl << endl;
    outfile << "Output file opened correctly." << endl << endl;
}

// *********************************************************************
int OpenInput()
{
    infile.open("USconstitution.dat");
    if (!infile)
    {
        cout << "Error opening input file." << endl << endl;
        outfile << "Error opening input file."  << endl << endl;
        return 1;
    }
    else
    {
        cout << "Input file opened correctly." << endl << endl;
        outfile << "Input file opened correctly." << endl << endl;

    }
}

// *********************************************************************
void PrintHeader()
{
    cout << "Erin Corona" << endl;
    cout << "CS 372.30137" << endl;
    cout << "Trees " << endl;
    cout << "Due Friday, July 13, 2012" << endl << endl;

    outfile << "Erin Corona" << endl;
    outfile << "CS 372.30137" << endl;
    outfile << "Trees " << endl;
    outfile << "Due Friday, July 13, 2012" << endl << endl;
}