package source;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


/*
 * this class is only a wrapper to invoke the tree constructed by the Node data structure
 * 
 * this class is supposed to build B tree with positive integers ONLY
 * 
 */
public class BTree {

	
	public static void main(String[] args) {
		BTree tree = new BTree();
		
		tree.interactiveDelete();
		//tree.insert();
		//tree.interactiveInsert();

	}
	
	int t = 2;
	/*
	 * split the sample tree
	 * 
	 *                 5
	 *      1,2,3              6, 7, 8           
	 */
	public void splitSampleTree(){
		Node sample = this.createSampleTree();
		sample.treeToString("");

		sample = sample.split(sample, sample.children[0], 0);	
		System.out.println("---------");
		sample.treeToString("");
		System.out.println("---------");
		
		sample = sample.split(sample, sample.children[2], 2);
		sample.treeToString("");
		

	}
	
	/*
	 * split a tree contains only the root
	 */
	public void splitRoot(){
		//create the root
		Node root = new Node(2);
		
		
		for(int i=0;i<3; i++ ){
			root.keys[i] = i+1;
		}
		
		root = root.split(null, root, 0);
		root.treeToString("");
	}
	
	/*
	 * create a full tree with t = 2
	 * 
	 *                 5
	 *      1,2,3              6, 7, 8           
	 */
	private Node createSampleTree(){
		Node root = new Node(t);
		root.keys[0] = 5;
		root.isLeaf = false;
		
		
		//full tree of left node and right node
		Node left = new Node(t);
		Node right = new Node(t);
		
		left.isLeaf = true;
		right.isLeaf = true;
		
		for(int i = 0 ;i< 2*t-1; i++){
			left.keys[i] = i+1;
			right.keys[i] = i+6;
		}	
		
		
		
		root.children[0] = left;
		root.children[1] = right;
		
		return root;
	}
	
	
	public void interactiveDelete(){
		//construct a tree firstly
		Node root = new Node(2);
		
		
		int max = 18;
		
		for(int i = 1; i< max+1; i++){
			root = root.insert(root, i);
			//providing the sample trees
			root.treeToString("");
			System.out.println("--------------------------------");
		}
		
		System.out.println("\n\n");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 try {
			
			//press any key to continue
			while(br.readLine() != "exit" && max > -1){	
				root = root.delete(root, max);
				System.out.println(".............................");
				root.treeToString("");
				System.out.println(".............................");
				max--;
			}
			System.out.println("exit");
			
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	/*
	 * insert values in a noop
	 */
	public void insert(){
		Node root = new Node(2);
	
		for(int i = 1; i< 4; i++){
			root = root.insert(root, i);
			root.treeToString("");
			System.out.println("--------------------------------");
		}
		
		System.out.println("deletion.......");
		root.delete(root, 3);
		root.treeToString("");
	}
	
	
	public void displayKeySize(Node root, String indent){
		System.out.println(indent+root.size);
		int i = 0;
		while(i < 2*root.t && root.children[i] != null){
			displayKeySize(root.children[i], indent+"\t");
			i++;
		}
	}
	
	/*
	 * insert the values provided from a command line
	 */
	public void interactiveInsert(){
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 try {
			System.out.println("create a root");
			Integer a = Integer.parseInt( br.readLine());
			Node root = new Node(t);
			root.keys[0] = a.intValue();
			
			System.out.println("insert new elements");
			while((a = Integer.parseInt( br.readLine())) != -1){	
				root = root.insert(root, a.intValue());
				root.treeToString("");
				System.out.println("\n");
			}
			System.out.println("exit");
			
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
}



class Node{
	/*
	 * the minimal node size is t, the maximum node size is 2*t-1
	 * 
	 * #Every node other than the root must have at least t - 1 keys. 
	 * Every internal node other than the root thus has at least t children. 
	 * If the tree is nonempty, the root must have at least one key.
	 * 
	 * #Every node can contain at most 2t - 1 keys. Therefore, 
	 * an internal node can have at most 2t children. 
	 * We say that a node is full if it contains exactly 2t - 1 keys
	 * 
	 * That is , the leaf size is [t, 2t], the keys size is [t-1, 2t-1]
	 * 
	 * 
	 * 
	 * The methods are not well construced, as each method could operate on other nodes, which is passed 
	 * as a parameter. If we do not want to operate on other nodes, we should not have the node parareter
	 * in all these methods. but I did, shame.
	 */
	int t; 
	int[] keys;
	Node[] children;
	boolean isLeaf;
	int size;
	
	public Node(int t){
		this.t = t;
		keys = new int[2*t-1];//a leaf could have up to 2*t-1 keys
		children = new Node[2*t];//an internal node could have up to 2*t chilren
		
		//represent null key as -1
		//all children are null
		for(int i = 0; i< 2*t-1; i++){
			keys[i] = -1;
			children[i] = null;
		}
		children[2*t-1] = null;
		
		//a node is set to be leaf by default
		isLeaf = true;
		size = 0;
	}
	
	/*
	 * search for @param elem in the tree rooted at @param root
	 * @return true if the elem exists, otherwise, @return false
	 */
	public boolean search(Node root, int elem){
		int i = 0;
		while(i < root.size && root.keys[i] < elem){
			i++;
		}
		if(i < root.size && root.keys[i] == elem){
			//found
			return true;
		}
		else if(root.children[i] != null){
			return search(root.children[i], elem);
		}
		else{
			return false;
		}
	}
	
	
	/*
	 * split the child pointed by the index of parent when child is full
	 * the parent is supposed to be non-full
	 * 
	 * the new parent is returned, which should always be handled by the caller
	 */
	public Node split(Node parent, Node child, int index){
		
		//allocate a new node to hold the other half splitted from child
		Node newNode = new Node(t);
		newNode.isLeaf = child.isLeaf;
		
		//move the values greater than the median, ie., child.keys[t-1] to the new node
		for(int i = t; i < 2*t - 1 ; i++){
			//assign the keys
			newNode.keys[i-t] = child.keys[i];
			child.keys[i] = -1;
			
			//assign the children
			newNode.children[i-t] = child.children[i];
			child.children[i] = null;
		}
		newNode.children[t - 1] = child.children[2*t - 1];
		
		newNode.size = t - 1;
		child.size = t - 1;
				
		/*
		 * move up the median value  to the parent
		 * first, move the keys and pointers one step backward since index(inclusively),
		 * then, insert the median value as the index-th key in the parent
		 */
		if(parent != null){
			parent.children[2*t -1] = parent.children[2*t-2];
			for(int i = 2*t -2 ; i> index; i--){
				parent.keys[i] = parent.keys[i-1];
				parent.children[i] = parent.children[i-1];
			}
			
			parent.keys[index] = child.keys[t-1];
			parent.children[index+1] = newNode;
			parent.children[index] = child;
			parent.size++;
			
		}
		else{
			/*
			 * we are splitting the root, which is the child
			 * the median value would be the only key in the new root
			 * 
			 * and the @parem index is useless
			 */
			Node root = new Node(child.t);
			root.isLeaf = false;
			
			root.keys[0] = child.keys[t-1];
			root.children[0] = child;
			root.children[1] = newNode;
			root.size = 1;
			
			parent = root;
		
		}
		child.keys[t-1] = -1;
		
		//return the parent when it's possble that the parent is modified
		return parent;
	
	
		
	}
	
	
	/*
	 * @param root, the tree 's root
	 * @param elem, the element to be inserted
	 */
	public Node insert(Node root, int elem){
		if(root.isFull()){
			//split the root
			root = root.split(null, root, 0);
		}
		//insert into the appropriate subtree
		root = insertNonFull(root, elem);
		return root;
	}
	
	/*
	 * insert the elem into a leaf, building the tree bottom up
	 * node is supposed to be nonfull, if it's full, we should go recursively to go into its children or split it
	 * 
	 * @param index, the parent's index-th children is elem
	 * @param node, it should have at least one element
	 */
	private Node insertNonFull(Node node, int elem){
		int i = -1;
		
		if(node.isLeaf){
			
			i = 2*t - 2;
			while(i>0 && (node.keys[i] > elem || node.keys[i] == -1) ){
				node.keys[i] = node.keys[i-1];
				i--;
			}
			//so, it's possible to accept duplicated keys
			if(i == 0){
				if(node.keys[0] == -1 ){
					//this is an empty node
					node.keys[0] = elem;
				}
				else if(node.keys[0]>elem){
					int temp = elem;
					elem = node.keys[0];
					node.keys[0] = temp;
					node.keys[1] = elem;
				}
				else{
					node.keys[1] = elem;
				}
			}
			else{
				i++;
				node.keys[i] = elem;	
			}
			node.size++;
			return node;
		}
		
		
		
		// insert into the appropriate subtree that node.keys[i] > elem
		i = 0;
		while (i < 2 * t - 1 && node.keys[i] < elem && node.keys[i] != -1) {
			i++;
		}
		
		if(node.children[i].isFull()){
			node = node.split(node, node.children[i], i);
			if(node.keys[i] > elem){
				insertNonFull(node.children[i], elem);
			}
			else{
				insertNonFull(node.children[i+1], elem);
			}
		}
		else{
			insertNonFull(node.children[i], elem);
		}
		
		return node;

	}
	
	/*
	 * it's possible that the root is replaced or merged, so return the root
	 */
	
	public Node delete(Node root, int elem){
		if(!root.search(root, elem)){
			return root;
		}
		else{
			root = deleteOP(root, elem);
			//shrink the root
			if(root.size == 0){
				root = root.children[0];
			}
			return root;
		}
	}
	
	/*
	 * delete the @parem elem from the tree rooted at @param root
	 */
	public Node deleteOP(Node root, int elem){
		//see if the elem located at the current node
		int i = 0;
		while(i < root.size && root.keys[i] < elem){
			i++;
		}
		
		
		
		if(i >= root.size ||  root.keys[i] != elem ){
			/*
			 * does not exist in this node, traversing down, keys[i] > elem
			 * 
			 * If ci[x] has only t - 1 keys but has an immediate sibling with at least t keys,
			 * give ci[x] an extra key by moving a key from x down into ci[x], 
			 * moving a key from ci[x]'s immediate left or right sibling up into x, 
			 * and moving the appropriate child pointer from the sibling into ci[x].
			 */
			if(root.children[i].size == t -1){
				if(i != 0 && root.children[i-1].size > t-1){
					//delete the largest element k of the sibling
					int k = root.children[i-1].keys[root.children[i-1].size-1];
					root.children[i-1] = root.children[i-1].deleteOP(root.children[i-1], k);
					
					//replace element j = keys[i] by k in the parent
					int j = root.keys[i];
					root.keys[i] = k;
					
					//insert j into the selected children
					root.children[i].insertNonFull(root.children[i], j);
					
				}
				else if(i < 2*t-1 && root.children[i+1]!= null && root.children[i+1].size > t - 1){
					//analog to the first condition
					int k = root.children[i+1].keys[0];
					root.children[i+1] = root.children[i+1].deleteOP(root.children[i+1], k);
					
					int j = root.keys[i];
					root.keys[i] = k;
					
					root.children[i].insertNonFull(root.children[i], j);
				}
				else{
					/*
					 * If ci[x] and both of ci[x]'s immediate siblings have t - 1 keys,
					 * merge ci[x] with one sibling, 
					 * which involves moving a key from x down into the new merged node to become 
					 * the median key for that node.
					 */
					if(i < 2*t ){
						if(i < root.size && root.children[i+1] != null){
							root.merge(root, i);
						}
						else if(i != 0 && root.children[i-1] != null){
							root.merge(root, i-1);
							i--;
						}
						
					}
					else{
						//exceed the boundary
					}
					
					
					
				}
			}
			
			//then, delete the elem in the subtree
			root.children[i] = root.children[i].deleteOP(root.children[i], elem);
		}
		else{
			if(root.isLeaf){
				root.keys[root.size - 1] = -1;
				root.size--;
				while(i < root.size ){
					root.keys[i] = root.keys[i+1];
				}
			}
			else{
				//delete from an internal node
				if( root.children[i].size > t - 1){
					//replace elem with the largest key of the left subtree
					int temp = root.children[i].keys[root.children[i].size-1];
					root.children[i] = root.children[i].deleteOP(root.children[i], temp);
					
					root.keys[i] = temp;
					
				}
				else if(root.children[i+1].size > t - 1){
					//replace elem with the smallest key of the right subtree
					int temp = root.children[i+1].keys[0];
					root.children[i+1] = root.children[i+1].deleteOP(root.children[i+1], temp);
					
					root.keys[i] = temp;
					
				}
				else{
					//merge the two children  and the elem  into one node
					merge(root, i);
					
					//delete the elem from the newly created child
					root.children[i] = root.children[i].deleteOP(root.children[i], elem);
				}
			}
		}
		return root;
	}
	
	/*
	 * merge the root's i-th child and i+1-th child
	 * 
	 * both the children have size t - 1;
	 */
	private void merge(Node root, int i){
		//merge the element from the root to the children
		Node child = root.children[i];
		child.keys[child.size] = root.keys[i];
		
		//merge the sibling into the selected child
		for(int j = t ; j < 2*t - 1; j++){
			child.keys[j] = root.children[i+1].keys[j-t];
			
			child.children[j] = root.children[i+1].children[j-t];
		}
		child.children[2*t-1] = root.children[i+1].children[t-1];
		
		child.size = 2*t - 1;
		
		//re-assign the root's childrens and keys
		for(int j = i; j < root.size - 1; j++){
			root.keys[j] = root.keys[j+1];
			root.children[j+1] = root.children[j+2];
		}
		//remove the last element
		root.keys[root.size-1] = -1;
		root.children[root.size] = null;
		
		root.size--;
	}
	
	
	public boolean isFull(){
		return keys[2*t-2] != -1;
	}
	
	/*
	 * print out the keys only
	 */
	public String nodeToString(String indent){
		//print out the keys
		int i = 0;
		System.out.print(indent);
		while(i<2*t-1 && keys[i] != -1){
			System.out.print(keys[i]+"\t");
			i++;
		}
		System.out.println();
		return null;
	}

	/*
	 * print out the key at the current node as well as its children's keys
	 * 
	 * the children's keys is indented
	 */
	public String treeToString(String indent){
		String nodeStr = nodeToString(indent);
		
		int i = 0;
		while( i < 2*t  && this.children[i] != null ){
			System.out.print(indent);
			nodeStr += children[i].treeToString(indent+"\t");
			i++;
		}
		
		return nodeStr;
	}
}