#include <iostream>
#include <string>
#include <fstream>
#include <iomanip>
#include <cctype>
#include <stack>
using namespace std;
 
class Node;
stack<string> theStack_;
typedef Node * nodePtr_;
 
class Node
{
public:
    string data_;
    nodePtr_ left_;
    nodePtr_ right_;
    Node() : left_(NULL), right_(NULL), data_("") { }
};
 
 
class BST
{
private:
    nodePtr_ root_;
public:
    BST() : root_(NULL) { }
 
    void insert(string data)
    {
        insert(data, root_);
    }
    void insert(string data, nodePtr_ &node)
    {
        if (node == NULL)
        {
            node = new Node();
            node->data_ = data;
        }
        else if (data < node->data_)
        {
            // Traverse left sub tree
            insert (data, node->left_);
        }
        else if ( data > node->data_)
        {
            // Traverse right sub tree
            insert (data, node->right_);
        }
        else
        {
            // Node exists
            cout << "Node value: " << node->data_ << " already exists!" << endl;
        }
    }
 
    bool spellCheck(string data)
    {
        bool broken = spellCheck(data, root_, 0);
        return broken;
    }
    bool spellCheck(string data, nodePtr_ &node, int indent)
    {
        if (node == NULL)
        {
            return false; // Empty
        }
        else if (data == node->data_)
        {
            return true;
        }
        else if (data < node->data_)
        {
            return true;
        }
        else
        {
            return spellCheck(data, node->right_, indent+8);
        }
    }
    // Recursive printing
    void printTree( ostream &output, nodePtr_ &node, int indent)
    {
        if (node != NULL)
        {
            printTree (output, node->right_, indent+8);
            output << setw(indent) << node->data_ << endl;
 
            printTree (output, node->left_, indent+8);
        }   
    } 
    void removeNode (string data)
    {
        bool found_ = false;
        nodePtr_ node = root_;
        nodePtr_ parent_ = NULL;
 
 
        while (!found_ && (node != NULL))
        {
            if (data < node->data_)
            {
                // Go left
                parent_ = node;
                node = node->left_;
            }
            else if (data > node->data_)
            {
                // go right
                parent_ = node;
                node = node->right_;
            }
            else
            {
                // found!
                found_ = true;
            }
        }
 
        if (!found_)
        {
            return;
        }
 
        // find the successor
        if ((node->left_ != NULL) && (node->right_ != NULL))
        {
            // Goto left most node
            nodePtr_ successor = node->right_;
            parent_ = node;
            while (successor->left_ != NULL)
            {
                parent_ = successor;
                successor = successor->left_;
            }
            node->data_ = successor->data_;
            node = successor;
        }
 
        // now we can delete the node with either one child or no child
        nodePtr_ subTree = node->left_;
 
        if (subTree == NULL)
        {
            subTree = node->right_;
        }
        if (parent_ == NULL)
        {
            // delete root node
            root_ = subTree;
        }
        else if (parent_->left_ == node)
        {
            // delete a node with left subtree
            parent_->left_ = subTree;
        }
        else
        {
            // Delete a node with a right subtree
            parent_->right_ = subTree;
        }
        delete node;
    }
 
 
 
 
 
 
    // Trying to sort
    bool treeContains( nodePtr_ &node, string item, int indent)
    {
        if (node == NULL)
        {
            return false; // tree is empty
        }
        else if (item == node->data_)
        {
            return true;
        }
        else if (item < node->data_)
        {
            return true;
        }
        else 
        {
            return treeContains( node->right_, item, indent+8);
        }
    } 
    friend ostream& operator<<( ostream &output, BST &bst);
};
ostream& operator<< (ostream &output, BST &bst)
{
    bst.printTree(output, bst.root_, 0);
    //bst.printTree(bst.root_);
    return output;
}
 
 
 
 
 
 
 
 
 
 
int main()
{
    BST bst;
    string line;
    ifstream dictionaryFile("dictionary.txt");
    ifstream paragraphFile("paragraph.txt");
    int fileSize = 0; // Size of paragraph
    int dictLoaded = 0; // 0 - not loaded, 1 - loaded, 1< - done
    bool brokenWord = false;
    string search_for = " ";
 
    if (dictLoaded == 0)
    {
        if (dictionaryFile.is_open())
        {
            while (!dictionaryFile.eof())
            {
                getline(dictionaryFile,line);
                bst.insert(line);
            }
        }
        dictionaryFile.close();
        dictLoaded = 1;
    }
 
    if (dictLoaded == 1)
    {
        if (paragraphFile.is_open())
        {
            while (dictLoaded >> line)
            {
                if (line == search_word)
                {
                }
                //getline(paragraphFile,line);
                //brokenWord = bst.spellCheck(line);
                //if (brokenWord)
                //{
                //    cout << "Bad word! ";
                //}
                //else
                //{
                //    cout << "No bad words!";
                //}
            }
        }
        dictLoaded = 2;
        paragraphFile.close();
    }
    cout << bst << endl;
    return 0;
}

std::ifstream in ( "myfile" );
 
if ( in ) 
{
  std::string word;
  while ( in>> word ) 
   {
       spellCheck(word);
 
   }
}