/*
 * Andrew Shultzabarger
 * CS 4343
 * Due: December 7th (allowed by Dr. Rao)
 *
 * Red-Black Tree Implementation
 * All algorithms were taken from the book.
 *
 */

package rbt;

import java.util.Random;

enum Color { RED, BLACK }

/*
 * Node elements used for storing in the red-black tree
 *
 * Satellite data is of type integer
 */
class Node
{
    public Node left, right, p;
    public Color color;
    public int key;

    public Node(int k)
    {
        this.key = k;
        this.color = Color.BLACK;
        this.left = null;
        this.right = null;
        this.p = null;
    }
}

/*
 * Red-Black tree implementation
 *
 * Performs insert and delete for any given Node element.
 * Also performs treewalks starting from the root node.
 *
 * Satellite data comparisons are done using boolean inequality operators
 */
class Tree
{
    public Node nil;
    public Node root;

    /*
     * Tree object constructor. Initializes the sentinel nil node to refer
     * to itself.
     */
    public Tree(Node n)
    {
        this.nil = n;
        this.root = this.nil;

        this.nil.left = this.nil;
        this.nil.right = this.nil;
        this.nil.p = this.nil;
    }

    /*
     * Finds the minimum element from a given node in a tree
     */
    public Node treeMinimum(Node n)
    {
        while(n.left != this.nil)
        {
            n = n.left;
        }
        return n;
    }

    /*
     * Finds the next element from a given node in a tree
     */
    public Node treeSuccessor(Node n)
    {
        Node y = this.nil;

        if(n.right != this.nil)
        {
           return this.treeMinimum(n.right);
        }

        y = n.p;

        while(y != this.nil && n == y.right)
        {
            n = y;
            y = y.p;
        }
        return y;
    }

    /*
     * Performs a left rotation from a given node in the tree
     */
    public void leftRotate(Node x)
    {
        Node y = x.right;
        x.right = y.left;

        if(y.left != this.nil)
        {
            y.left.p = x;
        }
        y.p = x.p;

        if(x.p == this.nil)
        {
            this.root = y;
        }
        else
        {
            if(x == x.p.left)
            {
                x.p.left = y;
            }
            else
            {
                x.p.right = y;
            }
        }
        y.left = x;
        x.p = y;
    }

    /*
     * Performs a right rotation from a given node in the tree
     */
    public void rightRotate(Node x)
    {
        Node y = x.left;
        x.left = y.right;

        if(y.right != this.nil)
        {
            y.right.p = x;
        }
        y.p = x.p;

        if(x.p == this.nil)
        {
            this.root = y;
        }
        else
        {
            if(x == x.p.right)
            {
                x.p.right = y;
            }
            else
            {
                x.p.left = y;
            }
        }
        y.right = x;
        x.p = y;
    }

    /*
     * Reorders the tree using the rotation methods to preserve the red-black
     * tree properties.
     */
    public void rbInsertFixup(Node z)
    {
        Node y = this.nil;

        while(z.p.color == Color.RED)
        {
            if(z.p == z.p.p.left)
            {
                y = z.p.p.right;

                if(y.color == Color.RED)
                {
                    z.p.color = Color.BLACK;
                    y.color = Color.BLACK;
                    z.p.p.color = Color.RED;
                    z = z.p.p;
                }
                else
                {
                    if(z == z.p.right)
                    {
                        z = z.p;
                        leftRotate(z);
                    }
                    z.p.color = Color.BLACK;
                    z.p.p.color = Color.RED;
                    rightRotate(z.p.p);
                }
            }
            else
            {
                y = z.p.p.left;

                if(y.color == Color.RED)
                {
                    z.p.color = Color.BLACK;
                    y.color = Color.BLACK;
                    z.p.p.color = Color.RED;
                    z = z.p.p;
                }
                else
                {
                    if(z == z.p.left)
                    {
                        z = z.p;
                        rightRotate(z);
                    }
                    z.p.color = Color.BLACK;
                    z.p.p.color = Color.RED;
                    leftRotate(z.p.p);
                }
            }
        }
        this.root.color = Color.BLACK;
    }

    /*
     * Inserts a given node into the tree. Calls rbInsertFixup() to reorder
     * the tree to preserve the red-black tree properties
     */
    public void rbInsert(Node z)
    {
        Node y = this.nil;
        Node x = this.root;

        while(x != this.nil)
        {
            y = x;

            if(z.key < x.key)
            {
                x = x.left;
            }
            else
            {
                x = x.right;
            }
        }
        z.p = y;

        if(y == this.nil)
        {
            this.root = z;
        }
        else
        {
            if(z.key < y.key)
            {
                y.left = z;
            }
            else
            {
                y.right = z;
            }
        }

        z.left = this.nil;
        z.right = this.nil;
        z.color = Color.RED;
        rbInsertFixup(z);
    }

    /*
     * Reorders the tree using the rotation methods to preserve the red-black
     * tree properties.
     */
    public void rbDeleteFixup(Node x)
    {
        Node w = this.nil;

        while(x != this.root && x.color == Color.BLACK)
        {
            if(x == x.p.left)
            {
                w = x.p.right;

                if(w.color == Color.RED)
                {
                    w.color = Color.BLACK;
                    x.p.color = Color.RED;
                    leftRotate(x.p);
                    w = x.p.right;
                }

                if(w.left.color == Color.BLACK && w.right.color == Color.BLACK)
                {
                    w.color = Color.RED;
                    x = x.p;
                }
                else
                {
                    if(w.right.color == Color.BLACK)
                    {
                        w.left.color = Color.BLACK;
                        w.color = Color.RED;
                        rightRotate(w);
                        w = x.p.right;
                    }

                    w.color = x.p.color;
                    x.p.color = Color.BLACK;
                    w.right.color = Color.BLACK;
                    leftRotate(x.p);
                    x = this.root;
                }
            }
            else
            {
                w = x.p.left;

                if(w.color == Color.RED)
                {
                    w.color = Color.BLACK;
                    x.p.color = Color.RED;
                    rightRotate(x.p);
                    w = x.p.left;
                }

                if(w.right.color == Color.BLACK && w.left.color == Color.BLACK)
                {
                    w.color = Color.RED;
                    x = x.p;
                }
                else
                {
                    if(w.left.color == Color.BLACK)
                    {
                        w.right.color = Color.BLACK;
                        w.color = Color.RED;
                        leftRotate(w);
                        w = x.p.left;
                    }

                    w.color = x.p.color;
                    x.p.color = Color.BLACK;
                    w.left.color = Color.BLACK;
                    rightRotate(x.p);
                    x = this.root;
                }
            }
        }
        x.color = Color.BLACK;
    }

    /*
     * Deletes a specified node from the tree. Calls rbDeleteFixup() to reorder
     * the tree to preserve the red-black tree properties.
     */
    public Node rbDelete(Node z)
    {
        Node x = this.nil;
        Node y = this.nil;

        if(z.left == this.nil || z.right == this.nil)
        {
            y = z;
        }
        else
        {
            y = this.treeSuccessor(z);
        }

        if(y.left != this.nil)
        {
            x = y.left;
        }
        else
        {
            x = y.right;
        }
        x.p = y.p;

        if(y.p == this.nil)
        {
            this.root = x;
        }
        else
        {
            if(y == y.p.left)
            {
                y.p.left = x;
            }
            else
            {
                y.p.right = x;
            }
        }

        if(y != z)
        {
            z.key = y.key;
        }

        if(y.color == Color.BLACK)
        {
            rbDeleteFixup(x);
        }
        return y;
    }

    public void inorderWalk(Node n)
    {
        boolean printParen;

        if(n != this.nil)
        {
            printParen = n.left != this.nil || n.right != this.nil;

            if(printParen) { System.out.print("( "); }

            this.inorderWalk(n.left);
            System.out.print(n.key + " " + n.color + ", ");
            this.inorderWalk(n.right);

            if(printParen) { System.out.print(") "); }
        }
    }

    public void preorderWalk(Node n)
    {
        if(n != this.nil)
        {
            System.out.print(n.key + " " + n.color + ", ");
            this.preorderWalk(n.left);
            this.preorderWalk(n.right);
        }
    }

    public void postorderWalk(Node n)
    {
        if(n != this.nil)
        {
            this.postorderWalk(n.left);
            this.postorderWalk(n.right);
            System.out.print(n.key + " " + n.color + ", ");
        }
    }
}

public class Main
{
    private static final int NUM_KEYS = 40;
    private static final Random rand = new Random();

    /*
     * Method for generating a list of random integers
     */
    private static final int[] getNewKeySet(int numKeys)
    {
        int keySet[] = new int[numKeys];

        for(int i = 0; i < numKeys; ++i)
        {
            keySet[i] = Main.rand.nextInt(numKeys * numKeys);
        }
        return keySet;
    }

    /*
     * Main method
     */
    public static void main(String[] args)
    {
        int keySet[] = getNewKeySet(Main.NUM_KEYS);
        Node dList[] = new Node[Main.NUM_KEYS];
        Node curr;
        int index;

        Tree tree = new Tree(new Node(-1));

        /*
         * Insert the initial 30 keys, save a copy of the generated nodes
         * in the dList[] array. This is used to reference the exact objects
         * for deletion.
         */
        System.out.println("\n\n---------------------------------------\n\n");
        System.out.println("[!] INITIAL 30 NODE INSERTIONS");
        System.out.println("\n\n---------------------------------------\n\n");

        for(int i = 0; i < 30; ++i)
        {
            curr = new Node(keySet[i]);
            tree.rbInsert(curr);
            dList[i] = curr;
        }

        /*
         * Print the tree using all three tree-walk algorithms
         */
        System.out.println("\n\n---------------------------------------\n\n");
        System.out.println("[!] INITIAL TREE TRAVERSALS");
        System.out.println("\n\n---------------------------------------\n\n");

        System.out.println("Inorder");
        tree.inorderWalk(tree.root);
        System.out.println();

        System.out.println("\nPreorder");
        tree.preorderWalk(tree.root);
        System.out.println();

        System.out.println("\nPostorder");
        tree.postorderWalk(tree.root);
        System.out.println();

        /*
         * Delete from the tree 5 keys slected at random.
         */
        System.out.println("\n\n---------------------------------------\n\n");
        System.out.println("[!] 5 RANDOM NODE DELETIONS");
        System.out.println("\n\n---------------------------------------\n\n");

        index = rand.nextInt(25);
        for(int i = index, count = 0; count < 5; ++i, ++count)
        {
            System.out.println("\nDeleting key " + dList[i].key);
            tree.rbDelete(dList[i]);
            tree.inorderWalk(tree.root);
            System.out.println();
        }

        /*
         * Insert the remaining 10 keys from the keyList[]
         */
        System.out.println("\n\n---------------------------------------\n\n");
        System.out.println("[!] REMAINING 10 NODE INSERTIONS");
        System.out.println("\n\n---------------------------------------\n\n");

        for(int i = 30; i < Main.NUM_KEYS; ++i)
        {
            curr = new Node(keySet[i]);
            tree.rbInsert(curr);
        }

        /*
         * Print the resulting tree using inorder tree traversal
         */
        System.out.println("\n\n---------------------------------------\n\n");
        System.out.println("[!] RESULTING TREE TRAVERSAL");
        System.out.println("\n\n---------------------------------------\n\n");

        System.out.println("Inorder");
        tree.inorderWalk(tree.root);
        System.out.println();
    }
}