package Tree234;

public class Tree234 {
	private Node root = new Node();
	
	/**
	 * 在树中查找一个数据项
	 * @param key
	 * @return
	 */
	public int find(long key) {
		Node curNode = this.root;
		int childNumber;
		
		while(true) {
			if((childNumber=curNode.findItem(key)) != -1) {
				return childNumber;
			}else if(curNode.isLeaf()) {
				return -1;
			}else {
				curNode = this.getNextChild(curNode,key);
			}
		}
	}
	
	/**
	 * 插入一个值
	 * @param dValue
	 */
	public void insert(long dValue) {
		System.out.println("插入一个值:"+dValue);
		Node curNode = this.root;
		DataItem tempitem = new DataItem(dValue);
		
		while(true) {
			if(curNode.isFull()) {
				this.split(curNode);
				curNode = curNode.getParent();
				curNode = this.getNextChild(curNode,dValue);
			}else if(curNode.isLeaf()) {
				break;
			}else {
				curNode = this.getNextChild(curNode,dValue);
			}
		}
		
		curNode.insertItem(tempitem);
		this.displayTree();
	}
	
	public void split(Node thisNode) {
		DataItem itemB,itemC;
		Node parent,child2,child3;
		int itemIndex;
		
		itemC = thisNode.removeItem();
		itemB = thisNode.removeItem();
		child2 = thisNode.disconnectChild(2);
		child3 = thisNode.disconnectChild(3);
		Node newRight = new Node();
		
		if(this.root == thisNode) {
			this.root = new Node();
			parent = this.root;
			root.connectChild(0,thisNode);
		}else {
			parent = thisNode.getParent();
		}
		
		itemIndex = parent.insertItem(itemB);
		int n = parent.getNumItems();
		
		for(int j=n-1;j>itemIndex;j--) {
			Node temp = parent.disconnectChild(j);
			parent.connectChild(j+1,temp);
		}
		
		
		
		newRight.insertItem(itemC);
		newRight.connectChild(0,child2);
		newRight.connectChild(1, child3);
		parent.connectChild(itemIndex+1, newRight);
		
	}
	
	public Node getNextChild(Node theNode,long theValue) {
		int j;
		int numItems = theNode.getNumItems();
		
		for(j=0;j<numItems;j++) {
			if(theValue < theNode.getDataItem(j).dData) {
				return theNode.getChild(j);
			}
		}
		return theNode.getChild(j);
	}
	
	public void displayTree() {
		this.recDisplay(this.root,0,0);
	}
	
	private void recDisplay(Node thisNode,int level,int childNumber) {
		System.out.println("level="+level+" child="+childNumber);
		thisNode.displayNode();
		
		int numItems = thisNode.getNumItems();
		
		for(int j=0;j<numItems+1;j++) {
			Node nextNode = thisNode.getChild(j);
			if(nextNode != null) {
				recDisplay(nextNode,level+1,j);
			}else {
				return;
			}
		}
	}
}