public class BNode<E extends Comparable<E>>{
 private int size; //number of items in the node
 private BNode<E> left;
 private BPair<E>[] seq;
 private int capacity;//capacity of the sequence
 
 //constructors
 
 public BNode(int m){
	 size=0;
	 left=null;
	 seq= (BPair<E>[]) new BPair[m-1];//Compiler may warn, but ok
	 capacity=m-1;
 }
 
 public BNode(int k,BNode<E> m,BPair<E>[] seq1){
	 size=k;
	 left=m;
     seq=(BPair<E>[]) seq1.clone();
     capacity=seq.length;
	
 }
 
 /**create a new node just containing the value e*/
 public BNode(E e,int m){
	 BPair<E>[] myseq=(BPair<E>[]) new BPair[m-1]; //Compiler may warn, but ok
	 myseq[0]=new BPair<E>(e,null);
	 size=1;
	 left=null;
	 seq=myseq;
	 capacity=m-1;
 }
 
 //getters and setters
 
 public int getCapacity(){
	 return capacity;
 }

public int getSize() {
	return size;
}

public void setSize(int k) {
	size = k;
}

public BNode<E> getLeft() {
	return left;
}

public void setLeft(BNode<E> left) {
	this.left = left;
}

public BPair<E>[] getSeq() {
	return seq;
}

public void setSeq(BPair<E>[] seq) {
	this.seq = seq;
}

/**assuming size is < capacity, add element e in order
 * If value is being passed back up the tree, q1 and q2 are the two nodes formed by 
 * splitting
 */
public void addElement(BNode<E> q1, BNode<E> q2, E e){
	boolean added=false;
	int temp=0;
	while((temp<size)&&(seq[temp].val.compareTo(e)<0)) temp++;
	if (temp==size) {seq[temp]=new BPair<E>(e,q2);added=true;}
	else{
		if (seq[temp].val.compareTo(e)>0){
		for(int i=size;i>temp;i--) seq[i]=new BPair<E>(seq[i-1]);
		seq[temp]=new BPair<E>(e,q2);
		added=true;
	}
	}
	if (added==true){
		if(temp==0) left=q1;
		else seq[temp-1].setRight(q1);
	}
	size++;
}

/**Assuming sufficient room in node, add pair into next available space*/
public void addPair(BPair<E> mypair){
	seq[size]=mypair;
	size++;
}

/**find the index median of the values in a full node, and an extra value e
 * assuming they are all distinct. Equals -1 if median is e*/
public int median(E e){
	int m=capacity+1;
    E[] tempArray= (E[]) new Comparable[m];//Compiler may warn, but ok
	for(int i=0;i<size;i++) tempArray[i]=seq[i].getVal();
	int temp=0;
	while((temp<m-1)&&(tempArray[temp].compareTo(e)<0)) temp++;
	if (temp==m-1) tempArray[temp]=e;
	else{
		for(int i=m-1;i>temp;i--) tempArray[i]=tempArray[i-1];
		tempArray[temp]=e;
     }
	E med = tempArray[m/2];
	if (med==e) return -1;
	temp=0;
	while((temp<size)&&(seq[temp].getVal().compareTo(med)<0)) temp++;
	if ((temp==size)||(seq[temp].getVal().compareTo(med)>0)) return -1;
	else return temp;
	
	}


/**separate full node + value e into two subnodes containing elements < med, and
 * >med respectively
 * @param e
 * @return BCluster containing references to the subnodes, and the value being passed up tree
 */
public BCluster<E> divideNode(E e, BNode<E> p1,BNode<E> p2){
	int mymed=median(e);
	//System.out.println("position of median is: " + mymed);
	E med;
	if(mymed==-1) med=e;
	else med=seq[mymed].getVal();
    int m=capacity+1;
	BNode<E> subNode1=new BNode<E>(m);
	BNode<E> subNode2=new BNode<E>(m);
	for(int i=0;i<size;i++){
		if(seq[i].getVal().compareTo(med)<0) subNode1.addPair(seq[i]);
		else{
			if(seq[i].getVal().compareTo(med)>0) subNode2.addPair(seq[i]);
		}
	}
	if (med.compareTo(e)>0) {subNode1.addElement(p1, p2, e);subNode2.setLeft(seq[mymed].getRight());}
	
	else{
		if (med.compareTo(e)<0) {subNode2.addElement(p1, p2, e);subNode1.setLeft(left);}
		else{subNode1.getSeq()[subNode1.getSize()-1].setRight(p1);
	         subNode2.setLeft(p2);
	         subNode1.setLeft(left);
		}
	}
			
		
	
	
	return (new BCluster<E>(subNode1,subNode2,med));

}

/**assuming size is >0, remove element e if present*/
public boolean removeElement(E e){
	return true;
	//to be completed
}
 

/** is this node a leaf?*/
public boolean isLeaf(){
	boolean temp=(left==null);
	int i=0;
	while((temp==true)&&(i<size)) {
		if (seq[i].right!=null) temp=false;
		i++;
	}
	return temp;
	
}
 
 
/**return String representation of node*/
public String toString(){
	String s="[";
	for (int i=0;i<size-1;i++) s=s+seq[i].getVal()+",";
	s=s+seq[size-1].getVal()+"]";
	return s;
}
}