public class RedBlackTree <E extends Comparable<E>>{

    private Node<E> root;
    private static final boolean RED = false;
    private static final boolean BLACK = true;


    public RedBlackTree() {

    }

    public boolean insert(E element) throws NullPointerException{

        Node<E> current = root;
        Node<E> newnode = new Node<E>(element);

        //iterate through loop to find a spot for the new node. break loop if we reach a null child.
        while(current != null) {

            //step right
            if(current.element.compareTo(element) < 0) {
                if(current.rightChild == null)
                    break;

                current = current.rightChild;

            //step left
            }else if(current.element.compareTo(element) > 0) {
                if(current.leftChild == null)
                    break;

                current = current.leftChild;

            //equals current element
            }else {
                return false;

            }
        }

        //link newnode to parent node.
        newnode.parent = current;

        //if current is null tree is empty, insert first node
        if(current == null) {
            root = newnode;
            root.color = BLACK;

        }else {
            if(current.element.compareTo(element) < 0) {
                current.rightChild = newnode;
                newnode.parent = current;
                insertUtil(newnode);

            }else if(current.element.compareTo(element) > 0) {
                current.leftChild = newnode;
                newnode.parent = current;
                insertUtil(newnode);

            }
        }



        return true;
    }


    private void insertUtil(Node<E> current) {


        while(current.parent.color == RED) {

            Node<E> parent = current.parent, grandparent = current.parent.parent, uncle;

            if(parent != null && grandparent != null) {


                if(current == parent.leftChild) {

                    //left-left case
                    if(parent == grandparent.leftChild) {

                        uncle = grandparent.rightChild;

                        //ll case black uncle
                        if(uncle == null || uncle.color == BLACK) {
                            System.out.println("llbu");
                            rightRotate(current.parent.parent);
                            current.parent.rightChild.color = RED;

                        //ll case red uncle
                        }else {
                            System.out.println("llru");
                            recolor(current.parent);

                        }

                    //right-left case
                    }else if(parent == grandparent.rightChild) {

                        uncle = grandparent.leftChild;

                        //rl case black uncle
                        if(uncle == null || uncle.color == BLACK) {
                            System.out.println("rlbu");
                            rightRotate(current.parent);
                            leftRotate(current.parent);
                        //rl case red uncle
                        }else {
                            System.out.println("rlru");
                            recolor(current.parent);

                        }
                    }


                }else if(current == parent.rightChild) {

                    //right-right case
                    if(parent == grandparent.rightChild) {

                        uncle = grandparent.leftChild;
                        //rr case black uncle
                        if(uncle == null || uncle.color == BLACK) {
                            System.out.println("rrbu");
                            leftRotate(current.parent.parent);
                            current.parent.leftChild.color = RED;

                        //rr case red uncle
                        }else {
                            System.out.println("rrru");
                            recolor(current.parent);

                        }

                    //left-right case
                    }else if(parent == grandparent.leftChild) {

                        uncle = grandparent.rightChild;

                        //lr case black uncle
                        if(uncle == null || uncle.color == BLACK) {

                            System.out.println("lrbu");

                            leftRotate(current.parent);
                            rightRotate(current.parent);


                        //lr case red uncle
                        }else {
                            System.out.println("lrru");

                            recolor(current.parent);

                        }
                    }
                }

                root.color = BLACK;

                //handle exception cases while trying to step to the next node
                try {
                    current = current.parent.parent;

                    if(current == root || current == null)
                        break;

                }catch(Exception e) {
                    break;
                }

            }

        }

    }



    private void leftRotate(Node<E> node) {
        Node<E>  rightChild = node.rightChild;
        Node<E>  rLeftChild = rightChild.leftChild;

        rightChild.leftChild = node;
        node.rightChild = rLeftChild;

        if(rLeftChild != null)
            rLeftChild.parent = node;

        //case where node was a subtree
        if(node.parent != null) {
            node.parent.leftChild = rightChild;
            node.parent.color = RED;
        }
        //case where node was the root
        else
            root = rightChild;

        rightChild.color = BLACK;

        rightChild.parent = node.parent;
        node.parent = rightChild;




    }

    private void rightRotate(Node<E> node) {

        Node<E>  leftChild = node.leftChild;
        Node<E>  lRightChild = leftChild.rightChild;

        leftChild.rightChild = node;
        node.leftChild = lRightChild;

        if(lRightChild != null)
            lRightChild.parent = node;

        //case where node was a subtree
        if(node.parent != null) {
            node.parent.rightChild = leftChild;
            node.parent.color = RED;
        }
        //case where node was the root
        else
            root = leftChild;


        leftChild.color = BLACK;

        leftChild.parent = node.parent;
        node.parent = leftChild;


    }

    private void recolor(Node<E> node) {
        node.color = BLACK;

        if(node == node.parent.rightChild) {
            if(node.parent.leftChild != null)
                node.parent.leftChild.color = BLACK;

        }else if(node == node.parent.leftChild) {
            if(node.parent.rightChild != null)
                node.parent.rightChild.color = BLACK;
        }

        if(node.parent != root)
            node.parent.color = RED;
    }

    public boolean contains(E object) {
        return true;
    }

    public String toString() {
        return toString(root);
    }

    private String toString(Node current) {
        String s = "";

        if(current == null)
            return "";

        if(current.color == RED) {
            s += "*" + current.element + " ";

        }else {
            s += current.element + " ";

        }

        if(current.leftChild != null) {
            s += toString(current.leftChild);

        }

        if(current.rightChild != null) {
            s += toString(current.rightChild);

        }

        return s;
    }

    private static class Node <E extends Comparable<E>>{
        private E element;
        private Node leftChild;
        private Node rightChild;
        private Node parent;
        private boolean color;

        public Node(){
            element = null;
            leftChild = null;
            rightChild = null;
            parent = null;
            color = RED;
        }

        public Node(E element) {
            this.element = element;
            leftChild = null;
            rightChild = null;
            parent = null;
            color = RED;
        }

    }
}