package zad1;

class RBT implements Structure{

    /* Class containing left and right child of current node and key value*/
    class Node {
        String key;
        String color="black";
        Node parent= nullNode, left = nullNode, right = nullNode;

        public Node(String key, Node parent) {
            this.key = key;
            this.parent = parent;
            this.color="black";
            left = right = null;
        }
        public Node(String key) {
            this.key = key;
        }
    }

    // Root of BST
    Node root;
    Node nullNode = new Node(null);

    // Constructor
    RBT() {
        root = nullNode;
    }

    public Node getRoot(){
        return root;
    }

    public void insert(String key) {
        char c = key.charAt(key.length()-1);
        if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')))
            key=key.substring(0,key.length()-1);
        c = key.charAt(0);
        if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')))
            key=key.substring(1);

        Node node = new Node(key);
        Node temp = root;
        if (root == nullNode) {
            root = node;
            node.color = "black";
            node.parent = nullNode;
        } else {
            node.color = "red";
            while (true) {
                if (node.key.compareTo(temp.key)<0) {
                    if (temp.left == nullNode) {
                        temp.left = node;
                        node.parent = temp;
                        break;
                    } else {
                        temp = temp.left;
                    }
                } else if (node.key.compareTo(temp.key)>=0) {
                    if (temp.right == nullNode) {
                        temp.right = node;
                        node.parent = temp;
                        break;
                    } else {
                        temp = temp.right;
                    }
                }
            }
            fixTree(node);
        }
    }

    //Takes as argument the newly inserted node
    private void fixTree(Node node) {
        while (node.parent.color == "red") {
            Node uncle = nullNode;
            if (node.parent == node.parent.parent.left) {
                uncle = node.parent.parent.right;

                if (uncle != nullNode && uncle.color == "red") {
                    node.parent.color = "black";
                    uncle.color = "black";
                    node.parent.parent.color = "red";
                    node = node.parent.parent;
                    continue;
                }
                if (node == node.parent.right) {
                    //Double rotation needed
                    node = node.parent;
                    rotateLeft(node);
                }
                node.parent.color = "black";
                node.parent.parent.color = "red";
                //if the "else if" code hasn't executed, this
                //is a case where we only need a single rotation
                rotateRight(node.parent.parent);
            } else {
                uncle = node.parent.parent.left;
                 if (uncle != nullNode && uncle.color == "red") {
                    node.parent.color = "black";
                    uncle.color = "black";
                    node.parent.parent.color = "red";
                    node = node.parent.parent;
                    continue;
                }
                if (node == node.parent.left) {
                    //Double rotation needed
                    node = node.parent;
                    rotateRight(node);
                }
                node.parent.color = "black";
                node.parent.parent.color = "red";
                //if the "else if" code hasn't executed, this
                //is a case where we only need a single rotation
                rotateLeft(node.parent.parent);
            }
        }
        root.color = "black";
    }

    void rotateLeft(Node node) {
        if (node.parent != nullNode) {
            if (node == node.parent.left) {
                node.parent.left = node.right;
            } else {
                node.parent.right = node.right;
            }
            node.right.parent = node.parent;
            node.parent = node.right;
            if (node.right.left != nullNode) {
                node.right.left.parent = node;
            }
            node.right = node.right.left;
            node.parent.left = node;
        } else {//Need to rotate root
            Node right = root.right;
            root.right = right.left;
            right.left.parent = root;
            root.parent = right;
            right.left = root;
            right.parent = nullNode;
            root = right;
        }
    }

    void rotateRight(Node node) {
        if (node.parent != nullNode) {
            if (node == node.parent.left) {
                node.parent.left = node.left;
            } else {
                node.parent.right = node.left;
            }

            node.left.parent = node.parent;
            node.parent = node.left;
            if (node.left.right != nullNode) {
                node.left.right.parent = node;
            }
            node.left = node.left.right;
            node.parent.right = node;
        } else {//Need to rotate root
            Node left = root.left;
            root.left = root.left.right;
            left.right.parent = root;
            root.parent = left;
            left.right = root;
            left.parent = nullNode;
            root = left;
        }
    }

    //usuwanie
    void transplant(Node target, Node with){
        if(target.parent == nullNode){
            root = with;
        }else if(target == target.parent.left){
            target.parent.left = with;
        }else
            target.parent.right = with;
        with.parent = target.parent;
  }

  boolean delete(String key){
      Node z;
      if((z = search(root,key))==nullNode) return false;
      Node x;
      Node y = z; // temporary reference y
      String y_original_color = y.color;

      if(z.left == nullNode){
          x = z.right;
          transplant(z, z.right);
      }else if(z.right == nullNode){
          x = z.left;
          transplant(z, z.left);
      }else{
          y = minValue(z.right);
          y_original_color = y.color;
          x = y.right;
          if(y.parent == z)
              x.parent = y;
          else{
              transplant(y, y.right);
              y.right = z.right;
              y.right.parent = y;
          }
          transplant(z, y);
          y.left = z.left;
          y.left.parent = y;
          y.color = z.color;
      }
      if(y_original_color.equals("black"))
          deleteFixup(x);
      return true;
  }

  void deleteFixup(Node x){
      while(x!=root && x.color == "black"){
          if(x == x.parent.left){
              Node w = x.parent.right;
              if(w.color == "red"){
                  w.color = "black";
                  x.parent.color = "red";
                  rotateLeft(x.parent);
                  w = x.parent.right;
              }
              if(w.left.color == "black" && w.right.color == "black"){
                  w.color = "red";
                  x = x.parent;
                  continue;
              }
              else if(w.right.color == "black"){
                  w.left.color = "black";
                  w.color = "red";
                  rotateRight(w);
                  w = x.parent.right;
              }
              if(w.right.color == "red"){
                  w.color = x.parent.color;
                  x.parent.color = "black";
                  w.right.color = "black";
                  rotateLeft(x.parent);
                  x = root;
              }
          }else{
              Node w = x.parent.left;
              if(w.color == "red"){
                  w.color = "black";
                  x.parent.color = "red";
                  rotateRight(x.parent);
                  w = x.parent.left;
              }
              if(w.right.color == "black" && w.left.color == "black"){
                  w.color = "red";
                  x = x.parent;
                  continue;
              }
              else if(w.left.color == "black"){
                  w.right.color = "black";
                  w.color = "red";
                  rotateLeft(w);
                  w = x.parent.left;
              }
              if(w.left.color == "red"){
                  w.color = x.parent.color;
                  x.parent.color = "black";
                  w.left.color = "black";
                  rotateRight(x.parent);
                  x = root;
              }
          }
      }
      x.color = "black";
  }
    //max
    public void max(Node root){
        Node n = maxValue(root);
        if(n==nullNode)
            System.out.println();
        else
            System.out.println(n.key);
    }
    public Node maxValue(Node root) {
        if(root==nullNode){
            return root;
        }
        else if(root.right==nullNode){
            return root;
        }
        else
            return maxValue(root.right);
    }
    //min
    public void min(Node root){
        Node n = minValue(root);
        if(n==nullNode)
            System.out.println();
        else
            System.out.println(n.key);
    }
    public Node minValue(Node root) {
        if(root==nullNode){
            return root;
        }
        else if(root.left==nullNode){
            return root;
        }
        else
            return minValue(root.left);
    }

    // This method mainly calls InorderRec()
    void inorder()  {
       inorderRec(root);
       System.out.print("\n");
    }

    // A utility function to do inorder traversal of BST
    void inorderRec(Node root) {
        if (root != nullNode) {
            inorderRec(root.left);
            if(root.parent==nullNode)
                System.out.print(root.key+"["+root.color+"] ");
            else
                System.out.print(root.key+"["+root.color+"] ");
            inorderRec(root.right);
        }
    }
    //szukanie
    public Node search(Node root, String key)
    {
        // Base Cases: root is null or key is present at root
        if(root==nullNode||root.key.equals(key))
            return root;

        if (key.compareTo(root.key)<0)
            return search(root.left, key);

        return search(root.right, key);
    }

    public void find(String key){
        if(search(this.getRoot(),key)==nullNode)
            System.out.println("0");
        else
            System.out.println("1");
    }
  //succesor
    public void successor(String key){
        Node n = search(this.getRoot(),key);
        if(n==nullNode)
            System.out.println();
        else{
            if(n.right==nullNode){
                Node p = n.parent;
                if(p==nullNode)
                    System.out.println();
                else if(p.left==n)
                    System.out.println(p.key);
                else if(p.parent==nullNode)
                    System.out.println();
                else
                    System.out.println(p.parent.key);
            }
            else
                min(n.right);
        }
    }
    // Driver Program to test above functions
    public static void main(String[] args) {
        RBT tree = new RBT();

        tree.insert("1S1");
        tree.insert("b");
        tree.insert("c>");
        tree.insert("dwa");
        tree.insert("AL");
        tree.insert("1A");
        tree.insert("D");

        tree.inorder();
        tree.find("dwa");
        tree.successor("D");
        tree.max(tree.getRoot());
        tree.delete("dwa");
        tree.max(tree.getRoot());
    }
}