///////////////////////////////////////////
///
/// Title: BSTRotation
/// Author: Evan Gaul
/// Email: eagaul@wisc.edu
/// Date: 9/17/25
/// Assignment: P102.BSTRotation
/// Course: CS400 Lec004 Fall 2025
/// Professor: Ashley Samuelson
///////////////////////////////////////////
///
/// Assistance: None
///
///////////////////////////////////////////

/**
 * Implementation of a rotation on a binary search tree
 * @param <T>
 */
public class BSTRotation<T extends Comparable<T>> extends BinarySearchTree<T> {
    protected void rotate(BinaryNode<T> child, BinaryNode<T> parent)
            throws NullPointerException, IllegalArgumentException {
        if (child == null || parent == null) {
            throw new NullPointerException("child or parent is null!");
        }

        if (child == parent.getLeft()) {
            // Right Rotation, child is left of parent

            // detach childs right subtree and attach as parents left
            parent.setLeft(child.getRight());
            if (child.getRight() != null) {
                child.getRight().setParent(parent);
            }

            // link parent as childs right
            child.setRight(parent);

            // update grandparent link
            BinaryNode<T> grandparent = parent.getParent();
            child.setParent(grandparent);
            parent.setParent(child);

            if (grandparent == null) {
                root = child; // parent was root
            } else if (grandparent.getLeft() == parent) {
                grandparent.setLeft(child);
            } else {
                grandparent.setRight(child);
            }
        } else if (child == parent.getRight()) {
            // Left Rotation, child is right child, similar to above code

            parent.setRight(child.getLeft());
            if (child.getLeft() != null) {
                child.getLeft().setParent(parent);
            }

            child.setLeft(parent);

            BinaryNode<T> grandparent = parent.getParent();
            child.setParent(grandparent);
            parent.setParent(child);

            if (grandparent == null) {
                root = child;
            } else if (grandparent.getLeft() == parent) {
                grandparent.setLeft(child);
            } else {
                grandparent.setRight(child);
            }

        } else {
            throw new IllegalArgumentException("Child is not a child of the parent");
        }
    }

    // Test Methods!

    /**
     * First test method
     * Tests simple left and right rotations at root
     * @return true if passed, false if not
     */
    public boolean test1() {
        BSTRotation<Integer> tree = new BSTRotation<>();
        // Right rotation at root
        tree.insert(10);
        tree.insert(5); // left child of root
        tree.rotate(tree.root.getLeft(), tree.root);
        if (!(tree.root.getData() == 5 && tree.root.getRight().getData() == 10)) return false;

        // Left rotation at root
        tree.insert(15);
        tree.rotate(tree.root.getRight(), tree.root);
        return tree.root.getData() == 10 && tree.root.getLeft().getData() == 5 && tree.root.getRight().getData() == 15;
    }

    /**
     * Second test method
     * Tests rotations where child has a subtree
     * @return true if passed, false if not
     */
    public boolean test2() {
        BSTRotation<Integer> tree = new BSTRotation<>();
        tree.insert(20);
        tree.insert(10);
        tree.insert(30);
        tree.insert(5);
        tree.insert(15);
        // Tree should look something like this:
        //              20
        //            10  30
        //           5  15
        // Right rotation where child has right subtree
        tree.rotate(tree.root.getLeft().getRight(), tree.root.getLeft()); // rotate 15 and 10
        BinaryNode<Integer> left = tree.root.getLeft();
        // Tree should look something like this after rotate:
        //              20
        //            15  30
        //           10
        //          5
        return left.getData() == 15 && left.getLeft().getData() == 10 && left.getRight() == null;
    }

    /**
     * Third test method
     * Tests rotation not at route with grandparents
     * @return true if passed, false if not
     */
    public boolean test3() {
        BSTRotation<Integer> tree = new BSTRotation<>();

        // Build tree manually
        BinaryNode<Integer> n30 = new BinaryNode<>(30);
        BinaryNode<Integer> n20 = new BinaryNode<>(20);
        BinaryNode<Integer> n40 = new BinaryNode<>(40);
        BinaryNode<Integer> n35 = new BinaryNode<>(35);

        tree.root = n30;

        n30.setLeft(n20);
        n20.setParent(n30);

        n30.setRight(n40);
        n40.setParent(n30);

        n40.setLeft(n35);
        n35.setParent(n40);

        // Rotate 35 aand 40
        tree.rotate(n35, n40);

        // check tree structure
        return tree.root.getRight() == n35 &&
                n35.getParent() == n30 &&
                n35.getRight() == n40 &&
                n40.getParent() == n35 &&
                n40.getLeft() == null;
    }


    public static void main(String[] args) {
        BSTRotation<Integer> tree = new BSTRotation<>();
        System.out.println("Test1: " + tree.test1());
        System.out.println("Test2: " + tree.test2());
        System.out.println("Test3: " + tree.test3());
    }
}