//-----------bst.cpp --------
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <fstream.h>

#include "bst.h"

//---------------------------------------------------------------------------
#pragma package(smart_init)

void TrimSpaces(char destination[], const char source[])
{
    int i;

    strcpy(destination, source);
    for(i = (strlen(source)-1); destination[i] == ' '; i--)
    {
        if(destination[i] == '\0')
            break;
    }
    destination[i+1] = '\0';
}

TreeNode::TreeNode(TreeNode* LeftChild, TreeNode* RightChild, char string[], int FilePosition)
{
    Left = LeftChild;
    Right = RightChild;
    strcpy(DataString, string);
    RecordLocation = FilePosition;
}

BST::BST()
{
    Root = 0;
}

BST::~BST()
{
    DeleteTree(Root);       //make call to DeleteTree which will free all dynamic memory
}      

void BST::DeleteTree(TreeNode* Node)   //operates with a post-order traversal
{
    if(Node!=0)
    {
        DeleteTree(Node->Left);   //delete the left sub-tree
        DeleteTree(Node->Right);  //delete the right sub-tree
        delete Node;
    }
    Node = NULL;  //Node is no longer in use
}

void BST::Insert(char string[], int FilePosition)   //creates a new node for string
{
    TreeNode* Node = Root;
    if(Root == 0)              //if the Root has not been established
    {
        Root = new TreeNode(0, 0, string, FilePosition);
        return;
    }
    int comparison;

    while(1)
    {
        char temp[20];
        TrimSpaces(temp, Node->DataString);
        comparison = strcmp(string, temp);
        if(comparison < 0)
        {
            if(Node->Left == 0)   //if Left is empty put the new node there
            {
                Node->Left = new TreeNode(0, 0, string, FilePosition);
                return;
            }
            else
                Node = Node->Left;   //check left sub-tree
        }
        else if(comparison > 0)
        {
            if(Node->Right == 0)   //if Right is empty put the new node there
            {
                Node->Right = new TreeNode(0, 0, string, FilePosition);
                return;
            }
            else
                Node = Node->Right;   //check right sub-tree
        }
        else
        {
            Node->Right = new TreeNode(0, Node->Right, string, FilePosition); //if its a duplicate
            return;                                            //put the duplicate in the right branch
        }
    }
}

bool BST::Remove(char string[])
{
    return FindAndRemove(string, Root);    //Find and remove uses recursion to locate
}                                          //and destroy the node containing string

bool BST::FindAndRemove(char string[], TreeNode *Node)
{
    if(Node == 0)
        return false;
    char temp[20];
    TrimSpaces(temp, Node->DataString);
    int compare = strcmp(string, temp);
    if(compare < 0)
        return FindAndRemove(string, Node->Left);    //look in left sub-tree
    else if(compare > 0)
        return FindAndRemove(string, Node->Right);   //look in right sub-tree
    else if(Node->Left != 0 && Node->Right != 0)     //if the node that needs to
    {                                                //be remmoved is the root of
        TreeNode *TempNode = Node;                   //a sub-tree the removal is
        while(TempNode->Left != 0)                   //handled here
            TempNode = TempNode->Left;   //find minimum node
        strcpy(Node->DataString, TempNode->DataString);   //replace contents of node to be
        Node->RecordLocation = TempNode->RecordLocation;  //removed with contents of minimum node
        return FindAndRemove(TempNode->DataString, TempNode);     //remove minimum's old location
    }
    else if(Node->Left == 0 && Node->Right == 0)
    {
        RemoveLeaf(Node->DataString);   //if the node to be removed is a leaf just delete the leaf
    }
    else if(Node->Left == 0)          //if the node to be removed has no left child
    {
        TreeNode *temp = Node->Right;
        strcpy(Node->DataString, Node->Right->DataString);  //move contents of right child to node
        Node->RecordLocation = Node->Right->RecordLocation; //move contents of right child to node
        Node->Left = Node->Right->Left;       //make node's left child its right child's left node
        Node->Right = Node->Right->Right;     //make node's right child its right child's right node
        delete temp;       //delete the right child, node has now become its right child
        return true;
    }
    else         //the node to be removed has no right child
    {
        TreeNode *temp = Node->Left;
        strcpy(Node->DataString, Node->Left->DataString);  //move contents of left child to node
        Node->RecordLocation = Node->Left->RecordLocation; //move contents of left child to node
        Node->Right = Node->Left->Right;      //make node's left child its left child's right node
        Node->Left = Node->Left->Left;        //make node's left child its left child's left node

        delete temp;    //delete the left child, node has now become its left child
        return true;
    }
}

void BST::RemoveLeaf(char string[])
{
    TreeNode *LastNode = Root;    //keep track of the previous node
    TreeNode *Node = Root;
    while(Node != 0)
    {
        int compare = strcmp(string, Node->DataString);
        if(compare < 0)
        {
            LastNode = Node;
            Node = Node->Left;    //look at left sub-tree
        }
        else if(compare > 0)
        {
            LastNode = Node;
            Node = Node->Right;   //look at right sub-tree
        }
        else
        {
            if(LastNode->Left == Node)
                LastNode->Left = 0;    //set the pointer that pointed to node to NULL
            else
                LastNode->Right = 0;   //set the pointer that pointed to node to NULL
            delete Node;
            return;
        }
    }
}


int BST::Search(char string[])
{
    TreeNode* Node = Root;
    int comparison;
    while(Node!=0)
    {
        char temp[20];
        TrimSpaces(temp, Node->DataString);
        comparison = strcmp(string, temp);
        if(comparison < 0)
            Node = Node->Left;       //look at left sub-tree
        else if(comparison > 0)
            Node = Node->Right;      //look at right sub-tree
        else
            return Node->RecordLocation;       //string has been found
    }
    return -1;    // the record cannot be found
}

TreeNode* BST::SearchFirstMatch(char string[])  //returns a pointer to the first node
{                                               //that matches string
    TreeNode* Node = Root;
    int comparison;
    while(Node!=0)
    {
        char temp[20];

        TrimSpaces(temp, Node->DataString);
        comparison = strcmp(string, temp);
        if(comparison < 0)
            Node = Node->Left;       //look at left sub-tree
        else if(comparison > 0)
            Node = Node->Right;      //look at right sub-tree
        else
            return Node;       //string has been found
    }
    return 0;
}

void BST::SaveToFile(char FileName[])   //save nodes to file in the order that they
{                                       //are outputed by a preorder traversal
    FILE *OutputFile;
    OutputFile = fopen(FileName, "w");
    if(OutputFile == NULL)
        return;
    SaveNode(Root, OutputFile);      //recursive funciton that will save each node to file
    fclose(OutputFile);
}

void BST::SaveNode(const TreeNode* Node, FILE *OutputFile)
{
                                                // % marks beginning of location number
    if(Node!=0)                                 // # marks and of node
    {
        fputs(Node->DataString, OutputFile);    //output the node's string to file
        putc('%', OutputFile);                  //output flag
        char temp[10];
        itoa(Node->RecordLocation, temp, 10);   //convert int so that it can be sent to file
        fputs(temp, OutputFile);
        putc('#', OutputFile);
        SaveNode(Node->Left, OutputFile);     //save nodes in left sub-tree
        SaveNode(Node->Right, OutputFile);    //save nodes in right sub-tree
    }
}

void BST::LoadFromFile(char FileName[])   //nodes are added to the tree in the same
{                                         //order that they were outputed by the
    fstream InputFile(FileName, ios::in); //pre-order traversal. As a result, the
    char chr;                             //tree has the same structures as the time
    char string[20];                      //when it was saved to file
    char Location[6];
    int i;
    for(InputFile.get(chr);!InputFile.eof(); InputFile.get(chr))   //read through the
    {                                                              //whole file
        for(i=0;chr!='%'; i++)   //input the node's string until
        {                        // % is reached
            string[i] = chr;
            InputFile.get(chr);
        }
        string[i] = '\0';        //terminate the string
        InputFile.get(chr);
        for(i=0;chr!='#'; i++)
        {
            Location[i] = chr;       //input the node's location until
            InputFile.get(chr);      // # is reached
        }
        Location[i] ='\0';
        Insert(string, atoi(Location));    //add the node to the tree
    }
}

int BST::LeftDepth()
{
    return TreeDepth(Root->Left);   //measure the left sub-tree
}

int BST::RightDepth()
{
    return TreeDepth(Root->Right);   //measure the right sub-tree
}                                       

int BST::TreeDepth(TreeNode *Node)
{
    int left = 0;
    int right = 0;
    if(Node->Left != 0)
        left = TreeDepth(Node->Left);   //get the depth of the left sub-tree
    if(Node->Right != 0)
        right = TreeDepth(Node->Right); //get the depth of the right sub-tree
    if( left > right)     //check to see which sub-tree is deeper
        return left+1;    //return the depth of the left sub-tree plus 1
    else
        return right+1;   //return the depth of the right sub-tree plus 1
}

int BST::NumberOfLeaves(TreeNode* Node)
{
    int total = 0;
    if(Node->Left == 0 && Node->Right == 0)
        return 1;         //the node is a leaf
    if(Node->Left!= 0)                        //count the number of leaves in the
        total += NumberOfLeaves(Node->Left);  //left sub-tree
    if(Node->Right!=0)                        //count the number of leaves in the
        total += NumberOfLeaves(Node->Right); //right sub-tree
    return total;          //return the total of all the leaves in this sub-tree
}




 


//-----------bst.h ----------
#include <stdio.h>
#ifndef bstH
#define bstH
//---------------------------------------------------------------------------
class TreeNode
{
    public:
        TreeNode(TreeNode* LeftChild, TreeNode* RightChild, char string[], int FilePosition);
        TreeNode* Left;
        TreeNode* Right;
        char DataString[20];    //hold first or last name of record
        int RecordLocation;     //hold record's position in the relative file
};


class BST
{
    friend class bst_class;
    public:
        BST();
        ~BST();

        int Search(char string[]);                 //returns the file position of string
        TreeNode* SearchFirstMatch(char string[]); //same as search but returns a TreeNode*
                                                        //to the first matching node
        void Insert(char string[], int FilePosition);   //creates new nodes
        bool Remove(char string[]);                     //removes nodes

        void LoadFromFile(char FileName[]);     //recreates the tree from a file
        void SaveToFile(char FileName[]);       //stores the tree to a file

        int LeftDepth();                   //Finds the depth of the left sub-tree
        int RightDepth();                  //Finds the depth of the right sub-tree
        int NumberOfLeaves(TreeNode*);     //Finds the number of leaves in the tree

        TreeNode* Root;

    private:
        int TreeDepth(TreeNode*);       //recursive function to find the depth from TreeNode*
        bool FindAndRemove(char string[], TreeNode *Node);   //locates and removes the node containing string
        void RemoveLeaf(char[]);                             //removes a leaf containing the argument
        void DeleteTree(TreeNode*);                          //used with the destructor to destroy the tree
        void SaveNode(const TreeNode* Node, FILE *OutputFile);   //saves the contents of a node to the file
                                                                 //pointed to by OutputFile

};
#endif