#ifndef BST_H
#define BST_H
 
//-----------------------------------------------------------------------------------------
 
#include <string>
#include "LinkedList.h"
 
//-----------------------------------------------------------------------------------------
 
using namespace std;
 
//-----------------------------------------------------------------------------------------
 
class BST
{
public:
    //Default constructor, sets the address of root to NULL
    BST ();
 
    //Deconstructor
    ~BST () {};
 
    //Insert new data into binary search tree
    bool Insert (string &word, int docID);
 
    //Find the word passed in as a parameter and copy document list
    bool Find (string &word, LinkedList &list);
 
    //friend ostream &operator << (ostream &ostr, BST &BSTree);
 
private:
    struct BSTNode {
        string Word; //contains a single word
        LinkedList DocList; //a linked list of document IDs
        BSTNode *left; //points to the left child
        BSTNode *right; //points to the right child
    };
 
    BSTNode * root;
 
    //Insert into subtree
    bool InsertIntoSubTree(BSTNode &parent, BSTNode &newNode);
};
#endif

#include "BST.h"
 
BST::BST()
{
    root = NULL;
}
 
//-----------------------------------------------------------------------------------------
// Insert new data into binary search tree
//-----------------------------------------------------------------------------------------
bool BST::Insert(string &word, int docID)
{
    BSTNode *newNode = new BSTNode;
    bool success = false;
 
    newNode->Word = word;
    newNode->DocList.Insert(docID);
    newNode->left = NULL;
    newNode->right = NULL;
 
    if (root == NULL)
    {
        root = newNode;
        success = true;        
        cout << "root: " << root->Word << endl;
    }
    else if (root->Word == word)
    {
        return false;
    }
    else
    {
        success = InsertIntoSubTree(*root, *newNode);
    }
 
    return success;
}
 
//-----------------------------------------------------------------------------------------
// Insert into the BST sub branch
//-----------------------------------------------------------------------------------------
bool BST::InsertIntoSubTree(BSTNode &parent, BSTNode &newNode)
{
    bool success = false;
 
    if (newNode.Word < parent.Word)
    {
        if (parent.left == NULL)
        {
            parent.left = &newNode;
            success = true;
            cout << "left: " << parent.Word << endl;
        }
        else
        {
            success = InsertIntoSubTree(*parent.left, newNode);
        }
    }
    else
    {
        if (parent.right == NULL)
        {
            parent.right = &newNode;
            success = true;
            cout << "right: " << parent.Word << endl;
        }
        else
        {
            success = InsertIntoSubTree(*parent.right, newNode);
        }
    }
 
    return success;
}
 
//-----------------------------------------------------------------------------------------
/*ostream &operator << (ostream &ostr, BST &BSTree)
{
    //ostr << "The document numbers contained in the list:";
    
    for (BSTNode *ptr = &BSTree.root; ptr-> != NULL; ptr = ptr->left)
    {
        ostr << ptr.Word;
    }
    
    return ostr;
}*/

// BSTTest.cpp
//--------------------------------------------------------------------
 
#include "WordStream.h"
#include "BST.h"
 
//--------------------------------------------------------------------
 
using namespace std;
 
//--------------------------------------------------------------------
 
int main()
{
    BST * newBST = new BST;
    string filename = "test.txt";
    WordStream file(filename);
    string word;
 
    while (file.Next(word)) //continuially reads a word from a file until end of file is reached
    {
        cout << "Input word: " << word << endl; //display what is being inputed
        newBST->Insert(word,1);
    }
 
    system("pause");
 
    return 0;
}