package ddAsAVL;

public class DynamicDict {
	private AVLNode root; 
	
	
	public DynamicDict(){
		root = null;
	}
	
	public boolean isEmpty(){
		if(root==null){
			return true;
		}else{
			return false;
		}
	}
	
	public String find(int key){
		return find(key,root);
	}
	
	//This is good
	public String find(int key,AVLNode currentNodeConsidered){
		if(currentNodeConsidered==null){
			return "Woah bro, invalid key";
		}
		if(currentNodeConsidered.key==key){
			if(currentNodeConsidered.extant==1){
				System.out.println("Dude, you deleted that node");
				return null;
			}else{
			return currentNodeConsidered.data;
			}
		}
		if(currentNodeConsidered.key<key){
			return find(key,currentNodeConsidered.right);
		}else{
			return find(key,currentNodeConsidered.left);
		}
	}
	

	
	public void insert(int key, String data){
		root = insert(key, data, root);		
	}
	
	public AVLNode insert(int key, String data, AVLNode currentNodeConsidered){
		// will occur when insert is finally called on node who has a null child
		if (currentNodeConsidered==null){ //and in one instance when the tree is initialized  
			return new AVLNode(key, data,null, null);
		}
		//otherwise, we traverse down the tree (consider the children)
		//this all starts starting with the left and right of the root
		
		//Not exactly sure why this is necessary, but it updates the data if they insert a key that's already in there
		if(key==currentNodeConsidered.key){
			System.out.println("That key was already inserted, we'll just update the data");
			currentNodeConsidered.data = data; 
			return currentNodeConsidered;
		}
		
		if(key>currentNodeConsidered.key){
			//if the key is greater than the current node's we attempt to insert as the currentNode's right node. 
			//if the right node is null, then it'll be added as such. If it's not null, it'll repeat the process 
			//for that node, perhaps considering the left case. 
			currentNodeConsidered.right= insert(key,data,currentNodeConsidered.right);
		}else{ 
			currentNodeConsidered.left = insert(key,data,currentNodeConsidered.left);
		}
		
		
		
		//Balancing code
		int heightOfLeftNode = (currentNodeConsidered.left==null) ? -1 : currentNodeConsidered.left.height;
		int heightOfRightNode = (currentNodeConsidered.right==null) ? -1: currentNodeConsidered.right.height;
		//currentNodeConsidered.height = Math.max(heightOfLeftNode, heightOfRightNode)+1;
		if(heightOfLeftNode>heightOfRightNode+1){
			//We have to do a LL or LR switch 
			if(key<currentNodeConsidered.left.key){
				//LL
				System.out.println("Doing LL switch");
				//store
				AVLNode nodeThatJumps = currentNodeConsidered.left.right;
				//set
				currentNodeConsidered.left.right=currentNodeConsidered; 
				//set
				AVLNode nodeThatWillBeRoot = currentNodeConsidered.left;
				currentNodeConsidered.left=nodeThatJumps;
				currentNodeConsidered=nodeThatWillBeRoot;
				
			}else{//LR
				System.out.println("Doing LR switch");
				AVLNode nodeThatJumps = currentNodeConsidered.left.right;
				currentNodeConsidered.left.right= (nodeThatJumps==null) ? null:nodeThatJumps.left;
				nodeThatJumps.left=currentNodeConsidered.left;
				currentNodeConsidered.left=nodeThatJumps.right;
				nodeThatJumps.right = currentNodeConsidered;
				currentNodeConsidered = nodeThatJumps;
			} 
					
		}
		
		if(heightOfRightNode>heightOfLeftNode +1){//RR or RL
			if(key >currentNodeConsidered.right.key){
				//RR
				System.out.println("Doing RR switch");
				//store
				AVLNode nodeThatJumps = currentNodeConsidered.right.left;
				//set
				currentNodeConsidered.right.left=currentNodeConsidered; 
				//set
				AVLNode nodeThatWillBeRoot = currentNodeConsidered.right;
				currentNodeConsidered.right=nodeThatJumps;
				currentNodeConsidered=nodeThatWillBeRoot;//realized we needed to update what's the new root node
			}else{
				//RL
				System.out.println("Doing RL switch");
				AVLNode nodeThatJumps = currentNodeConsidered.right.left;
				currentNodeConsidered.right.left= nodeThatJumps.right;
				nodeThatJumps.right=currentNodeConsidered.right;
				currentNodeConsidered.right=nodeThatJumps.left;
				nodeThatJumps.left = currentNodeConsidered;
				currentNodeConsidered = nodeThatJumps;
				
			}
		}
		
		updateHeight();
		
		return currentNodeConsidered; //this should take care of the stack of recursive calls 
		//other than the innermost one. That is, it leaves everything as it was up the stack. 
		
	}
	
	
	public void remove(int key){
		remove(key,root);
	}
	
	public AVLNode remove(int key, AVLNode currentNodeConsidered){
		if(currentNodeConsidered==null){
			System.out.println("Um, no node with that key.");
			return null;
		}
		if(key<currentNodeConsidered.key){
			currentNodeConsidered.left=remove(key,currentNodeConsidered.left);
		}
		if(key>currentNodeConsidered.key){
			currentNodeConsidered.right=remove(key,currentNodeConsidered.right);
		}
		if(key==currentNodeConsidered.key){//we found what we need to remove
			if(currentNodeConsidered.extant==0){
				System.out.println("Um, that node has been deleted.");
			}else{
				currentNodeConsidered.extant=0;
				System.out.println(key+" was succesfully deleted.");
			}
			
			
			
		}
		return currentNodeConsidered;
	
	}
	
	
	
	public AVLNode findMax(AVLNode rootOfSubtree){//Precondition that rootOfSubtree is not null
		while(rootOfSubtree.right!=null){
			rootOfSubtree=rootOfSubtree.right;
		}
		return rootOfSubtree;
	}
	
	
	public int count(){
		return count(root);
	}
	
	public int count(AVLNode rootOfSubtree){
		if(rootOfSubtree==null){return -1;}
		
		if(rootOfSubtree.left==null&&rootOfSubtree.right==null){
			return rootOfSubtree.extant;
		}else if(rootOfSubtree.left==null){
			return rootOfSubtree.extant+count(rootOfSubtree.right);
		}else if(rootOfSubtree.right==null){
			return rootOfSubtree.extant+count(rootOfSubtree.left);
		}else{//has two children
			return rootOfSubtree.extant+count(rootOfSubtree.right)+count(rootOfSubtree.left);
		}
	}

	
	
	public int height(){
		return height(root);
	}
	
	public int height(AVLNode rootOfSubtree){
		if(rootOfSubtree.left==null&&rootOfSubtree.right==null){
			return 1;
		}else if(rootOfSubtree.left==null){
			return 1+height(rootOfSubtree.right);
		}else if(rootOfSubtree.right==null){
			return 1+height(rootOfSubtree.left);
		}else{//has two children
			return 1+Math.max(height(rootOfSubtree.right),height(rootOfSubtree.left));
		}
	}
	
	public void updateHeight(){
		updateHeight(root);
	}
	
	public int updateHeight(AVLNode rootOfSubtree){
		if(rootOfSubtree.left==null&&rootOfSubtree.right==null){
			rootOfSubtree.height=0;
			return rootOfSubtree.height;
		}else if(rootOfSubtree.left==null){
			rootOfSubtree.height=1+updateHeight(rootOfSubtree.right);
			return rootOfSubtree.height;
		}else if(rootOfSubtree.right==null){
			rootOfSubtree.height= 1+updateHeight(rootOfSubtree.left);
			return rootOfSubtree.height;
		}else{//has two children
			rootOfSubtree.height= 1+Math.max(updateHeight(rootOfSubtree.right),updateHeight(rootOfSubtree.left));
			return rootOfSubtree.height;
		}
	
	}
	
	
	
	
}