/*
 * Red Black Tree for CSC 3102 Portfolio
 */

/*
 * --REQUIRED METHODS-- (Restructuring)
 * TreeNode Restructure(TreeNode x)
 * void Rotate(TreeNode x) 
 * 
 * --REQUIRED METHODS-- (Red-Black Tree)
 * void Add(int val) 
 * int CheckColor(int val)
 * int BDepth(int val) 
 * 
 * void Remove(int val)
 */

namespace RedBlackTree
{
    class TreeNode
    {
        public int data;
        public char color;
        public TreeNode? p, rChild, lChild;

        public TreeNode()
        {
            data = 0;
            color = default;
            p = null;
            rChild = null;
            lChild = null;         
        }

        public TreeNode(int data)
        {
            this.data = data;
            color = 'R';
            p = null;
            rChild = null;
            lChild = null;
        }
    }

    class RedBlackTree
    {
        public TreeNode? root;

        /*
         * Basic constructor for the Red-Black Tree
         */
        public RedBlackTree()
        {
            root = null;
        }

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

            Restructure(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 (root == null)
            {
                return null;
            }
            TreeNode v = root;
            while (v.data != value) //find the node that value is at
            {
                if (value < v.data)
                {
                    if (v.lChild == null)
                    {
                        return null;
                    }
                    else
                    {
                        v = v.lChild;
                    }                   
                }
                else //(value > v.data)
                {
                    if (v.rChild == null)
                    {
                        return null;
                    }
                    else
                    {
                        v = v.rChild;
                    }                 
                }
            } //end of while loop

            TreeNode u = Replace(v);
            bool doubleBlack = ((u == null || u.color == 'B') && (v.color == 'B'));
            TreeNode tempP = v.p;

            if (u == null)
            {
                if (v == root)
                {
                    root = null;
                }
                else
                {
                    if (doubleBlack)
                    {
                        DoubleBlack(v);
                    }
                    else
                    {
                        if (v.p.lChild == v && v.p.rChild != null)
                        {
                            v.p.rChild.color = 'R';
                        }
                        else if (v.p.rChild == v && v.p.lChild != null)
                        {
                            v.p.lChild.color = 'R';
                        }
                    }
                    if (v.p.lChild == v)
                    {
                        v.p.lChild = null;
                    }
                    else
                    {
                        v.p.rChild = null;
                    }
                }
                return value;
            }
            
            if (v.lChild == null || v.rChild == null)
            {
                if (v == root)
                {
                    root = u;
                    u.p = v.p; ;
                    u.rChild = v.rChild;
                    u.lChild = v.lChild;
                    v.p = v.rChild = v.lChild = null;
                    Remove(u.data);
                }
                else
                {
                    if (v.p.lChild == v)
                    {
                        v.p.lChild = u;
                    }
                    else
                    {
                        v.p.rChild = u;
                    }
                    u.p = v.p;
                    if (doubleBlack)
                    {
                        DoubleBlack(u);
                    }
                    else
                    {
                        u.color = 'B';
                    }
                }
                return value;
            }

            //2 children
            u.p = v.p;
            u.lChild = v.lChild;
            u.rChild = v.rChild;
            v.p = v.lChild = v.rChild = null;
            Remove(u.data);

            return value;
        }

        /*
         * Fixes Double Black Condition
         */
        void DoubleBlack(TreeNode x)
        {
            if (x == root)
            {
                x.color = 'B';
                return;
            }

            TreeNode? s; //sibling
            if ( x.p.lChild == x) //x is parent's left child, so s is parent's right child
            {
                s = x.p.rChild;
            }
            else //(x.p.rChild == x), x is parent's right child, so s is parent's left child
            {
                s = x.p.lChild;
            }

            if (s == null)
            {
                DoubleBlack(x.p);
            }
            else
            {
                if (s.color == 'R')
                {
                    x.p.color = 'R';
                    s.color = 'B';
                    if (x.p.lChild == x) //sibling is on the right
                    {
                        if (s.rChild == null)
                        {
                            var temp = new TreeNode();
                            s.rChild = temp;
                        }
                        Rotate(s.rChild);
                        s.rChild = null;
                    }
                    else //x.p.rChild == x, sibling is on the left
                    {
                        if (s.lChild == null)
                        {
                            var temp = new TreeNode();
                            s.lChild = temp;
                        }
                        Rotate(s.lChild);
                        s.lChild = null;
                    }
                    DoubleBlack(x);
                }
                else //s.color == 'B'
                {
                    if (s.rChild != null && s.rChild.color == 'R' || s.lChild != null && s.lChild.color == 'R')
                    {
                        if (s.lChild != null && s.lChild.color == 'R')
                        {
                            if (x.p.rChild == x) //sibling is on left
                            {
                                s.lChild.color = s.color;
                                s.color = x.p.color;
                                Rotate(s.lChild);
                            }
                            else //sibling is on right
                            {
                                s.lChild.color = s.color;
                                DoubleRotate(s.lChild);
                            }
                        }
                        else
                        {
                            if (x.p.rChild == x) //sibling is on left
                            {
                                s.rChild.color = s.color;
                                DoubleRotate(s.rChild);
                            }
                            else //sibling is on right
                            {
                                s.rChild.color = s.color;
                                s.color = s.p.color;
                                Rotate(s.rChild);
                            }
                        }
                        x.p.color = 'B';
                    }
                    else //both children are black
                    {
                        s.color = 'R';
                        if (x.p.color == 'B')
                        {
                            DoubleBlack(x.p);
                        }
                        else
                        {
                            x.p.color = 'B';
                        }
                    }
                }
            }
        }

        /*
         * Returns the right first, then left most node as the succcessor
         */
        TreeNode Successor(TreeNode x)
        {
            TreeNode node = x;
            node = node.rChild;
            while (node.lChild != null)
            {
                node = node.lChild;
            }
            return node;
        }

        TreeNode? Replace(TreeNode x)
        {
            if (x.rChild != null && x.lChild != null)
            {
                return Successor(x);
            }
            else if(x.rChild == null && x.lChild == null)
            {
                return null;
            }
            else if (x.rChild == null && x.lChild != null)
            {
                return x.lChild;
            }
            else // (x.lChild == null && x.rChild != null) 
            {
                return x.rChild;
            }
        }
        /*
         * Checks the color of the node with the specified value
         * Returns -1 if value DNE, 0 if red, 1 if black, 2 if double black
         */
        int CheckColor(int val)
        {
            var node = root;
            while (node != null)
            {
                if (node.data == val)
                {
                    if (node.color == 'B')
                    {
                        return 1;
                    }
                    else if (node.color == 'R')
                    {
                        return 0;
                    }
                    else //(node.color == 'D') 
                    {
                        return 2;
                    }
                }
                else if (val < node.data)
                {
                    node = node.lChild;
                }
                else //(val > node.data)
                {
                    node = node.rChild;
                }
            } //end of while loop
            return -1;
        }


        /*
         * Searches for specified value in tree, and returns number of black nodes 
         */
        int BDepth(int val)
        {
            if (!Has(val))
            {
                return -1;
            }
            return Bdepth(root, val);
        }

        /*
         * Helper function that uses recursion to find the number of black nodes that are ancestors to the specified value
         */
        int Bdepth(TreeNode node, int val)
        {
            if (val < node.data)
            {
                if (node.color == 'B')
                {
                    return 1 + Bdepth(node.lChild, val);
                }
                else
                {
                    return Bdepth(node.lChild, val);
                }
            }
            else if (val > node.data)
            {
                if (node.color == 'B')
                {
                    return 1 + Bdepth(node.rChild, val);
                }
                else
                {
                    return Bdepth(node.rChild, val);
                }
            }
            else
            {
                if (node.color == 'B')
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
        }

        /*
         * Checks the tree to see if it has the value
         */ 
        bool Has(int val)
        {
            var node = root;
            while (node != null)
            {
                if (val == node.data)
                {
                    return true;
                }
                else if (val < node.data)
                {
                    node = node.lChild;
                }
                else //(val > node.data)
                {
                    node = node.rChild;
                }
            }
            return false;
        }


        /*
         * Notices the node that broke a condition, and corrects it
         */
        TreeNode Restructure(TreeNode x)
        {
            if (root.color == 'R') //the root is red
            {
                root.color = 'B';
            }

            while (x != root && x != null && x.color == 'R' && x.p.color == 'R')
            {
                if (x.p.p != null && x.p == x.p.p.lChild)
                {
                    var unc = x.p.p.rChild; //x's uncle
                    if (unc != null && unc.color == 'R')
                    {
                        unc.color = 'B'; //change uncles color
                        x.p.color = 'B'; //change parent's color
                        x.p.p.color = 'R'; //change grandparent's color

                        x = x.p;
                    }
                    else
                    {
                        if (x == x.p.lChild) //line condition
                        {
                            Rotate(x);
                            x.p.color = 'R';
                            x.color = 'B';
                            if (x.p.rChild != null)
                            {
                                x.p.rChild.color = 'B';
                            }
                            
                            x = x.p;
                        }
                        else //zigzag condition
                        {
                            DoubleRotate(x);
                            x.color = 'R';
                            if (x.rChild != null)
                            {
                                x.rChild.color = 'B';
                            }
                            if (x.lChild != null)
                            {
                                x.lChild.color = 'B';
                            }
                        }
                    }
                }
                else if (x.p.p != null && x.p == x.p.p.rChild)
                {
                    var unc = x.p.p.lChild;
                    if (unc != null && unc.color == 'R')
                    {
                        unc.color = 'B';
                        x.p.color = 'B';
                        x.p.p.color = 'R';

                        x = x.p;
                    }
                    else
                    {
                        if (x.p.rChild == x) //line condition
                        {
                            Rotate(x);
                            x.p.color = 'R';
                            x.color = 'B';
                            if (x.p.lChild != null)
                            {
                                x.p.lChild.color = 'B';
                            }

                            x = x.p;
                        }
                        else
                        {
                            DoubleRotate(x);
                            x.color = 'R';
                            if (x.rChild != null)
                            {
                                x.rChild.color = 'B';
                            }
                            if (x.lChild != null)
                            {
                                x.lChild.color = 'B';
                            }
                        }
                    }
                }
            }
            root.color = 'B';
            return x;
        }

        /*
         * Rotates a node when it breaks a condition
         * @x - the node that is at the bottom of the rotation
         */
        public void Rotate(TreeNode x)
        {
            if (x.p.lChild == x) //rotate towards the right
            {
                if (x.p.p == root)
                {
                    var y = x.p;
                    var z = root;
                    var newLChild = y.rChild;

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

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

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

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


                    z.p = 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.p = z;
                    }

                }
            }
            else //(x.p.rChild == x), rotate towards the left
            {
                if (x.p.p == root)
                {
                    var y = x.p;
                    var z = root;
                    var newRChild = y.lChild;

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

                    z.p = 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.p = z;
                    }

                }
                else
                {
                    var y = x.p;
                    var z = y.p;
                    var newRChild = y.lChild;

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

                    z.p = 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.p = z;
                    }

                }
            }
        }

        /*
         * Rotates around x, when the three nodes out of balance are in a zigzag
         */
        public void DoubleRotate(TreeNode x)
        {
            if (x.p.lChild == x) //Right-Left rotation
            {
                if (x.p.p == root)
                {
                    var y = x.p;
                    var z = root;
                    var xRChild = x.rChild;
                    var xLChild = x.lChild;

                    root = x;
                    x.p = null;

                    x.lChild = z;
                    z.p = x;

                    x.rChild = y;
                    y.p = x;

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

                    y.lChild = xRChild;
                    if (xRChild != null)
                    {
                        xRChild.p = y;
                    }

                    x.color = 'B';
                    y.color = 'R';
                    z.color = 'R';
                }
                else
                {
                    var y = x.p;
                    var z = y.p;
                    var xLChild = x.lChild;
                    var xRChild = x.rChild;

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

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

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

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

                    y.lChild = xRChild;
                    if (xRChild != null)
                    {
                        xRChild.p = y;
                    }

                    x.color = 'B';
                    y.color = 'R';
                    z.color = 'R';

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

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

                    x.lChild = y;
                    y.p = x;

                    x.rChild = z;
                    z.p = x;

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

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

                    x.color = 'B';
                    y.color = 'R';
                    z.color = 'R';

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

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

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

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

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

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

                    x.color = 'B';
                    y.color = 'R';
                    z.color = 'R';
                }
            }
        }   
        

        /*
         * Calulates the black node height difference
         */
        int BNodeDiff(TreeNode node)
        {
            return BNodeHeight(node.lChild) - BNodeHeight(node.rChild);
        }


        /*
         * Does the calculation for the BNodeDiff(TreeNode node) function
         */
        int BNodeHeight(TreeNode node)
        {
            if (node == null)
            {
                return 1;
            }
            else if (node.color == 'B')
            {
                return 1 + Math.Max(BNodeHeight(node.lChild), BNodeHeight(node.rChild));
            }
            else
            {
                return Math.Max(BNodeHeight(node.lChild), BNodeHeight(node.rChild));
            }
        }


        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 + "(" + node.color + ") ");
            if (node.rChild != null)
            {
                Print(node.rChild);
            }
        }
    }
}