/**simple implementation of an m-way search tree*/
public class MTree<E extends Comparable<E>> {
  private MNode<E> root;
  private int size;
  private int capacity; //number of elements at each node
  
  public MTree(int m){
	  root=null;
	  size=0;
	  capacity=m-1;
	  System.out.println("creating new tree with capacity " + capacity);
  }

public int getCapacity(){
	return capacity;
}

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

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

public int getSize() {
	return size;
}

public void setSize(int size) {
	this.size = size;
}

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

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


  
/**insert node containing element e if doesn't already exist
 * starting at node p
 * @return root
 */
  public MNode<E> insert(E e, MNode<E> p){
	  if(p==null) {p=new MNode<E>(e,this.getCapacity()+1); size++;}
	  else{
		  if (p.getSize()<p.getCapacity()) {p.addElement(e);size++;}
		  else{
			  if (p.getSeq()[0].getVal().compareTo(e)>0) p.setLeft(insert(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) 
					  p.getSeq()[i-1].setRight(insert(e,p.getSeq()[i-1].getRight()));
			  }
		  }
	  }
	  return p;
  }
		  
  
  /**insert node containing e if doesnt already exist, starting at root*/
  public void insert(E e){
	  if (isEmpty()) {setRoot(new MNode<E>(e,capacity+1));size++;}
	  else insert(e, this.root);
  }

  
  /**see if tree contains value e
   * starting at node p*/
  public boolean contains(E e, MNode<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(MNode<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);
  }
  
 /**output nodes of tree in DFS fashion
  * starting from node p
  */
  //for testing purposes
  public String outputNodes(MNode<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);
  }
  
}