public class BacktrackingBST implements Backtrack, ADTSet<BacktrackingBST.Node> {
    private Stack stack;
    private Stack redoStack;
    BacktrackingBST.Node root = null;

    // Do not change the constructor's signature
    public BacktrackingBST(Stack stack, Stack redoStack) {
        this.stack = stack;
        this.redoStack = redoStack;
    }

    public Node getRoot() {
        return root;
    }

    public Node search(int x) {
        Node current = getRoot();
        while (current!=null){
            if (current.getKey()==x) return current;
            else if (current.getKey()>x){
                current=current.left;
            }
            else {
                current = current.right;
            }

        }
        return null;

    }

    public void insert(BacktrackingBST.Node z) {
        Node current = root;
        Node parent = null;
        while (current!=null){
            parent = current;
            if (current.getKey()>z.getKey()){
                current=current.left;
            }
            else {
                current = current.right;
            }
        }
        if (parent == null){
            root = z;
            z.setParent(null);
        }
        else if (parent.getKey()>z.getKey()){
            parent.left =z ;
            z.setParent(parent);
        }
        else {
            parent.right = z;
            z.setParent(parent);
        }
        stack.push(new BacktrackAction(true,z,z,-1));

    }

    public void delete(Node x) {
        Node xCopy = new Node(x); // create a copy of x for backtracking.
        int id = x.sideCheck(); // check whether x is a right child, left child, or the root.
        int deleteCase; // will be used for backtracking
        if (x.right == null & x.left == null){ // case 1: x is a leaf
            deleteCase=1;
            stack.push(new BacktrackAction(false,xCopy,x,deleteCase)); // push backtrack action into the stack
            if (id==0){
                root = null;
            }
            else if (id==1){
                x.getParent().right=null;
            }
            else {
                x.getParent().left = null;
            }
        }
        else if (x.right == null | x.left == null){    // case 2 : x has only one child.
            deleteCase = 2;
            stack.push(new BacktrackAction(false,xCopy,x,deleteCase)); // push backtrack action into the stack
            if (x.right == null){ // following actions in this code block will delete x and make his child - his parent's child, and his child's parent - his parent.
                x.left.setParent(x.getParent());
                if (id==0){
                    root = x.left;
                }
                else if (id == 1){
                    x.getParent().right = x.left;
                }
                else x.getParent().left = x.left;
            }
            else { // following actions in this code block will delete x and make his child - his parent's child, and his child's parent - his parent.
                x.right.setParent(x.getParent());
                if (id==0){
                    root = x.right;
                }
                else if (id == 1){
                    x.getParent().right = x.right;
                }
                else x.getParent().left = x.right;
            }
        }
        else { // following actions in this code block will delete the successor of x and replace x with it.
            deleteCase = 3;
            Node suc = successor(x);
            Node replace = new Node(suc);
            delete(suc); // delete the successor of x because x will be replaced with it.
            stack.push(new BacktrackAction(false,xCopy,x,deleteCase));// push backtrack action into the stack
            x.replace(replace);
        }

    }

    public Node minimum() {
        Node output = getRoot();
        if (output!=null){
            while (output.left != null){
                output = output.left;
            }
        }
        return output;
    }

    public Node maximum() {
        Node output = getRoot();
        if (output!=null){
            while (output.right != null){
                output = output.right;
            }
        }

        return output;
    }

    public Node successor(Node x) {
        if (x.right!=null){
            Node output = x.right;
            while (output.left!=null){
                output = output.left;
            }
            return output;
        }
        else {
            Node output = x;
            while (output.getParent().right == output){
                output=output.getParent();
            }
            return output.getParent();
        }
    }

    public Node predecessor(Node x) {
        Node output = x.left;
        if (output!=null){
            while (output.right!=null){
                output = output.right;
            }
        }
        return output;
    }

    @Override
    public void backtrack() {
        BacktrackAction bk = (BacktrackAction)stack.pop(); // check what the last action was.
        if (bk.isInsert()){ // if last action was an insert, just delete the inserted element.
            delete(bk.getPointer());
            stack.pop(); // get rid of the redundant delete action that was pushed into the stack while deleting.
        }
        else {
            int id = bk.getNode().sideCheck();
            if (bk.getDeleteCase()==1){
                if (id==0){
                    root = bk.getNode();
                }
                else if (id==1){
                    bk.getNode().getParent().right=bk.getNode();
                }
                else {
                    bk.getNode().getParent().left=bk.getNode();
                }
            }
            else if (bk.getDeleteCase()==2){
                if (id==0){
                    root.setParent(bk.getNode());
                    root = bk.getNode();
                }
                else  if (id == 1){
                    bk.getNode().getParent().right=bk.getNode();
//                    bk.getNode().getParent().right.setParent(bk.getNode());
                    if (bk.getNode().right!=null){
                        bk.getNode().right.setParent(bk.getNode());
                    }
                    if (bk.getNode().left!=null){
                        bk.getNode().left.setParent(bk.getNode());
                    }


                }
                else {
                    bk.getNode().getParent().left=bk.getNode();
                    if (bk.getNode().right!=null){
                        bk.getNode().right.setParent(bk.getNode());
                    }
                    if (bk.getNode().left!=null){
                        bk.getNode().left.setParent(bk.getNode());
                    }
                }

            }
            else {
                if (id==0){
                    root.replace(bk.getNode());
                    backtrack();

                }
                else if (id==1){
                    bk.getNode().getParent().right.replace(bk.getNode());
                    backtrack();

                }
                else{
                    bk.getNode().getParent().left.replace(bk.getNode());
                    backtrack();

                }
            }
        }
    }

    @Override
    public void retrack() {

    }

    public void printPreOrder(){
        printTree(getRoot());
    }
    public void printTree (BacktrackingBST.Node node) {
        System.out.print(node.getKey() + " ");
        if (node.left != null)
            printTree(node.left);
        if (node.right != null)
            printTree(node.right);
    }


    @Override
    public void print() {
        printPreOrder();
    }

    public static class Node{
        //These fields are public for grading purposes. By coding conventions and best practice they should be private.
        public BacktrackingBST.Node left;
        public BacktrackingBST.Node right;

        private BacktrackingBST.Node parent;
        private int key;
        private Object value;

        public Node(int key, Object value) {
            this.key = key;
            this.value = value;
        }
        public Node(Node toCopy){
            this.left = toCopy.left;
            this.right = toCopy.right;
            this.parent = toCopy.parent;
            this.key = toCopy.key;
            this.value = toCopy.value;

        }

        public Node getParent() {
            return parent;
        }

        public void setParent(Node parent) {
            this.parent = parent;
        }

        public int getKey() {
            return key;
        }

        public Object getValue() {
            return value;
        }
        public void replace(Node replace){
            this.key = replace.getKey();
            this.value = replace.value;
        }
        public int sideCheck(){
            if (this.getParent()==null) return 0;
            if (this.getKey()>this.getParent().getKey())return 1; // right child
            else return -1; //left child
        }

        @Override
        public String toString() {
            return ""+key ;
        }
    }

    private static class BacktrackAction{
        private boolean isInsert;
        private Node node;
        private Node pointer;
        private int deleteCase;

        public BacktrackAction(boolean isInsert, Node node , Node pointer, int deleteCase) {
            this.isInsert = isInsert;
            this.node = node;
            this.pointer = pointer;
            this.deleteCase = deleteCase;
        }

        public boolean isInsert() {
            return isInsert;
        }

        public Node getNode() {
            return node;
        }

        public int getDeleteCase() {
            return deleteCase;
        }

        public Node getPointer() {
            return pointer;
        }

        public void setPointer(Node pointer) {
            this.pointer = pointer;
        }
    }
    public void treeFormPrint(){
        if (root != null) treeFormPrint(root, "");
        else System.out.println("Empty tree");
    }

    // TODO remove
    private void treeFormPrint(Node node, String acc){
        String signSpace = acc + "            ";
        if (node.right != null) {
            treeFormPrint(node.right, acc+"               ");
            if (node.right.parent == node)
                System.out.println(signSpace + "/");
            else System.out.println(signSpace + "$");
        }
        System.out.println(acc + "| key: " + node.key);
        System.out.println(acc + "| par: " + node.parent);
        if (node.left != null) {
            if (node.left.parent == node)
                System.out.println(signSpace + "\\");
            else System.out.println(signSpace + "$");
            treeFormPrint(node.left, acc+"               ");
        }
    }

}