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) {

        // Check for valid range of ID
        if (aCustomer.getID() < MINID || aCustomer.getID() > MAXID) {
            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());

            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 = insertSplay(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);
                break;
            case AVL:
                m_root = deleteRecursively(m_root, id);
                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) {
        int balanceFactor = getBalance(node);

        // Left Right
        if (balanceFactor > 1 && getBalance(node.getLeft()) < 0) {
            node.setLeft(leftRotate(node.getLeft()));
            return rightRotate(node);
        }
        // Left Left
        if (balanceFactor > 1 && getBalance(node.getLeft()) >= 0) {
            return rightRotate(node);
        }
        // Right Left
        if (balanceFactor < -1 && getBalance(node.getRight()) > 0) {
            node.setRight(rightRotate(node.getRight()));
            return leftRotate(node);
        }
        // Right right
        if (balanceFactor < -1 && getBalance(node.getRight()) <= 0) {
            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) {
        // Check for null node
        if (node == null) {
            return;
        }

        // heights for left and right children
        // -1 if null which would be default
        int leftHeight = -1;
        int rightHeight = -1;

        // Check if left child is not null and get its height
        if (node.getLeft() != null) {
            leftHeight = node.getLeft().getHeight();
        }

        // Check if right child is not null and get its height
        if (node.getRight() != null) {
            rightHeight = node.getRight().getHeight();
        }

        node.setHeight(Math.max(leftHeight, rightHeight) + 1);
    }


    // 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
           // System.out.println("Deleting node with ID: " + id);
            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 = node.getLeft();
        }
        return node;
    }

    public void BstToAVL() {
        // Creating an ArrayList to hold the nodes in sorted order
        ArrayList<Customer> nodeList = new ArrayList<>();

        // Filling the ArrayList with nodes in sorted order
        traverseInOrder(m_root, nodeList);

        // Converting the ArrayList to an AVL tree
        m_root = arrayToAVL(nodeList, 0, nodeList.size() - 1);
    }

    // Recursively build the AVL tree subtrees
    private Customer arrayToAVL(ArrayList<Customer> nodeList, int start, int end) {
        // No elements left in our tree
        if (start > end) {
            return null;
        }
        // Find the middle of the ArrayList.
        int mid = (start + end) / 2;
        // Create a root node
        Customer node = nodeList.get(mid);

        // Create the left subtree
        node.setLeft(arrayToAVL(nodeList, start, mid - 1));
        // Create the right subtree
        node.setRight(arrayToAVL(nodeList, mid + 1, end));

        return node;
    }

    // Traverse tree in order (Left subtree then root, then right subtree)
    // While storing the values into our ArrayList.
    private void traverseInOrder(Customer node, ArrayList<Customer> nodeList) {
        // If node is null, no nodes left
        if (node == null) {
            return;
        }
        // Traverse left of subtree first
        traverseInOrder(node.getLeft(), nodeList);
        // Add the current node to our ArrayList
        nodeList.add(node);
        // Traverse right of subtree afterwards
        traverseInOrder(node.getRight(), nodeList);
    }

    private Customer insertBST(Customer node, Customer aCustomer) {
        
        // Base case if the node is null create a new customer
        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 height of the node after insertion
        updateHeight(node);

        return node;
    }

    // AVL Insertion
    private Customer insertAVL(Customer node, Customer aCustomer) {
        if (node == null) {
            return new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude());
        }

        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);
        return balance(node);
    }

    //insert splay
private Customer insertSplay(Customer node, Customer aCustomer) {
    // Insert the node using insertBST and get the updated subtree root
    node = insertBST(node, aCustomer);

    // Perform splay operation starting from the current root
    node = splay(node, aCustomer);

    // Return the new root after splaying
    return node;
}
    private Customer splay(Customer node, Customer aCustomer) {
        // Base case if node is null or id 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
            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 node;
            } else {
                // Final rotation
                node = rightRotateSplay(node);
                return node;
            }
        } else {
            // Our id in the right subtree
            // If right child is null return node
            if (node.getRight() == null) {
                return node;
            }
            
            // Right-Right (Zig-Zig)
            if (aCustomer.getID() > node.getRight().getID()) {
                //splay the right-right grandchild
                node.getRight().setRight(splay(node.getRight().getRight(), aCustomer));
                // First rotation
                node = leftRotateSplay(node);
            }
            // Right-Left (Zig-Zag)
            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()));
                }
            }
            
            // Second rotation
            if (node.getRight() == null) {
                return node;
            } else {
                // Final rotation
                node = leftRotateSplay(node);
                return 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