/*
 *****************************************************************************
 *		File Name: BTreeString.java
 *		Purpose: class represents BigString
 *		Authors: Han Don, Jeff Xing, Carol Cheung
 *		Version: 1
 *		Last Date Updated: Feb. 27, 2001
 ****************************************************************************/

import java.io.*;
import java.util.Vector;

/**
 *  BTreeString holds a (ususlly long) string in a B+ tree. There 
 *  two type of nodes in the tree: parent nodes and leaves. A parent 
 *  node holds only the keys and pointers that points to the next level.
 *  A leaf contain a piece of string and a pointer to its successor
 *  where applicapable, all the leaves are linked.
 *  BTreeString supports following operations:
 *  	Build a B+ tree that holds a string;
 *		Return the string it holds;
 *		Output the string leaf by leaf;
 *		Return a character that is held in the string 
 *			at the position specified.
 */
public class BTreeString{

	/**
	 *  The total length of string in this BTree.
	 */
	private long stringLength;
	
	/**
	 *  The height of the BTree.
	 */
	private int height;
	
	/**
	 *  The root of the BTree if the tree has only one node.
	 */
	private LeafNode leafRoot;
	
	/**
	 *  The root of the BTree if the tree has more than one nodes.
	 */
	private ParNode parRoot;
	
	/**
	 *  True if the root is a ParNode.
	 */
	private boolean isRootAParNode;
	
	/**
	 *  The maximum length of a LeafNode string.
	 */
	private final static int LEAF_LENGTH = LeafNode.SMALL_STRING_LENGTH;
	
	/**
	 *  The order of the tree.
	 */
	private final static int ORDER = ParNode.ORDER;
		
	/**
	 *  Construct a B+ tree which holds the string 
	 *  that is passed in.
	 */
	public BTreeString(String string) {
	
		// the previous position, current position and next position.
		long prevPos, pos, nextPos;
		
		// number of leaves in the tree, starting from 0.
		long nodeCount = 0; 
		stringLength = string.length();
		
		// The char array holding a piece of string.
		char [] chArray = new char[LEAF_LENGTH];

		// get the stopping point and create a LeafRoot.
		if (stringLength < LEAF_LENGTH)
			nextPos = stringLength;
		else
			nextPos = LEAF_LENGTH;
		
		for (pos = 0; pos < nextPos; pos++) {
			chArray[(int)pos] = string.charAt((int)pos);
		}
		
		leafRoot = new LeafNode(chArray, nodeCount);
		height = 1;
		nodeCount++;
		
		// append the rest of the string to the tree.
		while (nextPos < stringLength) {
			prevPos = pos;					
			char [] ch = new char[LEAF_LENGTH];

			nodeCount++;
			if (stringLength < (nodeCount*LEAF_LENGTH))
				nextPos = stringLength;
			else
				nextPos = nodeCount * LEAF_LENGTH;

			for (int i = 0; i < (nextPos-prevPos); i++) {
				ch[i] = string.charAt(((int)pos));
				pos++;
			}
			append(ch, nodeCount-1);
		}
	}

	
		 
	/**
	 *  Return a string that is stored in the tree, containing the 
	 *  characters from beginIndex to endIndex - 1.
	 */	 
	public String getString(long beginIndex, long endIndex) throws
	 	StringIndexOutOfBoundsException
	{ 
	
		// beginning, ending and current keys of leaves that contain the
		// string to be returned.
		long beginKey, endKey, curK;
	    
		String s = "";	// the string to be returned.
		LeafNode ln;	// a leaf.
	    
		// get the beginning leaf. 
		ln = searchLeaf(beginIndex);
		    
		// find out the key of node which we start from
		beginKey = (long) Math.floor(beginIndex/LEAF_LENGTH);
	    
		// find out the key of node which we stop by
		endKey = (long) Math.floor(endIndex/LEAF_LENGTH);    
	    
		// simply return the string if it is stored in one leaf.
		if(beginKey == endKey)
			return ln.stringBetween(
				(int)(beginIndex-LEAF_LENGTH*beginKey),
				(int)(endIndex-LEAF_LENGTH*endKey));
		
		else
			s += ln.stringBetween(
			(int)(beginIndex-LEAF_LENGTH*beginKey), LEAF_LENGTH);

		curK = beginKey;
	    
		// Append the leaves between the begin and end keys 
		// exclusive to the string.
		while (curK < (endKey-1)) {		
			ln = ln.getNext();	
			s += ln.toString();
			curK++;
		}
		
		// Append the last leaf.
		if ((endIndex - endKey*LEAF_LENGTH) > 0) {
			ln = ln.getNext();
			s += ln.stringBetween(0, 
				(int)(endIndex - endKey * LEAF_LENGTH+1));
		}
		
		return s;
	 }

	 
 	/**
	 *  Output the string, that is stored in the tree containing 
	 *  the characters from beginIndex to endIndex - 1, one leaf 
	 *  by one to stdout.
	 */
 	public void printTree(long beginIndex, long endIndex, OutputStream os) 
 		throws StringIndexOutOfBoundsException, IOException
	{ 
		// beginning, ending and current keys of leaves that 
		// contain the string to be output.
		long beginKey, endKey, curK;
	    
		String s = "";	// the string to be returned.
		LeafNode ln;	// a leaf.
	    
		// get the beginning leaf. 
		ln = searchLeaf(beginIndex);
		    
		// find out the key of node which we start from
		beginKey = (long) Math.floor(beginIndex/LEAF_LENGTH);
	    
		// find out the key of node which we stop by
		endKey = (long) Math.floor(endIndex/LEAF_LENGTH);    
	    
		// simply return the string if it is stored in one leaf.
		if(beginKey == endKey) {
			os.write((ln.stringBetween(
				(int)(beginIndex-LEAF_LENGTH*beginKey),
	      			(int)(endIndex-LEAF_LENGTH*endKey)))
				.getBytes());
			return;
		}
		
		else
			os.write((ln.stringBetween(
			(int)(beginIndex-LEAF_LENGTH*beginKey), LEAF_LENGTH))
			.getBytes());

		curK = beginKey;
		// output the leaves between the begin and end keys 
		// exclusive.
		while (curK < (endKey-1)) {		
			ln = ln.getNext();
			os.write((ln.toString()).getBytes());
			curK++;
		}
		// output the last leaf.
		if ((endIndex - endKey*LEAF_LENGTH) > 0) {
			ln = ln.getNext();
			os.write((ln.stringBetween(0,
			(int)(endIndex - endKey * LEAF_LENGTH))).getBytes());
		}
	 }
	 
	 
	/**
	 *  Returns the character of the string stored in the tree 
	 *  at position index, beginning with 0.
	 */
	public char getChar(long index) {
		char c = ' ';
		LeafNode ln;
		long beginKey;
	    
		// get the leaf that contains the char at position index. 
		ln = searchLeaf(index);
	    
		// find out the key of node which we start from
		beginKey = (long) Math.floor(index/LEAF_LENGTH);
		c = ln.getElementAt((int)(index-LEAF_LENGTH*beginKey));
	
		return c;
	}

	
	/**
	 * Returns the length of the string in the tree
	 */
	public long getStringLength() { return stringLength; }
	
	 
	/**
	 *  Append a LeafNode to the tree.
	 */
	private void append(char [] value, long numNodes) {
	 	Vector v;
	 	if (numNodes > 0)
			v = findLeaf(numNodes-1);
		else {
			// System.out.println("numNodes-1 < 0");
			return;
		}
		
		LeafNode lastLeaf = (LeafNode)v.elementAt(height-1);
		LeafNode newLastLeaf = new LeafNode(value, numNodes);
		
		// link the new lastLeaf with the old last leaf.
		lastLeaf.setNext(newLastLeaf);

		updateTree(v, newLastLeaf, null, (height-1), numNodes);
	 }

	 
	/**
	 *  Update the tree when a new leaf is appened to the tree.
	 */
	private void updateTree(Vector v, LeafNode leaf, ParNode par, 
	 				int curLevel, long key) {
		
		// next available slot for a ParNode. pos >= 0 if
		// there exist a slot.
		int pos;	
		

		// check parameters. should always be false.
		if (curLevel > (height-1) || (leaf != null && par != null)  
				|| (parRoot != null && leafRoot != null) 
				|| (leaf == null && par == null) || key <= 0 
				|| (parRoot == null && leafRoot == null))
			System.out.println("updateTree: wrong in parameters!");

		
		// My sibling is a leafRoot
		if (leaf != null && height == 1) {
			if (leafRoot == null) {
				// System.out.println("leafRoot is null!");
				return;
			}
			
			//create a parRoot
			parRoot = new ParNode();
			LeafNode aLeaf = leafRoot;
			
			// let the new root point to its children.
			parRoot.setLeafNode((key-1), aLeaf);			
			parRoot.setLeafNode(key, leaf);
			leafRoot = null;
			height++;
			if (!isRootAParNode)
				isRootAParNode = true;
			return;
		}
		
		// My parent is a parRoot.
		else if (curLevel == 1) {
			if (parRoot == null) {
				// System.out.println("parRoot is null!");
				return;
			}		
			
			pos = parRoot.nextAvailable();
			
			if (pos >= 0) {
				//My children are leaves.
				if (leaf != null) 
					parRoot.setLeafNode(key, leaf);
				
				//my children are parrent nodes as well.
				else 
					parRoot.setParNode(key, par);
			}
			
			// we need a new parRoot.
			else {
				ParNode p = new ParNode();	// the new root
				long rootKey = parRoot.getLastKey();
				ParNode pNode = new ParNode();
				
				// I'm a leaf.
				if (leaf != null) 
						pNode.setLeafNode(key, leaf);
				
				// I'm a parent node.	
				else 
					pNode.setParNode(key,par);
					
				// let the new root point to its children.	
				p.setParNode(rootKey, parRoot);
				p.setParNode(key, pNode);
					
				// update height and assign parRoot to new root
				height++;					
				parRoot = p;
			}
			
			return;
		}

		
		// I am a leafNode and my parent is not the root.
		else if (leaf != null && (height-1) == curLevel && curLevel > 1)
		{
			
			ParNode pNode = (ParNode)v.elementAt(curLevel - 1);
			pos = pNode.nextAvailable();
			
			if (pos >= 0) {
				pNode.setLeafNode(key, leaf);
				// update the key of the upper level.
				updateKey(v, curLevel-1, key);
				return;
			}
			
			// We need a new parNode.
			else {
				ParNode newParNode = new ParNode();
				newParNode.setLeafNode(key, leaf);
				// update the upper level.
				updateTree(v, null, newParNode, curLevel-1, 
					key);
			}
		}
		
		// I am a ParNode and my parent is not the root.
		else if (par != null && curLevel > 1) {
			ParNode pNode = (ParNode)v.elementAt(curLevel - 1);
			pos = pNode.nextAvailable();
			
			if (pos >= 0) {
				pNode.setParNode(key, par);
				// update the key of the upper level.
				updateKey(v, curLevel-1, key);
				return;
			}
			
			// We need a new parNode.
			else {
				ParNode newParNode = new ParNode();
				newParNode.setParNode(key, par);
				// update the upper level.
				updateTree(v, null, newParNode, curLevel-1,
					key);
			}
		}
		
		// something wrong, should never happen.
		else {
			/*
			System.out.println("wrong in the bottom of updateTree");
			*/
			return;
		}
	}


	/**
	 *  Update the last key of the rightest node of each level,
	 *  beginning from curLevel and ending at the root.
	 */
	private void updateKey(Vector v, int curLevel, long key) {
		int level = curLevel;
		
		// Go all the way up until the root, and update the 
		// key.
		while (level >= 0) {
			ParNode par = (ParNode)v.elementAt(level);
			par.updateLastKey(key);
			level--;
		}
	 }


	/**
 	 *  Returns the LeafNode containing the characters at index.
 	 */
	private LeafNode searchLeaf(long index) 
  	{
    		// return the root if there is only one leaf in the tree.
   	 	if (!isRootAParNode) return leafRoot;
    
    		LeafNode leaf = null;
		ParNode par = parRoot;
		
		// Get the key of the leaf.
		long key = (long) Math.floor(index/LEAF_LENGTH);
		
		// Go down the tree by following the key until we
		// get the leaf.
		while(leaf == null) {
	      		int k; 
			boolean found = false;
			for(k = 0; k < ORDER && !found; k++) {
				if(par.getKeyAt(k) >= key) {
					found = true;
					if(par.getLeafAt(0) == null) 
						par = par.getNextLevelAt(k);
	      				else 
	      					leaf = par.getLeafAt(k);
				}
	      		}
	   	}
	   	return leaf;	
 	}
	 
	/**
	 *  Return a vector that holds the path of nodes
	 *  whose keys are equal to beginKey.
	 */
	private Vector findLeaf(long beginKey) {
		Vector vec = new Vector();
    		
		// Simply return the root if the tree has only one node.
    		if (!isRootAParNode) {
			vec.addElement(leafRoot);
      			return vec;
    		}

      		// Add the root to the vector.
      		LeafNode leaf = null;
      		ParNode par = parRoot;
      		vec.addElement(parRoot);
     
      		// Add the rest of nodes to the vector, down to the leaf.
      		while(leaf == null) {     			
			int k = 0; 
			boolean found = false;
			
			// Find the position of the .
			while(k < ORDER && !found) {
           			if(par.getKeyAt(k) == beginKey) 
	     				found = true;
				else
					k++;
	 		}
				
			if(par.getLeafAt(0) == null) {
	   			par = par.getNextLevelAt(k);
				vec.addElement(par);
	 		}
	 		else {
	   			leaf = par.getLeafAt(k);
	   			vec.addElement(leaf);
	 		}
      		}
      		return vec;		    	   
 	}

}