/*
 * AVL Tree for CSC 3102 Portfolio
 */

/*
 * --REQUIRED METHODS-- (RESTRUCTURING)
 * TreeNode Restructure(TreeNode x)
 * void Rotate(TreeNode x)
 * --OPTIONAL METHODS--
 * void ReLink(TreeNode parent, TreeNode child, bool left)
 * 
 * --REQUIRED METHODS-- (AVL Tree)
 * bool IsBalanced(TreeNode x)
 * 
 * --METHODS I IMPLEMENTED--
 * void DoubleRotate(TreeNode x)
 * int BalanceDifference(TreeNode e)
 * void CheckTree(TreeNode node)
 * 
 * --METHODS I IMPLENETED FOR THE OG Binary Search Tree--
 * TreeNode? ReplacementNode(int value)
 * void PrintTree()
 */

namespace AVLTree_3102
{
    class TreeNode
    {
        public int data;
        public TreeNode? rChild, lChild, parent;

        TreeNode()
        {
            data = 0;
            rChild = null;
            lChild = null;
            parent = null;
        }

        public TreeNode(int data)
        {
            this.data = data;
            rChild = null;
            lChild = null;
            parent = null;
        }
    }

    class AVLTree
    {
        public TreeNode? root;

        public AVLTree()
        {
            root = null;
        }

        public void Add(int val)
        {
            if (root == null)
            {
                root = new TreeNode(val);
            }
            else
            {
                var node = root;
                while (true)
                {
                    if (val <= node.data) //move to the left 
                    {
                        if (node.lChild == null)
                        {
                            node.lChild = new TreeNode(val);
                            node.lChild.parent = node;
                            break;
                        }
                        else
                        {
                            node = node.lChild;
                        }
                    }
                    else //move to the right
                    {
                        if (node.rChild == null)
                        {
                            node.rChild = new TreeNode(val);
                            node.rChild.parent = node;
                            break;
                        }
                        else
                        {
                            node = node.rChild;
                        }
                    }
                } //end of while loop

                CheckTree(node);
            }
        }


        /*
         * removes the node that has the specified value
         * Uses ReplacementNode(int value) to remove the value from the tree
         * @value - the data of the node that is being removed
        */
        public int? Remove(int value)
        {
            if (value == root.data)
            {
                root = ReplacementNode(value);
                if (root != null)
                {
                    CheckTree(root);
                }
                return value;
            }
            else
            {
                var node = ReplacementNode(value);
                if (node != null)
                {
                    CheckTree(node);
                }
                return value;
            }    
        }


        /*
         * checks to see if a value is stored in the Binary Search Tree
         * @val - the value you are checking to see if it is in the BST
        */
        public bool Has(int val)
        {
            var node = root;
            while (true)
            {
                if (node == null)
                {
                    return false;
                }
                else if (node.data == val)
                {
                    return true;
                }
                else if (val < node.data)
                {
                    node = node.lChild;
                }
                else //(node.data > val)
                {
                    node = node.rChild;
                }
            }
        }


        //Height function that gets called
        public int Height()
        {
            if (root == null)
            {
                return 0;
            }
            else
            {
                return Height(root);
            }

        }

        //Height function that actually does the work
        private int Height(TreeNode? node)
        {
            if (node == null)
            {
                return 0;
            }
            else
            {
                return Math.Max(1 + Height(node.lChild), 1 + Height(node.rChild));
            }
        }

        /*
         * this returns the replacement node for the remove function
         * Replacement strategy is to go right first, then take the leftmost leafnode of the node that is being removed
         * @value - the value of the node that is being removed
        */
        private TreeNode? ReplacementNode(int value)
        {
            var node = root;
            while (node != null)
            {
                if (node.data == value)
                {
                    break;
                }
                else if (value < node.data)
                {
                    node = node.lChild;
                }
                else
                {
                    node = node.rChild;
                }
            }
            if (node == null)
            {
                return null;
            }

            TreeNode? replacement;
            if (node.rChild != null && node.lChild != null)
            {
                replacement = node.rChild;
                while (replacement.lChild != null)
                {
                    replacement = replacement.lChild;
                }
                if (node.rChild == replacement) //right child of the node we wanted to remove did not have any left children
                {
                    replacement.lChild = node.lChild;
                    replacement.lChild.parent = replacement;
                    replacement.parent = node.parent;
                }
                else //replacement is now the right-first, leftmost node
                {
                    if (replacement.rChild != null)
                    {
                        replacement.rChild.parent = replacement.parent;
                        replacement.parent.lChild = replacement.rChild;
                    } 
                    else //replacement.rChild == null
                    {
                        replacement.parent.lChild = null;
                    }
                    replacement.parent = node.parent;
                    replacement.lChild = node.lChild;
                    replacement.lChild.parent = replacement;
                    replacement.rChild = node.rChild;
                    replacement.rChild.parent = replacement; //now make replacement's parent's r/l child = replacement
                }
            }
            else if (node.rChild == null && node.lChild != null)
            {
                replacement = node.lChild;
                replacement.parent = node.parent;
                replacement.parent.lChild = replacement;
            }
            else if (node.rChild != null && node.lChild == null)
            {
                replacement = node.rChild;
                
                replacement.parent = node.parent; //now connect the parent to replacement
                replacement.parent.rChild = replacement;
                
            }
            else //node.lChild == null && node.rChild == null
            {
                if (node.parent.lChild == node)
                {
                    node.parent.lChild = null;
                }
                else //node.parent.rChild == node
                {
                    node.parent.rChild = null;
                }
                return null;
            }
            if (node == root)
            {

            }
            else if (node.parent.lChild == node)
            {
                replacement.parent.lChild = replacement;
            }
            else //node.parent.rChild == node
            {
                replacement.parent.rChild = replacement;
            }
            return replacement;
        }

        /*
         * Prints the binary search tree
        */
        public void PrintTree()
        {
            if (root == null)
            {
                Console.WriteLine("tree is null");
            }
            else
            {
                Console.Write("[ ");
                Print(root);
                Console.WriteLine("]");
            }
        }


        /*
         * This function traverses the binary search tree, using In Order Traversal
         * Used in the PrintTree() function
        */
        private void Print(TreeNode node)
        {
            if (node.lChild != null)
            {
                Print(node.lChild);
            }
            Console.Write(node.data + " ");
            if (node.rChild != null)
            {
                Print(node.rChild);
            }
        }



        /*
         * 
         * 
         * 
         * 
         * 
         * 
         * BEGINNING OF RESTRUCTURE and AVL FUNCTIONS
         * 
         * 
         * 
         * 
         * 
         * 
         */



        /*
         * Performs Tri-node restructure. x is the lowest of the three nodes
         */
        public TreeNode Restructure(TreeNode x)
        {
            var y = x.parent;
            var z = y.parent;

            if((z.lChild == y && y.lChild == x) ||( z.rChild == y && y.rChild == x))
            {
                Rotate(x);
            }
            else
            {
                DoubleRotate(x);
            }

            //returns whichever node is the parent of the other two
            if (x.parent == y && z.parent == y)
            {
                return y;
            }
            else if (z.parent == x && y.parent == x)
            {
                return x;
            }
            else
            {
                throw new Exception("Something went wrong in either of the restructure functions");
            }
        }

        /*
         * Rotates around x, when the three nodes out of balance are in a line
         * x is the lowest node of the three nodes
         */
        public void Rotate(TreeNode x)
        {
            if (x.parent.lChild == x) //rotate towards the right
            {
                if (x.parent.parent == root)
                {
                    var y = x.parent;
                    var z = root;
                    var newLChild = y.rChild;

                    root = y; //establish y's parent-child connections, and make it the new root
                    y.parent = null;

                    y.rChild = z; //establish z's connections
                    z.parent = y;

                    z.lChild = newLChild; //y's old right child is now z's new left child
                    if (newLChild != null)
                    {
                        newLChild.parent = z;
                    }
                    
                }
                else
                {
                    var y = x.parent;
                    var z = y.parent;
                    var newLChild = y.rChild;

                    if (z.parent.lChild == z)
                    {
                        y.parent = z.parent; //establish y's parent-child connections
                        z.parent.lChild = y;
                    }
                    else //(z.parent.rChild == z)
                    {
                        y.parent = z.parent; //establish y's parent-child connections
                        z.parent.rChild = y;
                    }
                    

                    z.parent = y; //establish z's parent-child connections
                    y.rChild = z;

                    z.lChild = newLChild; //establish y's old right child as z's new left child
                    if (newLChild != null)
                    {
                        newLChild.parent = z;
                    }
                    
                }
            }
            else //(x.parent.rChild == x), rotate towards the left
            {
                if (x.parent.parent == root)
                {
                    var y = x.parent;
                    var z = root;
                    var newRChild = y.lChild;

                    root = y; //make y the root and give it root properties
                    y.parent = null;

                    z.parent = y; //establish z's connections
                    y.lChild = z;

                    z.rChild = newRChild; //make y's old left child z's new rigtht child
                    if (newRChild != null)
                    {
                        newRChild.parent = z;
                    }
                    
                }
                else
                {
                    var y = x.parent;
                    var z = y.parent;
                    var newRChild = y.lChild;

                    if (z.parent.rChild == z)
                    {
                        y.parent = z.parent; //establish y's connections
                        z.parent.rChild = y;
                    }
                    else //(z.parent,lChild == z)
                    {
                        y.parent = z.parent; //establish y's connections
                        z.parent.lChild = y;
                    }
                    
                    z.parent = y; //establish z's connections
                    y.lChild = z;

                    z.rChild = newRChild; //y's old left child is z's new right child
                    if (newRChild != null)
                    {
                        newRChild.parent = z;
                    }
                    
                }
            }
        }
        
        /*
         * Rotates around x, when the three nodes out of balance are in a zigzag
         */
        public void DoubleRotate(TreeNode x)
        {
            if (x.parent.lChild == x) //Right-Left rotation
            {
                if (x.parent.parent == root)
                {
                    var y = x.parent;
                    var z = root;
                    var xRChild = x.rChild;
                    var xLChild = x.lChild;

                    root = x;
                    x.parent = null;

                    x.lChild = z;
                    z.parent = x;

                    x.rChild = y;
                    y.parent = x;

                    z.rChild = xLChild;
                    if (xLChild != null)
                    {
                        xLChild.parent = z;
                    }

                    y.lChild = xRChild;
                    if (xRChild != null)
                    {
                        xRChild.parent = y;
                    }
                }
                else
                {
                    var y = x.parent;
                    var z = y.parent;
                    var xLChild = x.lChild;
                    var xRChild = x.rChild;

                    if (z.parent.lChild == z) //establish x's connections
                    {
                        z.parent.lChild = x; 
                        x.parent = z.parent;
                    }
                    else //(z.parent.rChild == z)
                    {
                        z.parent.rChild = x;
                        x.parent = z.parent;
                    }

                    x.lChild = z; //establish z's connection
                    z.parent = x;

                    x.rChild = y; //establish y's connections
                    y.parent = x;

                    z.rChild = xLChild;
                    if (xLChild != null)
                    {
                        xLChild.parent = z;
                    }
                    
                    y.lChild = xRChild;
                    if (xRChild != null)
                    {
                        xRChild.parent = y;
                    }
                    
                }
            }
            else //(x.parent.rChild == x), Left-Right rotation
            {
                if (x.parent.parent == root)
                {
                    var y = x.parent;
                    var z = y.parent;
                    var xLChild = x.lChild;
                    var xRChild = x.rChild;

                    root = x; //x is the new root, and give it root properties
                    x.parent = null;

                    x.lChild = y;
                    y.parent = x;

                    x.rChild = z;
                    z.parent = x;

                    y.rChild = xLChild;
                    if (xLChild != null)
                    {
                        xLChild.parent = y;
                    }

                    z.lChild = xRChild;
                    if (xRChild != null)
                    {
                        xRChild.parent = z;
                    }

                }
                else
                {
                    var y = x.parent;
                    var z = y.parent;
                    var xLChild = x.lChild;
                    var xRChild = x.rChild;

                    if (z.parent.lChild == z) //establish x's connections
                    {
                        x.parent = z.parent;
                        z.parent.lChild = x;
                    }
                    else //(z.parent.rChild == z) 
                    {
                        x.parent = z.parent;
                        z.parent.rChild = x;
                    }

                    y.parent = x; //establish y's connections
                    x.lChild = y;

                    z.parent = x; //establish z's connections
                    x.rChild = z;

                    y.rChild = xLChild; //establish old left child's connections
                    if (xLChild != null)
                    {
                        xLChild.parent = y;
                    }

                    z.lChild = xRChild; //establish old right child's connections
                    if (xRChild != null)
                    {
                        xRChild.parent = z;
                    }
                }
            }
        }

        /*
         * if the tree is balanced, returns true. Otherwise, returns false
         */
        public bool IsBalanced(TreeNode x)
        {
            if (Math.Abs(Height(x.lChild) - Height(x.rChild)) <= 1)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        /* 
         * Returns the difference in heights of the left branch and the right branch of the specified node
         * if it returns -1, 0, or 1 the tree is balanced
         * if it returns a number <-1, it is unbalanced with the right side being taller than the left
         * if it returns a number >1, it is unbalanced with the left side being taller than the right
         */
        private int BalanceDifference(TreeNode e)
        {
            return Height(e.lChild) - Height(e.rChild);
        }

        /*
         * Goes through the tree, checking each node in a branch the heights of it's children
         * If the height is ever >1 or <-1, it calls restructure
         */
        private void CheckTree(TreeNode node)
        {
            while (node != null)
            {
                int diff = BalanceDifference(node);
                if (diff >= -1 && diff <= 1)
                {
                    node = node.parent;
                }
                else if (diff > 1)
                {
                    node = node.lChild;
                    int l = Height(node.lChild);
                    int r = Height(node.rChild);
                    if (l > r)
                    {
                        Restructure(node.lChild);
                    }
                    else //r > l
                    {
                        Restructure(node.rChild);
                    }
                }
                else if (diff < -1)
                {
                    node = node.rChild;
                    int l = Height(node.lChild);
                    int r = Height(node.rChild);
                    if (l > r)
                    {
                        Restructure(node.lChild);
                    }
                    else //r > l
                    {
                        Restructure(node.rChild);
                    }
                }
            } //end of while loop
        }
    }
}