package hw7;/* HW7
 * Due: 12 November 2017
 * Problem Header Hash Code: 253b66d5c07ac9c3474e83723d5bf028
*/

public class SplayTree extends BTreePrinter {
    Node root;

    public SplayTree() {

    }

    public SplayTree(Node root) {

        if (root.parent != null) { // To make sure the root has no parent
            if (root.key < root.parent.key) {
                root.parent.left = null;
            } else {
                root.parent.right = null;
            }
            root.parent = null;
        }
        this.root = root;
    }

    public void printTree() {
        super.printTree(root);
    }

    public Node find(int search_key) {
        splay(findWithoutSplaying(search_key));
        return root;
    }

    // This function is already complete, no need to modify
    public Node findWithoutSplaying(int search_key) {
        return find(root, search_key);
    }

    // This function is already complete, no need to modify
    private static Node find(Node node, int search_key) {
        if (search_key == node.key) {
            return node;
        } else if ((search_key < node.key) && (node.left != null)) {
            return find(node.left, search_key);
        } else if ((search_key > node.key) && (node.right != null)) {
            return find(node.right, search_key);
        } else {
            return null;
        }
    }

    // This function is already complete, no need to modify
    private Node findMin() {
        return findMin(root);
    }

    // This function is already complete, no need to modify
    private static Node findMin(Node node) {
        if (node.left == null) {
            return node;
        } else {
            return findMin(node.left);
        }
    }

    // This function is already complete, no need to modify
    public void insert(int key) {
        if (root == null) {
            root = new Node(key);
        } else {
            insert(this, root, key);
        }
    }

    // Fix this function to have splaying feature
    private static void insert(SplayTree tree, Node node, int key) {
        if (key == node.key) {
            System.out.println("Duplicated key:" + key);
        } else if (key < node.key) {//Go left
            if (node.left == null) {
                node.left = new Node(key);
                node.left.parent = node;
                tree.splay(node.left);
            } else {
                insert(tree, node.left, key);
            }
        } else { // Go right
            if (node.right == null) {
                node.right = new Node(key);
                node.right.parent = node;
                tree.splay(node.right);
            } else {
                insert(tree, node.right, key);
            }
        }
    }


    public void delete(int key) {
        // To delete a key in a splay tree, do the following steps
        // 1. splay node with the key to the root of tree1
        // 2. create another tree using the node of the right-subtree (tree2)
        // 3. Find min of the right-subtree and splay to the root
        // 4. Take left-subtree of the tree1 and hang as the left subtree of the tree2
        // 5. Reassign a new root (root of the tree2)
        splay(find(key));
        SplayTree t1 = new SplayTree(root.left);
        SplayTree t2 = new SplayTree(root.right);
        t2.splay(t2.findMin());
        t2.root.left = t1.root;
        root = t2.root;
    }

    // Use this function to call zigzig or zigzag
    public void splay(Node node) {
        if (node != null && node != root) {
            if (node.parent == root) {
                // Do something (just add one line of code)
                zig(node);
            } else {
                if (node.key < node.parent.key) {
                    if (node.parent.key < node.parent.parent.key) {
                        // Left outer case
                        // Do something (just add one line of code)
                        zigzig(node);
                    } else {
                        // Left inner case
                        // Do something (just add one line of code)
                        zigzag(node);
                    }
                } else {
                    if (node.parent.key > node.parent.parent.key) {
                        // Right outer case
                        // Do something (just add one line of code)
                        zigzig(node);
                    } else {
                        // Do something (just add one line of code)
                        zigzag(node);
                    }
                }
                // Do something (just add one line of code)
                splay(node);
            }
        }
    }

    // Use this function to call zig
    public void zigzig(Node node) { // Move two nodes up along the Outer path
        zig(node.parent);
        zig(node);

    }

    // Use this funciton to call zig
    public void zigzag(Node node) { // Move two nodes up along the Inner path
        zig(node);
        zig(node);
    }

    // This function should be called by zigzig or zigzag
    public void zig(Node node) {// Move up one step
        if (node.parent == null) {
            System.out.println("Cannot perform Zig operation on the root node");
        } else if (node.parent == root) { // If the node is a child of the root
            if (node.key < node.parent.key) {// Zig from left
                node.parent.left = node.right;
                node.right = node.parent;
                node.right.parent = node;
                root = node;
            } else { // Zig from right
                node.parent.right = node.left;
                node.left = node.parent;
                node.left.parent = node;
                root = node;
//                root.parent = null;
            }
        } else {// if the node is not a child of the root
            if (node.key < node.parent.key) {// Zig from left
                node.parent.left = node.right;
                node.right = node.parent;
                if (node.parent.parent.left == node.parent) {
                    node.parent.parent.left = node;
                } else {
                    node.parent.parent.right = node;
                }
                node.parent = node.parent.parent;
                node.right.parent = node;
            } else {
                node.parent.right = node.left;
                node.left = node.parent;
                if (node.parent.parent.left == node.parent) {
                    node.parent.parent.left = node;
                } else {
                    node.parent.parent.right = node;
                }
                node.parent = node.parent.parent;
                node.left.parent = node;
            }
        }
        if(node.left != null)
        {
            if(node.left.right != null) node.left.right.parent = node.left;
            if(node.left.left != null) node.left.left.parent = node.left;
        }
        if(node.right != null)
        {
            if(node.right.right != null) node.right.right.parent = node.right;
            if(node.right.left != null) node.right.left.parent = node.right;
        }
    }
}