free hosting   image hosting   hosting reseller   online album   e-shop   famous people 
Free Website Templates
Free Installer

User Manual


Presented by:     Team 20
                             Don Han, g9dhan@cdf
                             Jeff Xing, g0xinzhi@cdf
                             Carol Cheung, g9carolc@cdf
Presented to:     Professor Dave Wartman
                             CSC 408
                             Software Engineering
                             Department Of Computer Science
                             University of Toronto

Presented Date:  Feb 27, 2001


 

                  TABLE OF CONTENTS


1. Class BigString
              1.1 Class Description
              1.2 Constructor Summary
              1.3 Method Summary
              1.4 Constructor Detail
              1.5 Method Detail

2. Class BTreeString
              2.1 Class Description
              2.2 Constructor Summary
              2.3 Method Summary
              2.4 Constructor Detail
              2.5 Method Detail

3. Class LeafNode
              3.1 Class Description
              3.2 Field Summary
              3.3 Constructor Summary
              3.4 Method Summary
              3.5 Field Detail
              3.6 Constructor Detail
              3.7 Method Detail

4. Class ParNode
              4.1 Class Description
              4.2 Field Summary
              4.3 Constructor Summary
              4.4 Method Summary
              4.5 Field Detail
              4.6 Constructor Detail
              4.7 Method Detail
 
 
 
 

1. Class BigString

java.lang.Object
  |
  +--BigString

1.1 Class Description

public class BigString
extends java.lang.Object
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.
Example:
The following are some of the ways of creating a BigString:
StringBuffer sb = new StringBuffer("tuvwxyz");
BigString b1 = new BigString("abcdefg");
BigString b2 = new BigString(sb);
See Also:
String

 
 
1.2 Constructor Summary
BigString()
          Class constructor 
initializes an empty BigString
BigString(BigString bigValue)
          Class constructor 
initializes a new BigString, by setting the contents of the new BigString to the contents of the value passed in
BigString(char[] val)
          Class constructor 
initializes a new BigString, by setting the string value of the BigString to the parameter
BigString(java.lang.String val)
          Class constructor 
initializes a new BigString, by setting the string value of the BigString to the parameter
BigString(java.lang.StringBuffer val)
          Class constructor 
initializes a new BigString, by setting the string value of the BigString to the parameter
1.3 Method Summary
 char charAt(long index)
          locates the character in the BigString at the given index
 int compareTo(BigString bigString)
          compares the string values of two BigStrings lexicographically
 int compareToIgnoreCase(BigString bigString)
          compares the string values of two BigStrings lexicographically, case insensitively
 BigString concat(BigString bigString)
          concatenates bigString to the end of this BigString
 boolean equals(java.lang.Object obj)
          determines if this BigString has the same contents as the Object
 boolean equalsIgnoreCase(BigString bigString)
          determines if this BigString has the same contents as the argument, ignoring case
protected  BTreeString getMyBTree()
          gets the b+-tree for this BigString
protected  long getStart()
          gets the index of the first character in this BigString
protected  long getTreeLim()
          gets the uppermost index of this BigString's string in the tree
protected  java.util.Vector getVect()
          gets the vector of BigString concatenations
 long indexOf(BigString bigString)
          gets the location of the first occurence of the BigString argument in this BigString
 long indexOf(char ch)
          gets the location of the first occurence of the character argument in this BigString
 long indexOf(java.lang.String string)
          gets the location of the first occurence of the String argument in this BigString
 long length()
          gets the length of string held in this BigString
 void Optimize()
          optimizes the BigString
protected  void output(java.io.OutputStream os, long from, long to)
          puts the characters of this BigString that are located between the specified indices onto the specified OutputStream
 void print(java.io.OutputStream os)
          outputs onto the specified OutputStream, the contents of the string of this BigString
protected  java.lang.String substr(long from, long to)
          To get a substring, of type String, of this BigString
 BigString substring(long beginIndex)
          gets the substring from the specified index to the end of the string
 BigString substring(long beginIndex, long endIndex)
          gets the substring within the specified indices
 java.lang.String toString()
          gets the String value of the entire BigString
Methods inherited from class java.lang.Object
clone, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

1.4 Constructor Detail

BigString

public BigString()
Class constructor

initializes an empty BigString

BigString

public BigString(BigString bigValue)
          throws java.lang.NullPointerException
Class constructor

initializes a new BigString, by setting the contents of the new BigString to the contents of the value passed in
 
Parameters:
bigValue - BigString with data to set this BigString
Throws:
java.lang.NullPointerException - if bigValue is null

Preconditions: bigValue is non-null

BigString

public BigString(java.lang.String val)
Class constructor

initializes a new BigString, by setting the string value of the BigString to the parameter
 
Parameters:
val - the String that this BigString value's will have

Preconditions: the parameter is non-null

BigString

public BigString(char[] val)
Class constructor

initializes a new BigString, by setting the string value of the BigString to the parameter
 
Parameters:
val - the array of characters that this BigString's value will have

Preconditions: the parameter is non-null

BigString

public BigString(java.lang.StringBuffer val)
Class constructor

initializes a new BigString, by setting the string value of the BigString to the parameter
 
Parameters:
val - the StringBuffer contains the String that this BigString's value will have

Preconditions: the parameter is non-null
1.5 Method Detail

length

public long length()
gets the length of string held in this BigString
 
Returns:
Returns the length of the BigString

the length of the BigString is the number of characters contained in the value of the string this BigString represents

getTreeLim

protected long getTreeLim()
gets the uppermost index of this BigString's string in the tree
 
Returns:
Returns the limit of the tree for this BigString

getVect

protected java.util.Vector getVect()
gets the vector of BigString concatenations
 
Returns:
Returns the vector of concatenations for this BigString

getStart

protected long getStart()
gets the index of the first character in this BigString
 
Returns:
Returns the starting index for this BigString

getMyBTree

protected BTreeString getMyBTree()
gets the b+-tree for this BigString
 
Returns:
Returns the reference to the b+-tree for this BigString

concat

public BigString concat(BigString bigString)
                 throws java.lang.NullPointerException
concatenates bigString to the end of this BigString
 
Parameters:
bigString - the BigString to concatenate to this BigString
Returns:
Returns the concatenation of bigString to the end of this BigString in the form of a BigString
Throws:
java.lang.NullPointerException - if bigString is null
See Also:

Example:
b3 = b1.concat(b2);
if b1 and b2 are initialized BigStrings, then b3 is the BigString that is b1 followed by b2
if the string value of b1 is "theFirstBigString"
and b2 has string value "theSecondBigString", then b3 has string value "theFirstBigStringtheSecondBigString"

charAt

public char charAt(long index)
            throws java.lang.StringIndexOutOfBoundsException
locates the character in the BigString at the given index
 
Parameters:
index - the index of the character to be returned
Returns:
Returns the character at the specified index
Throws:
java.lang.StringIndexOutOfBoundsException - if (index < 0 || index > stringLength - 1)
See Also:

Example:
if b is a BigString initialized with string value "oneBigString", then c = b.charAt(3) will give c the value 'B'

substr

protected java.lang.String substr(long from,
                                  long to)
                           throws java.lang.StringIndexOutOfBoundsException
To get a substring, of type String, of this BigString
 
Parameters:
from - index of the start of the substring
to - index of the end of the substring
Returns:
Returns a String which is the substring of the String value of this BigString
Throws:
java.lang.StringIndexOutOfBoundsException - if the following precondition is not met

Preconditions: start <= from <= to <= start + length

toString

public java.lang.String toString()
gets the String value of the entire BigString
 
Overrides:
toString in class java.lang.Object
Returns:
Returns the String value of this BigString

output

protected void output(java.io.OutputStream os,
                      long from,
                      long to)
               throws java.io.IOException,
                      java.lang.StringIndexOutOfBoundsException
puts the characters of this BigString that are located between the specified indices onto the specified OutputStream
 
Parameters:
os - OutputStream to which characters will be output
from - index of first character that will be output
to - index of last character that will be output
Throws:
java.io.IOException - if there are any errors with OutputStream
StringOutOfBoundsException - if the first precondition is not met

Preconditions: start <= from <= to <= start + length, OutputStream os is a valid stream, which can to output to

print

public void print(java.io.OutputStream os)
           throws java.io.IOException
outputs onto the specified OutputStream, the contents of the string of this BigString
 
Parameters:
os - the OutputStream that characters will be output onto
Throws:
java.io.IOException - if there are any errors with the OutputStream

Preconditions: OutputStream os is a valid stream

substring

public BigString substring(long beginIndex,
                           long endIndex)
                    throws java.lang.StringIndexOutOfBoundsException
gets the substring within the specified indices
 
Parameters:
beginIndex - the index of the first character in the substring
endIndex - the index of the first character NOT in the substring
Returns:
BigString that contains a string value of that substring
Throws:
java.lang.StringIndexOutOfBoundsException - if beginIndex is less than the index of first character or endIndex is greater than the length of the string
See Also:

the starting index is inclusive, the ending index is exclusive

substring

public BigString substring(long beginIndex)
                    throws java.lang.StringIndexOutOfBoundsException
gets the substring from the specified index to the end of the string
 
Parameters:
beginIndex - the index of the first character in the substring
Returns:
BigString that contains a string value of that substring
Throws:
java.lang.StringIndexOutOfBoundsException - - if beginIndex is less than the index of first character
See Also:

the index argument is inclusive

Optimize

public void Optimize()
optimizes the BigString

equals

public boolean equals(java.lang.Object obj)
determines if this BigString has the same contents as the Object
 
Overrides:
equals in class java.lang.Object
Parameters:
obj - the Object to do the comparison with this BigString
Returns:
true if obj is non-null and is a BigString containing the exact character series
See Also:
String.equals(Object)

compareTo

public int compareTo(BigString bigString)
              throws java.lang.NullPointerException
compares the string values of two BigStrings lexicographically
 
Parameters:
bigString - the BigString to compare this BigString with
Returns:
-1 if this BigString is < argument, 0 if this BigString is exactly the same as argument, 1 if this BigString > argument
Throws:
java.lang.NullPointerException - if bigString is null
See Also:

-1 is returned if the string value of this BigString lexicographcally precedes the string value of the argument BigString
0 is returned if the string value of this BigString is the same lexicographcally as the string value of the argument BigString
1 is returned if the string value of this BigString lexicographcally follows the string value of the argument BigString
Example:
BigString b1, b2, b3, b4;
b1 = new BigString("string");
b2 = new BigString("method");
b3 = new BigString("class");
b4 = new BigString("method");
b4.compareTo(b1) returns -1
b4.compareTo(b2) returns 0
b4.compareTo(b3) returns 1

compareToIgnoreCase

public int compareToIgnoreCase(BigString bigString)
                        throws java.lang.NullPointerException
compares the string values of two BigStrings lexicographically, case insensitively
 
Parameters:
bigString - the BigString to compare this BigString with
Returns:
-1 if this BigString is < argument, 0 if this BigString is exactly the same as argument, 1 if this BigString > argument (ignoring case)
Throws:
java.lang.NullPointerException - if bigString is null
See Also:

-1 is returned if the string value of this BigString lexicographcally (when case is ignored) precedes the string value of the argument BigString
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
1 is returned if the string value of this BigString lexicographcally (when case is ignored) follows the string value of the argument BigString
Example:
BigString b1, b2, b3, b4;
b1 = new BigString("string");
b2 = new BigString("meThOd");
b3 = new BigString("class");
b4 = new BigString("method");
b4.compareToIgnoreCase(b1) returns -1
b4.compareToIgnoreCase(b2) returns 0
b4.compareToIgnoreCase(b3) returns 1

equalsIgnoreCase

public boolean equalsIgnoreCase(BigString bigString)
determines if this BigString has the same contents as the argument, ignoring case
 
Parameters:
bigString - the BigString to do the comparison with
Returns:
true if bigString is non-null and is a BigString containing the exact character series, ignoring case
See Also:

Example:
BigString b1, b2, b3, b4;
b1 = new BigString("method");
b2 = new BigString("meThOd");
b3 = new BigString("class");
b4 = new BigString("method");
b4.equalsIgnoreCase(b1) returns true
b4.equalsIgnoreCase(b2) returns true
b4.equalsIgnoreCase(b3) returns false

indexOf

public long indexOf(java.lang.String string)
             throws java.lang.NullPointerException
gets the location of the first occurence of the String argument in this BigString
 
Parameters:
string - the string to locate
Returns:
the index of the first character of where in this BigString the argument was found, or -1 if the argument is not found
Throws:
java.lang.NullPointerException - if string is null
See Also:

Example:
BigString b = new BigString("Superman");
b.indexOf("man") returns 5
b.indexOf("ape") returns -1

indexOf

public long indexOf(BigString bigString)
             throws java.lang.NullPointerException
gets the location of the first occurence of the BigString argument in this BigString
 
Parameters:
bigString - the BigString to locate
Returns:
the index of where in this BigString the argument was found, or -1 if the argument is not found
Throws:
java.lang.NullPointerException - if string is null

indexOf

public long indexOf(char ch)
gets the location of the first occurence of the character argument in this BigString
 
Parameters:
ch - the character to locate
Returns:
the index of where in this BigString the argument was found, or -1 if the argument is not found

Example:
BigString b = new BigString("Superman");
b.indexOf("r") returns 4


2. Class BTreeString

java.lang.Object
  |
  +--BTreeString

2.1 Class Description

public class BTreeString
extends java.lang.Object
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.

2.2 Constructor Summary
BTreeString(java.lang.String string)
          Construct a B+ tree which holds the string that is passed in.
2.3 Method Summary
 char getChar(long index)
          Returns the character of the string stored in the tree at position index, beginning with 0.
 java.lang.String getString(long beginIndex, long endIndex)
          Return a string that is stored in the tree, containing the characters from beginIndex to endIndex - 1.
 long getStringLength()
          Returns the length of the string in the tree
 void printTree(long beginIndex, long endIndex, java.io.OutputStream os)
          Output the string, that is stored in the tree containing the characters from beginIndex to endIndex - 1, one leaf by one to stdout.
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

2.4 Constructor Detail

BTreeString

public BTreeString(java.lang.String string)
Construct a B+ tree which holds the string that is passed in.
2.5 Method Detail

getString

public java.lang.String getString(long beginIndex,
                                  long endIndex)
                           throws java.lang.StringIndexOutOfBoundsException
Return a string that is stored in the tree, containing the characters from beginIndex to endIndex - 1.

printTree

public void printTree(long beginIndex,
                      long endIndex,
                      java.io.OutputStream os)
               throws java.lang.StringIndexOutOfBoundsException,
                      java.io.IOException
Output the string, that is stored in the tree containing the characters from beginIndex to endIndex - 1, one leaf by one to stdout.

getChar

public char getChar(long index)
Returns the character of the string stored in the tree at position index, beginning with 0.

getStringLength

public long getStringLength()
Returns the length of the string in the tree

 

3. Class LeafNode

java.lang.Object
  |
  +--LeafNode

3.1 Class Description

public class LeafNode
extends java.lang.Object
LeafNode holds a piece of string in a character array, and a pointer to its younger sibling. It provides the services that the the BTreeString requires.

3.2 Field Summary
static int SMALL_STRING_LENGTH
          The maximum length of string that I can hold.
3.3 Constructor Summary
LeafNode(char[] value, long k)
          Construct a new leaf.
3.4 Method Summary
 char getElementAt(int i)
          Return the character of the char array at index i.
 LeafNode getNext()
          Return my younger sibling.
 void setNext(LeafNode theNext)
          Link me and my younger sibling.
 java.lang.String stringBetween(int begin, int end)
          Return a new string representing the value of elements between the 'begin' and 'end' indice.
 java.lang.String toString()
          Return a new string representing the value of elements.
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

3.5 Field Detail

SMALL_STRING_LENGTH

public static final int SMALL_STRING_LENGTH
The maximum length of string that I can hold.
3.6 Constructor Detail

LeafNode

public LeafNode(char[] value,
                long k)
Construct a new leaf. precondition: value.length <= SMALL_STRING_LENGTH.
3.7 Method Detail

getNext

public LeafNode getNext()
Return my younger sibling.

setNext

public void setNext(LeafNode theNext)
Link me and my younger sibling.

getElementAt

public char getElementAt(int i)
Return the character of the char array at index i. Precondition: 0<= i < SMALL_STRING_LENGTH

toString

public java.lang.String toString()
Return a new string representing the value of elements.
 
Overrides:
toString in class java.lang.Object

stringBetween

public java.lang.String stringBetween(int begin,
                                      int end)
Return a new string representing the value of elements between the 'begin' and 'end' indice. precondition: 0 <= begin <= end <= elements.length

 

4. Class ParNode

java.lang.Object
  |
  +--ParNode

4.1 Class Description

public class ParNode
extends java.lang.Object
ParNode holds information of a parent node. It provides the services that the BTreeString requires.

4.2 Field Summary
static int ORDER
          The order of the tree.
4.3 Constructor Summary
ParNode()
          Class constructor
4.4 Method Summary
 long getKeyAt(int i)
          Return my key at index i.
 long getLastKey()
          Return my last key.
 LeafNode getLeafAt(int i)
          Return my leaf child at index i.
 ParNode getNextLevelAt(int i)
          Return my ParNode child at index i.
 int nextAvailable()
          returns the index of the next available slot for a child
 void setLeafNode(long newKey, LeafNode leaf)
          Set a new key and point to my leaf child 'par'.
 void setParNode(long newKey, ParNode par)
          Set a new key and point to my ParNode child 'par'.
 void updateLastKey(long key)
          Replace my last key with 'key'.
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

4.5 Field Detail

ORDER

public static final int ORDER
The order of the tree.
4.6 Constructor Detail

ParNode

public ParNode()
Class constructor
4.7 Method Detail

nextAvailable

public int nextAvailable()
returns the index of the next available slot for a child

updateLastKey

public void updateLastKey(long key)
Replace my last key with 'key'.

getLastKey

public long getLastKey()
Return my last key.

getLeafAt

public LeafNode getLeafAt(int i)
Return my leaf child at index i. precondition: 0 <= i < ORDER

getNextLevelAt

public ParNode getNextLevelAt(int i)
Return my ParNode child at index i. precondition: 0<= i < ORDER

getKeyAt

public long getKeyAt(int i)
Return my key at index i. precondition: 0 <= i < ORDER

setParNode

public void setParNode(long newKey,
                       ParNode par)
Set a new key and point to my ParNode child 'par'.

setLeafNode

public void setLeafNode(long newKey,
                        LeafNode leaf)
Set a new key and point to my leaf child 'par'.
 Class Tree Deprecated Index Help
 PREV CLASS   NEXT CLASS FRAMES  NO FRAMES
SUMMARY:  INNER | FIELD | CONSTR | METHOD DETAIL:  FIELD | CONSTR | METHOD