import java.io.*;
import java.util.*;
public class Btree {
    String table; //表名
    String index; //索引名
    String attribute; //屬性名
    int length;//屬性長度
    long total;//索引鍵值總數
    int type;//屬性類型
    long rootpos;//根節點地址
    int heigth;//樹當前高度
    long nodenumber; //節點個數
    long newpos; //空節點指針
    BufferManager buffer;
    public Btree(String indexname, BufferManager bf){
        buffer= bf;
        index = indexname;
    	try{
    		long current = 0;
    	    int length;
    	    byte[] name;
    	    RandomAccessFile indexlog = new RandomAccessFile(new File("indexlog.log"),"rws");
    	    while(current<indexlog.length()){
    	    	indexlog.seek(current);
    	    	length = indexlog.read();
    	    	if(length==0){
    	    		current = current+1533;
    	    		continue;
    	    	}
    	    	name = new byte[length*2];
    	    	indexlog.read(name);
    	    	if(index.equalsIgnoreCase(new String(name,"UTF16")))
    	    		break;
    	    	current = current+1533;
    	    }
    	    if(current>indexlog.length()){
    	    	indexlog.close();
    	    }
    	    else{
    	        indexlog.seek(current+511);
    	        length = indexlog.read();
    	        name = new byte[length*2];
    	        indexlog.read(name);
    	        table = new String(name, "UTF16");
    	        indexlog.seek(current+1022);
    	        length = indexlog.read();
    	        name = new byte[length*2];
    	        indexlog.read(name);
    	        attribute = new String(name, "UTF16");
    	        RandomAccessFile indexfile = new RandomAccessFile(new File(index),"rws");
    	        total = indexfile.readLong();
    	        type = indexfile.read();
    	        this.length = indexfile.read()*2;
    	        rootpos = indexfile.readLong();
         	    heigth = indexfile.readInt();
    	        nodenumber = indexfile.readLong();
    	        newpos = indexfile.readLong();
    	        indexfile.close();
    	    }
    	}catch(Exception e){
    		System.out.println("構建B+樹失敗");
    	}
    }
    public boolean insert(Keyword K, long P){
    	BtreeNode L;
    	if(rootpos == 0){
    		L = newNode(true, type, length, 0);
    		heigth++;
    		rootpos = L.getAddress();
    	}
    	else{
    		L = insertsearch(K);
    		if(L.search(K)>=0){
    			System.out.println("某unique屬性值已存在，不能重復");
    			return false;
    		}
    	}
    	if(L.indexno<L.max){
    		L.insert(K,P);
    	}
    	else{
    		BtreeNode newL = newNode(true, type, length, L.parent);
    		nodenumber++;
    		L.insert(K,P);
            int half = (L.indexno+1)/2;
            for(int i=half;i<=L.max; i++){
            	newL.address.add(L.address.get(i));
            	newL.keyentry.add(L.keyentry.get(i));
            	newL.indexno++;
            }
            newL.address.add(L.address.get(L.max+1));
            for(int i=half;i<=L.max; i++){
            	L.address.removeLast();
            	L.keyentry.removeLast();
            	L.indexno--;
            }
            L.address.removeLast();
            L.address.addLast(new Long(newL.getAddress()));
            Keyword minK = newL.keyentry.getFirst();
            L.updata();
            newL.updata();
            insert_in_parent(L,minK,newL);
    	}
    	total++;
    	updata();
    	return true;
    }
    public void insert_in_parent(BtreeNode N, Keyword K, BtreeNode newN){
    	if(N.getAddress()==rootpos){
    		BtreeNode rootNode = newNode(false, type, length, 0);
    		rootNode.address.add(N.getAddress());
    		rootNode.address.add(newN.getAddress());
    		rootNode.keyentry.add(K);
    		rootNode.indexno++;
    		heigth++;
    		nodenumber++;
    		rootNode.updata();
    		N.parent = newN.parent = rootNode.getAddress();
    		N.updata();
    		newN.updata();
    		rootpos = rootNode.getAddress();
    		return;
    	}
        BtreeNode P = getNode(N.parent);
        if(P.indexno<P.max){
        	P.insert(K,newN.getAddress(),true);
        	P.updata();
        }
        else{
        	P.insert(K,newN.getAddress(),true);
        	int half = (P.max+1)/2;
        	BtreeNode newT = newNode(false,type,length,P.parent);
        	nodenumber++;
        	for(int i=half;i<=P.max ; i++){
        		newT.address.add(P.address.get(i));
        		newT.keyentry.add(P.keyentry.get(i));
        		newT.indexno++;
        	}
        	newT.address.add(P.address.get(P.max+1));
        	for(int i=half; i<=P.max ; i++){
        		P.address.removeLast();
        		P.keyentry.removeLast();
        		P.indexno--;
        	}
        	P.address.removeLast();
        	Keyword newK = P.keyentry.getLast();
        	P.keyentry.removeLast();
        	P.indexno--;
        	P.updata();
        	newT.updata();
        	for(int i=0;i<=newT.indexno;i++){
        		BtreeNode b = getNode(newT.address.get(i));
        		b.parent = newT.getAddress();
        		b.updata();
        	}
        	insert_in_parent(P,newK,newT);
        }
    }
    public boolean delete(Keyword K){
    	BtreeNode L = insertsearch(K);
    	if(L.search(K)<0)
    		return false;
    	delete_entry(L,K);
    	total--;
    	updata();
    	return true;
    }
    public void delete_entry(BtreeNode N, Keyword K){
    	N.delete(K);
    	if(N.getAddress()==rootpos&&N.indexno==0){
    		rootpos = N.address.get(0);
    		N.address.removeFirst();
    		N.updata();
    		updata();
    		heigth--;
    	}
    	else if(N.indexno+1<(N.max+2)/2&&N.getAddress()!=rootpos){
    		BtreeNode parent = getNode(N.parent);
    		nodenumber--;
    		int add = parent.search(N.getAddress());
    		BtreeNode brotherN;
    		Keyword newK;
    		if(add>0){
    			brotherN = getNode(parent.address.get(add-1));
    			newK = parent.keyentry.get(add-1);
    		}
    		else{
    			brotherN = getNode(parent.address.get(add+1));
    			newK = parent.keyentry.get(add);
    		}
    		if(N.indexno+brotherN.indexno<= N.max){
    			if(add==0){
    				BtreeNode temp = brotherN;
    			    brotherN = N;
    			    N = temp;
    			}
    			if(!N.isleaf){
    				brotherN.keyentry.addLast(newK);
    				brotherN.indexno++;
    				for(int i = 0;i < N.indexno ;i++){
    					brotherN.address.addLast(N.address.get(i));
    					BtreeNode tempnode = getNode(brotherN.address.getLast().longValue());
    					tempnode.parent = brotherN.getAddress();
    					tempnode.updata();
    					brotherN.keyentry.addLast(N.keyentry.get(i));
    					brotherN.indexno++;
    				}
    				brotherN.address.addLast(N.address.get(N.indexno));
    				BtreeNode tempnode = getNode(brotherN.address.getLast().longValue());
    				tempnode.parent = brotherN.getAddress();
    				tempnode.updata();
    				brotherN.updata();
    			}
    			else{
    				for(int i = 0;i < N.indexno ;i++){
    					brotherN.address.add(brotherN.indexno, N.address.get(i));
    					brotherN.keyentry.addLast(N.keyentry.get(i));
    					brotherN.indexno++;
    				}
    				brotherN.address.set(brotherN.indexno, N.address.get(N.indexno));	
    				brotherN.updata();
    			}
    			if(add==0){
    				parent.address.set(add+1,parent.address.get(add));
    			}
    			else{
    				parent.address.set(add,parent.address.get(add-1));
    			}
    			brotherN.updata();
    			parent.updata();
    			delete_entry(parent, newK);
    		}