package BpTree;


class Elem
{
	Comparable key;
	Object obj;
	
	public Elem(Comparable k, Object o)
	{
		key = k;
		obj = 0;
	}

	public String toString()
	{
		return ""+key;
	}
}
class Pair
{
	Comparable key;
	Object pointer;
	
	public Pair(Comparable k, Object p)
	{
		key = k;
		pointer = p;
	}
	public String toString()
	{
		return "["+ key+", "+pointer+"]";
	}

}
class BpNode
{
	private boolean isLeaf;
	
	public static boolean LEAF = true;
	public static boolean NONLEAF = false;

	
	private final int MAXREC;

	public int count;
	Pair[] recArray;
	public BpNode leftSibling, rightSibling;
	
	
	public BpNode(boolean leaf, int max)	//	leaf == 1:leaf node ; leaf == 0:non_leaf node
	{
		MAXREC = max;
		recArray = new Pair[MAXREC];
		recArray[0] = new Pair(Integer.MIN_VALUE, null);
		count = 1;
		leftSibling = rightSibling = null;	
		
		if(leaf == LEAF)
		{
			isLeaf = true;			
		}
		else
		{
			isLeaf = false;
		}
		
		
	}

	
	public int maxLE(Comparable tar)
	{
		int result;
		for(result=1; result<count; result++)
		{
			if(recArray[result].key.compareTo(tar) > 0)
				break;			
		}
		return result-1;		
	}
	public void merge(BpNode other)
	{
		if(isLeaf)
		{
		for(int i=0; i<other.count-1; i++)
		{
			this.recArray[count+i] = other.recArray[i+1];
			
		}
		this.count = this.count + other.count-1;
		other.count = 1;		
		this.rightSibling = other.rightSibling;
		if(other.rightSibling != null)
			other.rightSibling.leftSibling = this;
		}		
		
		else
		{
			BpNode first = (BpNode)other.recArray[0].pointer;
			BpNode current = first;
			while(!current.isLeaf)	//	找到other節(jié)點(diǎn)一下最小的key值
				current = (BpNode)current.recArray[0].pointer;
			
			Pair tmp = new Pair(current.recArray[1].key, first);
			this.recArray[count] = tmp;
			for(int i=0; i<other.count-1; i++)
			{
				this.recArray[count +i +1] = other.recArray[i+1];
			}
			this.count = this.count + other.count;
			other.count = 1;	
			this.rightSibling = other.rightSibling;
			if(other.rightSibling != null)
				other.rightSibling.leftSibling = this;
		}
	}
	
	public void shuffle(BpNode other)
	{
		if(isLeaf)
		{
			Pair[] bigArr = new Pair[2*MAXREC];
			int i;
			for(i=0; i<this.count-1; i++)
				bigArr[i] = this.recArray[i+1];
			for(int j=0;j<other.count-1; j++)
			{
				bigArr[j+i] = other.recArray[j+1];
			}
			int max = this.count + other.count-2;
			
			BpNode new1 = new BpNode(this.isLeaf,this.MAXREC);
			BpNode new2 = new BpNode(this.isLeaf,this.MAXREC);
			
			int k;
			for(k = 0; k< (max+1)/2; k++)
			{
				new1.recArray[k+1] = bigArr[k];
				new1.count++;
			}
			for(int l=0; l<max/2; l++)
			{
				new2.recArray[l+1] = bigArr[l+k];
				new2.count++;
			}
			
			this.count = new1.count;
			this.recArray = new1.recArray;
			other.count = new2.count;
			other.recArray = new2.recArray;
		}
		
		else
		{	
			Pair[] bigArr = new Pair[2*MAXREC];
			
			for(int i=0; i<this.count; i++)
				bigArr[i] = this.recArray[i];
			
			BpNode first = (BpNode)other.recArray[0].pointer;
			BpNode current = first;
			while(!current.isLeaf)
				current = (BpNode)current.recArray[0].pointer;
			Pair tmp = new Pair(current.recArray[1].key, first);
					
			bigArr[this.count] = tmp;
			
			for(int i=0; i<other.count-1; i++)
			{
				bigArr[this.count +1+i] = other.recArray[i+1];
			}
			
			int max = this.count + other.count;
			
			BpNode new1 = new BpNode(this.isLeaf,this.MAXREC);
			BpNode new2 = new BpNode(this.isLeaf,this.MAXREC);
			
			
			int i;
			new1.count--;
			for(i=0; i< (max+1)/2; i++)
			{
				new1.recArray[i] = bigArr[i];
				new1.count++;
			}
			for(int l=0; l<max/2; l++)
			{
				new2.recArray[l+1] = bigArr[l+i];
				new2.count++;
			}
			

			Pair temp = new1.recArray[--new1.count];
			new1.recArray[new1.count] = null;
			new2.recArray[0].pointer = temp.pointer;

			this.count = new1.count;
			this.recArray = new1.recArray;
			other.count = new2.count;
			other.recArray = new2.recArray;			
		}		
	}
	public void addAfter(int currec, Pair p)
	{
		for(int i = count; i>currec+1; i--)
			recArray[i] = recArray[i-1];
		recArray[currec+1] = p;
		count++;
	}
	//	刪除recArray在index位置的元素，count--
	//	目標(biāo)后元素順序前移
	public void deleteAt(int index)
	{
		for(int i=index; i<count-1; i++)
			recArray[i] = recArray[i+1];
		recArray[--count] = null;
	}
	
	
	//	函數(shù)split(index, tar)將tar加入到當(dāng)前節(jié)點(diǎn),index是tar在recArray中的位置
	//	過程中，當(dāng)前節(jié)點(diǎn)分裂為兩個(gè)節(jié)點(diǎn)，分別接受原節(jié)點(diǎn)一半元素，新的節(jié)點(diǎn)被返回
	
	public BpNode split(int index, Pair tar)
	{
		Pair[] bigArr = new Pair[2 * MAXREC];
		
		int i;
		for(i=0;i<count-1;i++)
		{
			if(i==index)
				break;
			else
			{
				bigArr[i] = recArray[i+1];
			}
		}
		bigArr[i] = tar;
		for(int j=i+1; j< recArray.length; j++)
		{
			bigArr[j] = recArray[j];
		}
		
		BpNode new1 = new BpNode(this.isLeaf,this.MAXREC);	
		BpNode new2 = new BpNode(this.isLeaf,this.MAXREC);
		
		int k;
		for(k=0; k< MAXREC/2; k++)
		{
			new1.recArray[k+1] = bigArr[k];
			new1.count++;
		}
		for(int l=k; l<MAXREC; l++)
		{
			new2.recArray[l-k+1] = bigArr[l];
			new2.count++;
		}
		new1.recArray[0].pointer = this.recArray[0].pointer;
		
		new2.leftSibling = this;
		new2.rightSibling = this.rightSibling;
		if(this.rightSibling != null)
			this.rightSibling.leftSibling = new2;
		this.rightSibling = new2;
		
		
		//	當(dāng)前葉節(jié)點(diǎn)更新
		this.count = new1.count;
		this.recArray = new1.recArray;
		
		return new2;	
	}

	public String toString()
	{
		String res = "";
		
		for(int i=1; i<count; i++)
			res += recArray[i].key +",";

		return "『"+ res.substring(0, res.lastIndexOf(',')) +"』";
	}
	
	
	public boolean canMerge(BpNode other)
	{
		if(isLeaf)
		{
			return (this.count + other.count -1) <= MAXREC;
		}
		else
		{
			return (this.count + other.count) <= MAXREC;
		}
	}
	
	public boolean isLeaf()
	{
		return isLeaf;
	}
	public boolean isFull()
	{
		return count == MAXREC;
	}

	public boolean isBigEnough()
	{
		if(isLeaf)
		{
			return ((count-1) >= MAXREC/2);
		}
		else
		{
			return (count >= (MAXREC+1)/2);			
		}
	}
}

public class BpTree
{
	private BpNode root;
	final int DEGREE;
	
	
	public BpTree()
	{		
		root = null;
		DEGREE=4;
	}
	public BpTree(int degree)
	{
		root = null;
		DEGREE = degree;
	}
	
	
	public void insert(Comparable key)
	{
//		System.out.println("Inserting "+ key+"...");
		Elem tmp = new Elem(key,null);
		insert(tmp);
	}
	
	public void insert(Elem rec)
	{
		if(root == null)
		{
			root = new BpNode(BpNode.LEAF,DEGREE);
			Pair newP = new Pair(rec.key, rec);
			root.recArray[1] = newP;
			root.count++;
		}
		else
		{
			Pair p = insertHelp(root, rec);
			if(p != null)
			{
				BpNode tmp = new BpNode(BpNode.NONLEAF,DEGREE);
				tmp.recArray[0].pointer = root;
				tmp.recArray[1] = p;
				tmp.count++;
				root = tmp;				
			}			
		}
	}
	
	
	public void remove(Comparable k)
	{
//		System.out.println("Removing "+ k +"...");
		int currec = root.maxLE(k);
		if(root.isLeaf())
		{
			if(root.recArray[currec].key.equals(k))
				root.deleteAt(currec);
			if(root.count == 1)
				root = null;
		}            
		else                                                             
		{
			currec = removeHelp( (BpNode)root.recArray[currec].pointer, k, currec);
			
			if(currec == -1)
				return;
			else if(((BpNode)root.recArray[currec].pointer).count > 1)
			{	//	子結(jié)點(diǎn)重組了，更新相關(guān)節(jié)點(diǎn)
/*				root.recArray[currec].key = 
					((BpNode)root.recArray[currec].pointer).recArray[1].key;
*/				
				BpNode current = (BpNode)root.recArray[currec].pointer;
				
				while(!current.isLeaf())
				{
					current = (BpNode)current.recArray[0].pointer;
				}
				root.recArray[currec].key =
					current.recArray[1].key;
				
				return;				
			}
			
			root.deleteAt(currec);
			
			if(root.count >1)
				return;
			else		//	可能有問題
			{
				root = (BpNode)root.recArray[0].pointer;
				return;
			}
			
		}
		
	}
	
	private int removeHelp(BpNode node, Comparable k, int thispos)
	{
		int currec = node.maxLE(k);
		
		if(node.isLeaf())
		{
			if(!node.recArray[currec].key.equals(k))
				return -1;