//--------- AVL.cpp --------------
#include <vcl.h>
#pragma hdrstop
#include <string.h>
#include <fstream.h>
#include "AVL.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;
    Depth = 0;
    Deleted = false;
    Duplicates = 0;
}

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

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

void AVL::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
        DeleteTree(Node->Duplicates);
        delete Node;
    }
    Node = NULL;  //Node is no longer in use
}

void AVL::Insert(char string[], int FilePosition)
{
    InsertNode(string, FilePosition, Root, Root);
}                       

int AVL::InsertNode(char string[], int FilePosition, TreeNode* Node,
            TreeNode* PreviousNode)   //creates a new node for string
{
                         
    if(Root == 0)              //if the Root has not been established
    {
        Root = new TreeNode(0, 0, string, FilePosition); //esatablish root
        return 1;
    }
    char temp[20];
    TrimSpaces(temp, PreviousNode->DataString);   //trim spaces for comparison
    if(Node == 0)
    {
        char TempString[20];
        TrimSpaces(TempString, string);     //trim spaces for comparison
        if(strcmp(TempString, temp) > 0)
            PreviousNode->Right = new TreeNode(0, 0, string, FilePosition);  //make it a right child
        else if(strcmp(TempString, temp) < 0)
            PreviousNode->Left = new TreeNode(0, 0, string, FilePosition);  //make it a left child
        else
        {                  // The record is a duplicate, add it to the node's duplicate list
            PreviousNode->Duplicates = new TreeNode(0, 0, string, FilePosition);
            return 2;
        }
        return 1;
    }

    TrimSpaces(temp, Node->DataString);     //trim spaces for comparison
    if(Node->Deleted)
    {                                       // we use lazy deletes in this program
        bool GreaterThanLeft, LessThanRight;
        char temp2[20];
        if(Node->Left!=0)
        {
            TrimSpaces(temp2, Node->Left->DataString);
            if(strcmp(string, temp2) > 0)    //check to see if the record to be inserted is
                GreaterThanLeft = true;      //greater than the left child of deleted node
            else
                GreaterThanLeft = false;
        }
        else
            GreaterThanLeft = true;    //nothing in left so node is greater than it
        if(Node->Right!=0)
        {
            TrimSpaces(temp2, Node->Right->DataString);
            if(strcmp(string, temp2) > 0)
                LessThanRight = true;         //check to see if the record to be inserted is
            else                              //greater than the right child of deleted node
                LessThanRight = false;
        }
        else
            LessThanRight = true;        //nothing in right so node is greater than it

        if((LessThanRight && GreaterThanLeft) || strcmp(string, temp2) == 0)
        {   //if new record is between children or the new record is equal to deleted record

            strcpy(Node->DataString, string);      //replace the deleted node with the new node
            Node->RecordLocation = FilePosition;
            Node->Deleted = false;
            return 2;                  // no change in depth has occured, return 2
        }
    }
   else if(strcmp(string, Node->DataString) < 0)   //go to left subtree
   {
        int status = InsertNode(string, FilePosition, Node->Left, Node);   //attempt to insert node in left
        if(status == 1)               //if status is = to 1 we need to check for rotations
        {
            if(Node->Depth == -1)      //the sub-tree is already left-sided so a rotation is needed
            {
                LeftRotation(Node);
                return 0;              // 0 means not to check for rotation on next check
            }
            else if(Node->Depth == 0)  //if the sub-tree had equal sides at the beginning
                Node->Depth = -1;      //it has slightly more on the left after insertion
            else
            {
                Node->Depth = 0;     //the tree now has equal sides
                return 0;            // 0 means not to check for rotation on next check
            }
         }
         else if(status == 2)       //status 2 means no rotations are needed
            return 2;
   }
   else if(strcmp(string, Node->DataString) > 0)
   {                                                //insert node in right sub-tree
        int status = InsertNode(string, FilePosition, Node->Right, Node);
        if(status == 1)
        {
            if(Node->Depth == -1)
            {
                Node->Depth = 0;      //the tree was left-sided, now it is balanaced
                return 0;             // 0 means not to check for rotation on next check
            }
            else if(Node->Depth == 0)
                Node->Depth = 1;         //The sub-tree is now heavier on the right
            else
            {
                RightRotation(Node);     //right rotation needed
                return 0;                // 0 means not to check for rotation on next check
            }

         }
         if(status == 2)          // status 2 means that no roations will be needed
            return 2;
   }
   else
   {
        InsertNode(string, FilePosition, Node->Duplicates, Node);  //the node is a duplicate
        return 2;           // return 2 because duplicates won't be counted as adding to depth
   }
   return 1;     // 1 means that rotations may be needed on recursive call that called this function
}

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


void AVL::RightRotation(TreeNode* Node)   //make a right rotation
{
    TreeNode *Temp1, *Temp2, *HoldDuplicates;

   Temp1 = Node->Right;
   if(Temp1->Depth == 1)    // if depth is 1 a righ-right rotations is needed
   {
        TreeNode* TempNode;                              // swap Temp1 with Node --//
        TempNode = new TreeNode(0, 0, Temp1->DataString, Temp1->RecordLocation);   //
        strcpy(Temp1->DataString, Node->DataString);                               //
        Temp1->RecordLocation = Node->RecordLocation;                              //
        strcpy(Node->DataString, TempNode->DataString);                            //
        Node->RecordLocation = TempNode->RecordLocation;                           //
                                                                     ////////////////
        HoldDuplicates = Node->Duplicates;
        Node->Duplicates = Temp1->Duplicates;   //swap the duplicate lists
        Temp1->Duplicates = HoldDuplicates;

        Node->Right = Temp1->Right;
        Temp1->Right = Temp1->Left;    //reorder node configuration
        Temp1->Left = Node->Left;      //node will be the parent of Temp1
        Node->Left = Temp1;            //and Temp1's right child

        Temp1->Depth = 0;    // tree is now balanced
        delete TempNode;
   }
   else      // A right-left rotation is needed
   {
        TreeNode* TempNode;
        Temp2 = Temp1->Left;
        TempNode = new TreeNode(0, 0, Temp2->DataString, Temp2->RecordLocation);

        strcpy(Temp2->DataString, Node->DataString);   //swap node with temp2 //
        Temp2->RecordLocation = Node->RecordLocation;                         //
        strcpy(Node->DataString, TempNode->DataString);                       //
        Node->RecordLocation = TempNode->RecordLocation;                      //

        HoldDuplicates = Temp2->Duplicates;
        Temp2->Duplicates = Node->Duplicates;    //swap the duplicate lists
        Node->Duplicates = HoldDuplicates;
        delete TempNode;

        Temp1->Left = Temp2->Right;
        Node->Right = Temp1;           //node becomes the parent of Temp1 and Temp2
        Temp2->Right = Temp2->Left;
        Temp2->Left = Node->Left;
        Node->Left = Temp2;
        if(Temp2->Depth == -1)
            Temp1->Depth = 1;   //temp1 has lost its left sub-tree, update to reflex change
        else
            Temp1->Depth = 0;
        if(Temp2->Depth == 1)
            Temp2->Depth = -1;  //temp2 has lost it righ-sub tree, new depth is -1
        else
            Temp2->Depth = 0;
   }
   Node->Depth = 0;        // node is now balanced
}

void AVL::LeftRotation(TreeNode* Node)       //make a left rotation
{
    TreeNode *Temp1, *Temp2, *HoldDuplicates;

   Temp1 = Node->Left;
   if(Temp1->Depth == -1)   // if depth is -1 a left-left rotations is needed
   {
        TreeNode* TempNode;                              //swap node with Temp1 ///
        TempNode = new TreeNode(0, 0, Temp1->DataString, Temp1->RecordLocation); //
        strcpy(Temp1->DataString, Node->DataString);                             //
        Temp1->RecordLocation = Node->RecordLocation;                            //
        strcpy(Node->DataString, TempNode->DataString);                          //
        Node->RecordLocation = TempNode->RecordLocation;               ////////////

        HoldDuplicates = Node->Duplicates;
        Node->Duplicates = Temp1->Duplicates;   //swap duplicate lists
        Temp1->Duplicates = HoldDuplicates;

        Node->Left = Temp1->Left;
        Temp1->Left = Temp1->Right;    //node becomes the parent of Temp1
        Temp1->Right = Node->Right;    //and Temp1's Left child
        Node->Right = Temp1;

        Temp1->Depth = 0;       //temp1 is now balanced
        delete TempNode;
   }
   else                                  
   {                              // left-right rotation needed
        TreeNode* TempNode;
        Temp2 = Temp1->Right;
        TempNode = new TreeNode(0, 0, Temp2->DataString, Temp2->RecordLocation);

                                 
        strcpy(Temp2->DataString, Node->DataString);   //swap node with temp2 //
        Temp2->RecordLocation = Node->RecordLocation;                         //
        strcpy(Node->DataString, TempNode->DataString);                       //
        Node->RecordLocation = TempNode->RecordLocation;                      //

        HoldDuplicates = Temp2->Duplicates;
        Temp2->Duplicates = Node->Duplicates;   //swap duplicate lists
        Node->Duplicates = HoldDuplicates;
        delete TempNode;

        Temp1->Right = Temp2->Left;
        Node->Left = Temp1;
        Temp2->Left = Temp2->Right;     //node becomes the parent of Temp1 and Temp2
        Temp2->Right = Node->Right;           
        Node->Right = Temp2;
        if(Temp2->Depth == 1)
            Temp1->Depth = -1;     //Temp1 has lost its right side in rotation
        else
            Temp1->Depth = 0;
        if(Temp2->Depth == -1)
            Temp2->Depth = 1;     //Temp2 has lost its left side in rotation
        else
            Temp2->Depth = 0;
   }
   Node->Depth = 0;     // tree is now balanced
}

bool AVL::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->Duplicates!= 0)     //if the node matches and it has duplicates
    {
        TreeNode* TempNode;
        TreeNode* PreviousNode;
        while(TempNode->Duplicates != 0)  //find last node in duplicate list
        {
            PreviousNode = TempNode;
            TempNode = TempNode->Duplicates;
        }
        strcpy(Node->DataString, TempNode->DataString);  //node will be set equal to the
        Node->RecordLocation = TempNode->RecordLocation; //last node in the duplicate list
        delete TempNode;     //remove last node in duplicates list
        PreviousNode->Duplicates =0;   //terminate the duplicate list
    }
    else
    {
        Node->Deleted = true;   //delete the node
        return true;
    }
}


int AVL::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
        {
            if(!Node->Deleted)
                return Node->RecordLocation;       //string has been found
            else
                return -1;
        }
    }
    return -1;    // the record cannot be found
}

TreeNode* AVL::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
        {
            if(!Node->Deleted)
                return Node;       //string has been found
            else
                return 0;
        }
    }
    return 0;
}

void AVL::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 AVL::SaveNode(const TreeNode* Node, FILE *OutputFile)
{
                                                 // % marks beginning of location number
    if(Node!=0)                                 // # marks and of node
    {
        if(!Node->Deleted)
        {
            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 if any
        }
        SaveNode(Node->Left, OutputFile);     //save nodes in left sub-tree
        SaveNode(Node->Right, OutputFile);    //save nodes in right sub-tree
    }
}

void AVL::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.
    char chr;
    char string[20];
    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 AVL::LeftDepth()
{
    return TreeDepth(Root->Left);   //measure the left sub-tree
}

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

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


//---------- AVL.h --------------
#include <stdio.h>

#ifndef AVLH
#define AVLH
//---------------------------------------------------------------------------

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
        int Depth;
        bool Deleted;          //to mark node as deleted (lazy delete)
        TreeNode* Duplicates;    //will be used to list records that are duplicates
};


class AVL
{
    friend class avl_class;
    public:
        AVL();
        ~AVL();

        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);  //begins recursive call of InsertNode
        int InsertNode(char string[], int FilePosition, TreeNode*, TreeNode*); //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:
        void LeftRotation(TreeNode* Node);    //used to make left rotations on the avl
        void RightRotation(TreeNode* Node);   //used to make right rotations on the avl
        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