/*
 *****************************************************************************
 *		File Name: BigString.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;

/**
 *
 * BigString is a class that is similar to String. It is used to represent
 * character strings. It can be used to handle extremely long strings and the
 * efficiency of some operations have an improvement over regular String.
 * Some BigString operations are: printing the BigString, locating the index of
 * parts of the BigString, getting a character at a specified index, comparing
 * BigStrings, concatenating BigStrings.
 * 
 * <br> Example: <br>
 * The following are some of the ways of creating a BigString: <br>
 * <code> StringBuffer sb = new StringBuffer("tuvwxyz"); </code> <br>
 * <code> BigString b1 = new BigString("abcdefg"); </code> <br>
 * <code> BigString b2 = new BigString(sb); </code>
 * @see java.lang.String
 */
public class BigString {

	/**
	 * the length of this BigString
	 */
	private long stringLength;
	
	/**
	 * index where this BigString begins
	 */
	private long start;
	
	/*
	 * btree to store the actual string
	 */
	private BTreeString bt;	
	
	/**
	 * vector to hold possible BigString concatenations
	 */
	private Vector vect = new Vector(0);
	
	/**
	 * index that marks how far in the tree this BigString goes: every
	 * BigString references a b+-tree, but it may not use up the entire
	 * string that this tree holds
	 */
	private long treeLimit;	
	
	/*
	 * CONSTRUCTORS
	 */
	
	/**
	 * Class constructor <br> initializes an empty BigString
	 */ 
	public BigString() {
		stringLength = 0;
		start = 0;
		treeLimit = 0;
		bt = new BTreeString("");
	}
	
	/**
	 * Class constructor <br> initializes a new BigString, by setting the 
	 * contents of the new BigString to the contents of the value passed 
	 * in
	 * @param bigValue	BigString with data to set this BigString
	 * @throws	NullPointerException if <code> bigValue </code> is null
	 * <br> Preconditions: bigValue is non-null
	 */
	public BigString(BigString bigValue) throws NullPointerException{
	
		if(bigValue == null) {
			NullPointerException ne = new NullPointerException();
			throw ne;
		}
		
		this.bt = bigValue.getMyBTree();
		this.start = bigValue.getStart();
		//this.stringLength = bt.getStringLength() - this.start;
		
		treeLimit = bigValue.getTreeLim();
		
		if(bt.getStringLength()-start > bigValue.length() ){
			stringLength = bigValue.length();
		}
		else {
			stringLength = bt.getStringLength() - this.start;
		}
	}
	
	/**
	 * Class constructor <br> initializes a new BigString, by setting the
	 * string value of the BigString to the parameter
	 * @param val	the String that this BigString value's will have <br>
	 * Preconditions: the parameter is non-null
	 */
	public BigString(String val) {
		start = 0;
		stringLength = val.length();
		if (stringLength == 0) treeLimit = 0;
		else treeLimit = stringLength - 1;
		bt = new BTreeString(val);
	}
	
	/**
	 * Class constructor <br> initializes a new BigString, by setting the
	 * string value of the BigString to the parameter 
	 * @param val	the array of characters that this BigString's value
	 *		will have
	 * <br> Preconditions: the parameter is non-null
	 */
	public BigString(char [] val) {
		start = 0;
		stringLength = val.length;
		if(stringLength == 0) treeLimit = 0;
		else treeLimit = stringLength - 1;
		bt = new BTreeString(new String(val));
	}
	
	/**
	 * Class constructor <br> initializes a new BigString, by setting the
	 * string value of the BigString to the parameter
	 * @param val	the StringBuffer contains the String that this 
	 *		BigString's value will have
	 * <br> Preconditions: the parameter is non-null
	 */
	public BigString(StringBuffer val) {
		start = 0;
		stringLength = val.length();
		treeLimit = stringLength - 1;
		bt = new BTreeString(val.toString());
	}
	
	
	
	/**
	 * gets the length of string held in this BigString
	 * @return	Returns the length of the BigString
	 * <br> the length of the BigString is the number of characters 
	 * contained in the value of the string this BigString represents
	 */
	public long length() { return stringLength; }
	
	/**
	 * gets the uppermost index of this BigString's string in the tree
	 * @return 	Returns the limit of the tree for this BigString
	 */
	protected long getTreeLim() { return treeLimit; }
	
	/**
	 * gets the vector of BigString concatenations
	 * @return 	Returns the vector of concatenations for this BigString
	 */
	protected Vector getVect() { return vect; }
	
	/**
	 * gets the index of the first character in this BigString
	 * @return	Returns the starting index for this BigString
	 */
	protected long getStart() { return start; }
	
	/**
	 * gets the b+-tree for this BigString
	 * @return 	Returns the reference to the b+-tree for this BigString
	 */
	protected BTreeString getMyBTree() { return bt; }
	
	/**
	 * concatenates bigString to the end of this BigString
	 * @return	Returns the concatenation of bigString to the end of 
	 *		this BigString in the form of a BigString
	 * @param bigString	the BigString to concatenate to this BigString
	 * @throws	NullPointerException if bigString is null
	 * @see java.lang.String#concat(String)
	 * <br> Example: <br>
	 * <code> b3 = b1.concat(b2); </code> <br>
	 * if b1 and b2 are initialized BigStrings, then b3 is the BigString
	 * that is b1 followed by b2 <br> if the string value of b1 is 
	 * "theFirstBigString" <br> and b2 has string value
	 * "theSecondBigString", then b3 has string value
	 * "theFirstBigStringtheSecondBigString"
	 */
	public BigString concat(BigString bigString) throws NullPointerException
	{
		if(bigString == null) {
			NullPointerException ne = new NullPointerException();
			throw ne;
		}
		else {
			BigString b; // new BigString
			
			// check if bigString is an 'original'
			if(bigString.getVect().size() == 0) {
				b = new BigString(this, bigString);
			}
			else {
				// create a new BigString x
				BigString x = new BigString(bigString);

				b = new BigString(this,x,bigString.getVect());
			}
			return b;
		}
	}
	
	/**
	 * locates the character in the BigString at the given index
	 * @return	Returns the character at the specified index
	 * @param index	the index of the character to be returned
	 * @throws	StringIndexOutOfBoundsException
	 *		if <code>(index < 0 || index > stringLength - 1)</code>
	 * @see java.lang.String#charAt(int)
	 * <br> Example: <br>
	 * if b is a BigString initialized with string value
	 * "oneBigString", then c = b.charAt(3) will give c the value 'B'
	 */
	public char charAt(long index) throws StringIndexOutOfBoundsException
	{
		if(index > stringLength -1 || index < 0) {
			StringIndexOutOfBoundsException se;
			se = new StringIndexOutOfBoundsException();
			throw se;
		}
		else {
			char c;
			
			// this string may not start at index 0; calculate
			// the offset
			long newStart = start + index;
			
			// the character we want is in the tree that this Big-
			// String references
			if(newStart <= treeLimit + 1)
				c = bt.getChar(newStart); 
			
			// otherwise the vector must be checked
			else {
				// make a new offset, which is a new index
				// to start looking at in the BigStrings
				// in the vector
				long newInd = newStart - (treeLimit-start+1);
				
				int k = 0;	// index for vector elements
				BigString bStr;
				boolean found = false;
				do{
					bStr = (BigString)vect.elementAt(k);
					
					// the BigString at vector element k 
					// does not contain the character we
					// are looking for
					if(bStr.length() < newInd) {
						k += 1;
						
						// reseting in the index
						newInd -= bStr.length();
					}
					
					// the kth BigString has the character
					// we want
					else found = true;
				} while(k < vect.size() && !found);
				
				// to get the character we want we must look
				// in the tree of the BigString at element k
				BTreeString tree = bStr.getMyBTree();
				c = tree.getChar(newInd + bStr.getStart());
			}
			
			return c;
		}
	}
	
	/**
	 * To get a substring, of type String, of this BigString
	 * @return	Returns a String which is the substring of the String 
	 *		value of this BigString
	 * @param from	index of the start of the substring
	 * @param to	index of the end of the substring
	 * @throws	StringIndexOutOfBoundsException if the following
	 * 		precondition is not met
	 * <br> Preconditions: start <= from <= to <= start + length
	 */
	protected String substr(long from, long to) throws
		StringIndexOutOfBoundsException
	{
		if(!(start <= from && from <= to && to <= start + stringLength))
		{
			StringIndexOutOfBoundsException se;
			se = new StringIndexOutOfBoundsException();
			throw se;
		}
		
		String s = "";
		long count = 0;	// count keeps track of how much of the string
				// has been accumulated so far
						
		long len = to - from;	// length of substring
		
		// if the btree contains the entire substring then return that
		if(to <= treeLimit + 1) {
			return bt.getString(from, to);
		}
		// otherwise, the remainder of the btree is needed
		else if(from<=treeLimit){
		   	s += bt.getString(from, treeLimit+1);
			count += treeLimit + 1 - from; // **
		}
		
		
		// also some of the contents of BigStrings in the vector may be
		// used
		if( count != len ) {
			int k = 0;
			while(k != vect.size() && count != len) {
				BigString bStr = (BigString)vect.elementAt(k);
				
				// the string of the BigString at k is not long
				// enough; concatenate the entire string from
				// element k to s
				if(len - count > bStr.length()) {
					s = s + bStr.toString();
					count += bStr.length();
					k += 1;
				}
				
				// concatenate to string s the first (len-count)
				// characters
				else {
					s += bStr.substr(bStr.getStart(),
					bStr.getStart() + len - count);
					count = len;
				}
			}
		}
		return s;
	}
	
	/**
	 * gets the String value of the entire BigString
	 * @return	Returns the String value of this BigString
	 */
	public String toString() {
		// calling substr to return the entire string, with parameters
		// the starting index, until the ending index
		return substr(start, start+stringLength);
	}
	
	/**
	 * puts the characters of this BigString that are located
	 * between the specified indices onto the specified OutputStream
	 * @param os	OutputStream to which characters will be output
	 * @param from	index of first character that will be output
	 * @param to	index of last character that will be output
	 * @throws	IOException if there are any errors with OutputStream
	 * @throws	StringOutOfBoundsException if the first precondition is
	 *		not met
	 * <br> Preconditions: start <= from <= to <= start + length, 
	 * OutputStream os is a valid stream, which can to output to
	 */
	protected void output(OutputStream os, long from, long to)
		throws IOException, StringIndexOutOfBoundsException
	{
		if(!(start <= from && from <= to && to <= start+stringLength)){
			StringIndexOutOfBoundsException se;
			se = new StringIndexOutOfBoundsException();
			throw se;
		}
		
		long count = 0;	// count keeps track of how many characters
				// have been output so far
		
		long len = to - from;	// number of char we want output
		
		// if the btree contains all the characters we want to output
		if(to <= treeLimit + 1) {
			bt.printTree(from, to, os);
			return;
		}
		// otherwise, we output the remainder of the btree starting at
		// from
		else if(from <= treeLimit){
		   	bt.printTree(from, treeLimit + 1, os);
			count += treeLimit + 1 - from;
		}
		
		
		// also, some of the contents of the BigStrings in the vector
		// may be output
		if( count != len ) {
			int k = 0;
			while(k != vect.size() && count != len) {
				BigString bStr = (BigString)vect.elementAt(k);
				
				// the string of BigString at k does not have
				// enough characters; output all the characters
				// in BigString bStr
				if(len - count > bStr.length()) {
					bStr.print(os);
					count += bStr.length();
					k += 1;
				}
				
				// output the first (len-count) characters
				else {
					bStr.output(os,bStr.getStart(),
					bStr.getStart() + len - count);
					
					count = len;
				}
			}
		}
		return;
	}
	
	/**
	 * outputs onto the specified OutputStream, the contents of the string
	 * of this BigString
	 * @param os	the OutputStream that characters will be output onto
	 * @throws	IOException if there are any errors with the
	 * 		OutputStream
	 * <br> Preconditions: OutputStream os is a valid stream
	 */
	public void print (OutputStream os) throws IOException {
		// calling output to print the entire string, with parameters
		// the starting index, until the ending index
		output(os, start, start + stringLength);
		return;
	}
	
	/**
	 * gets the substring within the specified indices
	 * @param beginIndex	the index of the first character in the
	 *			substring
	 * @param endIndex	the index of the first character NOT in the
	 *			substring
	 * @throws	StringIndexOutOfBoundsException if beginIndex is less
	 *		than the index of first character or endIndex is
	 *		greater than the length of the string
	 * @return	BigString that contains a string value of that
	 *		substring
	 * @see java.lang.String#substring(int,int)
	 * <br> the starting index is inclusive, the ending index is exclusive
	 */
	public BigString substring(long beginIndex, long endIndex)
		throws StringIndexOutOfBoundsException
	{
		// method to be filled in
		return null;
	}
	
	/**
	 * gets the substring from the specified index to the end of the string
	 * @param beginIndex	the index of the first character in the
	 *			substring
	 * @throws	StringIndexOutOfBoundsException - if beginIndex is less
	 *		than the index of first character 
	 * @return	BigString that contains a string value of that
	 *		substring
	 * @see java.lang.String#substring(int)
	 * <br> the index argument is inclusive
	 */
	public BigString substring(long beginIndex) 
		throws StringIndexOutOfBoundsException
	{
		// method to be filled in
		return null;
	}
	
	/**
	 * optimizes the BigString
	 */
	public void Optimize() {
		// method to be filled in
		return;
	}
	
	/**
	 * determines if this BigString has the same contents as the Object
	 * @param obj	the Object to do the comparison with this BigString
	 * @return	true if <code> obj </code> is non-null and is a
	 		BigString containing the exact character series
	 * @see java.lang.String#equals(Object)
	 */
	public boolean equals(Object obj){
		// method to be filled in
		return false;
	}
	
	/**
	 * compares the string values of two BigStrings lexicographically
	 * @param bigString	the BigString to compare this BigString with
	 * @return	-1 if this BigString is < argument, 0 if this BigString
	 * 		is exactly the same as argument, 1 if this BigString >
	 *		argument
	 * @throws	NullPointerException if <code> bigString </code> is
	 *		null
	 * @see java.lang.String#compareTo(String)
	 * <br>
	 * -1 is returned if the string value of this BigString 
	 * lexicographcally precedes the string value of the argument BigString
	 * <br>
	 * 0 is returned if the string value of this BigString is the same
	 * lexicographcally as the string value of the argument BigString <br>
	 * 1 is returned if the string value of this BigString 
	 * lexicographcally follows the string value of the argument BigString
	 * <br> Example: <br>
	 * BigString b1, b2, b3, b4; <br>
	 * b1 = new BigString("string"); <br>
	 * b2 = new BigString("method"); <br>
	 * b3 = new BigString("class"); <br>
	 * b4 = new BigString("method"); <br>
	 * b4.compareTo(b1) returns -1 <br>
	 * b4.compareTo(b2) returns 0 <br>
	 * b4.compareTo(b3) returns 1
	 */
	public int compareTo(BigString bigString) throws NullPointerException
	{
		// method to be filled in
		return 0;
	}
	
	/**
	 * compares the string values of two BigStrings lexicographically, case
	 * insensitively
	 * @param bigString	the BigString to compare this BigString with
	 * @return	-1 if this BigString is < argument, 0 if this BigString
	 * 		is exactly the same as argument, 1 if this BigString >
	 *		argument (ignoring case)
	 * @throws	NullPointerException if <code> bigString </code> is
	 *		null
	 * @see java.lang.String#compareToIgnoreCase(String)
	 * <br>
	 * -1 is returned if the string value of this BigString 
	 * lexicographcally (when case is ignored) precedes the string value of
	 * the argument BigString <br>
	 * 0 is returned if the string value of this BigString is the same
	 * lexicographcally (when case is ignored) as the string value of the 
	 * argument BigString <br>
	 * 1 is returned if the string value of this BigString lexicographcally
	 * (when case is ignored) follows the string value of the argument 
	 * BigString
	 * <br> Example: <br>
	 * BigString b1, b2, b3, b4; <br>
	 * b1 = new BigString("string"); <br>
	 * b2 = new BigString("meThOd"); <br>
	 * b3 = new BigString("class"); <br>
	 * b4 = new BigString("method"); <br>
	 * b4.compareToIgnoreCase(b1) returns -1 <br>
	 * b4.compareToIgnoreCase(b2) returns 0 <br>
	 * b4.compareToIgnoreCase(b3) returns 1
	 */
	public int compareToIgnoreCase(BigString bigString)
		throws NullPointerException
	{
		// method to be filled in
		return 0;
	}
	
	/**
	 * determines if this BigString has the same contents as the argument,
	 * ignoring case
	 * @param bigString	the BigString to do the comparison with
	 * @return	true if <code> bigString </code> is non-null and is a
	 		BigString containing the exact character series,
			ignoring case
	 * @see java.lang.String#equalsIgnoreCase(String)
	 * <br> Example: <br>
	 * BigString b1, b2, b3, b4; <br>
	 * b1 = new BigString("method"); <br>
	 * b2 = new BigString("meThOd"); <br>
	 * b3 = new BigString("class"); <br>
	 * b4 = new BigString("method"); <br>
	 * b4.equalsIgnoreCase(b1) returns true <br>
	 * b4.equalsIgnoreCase(b2) returns true <br>
	 * b4.equalsIgnoreCase(b3) returns false
	 */
	public boolean equalsIgnoreCase(BigString bigString) {
		// method to be filled in
		return false;
	}
	
	/**
	 * gets the location of the first occurence of the String argument in 
	 * this BigString
	 * @param string	the string to locate
	 * @return	the index of the first character of where in this
	 *		BigString the argument was found, or -1 if the argument
	 *		is not found
	 * @throws	NullPointerException if <code> string </code> is null
	 * @see java.lang.String#indexOf(String)
	 * <br> Example: <br>
	 * BigString b = new BigString("Superman"); <br>
	 * b.indexOf("man") returns 5 <br>
	 * b.indexOf("ape") returns -1
	 */
	public long indexOf(String string) throws NullPointerException {
		// method to be filled in
		return 0;
	}
	
	/**
	 * gets the location of the first occurence of the BigString argument 
	 * in this BigString
	 * @param bigString	the BigString to locate
	 * @return	the index of where in this BigString the argument 
	 *		was found, or -1 if the argument is not found
	 * @throws	NullPointerException if <code> string </code> is null
	 */
	public long indexOf(BigString bigString) throws NullPointerException {
		// method to be filled in
		return 0;
	}
	
	/**
	 * gets the location of the first occurence of the character argument 
	 * in this BigString
	 * @param ch	the character to locate
	 * @return	the index of where in this BigString the argument 
	 *		was found, or -1 if the argument is not found
	 * <br> Example: <br>
	 * BigString b = new BigString("Superman"); <br>
	 * b.indexOf("r") returns 4 <br>
	 * b.indexOf("t") returns -1
	 */
	public long indexOf(char ch) {
		// method to be filled in
		return 0;
	}
	
	private BigString(BigString b1, BigString b2) {
		stringLength = 0;
		setMyContents(b1,b2);
		stringLength = b1.length() + b2.length();
	}
	
	private BigString (BigString b1, BigString b2, Vector v){
		stringLength = 0;
		setMyContents(b1,b2);
		copyVector(v, v.size());
		stringLength = b1.length() + b2.length();
	}
	
	/**
	 * sets variables in this BigString to values in b1 and b2
	 * @param b1	the first BigString
	 * @param b2	the second BigString
	 */
	private void setMyContents(BigString b1, BigString b2){
		bt = b1.getMyBTree();
		start = b1.getStart();
		treeLimit = b1.getTreeLim();
		copyVector(b1.getVect(),b1.getVect().size());
		addElement(b2);
	}
	
	/**
	 * an element by element copy of the vector into this BigString's 
	 * vector
	 * @param v	vector with elements to copy into this BigString's
	 *		vector
	 * @param limit	index of element where copying stops
	 * Preconditions: v is non-null, 0 <= limit <= v.size()
	 */
	private void copyVector(Vector v, int limit) {
		int k = 0;
		BigString temp;
		while(k < limit) {
			addElement((BigString)v.elementAt(k));
			k+=1;
		}
	}
	
	/**
	 * adds the BigString bStr to this BigString's vector
	 * @param bStr	a BigString to add to this BigString's vector
	 */
	private void addElement(BigString bStr) {
		vect.addElement(bStr);
		stringLength += bStr.length();	// the addition of a BigString
						// through concatenation will
						// increase the length of this
						// BigString
	}
}