//Splay Tree
//------ stree.cpp ------
#include <vcl.h>
#pragma hdrstop

#include "stree.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <fstream.h>

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

TreeNode::TreeNode(TreeNode* LeftChild, TreeNode* RightChild, TreeNode*
            ChildParent, char string[], int FilePosition)
{
    Left = LeftChild;                  //initialze node
    Right = RightChild;                //
    Parent = ChildParent;              //
    strcpy(DataString, string);        //
    RecordLocation = FilePosition;     //
    Duplicates = 0;                    //
}


void TrimSpaces(char destination[], const char source[])
{                                //trims off whitespace from end of string
    int i;
    strcpy(destination, source);
    for(i = (strlen(source)-1); destination[i] == ' '; i--)
    {
        if(destination[i] == '\0')
            break;
    }
    destination[i+1] = '\0';
}

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

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

void STree::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 STree::Insert(char string[], int FilePosition)   //creates a new node for string
{
    Splay(string, InsertItem(string, FilePosition));  //insert node and then splay it
}

TreeNode* STree::InsertItem(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, 0, string, FilePosition);
        return Root;
    }
    int comparison;

    while(1)
    {
        char temp[20], temp2[20];
        TrimSpaces(temp, Node->DataString);
        TrimSpaces(temp2, string);
        comparison = strcmp(temp2, temp);
        if(comparison < 0)
        {
            if(Node->Left == 0)   //if Left is empty put the new node there
            {
                Node->Left = new TreeNode(0, 0, Node, string, FilePosition);
                return Node->Left;  //Node->Left will be promoted to the root by splay()
            }
            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, Node, string, FilePosition);
                return Node->Right;   //Node->Right will be promoted to the root by splay()
            }
            else
                Node = Node->Right;   //check right sub-tree
        }
        else   //node is a duplicate
        {
            TreeNode* TempNode = Node;
            while(TempNode->Duplicates != 0)      //find the end of the duplicate list
                TempNode = TempNode->Duplicates;
            TempNode->Duplicates = new TreeNode(0, 0, TempNode, string, FilePosition);
            return Node;    //Node will be promoted to the root by splay()
        }
    }
}


void STree::Splay(char string[], TreeNode* Node)  //splay moves th node conating string
{                        //toward the root.
    if(Node==0)        //if node does not point to anything the the node
    {                  //containing string will have to be found
        Node = Root;   //If Node does point to the node containing string then
        while(1)       //we won't have to search for it.  This saves a little time
        {              //when a function calls splay() and already knows where string
            char temp[20];                           //is located
            TrimSpaces(temp, Node->DataString);
            int comparison = strcmp(string, temp);
            if(comparison < 0)
            {
                if(Node->Left == 0)   //if Left is empty we found the spot
                    break;
                else
                    Node = Node->Left;   //check left sub-tree
            }
            else if(comparison > 0)
            {
                if(Node->Right == 0)   //if Right is empty we found the spot
                    break;
                else
                    Node = Node->Right;   //check right sub-tree
            }
            else
                break;  //we found an exact match
        }
    }
    while(Node->Parent != 0)  //splay until the node becomes the root
    {
        if(Node->Parent->Parent != 0)   //if node is not a child of root
        {
            if(Node->Parent->Parent->Left == Node->Parent)
            {
                if(Node->Parent->Left == Node)
                    LeftLeft(Node);      //make a left-left rotation
                else
                    LeftRight(Node);     //make a left-right rotation
            }
            else
            {
                if(Node->Parent->Right == Node)
                    RightRight(Node);    //make a right-right rotation
                else
                    RightLeft(Node);    //make a right-left rotation
            }
        }
        else  //Node is a child of root
        {
            if(Node->Parent->Left == Node) //if node is the left child of root
                Left(Node);      //do a left roation
            else
                Right(Node);     //do a right rotation
        }
    }
}

void STree::Left(TreeNode* Node)
{
    TreeNode* Parent;
    TreeNode* Right;

    Parent = Node->Parent;    //initialize pointers
    Right = Node->Right;      //

    Node->Right = Parent;     //move the top to the bottom
    Node->Parent = 0;         //node is now the root
    if(Right!=0)
        Right->Parent = Parent; //if right exists, give it a parent
    Parent->Left = Right;    //attach child
    Parent->Parent = Node;   //Parent is now a child of node
    Root = Node;
}

void STree::Right(TreeNode* Node)            
{
    TreeNode* Parent;
    TreeNode* Left;

    Parent = Node->Parent;      //initialize pointers
    Left = Node->Left;          //

    Node->Left = Parent;        //move the top to the bottom
    Node->Parent = 0;           //node is now the root
    if(Left!=0)
        Left->Parent = Parent;   //if left exists, give it a parent
    Parent->Right = Left;       //attach child
    Parent->Parent = Node;   //Parent is now a child of node
    Root = Node;
}                                 

void STree::LeftLeft(TreeNode* Node)
{
    TreeNode *GrandParent, *GreatGrandParent;
    TreeNode *Parent, *Right, *ParentRight;
    Parent = Node->Parent;                  //intialize pointers
    GrandParent = Parent->Parent;           //
    GreatGrandParent = GrandParent->Parent; //
    Right = Node->Right;                    //
    ParentRight = Parent->Right;            //

    Parent->Parent = Node;   //move node to the top
    Parent->Right = GrandParent;  //move grandparent to the bottom
    GrandParent->Left = ParentRight;   //adjust children
    Node->Parent = GreatGrandParent;   //readjust node's parent
    GrandParent->Parent = Parent;      //put parent in the middle
    Node->Right = Parent;              //node is now to the left of the items
    Parent->Left = Right;              //adjust children
    if(Right!=0)
        Right->Parent = Parent;     //if there is a right child, give it a parent
    if(ParentRight!=0)
        ParentRight->Parent = GrandParent;   //give parentright a parent
    if(Node->Parent!=0)         //if node is not the root now then...
    {
        if(GreatGrandParent->Left == GrandParent) //if this subtree is on the left
            GreatGrandParent->Left = Node;  //node now on top on left side
        else
            GreatGrandParent->Right = Node; //node now on top on right side
    }
    else
        Root = Node;  //Node is now the root
}

void STree::RightRight(TreeNode* Node)
{
    TreeNode *GrandParent, *GreatGrandParent;
    TreeNode *Parent, *Left, *ParentLeft;
    Parent = Node->Parent;                  //intialize pointers
    GrandParent = Parent->Parent;           //
    GreatGrandParent = GrandParent->Parent; //
    Left = Node->Left;                    //
    ParentLeft = Parent->Left;            //
                                                    
    Parent->Parent = Node;   //move node to the top
    Parent->Left = GrandParent;  //move grandparent to the bottom
    GrandParent->Right = ParentLeft;   //adjust children
    Node->Parent = GreatGrandParent;   //readjust node's parent
    GrandParent->Parent = Parent;      //put parent in the middle
    Node->Left = Parent;              //node is now to the Right of the items
    Parent->Right = Left;              //adjust children
    if(Left!=0)
        Left->Parent = Parent;     //if there is a Left child, give it a parent
    if(ParentLeft!=0)
        ParentLeft->Parent = GrandParent;   //give parentLeft a parent
    if(Node->Parent!=0)        //if node is not the root
    {
        if(GreatGrandParent->Left == GrandParent)    //if this subtree is on the left
            GreatGrandParent->Left = Node;   //node now on top on left side
        else
            GreatGrandParent->Right = Node;  //node now on top on right side
    }
    else
        Root = Node;  //Node is now the root
}

void STree::LeftRight(TreeNode* Node)
{
    TreeNode *Parent, *GrandParent, *GreatGrandParent;
    TreeNode *Left, *Right;

    Parent = Node->Parent;                       //intialize pointers
    GrandParent = Parent->Parent;                 //
    GreatGrandParent = GrandParent->Parent;       //
    Left = Node->Left;                           //
    Right = Node->Right;                         //

    Node->Parent = GreatGrandParent;      //Node's Parent is now the parent of the subtree
    Node->Left = Parent;                  //Node's left child is now its parent
    Node->Right = GrandParent;            //Node's right child is its grandparent
    GrandParent->Parent = Node;      //grandparent is now a child of node
    Parent->Parent = Node;           //parent is now the child of its child
    Parent->Right = Left;            //reassign child
    GrandParent->Left = Right;       //reassign child

    if(Node->Parent!=0)           //if node is not the root
    {
        if(GreatGrandParent->Left == GrandParent)  //if we are working on the left subtree
            GreatGrandParent->Left = Node;       //adjust child pointer
        else
            GreatGrandParent->Right = Node;      //adjust child pointer
    }
    else
        Root = Node;  //Node is now the root
    if(Left!=0)
        Left->Parent = Parent;      //fix for change of parent
    if(Right!=0)
        Right->Parent = GrandParent;     //fix for change of parent
}

void STree::RightLeft(TreeNode* Node)
{
    TreeNode *Parent, *GrandParent, *GreatGrandParent;
    TreeNode *Right, *Left;

    Parent = Node->Parent;                       //intialize pointers
    GrandParent = Parent->Parent;                 //
    GreatGrandParent = GrandParent->Parent;       //
    Right = Node->Right;                           //
    Left = Node->Left;                         //

    Node->Parent = GreatGrandParent;      //Node's Parent is now the parent of the subtree
    Node->Right = Parent;                  //Node's Right child is now its parent
    Node->Left = GrandParent;            //Node's Left child is its grandparent
    GrandParent->Parent = Node;      //grandparent is now a child of node
    Parent->Parent = Node;           //parent is now the child of its child
    Parent->Left = Right;            //reassign child
    GrandParent->Right = Left;       //reassign child
    
    if(Node->Parent!=0)              //if node is not the root
    {
        if(GreatGrandParent->Left == GrandParent)    //if we are working on the left subtree
            GreatGrandParent->Left = Node;           //adjust child pointer
        else
            GreatGrandParent->Right = Node;         //adjust child pointer
    }
    else
        Root = Node;  //Node is now the root
    if(Left!=0)
        Left->Parent = GrandParent;      //fix for change of parent
    if(Right!=0)
        Right->Parent = Parent;     //fix for change of parent
}


bool STree::Remove(char string[])
{
    TreeNode* TempLeft;
    TreeNode* TempRight;

    Splay(string, 0);       //bring the node containg string to the root
    char temp[20];
    TrimSpaces(temp, Root->DataString);
    if(strcmp(string, temp)==0)     //check to make sure string was in the tree
    {
        TempLeft = Root->Left;     //hold pointers to left and right sub-trees
        TempRight = Root->Right;
        if(Root->Duplicates!=0)    //if there are duplicates
        {
            TreeNode* TempNode = Root;
            TreeNode* PreviousNode;
            while(TempNode->Duplicates!=0)  //find the end of the duplicates list
            {
                PreviousNode = TempNode;
                TempNode = TempNode->Duplicates;
            }
            strcpy(Root->DataString, TempNode->DataString);  //replace the node to be
            Root->RecordLocation = TempNode->RecordLocation; //removed with the contents of
            delete TempNode;                                 //a duplicate
            PreviousNode->Duplicates = 0;    //terminate duplicate list
        }                             
        else                            
        {
            delete Root;
            if(TempLeft!=0)
                TempLeft->Parent = 0;   //make TempLeft the Root
            Root = TempLeft;            //
            Splay(string, 0);         //bring a new root to the top
            Root->Right = TempRight;  //attach right subtree
            if(TempRight!=0)
                TempRight->Parent = Root; //adjust parent pointer
        }
    }
}



int STree::Search(char string[])
{
    Splay(string, 0);      //bring the node containing string to the root
    char temp[20];
    TrimSpaces(temp, Root->DataString);
    if(strcmp(string, temp)==0)   //check to make sure that string was found
        return Root->RecordLocation;  //return the location of string
    else
        return -1;    // the record cannot be found
}

TreeNode* STree::SearchFirstMatch(char string[])  //returns a pointer to the first node
{                                               //that matches string
    Splay(string, 0);     //bring the node containing string to the root
    char temp[20];
    TrimSpaces(temp, Root->DataString);
    if(strcmp(string, temp)==0)    //check to make sure that string was found
        return Root;    //return the node containing string
    else
        return 0;    // the record cannot be found
}

void STree::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 STree::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->Duplicates, OutputFile);           //save the duplicates
        SaveNode(Node->Left, OutputFile);     //save nodes in left sub-tree
        SaveNode(Node->Right, OutputFile);    //save nodes in right sub-tree
    }
}

void STree::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 STree::LeftDepth()
{
    return TreeDepth(Root->Left);   //measure the left sub-tree
}

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

int STree::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 STree::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
}







//-------- stree.h --------------
#include <stdio.h>
#ifndef streeH
#define streeH
//---------------------------------------------------------------------------

class TreeNode
{
    public:
        TreeNode(TreeNode* LeftChild, TreeNode* RightChild, TreeNode* ChildParent, char string[], int FilePosition);
        TreeNode* Left;
        TreeNode* Right;
        TreeNode* Duplicates;
        TreeNode* Parent;   //for determing parents, grand-parents and greatgrand-parent
        char DataString[20];    //hold first or last name of record
        int RecordLocation;     //hold record's position in the relative file
};


class STree
{
    friend class stree_class;
    public:
        STree();
        ~STree();

        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
        TreeNode* InsertItem(char string[], int FilePosition);
        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:
        void Splay(char string[], TreeNode* Node);  //for splaying tree

        void Left(TreeNode* Node);         //Rotation functions for splaying
        void Right(TreeNode* Node);        //
        void LeftLeft(TreeNode* Node);     //
        void RightRight(TreeNode* Node);   //
        void LeftRight(TreeNode* Node);    //
        void RightLeft(TreeNode* Node);    //

        int TreeDepth(TreeNode*);       //recursive function to find the depth from TreeNode*
        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