import java.util.ArrayList;

enum TREETYPE {BST, AVL, SPLAY};

public class WirelessPower {
    public int DEFAULT_HEIGHT = 0;
    public int DEFAULT_ID = 0;
    public int MINID = 10000;
    public int MAXID = 99999;
    public int MINLAT = -90;
    public int MAXLAT = 90;
    public int MINLONG = -180;
    public int MAXLONG = 180;

    /** 
     * The constructor performs the required initializations. It creates an empty object. It also 
     * specifies the type of the tree. The tree can be a regular BST which does not perform any 
     * re-structuring. It can be an AVL tree which re-balances the tree after every insertion or removal. 
     * The third type is a Splay tree which splays the accessed node to the tree root.
     * @param type one of the enumerators ot TREETYPE
     */
    public WirelessPower(TREETYPE type) {
       this.m_type = type; // Initalize m_type to type of tree 
        m_root = null; // Initalzing root of the tree to null 
    }

    /**
     * @return the enumerated type of TREETYPE
     */
    TREETYPE getType() {
  
        return m_type; // returning the type of tree.
    }

    /**
     * Copy constructor for WirelessPower
     */
    public WirelessPower(WirelessPower rhs) {
        //Copying the type of tree
        m_type = rhs.m_type; 
        //Deep copy of the tree.
        m_root = copyOfTree(rhs.m_root);
    }

    /**
     * This function inserts a Customer object into the tree in the proper position. 
     * The Customer::m_id should be used as the key to traverse the WirelessPower tree 
     * and abide by BST traversal rules. The comparison operators (>, <, ==, !=) work with 
     * the int type in C++. A Customer id is a unique number in the range MINID - MAXID. 
     * We do not allow a duplicate id or an object with invalid id in the tree.
     * Note:
     * •	In the WirelessPower tree data structure every node is a Customer object which is 
     *      represented as a pointer to the Customer object. Therefore, for every insertion we 
     *      need to allocate memory and use the information of customer to initialize the new node. 
     *      Memory allocation takes place in the WirelessPower class.
     * •	If the tree type is BST, after an insertion, we should update the height for all nodes 
     *      in the insertion path.
     * •	If the tree type is AVL, after an insertion, we should update the height of each node in 
     *      the insertion path as well as check for an imbalance at each node in this path.
     * •	If the tree type is SPLAY, after and insertion, we need to splay the inserted node 
     *      and bring it to the root of the tree while the tree preserves the BST property as well as updating the node heights.
     */
    // aCustomer here is the ID..
    public void insert(Customer aCustomer) {
        // Debugging statement to see the customer being inserted
       // System.out.println("Inserting customer with ID: " + aCustomer.getID());
    
        // Check for valid range of ID
        if (aCustomer.getID() < MINID || aCustomer.getID() > MAXID) {
           // System.out.println("ID out of range, not inserting.");
            return;
        }
    
        // Check if tree is empty 
        if (isEmpty()) {
            // Create a new customer node and set it as the root since tree is empty
            m_root = new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude());
           // System.out.println("Root set to: " + m_root.getID());
            return;
        }
        // To determine which type of insertion to use / rebalance as well
        switch (getType()) {
            case BST:
                m_root = insertBST(m_root, aCustomer);
                break;
            case AVL:
                m_root = insertAVL(m_root, aCustomer);
                break;
            case SPLAY:
                m_root = insertBST(m_root, aCustomer);
                m_root = splay(m_root, aCustomer);
                break;
        }
    }

    /**
     * The clear function makes it an empty tree.
     */
    public void clear() {
       m_root = null;
    }

    /**
     * The remove function traverses the tree to find a node with the id and removes 
     * it from the tree. In the case of BST or AVL tree the remove function should also update 
     * the heights for all nodes in the removal path. If the tree type is SPLAY, the remove 
     * function does not remove the node.
     */
    public void remove(int id) {
    
        switch (getType()) {
            case BST:
                m_root = deleteRecursively(m_root, id);
                updateHeight(m_root);
                break;
            case AVL:
                m_root = deleteRecursively(m_root, id);
                updateHeight(m_root);
                break;
            case SPLAY:
                //Do nothing if SPLAY tree
                break;
        }
    }

    /**
     * This function sets the type of an existing WirelessPower object. Once the type is changed, 
     * the function should re-structure the tree according to the following rules:
     * •	If the type is changed from BST or SPLAY to AVL, the function should reconstruct the 
     *      tree as an AVL tree. In the case of reconstruction the nodes are transferred from the 
     *      old tree to the new tree. There should not be any reallocation of memory.
     * •	If the type is changed from AVL to BST or Splay, there is no need for reconstruction. 
     *      After change the tree operations will perform according to the new type.
     * •	Any change between BST and SPLAY types will not trigger a reconstruction. After 
     *      change the tree operations will perform according to the new type.
     */
    public void setType(TREETYPE type) {
        //If the new type is the same as current just return
        //Nothing to do.
        if(m_type == type) {
            return;
        }

        switch(m_type) {
            //AVL doesn't need to be reconstructed to BST or SPLAY
            case AVL:
            //Just update the variable to tree type instead.
            if (type == TREETYPE.BST || type == TREETYPE.SPLAY) {
                m_type =type; // Update the type
            }
            break;
            case BST:
                if(type == TREETYPE.AVL){
                    BstToAVL();
                    m_type = type;
                } else {
                    m_type = type;
                }
            break;
            case SPLAY:
                if(type == TREETYPE.AVL) {
                    BstToAVL();
                    m_type = type;
                }
            break;
            default:
            break;
        }
    }

    /**
     * creates an exact deep copy of the rhs.
     */
    public Customer copy(WirelessPower rhs) {
        //Create a new customer root to hold for the copy of tree
        //But first check if it's empty.
        if(rhs.m_root == null) {
            return null;
        }
        //Copying the nodes recursively.
        Customer nRoot = copyOfTree(rhs.m_root);
        return nRoot;
    }

    public String dumpTree() {
        String result = "";
        result = dump(m_root, result);
        return result;
    }

    public String dump(Customer aCustomer, String result) {
        if (aCustomer == null) {
            return result;
        }
        //System.out.print("Customer: "+aCustomer.getID()+" result: "+result);
        result += "(";
        result = dump(aCustomer.m_left, result);// first visit the left child
        result += aCustomer.m_id + ":" + aCustomer.m_height;// second visit the node itself
        result = dump(aCustomer.m_right, result);// third visit the right child
        result += ")";
        return result;
    }

    // ***********************************************************************************************
    // Used for testing - provided for you
    // ***********************************************************************************************
    public Customer getRoot() {
        return m_root;
    }
    
    public String listCustomers() {
        String result = "";
        result = list(m_root, result);
        return result.trim();
    }
    
    private String list(Customer aCustomer, String result) {
        if (aCustomer == null) {
            return result;
        }
        //System.out.println("Customer: " + aCustomer.getID() + " result: " + result);
        result = list(aCustomer.m_left, result);// first visit the left child
        // second visit the node itself
        result += aCustomer.m_id + ":" + aCustomer.getLatitude() + ":" + aCustomer.getLongitude() + "\n";
        result = list(aCustomer.m_right, result);// third visit the right child
        return result;
    }
    
    private Customer m_root;       //the root of the BST
    private TREETYPE m_type;        // the type of tree, BST, AVL or SPLAY

    // ***************************************************
    // Any private helper functions must be delared here!
    // ***************************************************

    //Function to check if tree is empty.
    private boolean isEmpty() {
        return m_root == null;
    }

    //Helper function to recursively copy a tree structure
    private Customer copyOfTree(Customer node){
        //Base case
            if(node == null) {
                return null;
            }
        //Creating a new customer with the same properties..
        Customer newCustomer = new Customer(node.getID(),node.getLatitude(),node.getLongitude());

        //Recursively copy the left and right child
        newCustomer.setLeft(copyOfTree(node.getLeft()));
        newCustomer.setRight(copyOfTree(node.getRight()));
        //Also copying the height
        newCustomer.setHeight((node.getHeight()));

        return newCustomer;
    }

    
    //Calculate balance factor.
    private int getBalance(Customer node) {
        //Base case
        if(node == null) {
            return 0;
        }
        int leftHeight = -1;
        int rightHeight = -1;
        
        //Getting height of left and right child
        //Then left - right for balance factor.
        if(node.getLeft() != null) {
            leftHeight = node.getLeft().getHeight();
        }

        if(node.getRight() != null) {
            rightHeight = node.getRight().getHeight();
        }

        return leftHeight - rightHeight;
    }
    

    //AVL Balance 
    private Customer balance(Customer node) {
        
        //Left Right Case
        if(getBalance(node) > 1 && getBalance(node.getLeft()) < 0) {
            //rotating node left
            node.setLeft(leftRotate(node.getLeft()));
            //rotate node right
            return rightRotate(node);
        }
        
        //Left-Left Case 
        if(getBalance(node) >1 && getBalance(node.getLeft()) >= 0){
            //Right rotation
            return rightRotate(node);
        }
        
        //Right - Left Case
        if(getBalance(node) <-1 && getBalance(node.getRight()) > 0) {
            // Right rotation on right child
            node.setRight(rightRotate(node.getRight()));
            //Left Rotation
            return leftRotate(node);
        }
        
        //Right - Right
        if(getBalance(node) < -1 && getBalance(node.getRight()) <= 0 ){
            //Left rotate
            return leftRotate(node);
        }
        
        return node;
    }
    
    //Perform right rotation for AVL tree.
    private Customer rightRotate (Customer y) {
        //Making x the new root of the subtree.
        Customer x = y.getLeft();
        //Storing the right child of x.
        Customer temp = x.getRight();
        
        //Rotate to ->
        //y becomes the right child of x
        x.setRight(y);
        //temp(the right child of x) becomes the left child
        //Of y
        y.setLeft(temp);
        
        //Now we update the heights.
        updateHeight(y);
        updateHeight(x);
        
        //New root
        return x;
    }
    
    //Perform left rotation for AVL tree.
    private Customer leftRotate(Customer y) {
        //Making x the new root of the subtree.
        Customer x = y.getRight();
        //Storing the left child of x
        Customer temp = x.getLeft();
        
        //Rotate to <- 
        //y become the left child of x.
        x.setLeft(y);
        //temp(the left child of x) becomes the right child
        //Of Y
        y.setRight(temp);
        
        //Update height
        updateHeight(y);
        updateHeight(x);
        
        return x;
    }

    //Rotate function for splay to the left.
    private Customer leftRotateSplay(Customer x) {
        
        // No rotation possible for these two cases 
        if(x == null) {
            return x;
        }
        
        if(x.getRight() == null) {
            return x;
        }
        //Y is the new root after totation
        Customer y = x.getRight();
        //Move the left child of y to be the right child of x 
        x.setRight(y.getLeft());
        //Rotatiing here
        y.setLeft(x);

        updateHeight(x);
        updateHeight(y);
        return y;
    }
    
    //Rotate function for splay to the right
    private Customer rightRotateSplay (Customer x ) {
        
        // No rotation possible for these two cases 
        if(x == null) {
            return x;
        }
        
        if(x.getLeft() == null) {
            return x;
        }

        //Y is the new root after rotation
        Customer y = x.getLeft();
        //Move the right child of y to be the left child of x
        x.setLeft(y.getRight());
        //Rotating here
        y.setRight(x);

        updateHeight(x);
        updateHeight(y);
        return y; 
    }

    //Updates the height of tree.
    private void updateHeight(Customer node) {
        if (node != null) {
            int leftHeight;
            int rightHeight;
            
            // Check if the left child is null
            if (node.getLeft() != null) {
                leftHeight = node.getLeft().getHeight();
            } else {
                // Default height for null
                leftHeight = -1; 
            }
            // Check if the right child is null
            if (node.getRight() != null) {
                rightHeight = node.getRight().getHeight();
            } else {
                rightHeight = -1;
            }
            
            // Update the height of the current node
            node.setHeight(1 + Math.max(leftHeight, rightHeight));
        }
    }

    //Deletes nodes from a tree recursively.
    private Customer deleteRecursively (Customer node, int id) {
        //Base case
        if(node == null) {
            return null;
        }

        //Traversing the tree
        if(id < node.getID()) {
            //Go left
            node.setLeft(deleteRecursively(node.getLeft(), id));
        } else if (id > node.getID()) {
            //Go right
            node.setRight(deleteRecursively(node.getRight(), id));
        } else {
            //We found the node here we need to delete
            if (node.getLeft() == null) {
                //No left child so return the right
                return node.getRight();
            } else if (node.getRight() == null) {
                //No right child so return the left
                return node.getLeft();
            }
            //Node with two children replacing the min from the right subtree.
            Customer successor = findMin(node.getRight());
            //Replacing ID with the successor's ID
            node.setID(successor.getID());
            //Remove the successor
            node.setRight(deleteRecursively(node.getRight(), successor.getID()));
        }

        updateHeight(node);
        return balance(node);
    }


    //Help find the mininum 
    private Customer findMin(Customer node) {
        //Go to the left most child in tree (Min)
        while(node.getLeft() != null & node.getLeft() != null) {
            node = node.getLeft();
        }
        return node;
    }

    public void BstToAVL() {
        //Creating array with size of respective tree
        Customer[] nodeArray = new Customer[getSize(m_root)];
        //Int array to help keep track of the current index
        int[] i = {0};

        //Filling array with nodes in a sorted order and then converting
        //Our Array to a AVL tree
        traverseInOrder(m_root, nodeArray, i);
        m_root = arrayToAVL(nodeArray, 0, getSize(m_root) - 1);
    }

    //Recursively build the AVL tree subtrees
    private Customer arrayToAVL(Customer[] array, int start, int end) {
        //No elements left in our tree
        if (start > end) {
            return null;
        }
        // Find the middle of array. 
        int mid = (start + end) / 2; 
        // Create a root node
        Customer node = array[mid]; 
    
        //Create the left subtree 
        node.setLeft(arrayToAVL(array, start, mid - 1));
        //Create the right subtree
        node.setRight(arrayToAVL(array, mid + 1, end));
    
        return node;
    }
    
    //Traverse tree in order (Left subtree then root, then right subtree)
    //While storing the values into our array.
    private void traverseInOrder(Customer node, Customer[] array, int[] i) {
        //If node is null no nodes left
        if (node == null ) {
            return;
        }
        //Traverse left of subtree first 
        traverseInOrder(node.getLeft(), array, i);
        // Add the current node to our array
        array[i[0]++] = node; 
        //Traverse right of subtree afterwards
        traverseInOrder(node.getRight(), array, i);
    }

    //Get the size of tree
    private int getSize (Customer node) {
        //Base case
        //We reached the end of a branch (leaf node's child)
        if (node == null ) {
            return 0;
        }
        //Recursively call 
        return 1 + getSize(node.getLeft()) + getSize(node.getRight());
    }


    //Helper function to insert a BST Tree.
    private Customer insertBST (Customer node, Customer aCustomer) {
        //Base case 
        if (node == null) {
            return new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude());
        }

        //If key already in the tree return the node.
        //No Duplicates.
        if(node.getID() == aCustomer.getID()) {
            return node;
        }
        
        //Down the tree..
        if(aCustomer.getID() < node.getID()) {
            node.setLeft(insertBST(node.getLeft(), aCustomer));
        } else {
            node.setRight(insertBST(node.getRight(), aCustomer));
        }

        //Update the height of the ancestor node
        updateHeight(node);

        return node;

    }
    
    
    //AVL Insertion
    private Customer insertAVL(Customer node, Customer aCustomer){
        // if the tree is empty create a new node and return it
        if (node == null) {
          return new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude());
      }

        //If key already in the tree return the node.
        //No Duplicates.
        if(node.getID() == aCustomer.getID()) {
            return node;
        }
        
        //Down the tree..
        if(aCustomer.getID() < node.getID()) {
            node.setLeft(insertAVL(node.getLeft(), aCustomer));
        } else {
            node.setRight(insertAVL(node.getRight(), aCustomer));
        }

        //Update the height of the ancestor node
        updateHeight(node);
        //Returning balanced and rotated tree if necessary
        return balance(node);
    }

    private Customer splay(Customer node, Customer aCustomer) {
        // Base case: if node is null or key is found
        if (node == null || node.getID() == aCustomer.getID()) {
            return node;
        }
    
        // Our ID is in the left subtree
        if (aCustomer.getID() < node.getID()) {
            // If left child is null return node (key not found)
            if (node.getLeft() == null) {
                return node;
            }

            // Zig-Zig (Left Left)
            if (aCustomer.getID() < node.getLeft().getID()) {
                // splay the left left grandchild
                node.getLeft().setLeft(splay(node.getLeft().getLeft(), aCustomer));
                // perform first right rotation
                node = rightRotateSplay(node);
            }
            // Zig-Zag (Left Right)
            else if (aCustomer.getID() > node.getLeft().getID()) {
                // splay the left right grandchild
                node.getLeft().setRight(splay(node.getLeft().getRight(), aCustomer));
                // perform left rotation on left child
                if (node.getLeft().getRight() != null) {
                    node.setLeft(leftRotateSplay(node.getLeft()));
                }
            }
    
            //second right rotation if needed
            if (node.getLeft() == null) {
                // return the current node if the left child is null
                return node; 
            } else {
                return rightRotateSplay(node);
            }
        } 
        // Our id in the right subtree
        else {
            // If right child is null return node (key not found)
            if (node.getRight() == null) {
                return node;
            }
            // Zag-Zag (Right Right)
            if (aCustomer.getID() > node.getRight().getID()) {
                //splay the right-right grandchild
                node.getRight().setRight(splay(node.getRight().getRight(), aCustomer));
                //first left rotation
                node = leftRotateSplay(node);
            } 
            // Zag-Zig (Right Left)
            else if (aCustomer.getID() < node.getRight().getID()) {
                // splay the right-left grandchild
                node.getRight().setLeft(splay(node.getRight().getLeft(), aCustomer));
                //right rotation on right child
                if (node.getRight().getLeft() != null) {
                    node.setRight(rightRotateSplay(node.getRight()));
                }
            }
    
            if (node.getRight() == null) {
                return node; 
            } else {
                return leftRotateSplay(node); 
            }
        }
    }
    
    
    




    class Customer {
        int DEFAULT_HEIGHT = 0;
        int DEFAULT_ID = 0;
    
        Customer(int id, double lat, double longitude){
            m_id = id; m_latitude = lat; m_longitude = longitude;
            m_left = null; m_right = null; m_height = DEFAULT_HEIGHT;
        }
        //used for testing that ids are put in trees correctly
        Customer(int id){
            m_id = id; m_latitude = 0; m_longitude = 0;
            m_left = null; m_right = null; m_height = DEFAULT_HEIGHT;

        }
        int getHeight() {return m_height;}
        Customer getLeft() {return m_left;}
        Customer getRight() {return m_right;}
        int getID() {return m_id;}
        double getLatitude() {return m_latitude;}
        double getLongitude() {return m_longitude;}
        void setID(int id){m_id=id;}
        void setLatitude(double lat) {m_latitude=lat;}
        void setLongitude(double longitude) {m_longitude=longitude;}
        void setHeight(int height){m_height=height;}
        void setLeft(Customer left){m_left=left;}
        void setRight(Customer right){m_right=right;}
        String getLatStr() {
            String text = "";
            int latSeconds = (int)(Math.abs(m_latitude * 3600));
            int latDegrees = latSeconds / 3600;
            latSeconds = latSeconds % 3600;
            int latMinutes = latSeconds / 60;
            latSeconds %= 60;
            char latDirection = (m_latitude >= 0) ? 'N' : 'S';
            text = Integer.toString(latDegrees) + "\u00B0 " + Integer.toString(latMinutes) + "' " + 
                    Integer.toString(latSeconds) + "\" " + latDirection;
            return text;
        }
        String getLongStr() {
            String text = "";
            int longSeconds = (int)(Math.abs(m_longitude * 3600));
            int longDegrees = longSeconds / 3600;
            longSeconds = longSeconds % 3600;
            int longMinutes = longSeconds / 60;
            longSeconds %= 60;
            char longDirection = (m_longitude >= 0) ? 'E' : 'W';
            text = Integer.toString(longDegrees) + "\u00B0 " + Integer.toString(longMinutes) + "' " + 
                    Integer.toString(longSeconds) + "\" " + longDirection;
            return text;
        }
    
        //private data members
        private int m_id;
        private double m_latitude;
        private double m_longitude;
        private Customer m_left;    //the pointer to the left child in the BST
        private Customer m_right;   //the pointer to the right child in the BST
        private int m_height;        //the height of node in the BST
        
    } // end of class Customer
} //end of class WirelessPower
 
This code is currently not passing this test 
@Test
	void testInsertSplay() {
		s3.insert(d1); 
		s3.insert(d2); 
		s3.insert(d3); 
		s3.insert(d4); 
		s3.insert(d5); 
		s3.insert(d6); 
		s3.insert(d7);
		s3.insert(d8); 
		s3.insert(d9); 
		assertEquals(26241,s3.getRoot().getID());
		assertEquals(19372,s3.getRoot().getLeft().getID());
		assertEquals(93209,s3.getRoot().getRight().getID());
		assertEquals(19224,s3.getRoot().getLeft().getLeft().getID());
		assertEquals(20201,s3.getRoot().getLeft().getRight().getID());
		assertEquals(19289,s3.getRoot().getLeft().getLeft().getRight().getID());
		assertEquals(60496,s3.getRoot().getRight().getLeft().getID());
		assertEquals(27904,s3.getRoot().getRight().getLeft().getLeft().getID());
		assertEquals(53002,s3.getRoot().getRight().getLeft().getLeft().getRight().getID());
		assertEquals("(((19224:1(19289:0))19372:2(20201:0))26241:4(((27904:1(53002:0))60496:2)93209:3))",s3.dumpTree());		
	} 
at assertEquals(93209,s3.getRoot().getRight().getID()); expecting 93209 instead it was 53002 

	@Test
	void testInsertEasySplay() {
		s3.insert(d1);
		//this Customer is the root of the tree
		assertEquals(53002,s3.getRoot().getID());
		assertEquals(51.5078, s3.getRoot().getLatitude());
		assertEquals(-0.0878, s3.getRoot().getLongitude());

		//BST insert to the left of the root
		//splay to the root
		s3.insert(d2);
		assertEquals(20201,s3.getRoot().getID());
		assertEquals(39.2554, s3.getRoot().getLatitude());
		assertEquals(-76.7107, s3.getRoot().getLongitude());
		assertEquals(53002,s3.getRoot().getRight().getID());
		assertEquals(51.5078, s3.getRoot().getRight().getLatitude());
		assertEquals(-0.0878, s3.getRoot().getRight().getLongitude());

		//BST insert to the right of the right of the root
		//splay to the root
		s3.insert(d3);
		assertEquals(60496,s3.getRoot().getID());
		assertEquals(48.8584, s3.getRoot().getLatitude());
		assertEquals(2.2945, s3.getRoot().getLongitude());
		assertEquals(53002,s3.getRoot().getLeft().getID());
		assertEquals(51.5078, s3.getRoot().getLeft().getLatitude());
		assertEquals(-0.0878, s3.getRoot().getLeft().getLongitude());
		assertEquals(20201,s3.getRoot().getLeft().getLeft().getID());
		assertEquals(39.2554, s3.getRoot().getLeft().getLeft().getLatitude());
		assertEquals(-76.7107, s3.getRoot().getLeft().getLeft().getLongitude());
		//check the heights
		assertEquals("(((20201:0)53002:1)60496:2)",s3.dumpTree());
	} 
B ut it passes this test just fine.