/**simple implementation of an m-way B tree*/
public class BTree<E extends Comparable<E>> {
  private BNode<E> root;
  private int capacity; //number of elements at each node
  
  public BTree(int m){
	  root=null;
	  capacity=m-1;
	  System.out.println("Creating new tree with capacity " + capacity+ "\n");
  }

public int getCapacity(){
	return capacity;
}

public BNode<E> getRoot() {
	return root;
}

public void setRoot(BNode<E> r) {
	this.root = r;
}


public boolean isEmpty(){
	return (root==null);
}

public static boolean isEmpty(BNode p){
	return (p==null);
}



  
/**insert node containing element e if doesn't already exist
 * starting at node p
 * @return root
 */
  public BCluster<E> insert(E e, BNode<E> p){
	  BCluster<E> myBCluster=new BCluster<E>();
	  int m=capacity+1;
	  
	  if(p==null) {BNode<E> pNew=new BNode<E>(e,this.getCapacity()+1); 
	  myBCluster=new BCluster<E>(pNew,null,null);
	  }
	  
	  else{
		  if(p.isLeaf()){
			  if (p.getSize()<p.getCapacity()){
		          p.addElement(null,null,e);
		          myBCluster=new BCluster<E>(p,null,null);
		          }
			  else myBCluster=p.divideNode(e,null,null);
		  }
		  else{
			  if (p.getSeq()[0].getVal().compareTo(e)>0)
				 myBCluster=new BCluster<E>(insert(e,p.getLeft()));  
			  else{
				  int temp=0;
				  while ((temp<p.getSize())&&(p.getSeq()[temp].getVal().compareTo(e)<0))
				  {
					  //System.out.println("temp is " + temp);
					  temp++;}
				  if((temp==p.getSize())||(p.getSeq()[temp].getVal().compareTo(e)>0)){
					  myBCluster=new BCluster<E>(insert(e,p.getSeq()[temp-1].getRight()));
				  }
			  }
		  
		  
	 
		     if(myBCluster.getP2()!=null){//a value has been sent back up
		    	// System.out.println("The value " + myBCluster.getValue()+" has been returned");
		    	 if(p.getSize()<p.getCapacity()) {p.addElement(myBCluster.getP1(), myBCluster.getP2(), myBCluster.getValue());
		    	 myBCluster=new BCluster<E>(p,null,null);
		    	 }
		    	 else myBCluster=p.divideNode(myBCluster.getValue(),myBCluster.getP1(), myBCluster.getP2());
				}
			  
		  }
			
			  
	  
	  
	  }
	  return myBCluster;
  }
		  
  
  /**insert node containing e if doesnt already exist, starting at root*/
  public void insert(E e){
	  System.out.println("Inserting value " +e);
	  int m=capacity+1;
	  if (isEmpty()) setRoot(new BNode<E>(e,m));
	  else{
		  BCluster<E> newBCluster = new BCluster<E>(insert(e, root));
	      if(newBCluster.getP2()!=null){
	    	  //System.out.println("Moving root up! To contain " + newBCluster.getValue());
	    	  //System.out.println("will point to nodes "+ newBCluster.getP1() + " and " + newBCluster.getP2());
	    	  root=new BNode<E>(newBCluster.getValue(),m);
	    	  root.setLeft(newBCluster.getP1());
	    	  root.getSeq()[0].setRight(newBCluster.getP2());
	    	  
	      }
  }
  }

  
  /**see if tree contains value e
   * starting at node p*/
  public boolean contains(E e, BNode<E> p){
	  if(p==null) return false;
	  else{
		  if (p.getSeq()[0].getVal().compareTo(e)>0) return contains(e,p.getLeft());
	      else{
		     int i=0;
		     while((i<p.getSize())&&(p.getSeq()[i].getVal().compareTo(e)<0)) i++;
		     if((i<p.getSize())&&p.getSeq()[i].getVal().compareTo(e)==0) return true;
		     else return contains(e,p.getSeq()[i-1].getRight());
	           
	      }
	  }
  }
			
	    
	 
  
  /**see if tree contains value e*/
   public boolean contains(E e){
	   return contains(e,root);
   }
  
 

			  
/**create string using inorder traversal*/
  public String toString(BNode<E> p){
	  String s="";
	  if (p!=null) {
		  s=s+toString(p.getLeft());
		  int i=0;
		  while(i<p.getSize()){s=s+" " + p.getSeq()[i].getVal()+ " " + toString(p.getSeq()[i].getRight());i++;
	  }
	  }
	  return s;
	  
  }
  
  public String toString(){
	  return this.toString(root);
  }
  
  /**find the current size, from node p*/
  public int getSize(BNode<E> p){
	  int size=0;
	  if (p!=null){
		  size=getSize(p.getLeft());
		  int i=0;
		  while(i<p.getSize()) {size=size+1+ getSize(p.getSeq()[i].getRight());i++;}
	  }
	  return size;
		  
	  }
  
  public int getSize(){
     return getSize(root);
  }
	  
  
  
 /**output nodes of tree in DFS fashion
  * starting from node p
  */
  //for testing purposes
  public String outputNodes(BNode<E> p){
	  String s="";
	  if (p!=null){
		  s=s+p.toString()+outputNodes(p.getLeft());
		  int i=0;
		  while(i<p.getSize()) {s=s+outputNodes(p.getSeq()[i].getRight());i++;}
		   
	  
	  
  }
	  return s;
  
}
  
  
  
  public String outputNodes(){
	  return this.outputNodes(root);
  }
  
}