Classes BTree, BinaryTree, Bag, Set, and IdentitySet implement the Collection interface, which contains methods for the insertion, retrieval, and removal of elements.
Class BTree (for balanced tree) represents a group of ordered elements. Duplicates are not allowed. The elements are ordered according to a Comparator supplied when the tree is constructed.
Unlike class BinaryTree, which implements a binary search tree as described below, class BTree is automatically balanced, resulting in faster retrieval at the cost of slower insertion and deletion. (BinaryTree requires you to call the method balance() to balance the tree.)
In class BTree, nodes are never allowed to have less than a certain number of items, called the order of the tree. The default order is 50. Because many keys are held in a single node, class BTree tends to fragment memory less and is well suited for collecting a large number of elements.
The following example, given in its entirety in BTreeExample.java, finds all the prime numbers in the range specified by the user and inserts them into a BTree using the Sieve of Eratosthenes. The user can then test numbers within the range for primality by lookup.
NOTE: Complete code for this example is located in the examples directory created for your installation of Tools.h++ Professional. The "Examples" chapter in Part V, "Resources," describes the location of that directory, or you can check the online build guide for your installation media.
BTreeExample
BTree primes = new BTree(nc);
int[] numbers = new int[(int)limit];
int i = -1;
// fill the array with numbers
while ( ++i < limit ) numbers[i] = i;
// now find the primes
i = 2;
while (i < limit ) {
primes.insert(new Integer(i));
for (int j=i+i; j < limit; j+=i) numbers[j] = 0;
while ( ++i < limit && numbers[i] == 0 );
}
System.out.println("Found " + primes.size() + " primes.\n");
A BTree is a good choice in this case because of the potentially large collection, with elements inserted in order. Once the BTree is filled, you can test if some integer num is prime. A BTree is particularly efficient in this sort of write-once/read-many situation:
if (primes.contains(new Integer(num))) {
System.out.println( "\n" + num + " is a prime number!\n");
}
else {
System.out.println( "\n" + num + " is not a prime number.\n");
}
This class implements a binary search tree, and maintains elements in sorted order according to a Comparator object given at construction. Unlike class BTree, class BinaryTree allows duplicates. BinaryTree is great for sorting and searching when efficiency in both space and time is required. It works best when items are inserted in random order; otherwise it degenerates into a sorted, linked list.
Class Bag represents a simple collection of counted objects. Elements are unordered. Although duplicate entries are allowed, the Bag holds only a single reference for each group of objects that compare equal to each other. With each reference, the Bag maintains a tally of the number of such elements that have been inserted. Thus, this collection is an efficient way to store large numbers of objects of which only some smaller number are unique.
Equality of objects is determined by using the hashCode() and equals(Object) methods inherited or overridden from class Object.
Class Set offers the simplest, most fundamental method of collecting objects. In this class, elements are unordered and duplicates are not allowed. Set uses an underlying java.util.Hashtable, but unlike Hashtable, elements are taken singly. In other words, Sets traffic in single objects, not in keys and values.
Equality of objects is determined by using the hashCode() and equals(Object) methods inherited or overridden from class Object.
The following example, given in its entirety in SetExample.java, reads in the specified file, and inserts each word of the file into a Set.
NOTE: Complete code for this example is located in the examples directory created for your installation of Tools.h++ Professional. The "Examples" chapter in Part V, "Resources," describes the location of that directory, or you can check the online build guide for your installation media.
Since a Set does not allow duplicates, each word is guaranteed to be unique, so the number of entries in the Set corresponds to the number of unique words in the file.
// Prepare to tokenize the file:
StreamTokenizer st = new StreamTokenizer( new BufferedReader(
new InputStreamReader( fin ) ) );
Set set = new Set();
String word;
int token;
st.wordChars('!', '\\');
/*
* Read individual words from the file, ignoring
* End-Of-Line and null values:
*/
try {
while ( (token = st.nextToken()) != EOF)
if (token != EOL && st.sval != null)
set.insert(st.sval);
}
catch(IOException io) {
System.err.println("Error: IO exception on file read");
return;
}
// Display result:
System.out.println("\nThere are " + set.size() +
" unique words in " + args[0] + ".\n");
Class IdentitySet, which inherits from Set, retrieves an object on the basis of identity instead of value; in other words, it tests using ==, not the equals() method. Because duplicates are not allowed, a given object can only be inserted once. Because it is an IdentitySet, however, it can contain multiple elements that are equals() to each other.
©Copyright 2000, Rogue Wave Software, Inc.
Contact Rogue Wave about documentation or support issues.