public class DelegateTree implements IDelegateDB {
    public String name;
    private static int tableSize = 10;
    private int numEntries;
    private static Node root;
    public int visited;


    public class Node{
    private Delegate data;
    private Node left;
    private Node right;

    public Node(Delegate data){
     this.data = data;
     right = null;
     left = null;
    }

}
    public DelegateTree(){
        root = null;
        numEntries = 0;
    }

    @Override
    public void clearDB() {
      root = null;
    }

    public boolean Contains(Node node, String name){
        boolean got = false;
        if (node == null){
            System.out.println("Name not found");
            return false;
        }
        else if(name.compareTo(node.data.getName()) == 0){
            System.out.println("Person has been found:");
            return true;
        }
        else if(name.compareTo(node.data.getName()) > 0){ //Looks at two nodes and if the correct path is greater than the opposite node, it will run this code since the correct node is greater.
            return Contains(node.right, name);
        }
        else if(name.compareTo(node.data.getName()) < 0){ //Looks at two nodes from the root and if the node in the correct path is greater than the opposite node, it will run this code since the correct node is greater.
            return Contains(node.left, name);
        }
        return false;
        }



    @Override
    public boolean containsName(String name) {
           assert !name.equals("");
           boolean containing = Contains(root,name);
           if(containing){
               return true;
           }
           else{
               return false;
           }
           }

  public Node findPos(Node node, String name){
        if (node == null){
            return null;
        }
        else if(name.compareTo(node.data.getName()) == 0){
            return node;
        }
        else if(name.compareTo(node.data.getName()) > 0){
            node.right = findPos(node.right, name);
        }
        else if(name.compareTo(node.data.getName()) < 0){
            node.left = findPos(node.left, name);
        }
        return null;
        }


    @Override
    public Delegate get(String name) {
        System.out.println("Getting name..");
        Node find = findPos(root, name);
        if (find == null){
            System.out.println("Name not found" + name);
            return null;
        }
        System.out.println("Name is found:" + name);
        Delegate temp = find.data;
        return temp;
        }

    @Override
    public int size() {
        return numEntries;
    }

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

    @Override
    public Delegate put(Delegate delegate) {
        assert delegate == null;
        visited = 1;
        Node temp = insert(root, delegate);
        if (numEntries == 0){
            root = temp;
        }
        numEntries++;
        return delegate;

    }

    public Node insert(Node node, Delegate data){
        String name = data.getName();
        if (node == null){
            node = new Node(data);
            System.out.println(name);
        }
        else if(name.compareTo(node.data.getName()) > 0){ //Looks at two nodes and if the correct path is greater than the opposite node, it will run this code since the correct node is greater.
            node.right = insert(node.right, data);
            visited++;
        }
        else if(name.compareTo(node.data.getName()) < 0){//Looks at two nodes from the root and if the node in the correct path is greater than the opposite node, it will run this code since the correct node is greater.
            node.left = insert(node.left, data);
            visited++;
        }
        return node;
        }


    public boolean delete(Node node, Delegate data){
        Node current = root;
        Node parent = root;
        boolean leftChild = false;
        while(current){
            parent = current;
            if(data < current.data){
                // Move to the left if searched value is less
                current = current.left;
                leftChild = true;
            }
            else{
                // Move to the right if searched value is >=
                current = current.right;
                leftChild = false;
            }
            if(current == null){
                return false;
            }
        }
        // if reached here means node to be deleted is found

        // Leaf node deletion case
        if(current.left == null && current.right == null){
            System.out.println("Leaf node deletion case");
            // if root node is to be deleted
            if(current == root){
                root = null;
            }
            // left child
            else if(leftChild){
                parent.left = null;
            }
            // right child
            else{
                parent.right = null;
            }
        }
        // Node to be deleted has one child case
        // Node to be deleted has right child
        else if(current.left == null){
            System.out.println("One right child deletion case");
            // if root node is to be deleted
            if(current == root){
                root = current.right;
            }
            // if deleted node is left child
            else if(leftChild){
                parent.left = current.right;
            }
            // if deleted node is right child
            else{
                parent.right = current.right;
            }
        }
        // Node to be deleted has left child
        else if(current.right == null){
            System.out.println("One left child deletion case");
            if(current == root){
                root = current.left;
            }
            // if deleted node is left child
            else if(leftChild){
                parent.left = current.left;
            }
            // if deleted node is right child
            else{
                parent.right = current.left;
            }
        }
        // Node to be deleted has two children case
        else{
            System.out.println("Two children deletion case");
            // find in-order heir of the node to be deleted
            Node heir = findHeir(current);
            if(current == root){
                root = heir;
            }
            // if deleted node is left child
            else if(leftChild){
                parent.left = heir;
            }
            // if deleted node is right child
            else{
                parent.right = heir;
            }
            heir.left = current.left;
        }
        return true;
    }
    // Method to find the in-order heir of the deleted node
    /*private Node findHeir(Node node){
        Node successor = node;
        Node successorParent = node;
        // Start from the right child of the node to be deleted
        Node current = node.right;
        while(current != null){
            successorParent = successor;
            successor = current;
            current = current.left;
        }
        // When In-order heir is in the left subtree
        // perform two ref changes here as we have
        // access to successorParent
        if(successor != node.right){
            successorParent.left = successor.right;
            // applicable only when heir is not right child
            // so doing here
            successor.right = node.right;
        }
        return successor;
    }*/




    @Override
    public Delegate remove(String name) {

    }

    public static void TraversalInOrder(Node node) {
        if (node != null) {
            TraversalInOrder(node.left);
            System.out.println(node.data.getName());
            TraversalInOrder(node.right);
        }
    }
    @Override
    public void displayDB() {
        TraversalInOrder(root);
    }
}