import java.util.*;

public class Test5{
	
	public int getHeight(BST tree){
		return getHeight(tree.root);
	}
	
	public int getHeight(BSTNode current){
		if(current == null){
			return 0;
		}
		int L = getHeight(current.getLeft());
		int R = getHeight(current.getRight());
		
		if(L>R){
			return ++L;
		}
		else{
			return ++R;
		}
	}
	
	public boolean isFull(BSTNode current){
		if(current == null){
			return true;
		}
		if(current.getRight() == null && current.getLeft() != null ||
			current.getRight() != null && current.getLeft() == null){
				return false;
		}
		else{
			boolean b = isFull(current.getRight());
			boolean c = isFull(current.getLeft());
			if(b==false || c==false){
				return false;
			}
			else{
				return true;
			}
		}
	}
	
	//HEAP SHIT
	
	public Vector vHeap;
	
	public void add(Comparable c){
		int i = vHeap.size();
		vHeap.setElementAt(new Integer(214141),0);
		vHeap.add(c);
		
		while(i>1 && 
  		((Comparable)vHeap.elementAt(i)).compareTo(vHeap.elementAt(i/2))<0){
  		swap(i,(i/2));
  		i /= 2;
  		} 
	}
	
	private void swap(int a,int b){
  	Comparable temp = (Comparable)vHeap.elementAt(a);
  	vHeap.setElementAt(vHeap.elementAt(b),a);
  	vHeap.setElementAt(temp,b);
  	}
  	
  	public void heapify(int node){
  		int iRight = (node*2)+1;
  		int iLeft = node*2;
  		int iMin = iLeft;
  		int iSize = vHeap.size()-1;
  		Vector data = vHeap;
  		
  		if(iLeft <= iSize && 
  			((Comparable)data.elementAt(iLeft)).compareTo(data.elementAt(node))<0){
  			iMin = iLeft;
  		}
  		else{
  			iMin = node;
  		}
  	
  		if(iRight <= iSize &&
  			((Comparable)data.elementAt(iRight)).compareTo(data.elementAt(iMin))<0){
  			iMin = iRight;
  		}
  	
  		if(iMin != node){
  			swap(iMin,node);
  			heapify(iMin);
  		}
  	}
  		
  	public void BubbleSort(Integer[] bob){
  		for(int i=0; i<bob.length-1; i++){
  			for(int z=0; z<bob.length-1-i;z++){
  				if(bob[z+1].compareTo(bob[z])<0){
  					Integer temp = bob[z];
  					bob[z] = bob[z+1];
  					bob[z+1] = temp;
  				}
  			}
  		}
  	}
  	
  	public void InsertionSort(Integer[] bob){
  		for(int i=1; i<bob.length; i++){
  			Comparable cTemp = bob[i];
  			int z=i;
  			while(z>0 && cTemp.compareTo(bob[z-1])<0){
  				Integer temp = bob[z];
  					bob[z] = bob[z-1];
  					bob[z-1] = temp;
  					z--;
  			}
  		}
  	}	
	
	public static void main(String args[]){
		BST bob = new BST();
		Test5 shit = new Test5();
		
				
		bob.add(new Integer(10));
		System.out.println(shit.getHeight(bob));
		System.out.println(shit.isFull(bob.root));
		bob.add(new Integer(15));
		bob.add(new Integer(20));
		bob.add(new Integer(14));
		bob.add(new Integer(2));
		System.out.println(shit.getHeight(bob));
		System.out.println(shit.isFull(bob.root));
		bob.root = null;
		bob.add(new Integer(10));
		bob.add(new Integer(5));
		bob.add(new Integer(4));
		bob.add(new Integer(3));
		System.out.println(shit.getHeight(bob));
		System.out.println(shit.isFull(bob.root));
		
		System.out.println("/***************/");
		//Enumeration e;		
		
		shit.vHeap = new Vector();
		shit.vHeap.add(null);
		shit.add(new Integer(6));
		shit.add(new Integer(89));
		shit.add(new Integer(4));
		
		//e = shit.vHeap.elements();
		
		/*while(e.hasMoreElements()){
			System.out.println(e.nextElement());
		}*/
		System.out.println(shit.vHeap);
		
		Integer[] b = ArrayWrapper.getRandomIntegerArray(60);
		shit.InsertionSort(b);
		for(int i=0;i<b.length;i++){
			System.out.println(b[i]);
		}		
	}
}