by Michael Girdley and Richard Lesh
In this chapter, you will learn about the java.util package of classes in the Java class library. These classes implement many of those features or functions usually left for the programmer or someone else to implement. In programming experiences, I regularly find myself saying: "It would be so much easier if there were a built-in object that would do some common but complicated task." The java.util package is a well-designed and effective attempt to satisfy many of these specialized needs.
In many languages you will find yourself implementing a stack or a hash table class and all of the corresponding methods. Java has an already built-in stack type, which will enable you to quickly and efficiently include your own stack data structures in your Java programs. This frees you to deal with more important design and implementation issues. These classes are also useful in a variety of other ways and are the fundamental building blocks of the more complicated data structures used in other Java packages and in your own applications.
This chapter covers
Unless otherwise noted, all of the interfaces and classes discussed in this chapter extend the java.lang.Object class.
Table 13.1 shows the classes that are part of the utilities package that will be discussed.
You may not be familiar with some of these data types. The Dictionary class is used to implement a dictionary in your program. A hash table is a storage data type whose speed in searching is much greater than that of other data structures because it stores data items based on a key derived from some given formula. A stack, of course, functions as if you were stacking data items on the floor one upon the other in a single stack. As a consequence, the only two manipulations you can make to the stack are to remove the top item or to place another on top. The Vector class implements an interesting data structure that has the capability to begin with a limited capacity and then change in size to accommodate the data items you insert into it. It can be descibed as a "growable array."
One would expect that the Vector class, as described previously, would eliminate the necessity for creating your own data structures. But there may be times when you might want to conserve space to the maximum or access your data in a specialized way. In these cases, there is a technique to implement such data structures in Java.
As you learned before, Java has no pointers. Since dynamically linked lists and queues are implemented using pointers, is it then impossible to create these two data structures in Java? Not quite. Just as with many other tasks in Java, you need to do a little "funky stepping" to get it right, because the implementation of lists, queues, and other dynamic data structures is not intuitive.
To define your own dynamic data structures, you will want to make use of the fact that references to objects in Java are already dynamic. This is demonstrated and necessitated by the practices Java utilizes, such as interfaces and abstract implementations.
If you are accustomed to implementing dynamically linked lists or queues in C++, the format you will use to create your own version of these structures should seem very familiar to you. For example, the following creates a Node class for the list that contains a string:
class Node {
String Name;
Node Prev;
Node Next;
}
Of course, this would be a doubly linked list, which has links backward and forward to other nodes containing strings. You could just as easily convert this type to link objects in just about any way to exhibit just about any behavior you want: queues, stacks (remember, there is already a Stack object in the class library), doubly linked lists, circular lists, binary search trees, and the list goes on.
To implement such a list, you could create a DoubleList class that would contain one such Node object and links strung out from there. You can use the keyword null to represent an empty object. Here is an example of the DoubleList declaration:
class DoubleList {
// Declare the listhead to be of the Node type we created above.
// Also, set it to be an empty object.
Node ListHead = null;
.
.
}
Next you create methods to act upon the list, such as InsertNode or ClearMyListJerk--whatever you wanted.
You would also probably want to create a constructor method for the Node class that would accept parameters to set the previous and next nodes at construction time; or you could create a method such as SetNext or SetNextToNull. Either way would work just fine.
Out of all this you get a surprise bonus: No worry about freeing space allocated to create nodes because the Java Garbage Collection processes take care of all that for you. Just create objects when you need them, and then let Java take care of it.
The utilities package has two interfaces that can be used in classes of your own design: Enumeration and Observer. An interface is a set of methods that must be written for any class that claims to implement the interface. This provides a way to consistently use all classes that implement the interface. The following list summarizes the Enumeration and Observer interfaces:
Enumeration Interface for classes that can enumerate a vector
Observer Interface for classes that can observe observable objects
The Enumeration interface is used for classes that can retrieve data from a list, element by element. For example, there is an Enumeration class in the utilities package that implements the Enumeration interface for use in conjunction with the Vector class. This frees you from hard-core traversal of the different classes of data structures.
The Observer interface is useful in designing classes that can watch for changes that occur in other classes.
CAUTION:
Some of the examples in this chapter are not applets, but applications. Many of these data structures are best exhibited by just plain text input and output. Removing the baggage that would have come along with applets allowed the examples to be simplified so that the topic being demonstrated would be clearer.
When you are applying any code segments from this chapter in your own applets, remember that some of the examples here are not true applets and you need to deal with the differences inherent between them.
This interface specifies a set of methods used to enumerate--that is, iterate through--a list. An object that implements this interface may be used to iterate through a list only once because the Enumeration object is consumed through its use.
For example, an Enumeration object can be used to print all the elements of a Vector object, v, as follows:
for (Enumeration e=v.elements();e.hasMoreElements();)
System.out.print(e.nextElement()+" ");
The Enumeration interface specifies only two methods: hasMoreElements() and nextElement(). The hasMoreElements() method must return True if there are elements remaining in the enumeration. The nextElement() method must return an object representing the next element within the object that is being enumerated. The details of how the Enumeration interface is implemented and how the data is represented internally are left up to the implementation of the specific class.
This interface, if implemented by a class, allows an object of the class to observe other objects of the class Observable. The Observer is notified whenever the Observable object that it is watching has been changed.
The interface only specifies one method, update(Observable, Object). This method is called by the observed object to notify the Observer of changes. A reference to the observed object is passed along with any additional object that the observed object wishes to pass to the Observer. The first argument enables the Observer to operate on the observed object, while the second argument is used to pass information from the observed to the Observer.
The utilities package supplies ten different classes that provide a wide variety of functionality. Although these classes don't generally have much in common, they all provide support for the most common data structures used by programmers. The techniques described next will enable you to create your own specialized classes to supplement those missing.
The classes supplied in the java.util package, however limited, do provide a great advantage over previous languages. The main advantage is that these classes simplify some things and eliminate a lot of the garbage that you were stuck with in the past, in terms of freeing memory and doing mundane programming tasks.
However, there are a number of limitations. For example, you have to "dance a little bit" to implement some of the more complicated data structures. And also, if you want speed, there are much faster languages to choose from. Java provides a combination of power and simplicity while sacrificing speed. However, don't worry that your programs will be slugs. Although Java is not nearly as efficient as C++ and C, it still beats Visual Basic in terms of size and speed.
This class implements a data type that represents a collection of bits. The collection will grow dynamically as more bits are required. It is useful for representing a set of True/False values. Specific bits are identified using non-negative integers. The first bit is bit 0.
This class is most useful for storing a group of related True/False values, such as user responses to Yes/No questions. For example, if the applet had a number of radio buttons, you could slap those values into an instance of the BitSet class.
It is also useful in terms of bitmapping your own graphics. You can create bitsets that can represent a pixel at a time (of course, it would be much easier to use the Graphics class instead).
Individual bits in the set are turned on or off with the set() and clear() methods, respectively. Individual bits are queried with the get() method. These methods all take the specific bit number as their only argument. The basic Boolean operations AND, OR, and XOR can be performed on two BitSets using the and(), or(), and xor() methods. Because these methods modify one of the BitSets, one generally will use the clone() method to create a duplicate of one, and then AND, OR, or XOR the clone with the second BitSet. The result of the operation then will end up in the cloned BitSet. The BitSet1 program in Listing 13.1 illustrates the basic BitSet operations.
Listing 13.1. BitSet1.java--BitSet sample program.
import java.io.DataInputStream;
import java.util.BitSet;
class BitSet1 {
public static void main(String args[])
throws java.io.IOException
{
DataInputStream dis=new DataInputStream(System.in);
String bitstring;
BitSet set1,set2,set3;
set1=new BitSet();
set2=new BitSet();
// Get the first bit sequence and store it
System.out.println("Bit sequence #1:");
bitstring=dis.readLine();
for (short i=0;i<bitstring.length();i++){
if (bitstring.charAt(i)=='1')
set1.set(i);
else
set1.clear(i);
}
// Get the second bit sequence and store it
System.out.println("Bit sequence #2:");
bitstring=dis.readLine();
for (short i=0;i<bitstring.length();i++){
if (bitstring.charAt(i)=='1')
set2.set(i);
else
set2.clear(i);
}
System.out.println("BitSet #1: "+set1);
System.out.println("BitSet #2: "+set2);
// Test the AND operation
set3=(BitSet)set1.clone();
set3.and(set2);
System.out.println("set1 AND set2: "+set3);
// Test the OR operation
set3=(BitSet)set1.clone();
set3.or(set2);
System.out.println("set1 OR set2: "+set3);
// Test the XOR operation
set3=(BitSet)set1.clone();
set3.xor(set2);
System.out.println("set1 XOR set2: "+set3);
}
}
The output from this program looks like this:
Bit sequence #1:
1010
Bit sequence #2:
1100
BitSet #1: {0, 2}
BitSet #2: {0, 1}
set1 AND set2: {0}
set1 OR set2: {0, 1, 2}
set1 XOR set2: {1, 2}
Table 13.2 summarizes all the various methods available in the BitSet class.
In addition to extending the java.lang.Object class, BitSet implements the java.lang.Cloneable interface. This, of course, allows instances of the object to be cloned to create another instance of the class.
You will regularly run into instances in which you will need to access and manipulate dates and times in your applets on the Web. For example, you might want an applet to display the current time or date during its execution. Or, if you are programming a game, you can use the system clock to get your elapsed time right.
The Date class is used to represent dates and times in a platform-independent fashion. For example, the current date or a specific date can be printed as shown in Listing 13.2.
Listing 13.2. Date1.java--Date sample program.
import java.util.Date;
public class Date1{
public static void main (String args[]){
Date today=new Date();
System.out.println("Today is "+today.toLocaleString()+
" ("+today.toGMTString()+")");
Date birthday=new Date(89,10,14,8,30,00);
System.out.println("My birthday is"+
birthday.toString()+" ("+birthday.toGMTString()+")");
Date anniversary=new Date("Jun 21, 1986");
System.out.println("My anniversary is "+
anniversary+" ("+anniversary.toGMTString()+")");
}
}
The output from this program looks like this:
Today is 01/21/96 19:55:17 (22 Jan 1996 01:55:17 GMT) My birthday is Thu Nov 14 08:30:00 1989 (14 Nov 1989 14:30:00 GMT) My anniversary is Sat Jun 21 00:00:00 1989 (21 Jun 1986 05:00:00 GMT)
The default constructor is used when the current date and time are needed. A specific date and time can be used to initialize a Date object using the constructors that take three, five, and six integers. These constructors allow the date and time to be specified using YMD, YMDHM, or YMDHMS. Any parts of the time not specified by the three- and five-integer constructors will be set to zero.
Date/time formats can be conveniently summarized using notations of the form YMD, YMDHMS, HMS, or MDY. These abbreviated formats indicate in what order the various numeric parts of the date will appear. Each letter refers to a specific component of the date/time: year (Y), month (M), day , hour (H), minute (M), and second (S). Whether the letter M refers to month or minute depends on the context.
Alternately, a Date object can be constructed using a single string that represents a date and time using a variety of different syntax. One of the most important is the international standard date syntax of the form, "Sun, 14 Aug 1995 9:00:00 GMT." Continental U.S. time zone abbreviations are understood, but time zone offsets should be considered for general use; for example, "Sun, 14 Aug 1995 9:00:00 GMT+0600" (six hours west of the Greenwich meridian). The local time zone to the computer executing the code is assumed if none is supplied.
The Date class intends to store date and time information in UTC (Coordinated Universal Time). However, it does not necessarily achieve this goal. UTC is a time standard based on an atomic clock. Time specifications using UTC are considered equal to GMT (Greenwich Mean Time). The implementation of the Date class is limited by the time set by the underlying operating system. Because modern operating systems typically assume that a day is always 86,400 seconds, the extra leap seconds, which are needed about once a year to accurately reflect UTC, usually are not added.
The date can be converted to a text representation using the methods toString(), toGMTString(), and toLocaleString(), which convert the date and time to the standard UNIX, GMT, or local time formats, respectively. The toLocaleString function is very useful since you do not have to determine what your system's date format is. This may not sound like much, but it is just another piece of the very complicated puzzle that Sun has put together to allow your applets and applications to flow seamlessly into the system on which they are running.
When a date is being converted to a string by an automatic coercion, the toString() method will be used. The resulting string returned by the toString function follows UNIX time and date standards.
The Date class also has methods for setting and querying the date and time component values once the Date object is constructed. The individual parts of the date (month, date, year) and time (hours, minutes, seconds) are always specified in local time. When referring to the various parts of the date and time, the first letter of each part typically is used in an abbreviation. For example, YMDHMS would indicate that all six parts (year, month, date, hour, minute, second) are present. Each of these parts of the date and time have a specific range of acceptable values, as illustrated in Table 13.3.
The date and time also can be specified using a single integer UTC value that represents the number of milliseconds that have elapsed since a specific starting date (which might vary from system to system). For UNIX systems this date is January 1, 1970. The program Date2 in Listing 13.3 shows how this single value corresponds to the normal YMDHMS representation.
Listing 13.3. Date2.java--Date sample program.
import java.util.Date;
public class Date2{
public static void main (String args[]){
Date beginning=new Date(0);
Date anniversary=new Date("Jun 21, 1986");
Date today=new Date();
System.out.println(beginning+"="+beginning.getTime());
System.out.println(anniversary+"="+anniversary.getTime());
System.out.println(today+"="+today.getTime());
}
}
The output from this program looks like this:
Wed Dec 31 18:00:00 1969=0 Sat Jun 21 00:00:00 1986=519714000000 Sun Jan 21 19:55:17 1996=822275717000
Dates can be compared to each other by using this UTC value or by using the methods after(), before(), or equals().
CAUTION:
Don't try to launch space shuttles or coordinate nuclear attacks based on your operating system's local time as reflected by Java. Although the API is intended to reflect UTC, Coordinated Universal Time, it doesn't do so exactly. This inexact behavior is inherited from the time system of the underlying OS. The vast majority of all modern operating systems assume that 1 day = 3600 seconds * 24 hours, and as such, they reflect time to the accuracy that UTC does.
Under the UTC, about once a year there is an extra second, called a "leap second," added to account for the wobble of the earth. Most computer clocks are not accurate enough to reflect this distinction.
Between UTC and standard OS time (UT/GMT), there is this subtle difference; one is based on an atomic clock and the other is based on astronomical observations, which for all practical purposes is an invisibly fine hair to split.
For more information, Sun suggests you visit the U.S. Naval Observatory site, particularly the Directorate of Time at http://tycho.usno.navy.mil and their definitions of different systems of time at http://tycho.usno.navy.mil/systime.html.
Table 13.4 summarizes everything available in the Date class.
One of the most helpful methods available in the Date class is the parse method. This void takes an instance of the String type and then parses that string. The result of that parse is then placed in the calling instance of the class. If you had a date called ADate, you could set its value to be the date in the SomeString class with the code line:
ADate.parse(SomeString);
You will also find the before and after functions useful. They enable you to send in another instance of the Date class and then compare that date to the value in the calling instance.
The sample applet in Listing 13.4 demonstrates the use of the Date class in your own applet.
Listing 13.4. Using the Date class.
import java.awt.*;
import java.util.*;
public class MichaelSimpleClock extends java.applet.Applet {
Date TheDate = new Date();
Button DateButton = new Button(
" Click me! ");
public void init() {
add(DateButton);
}
public boolean handleEvent(Event e) {
if (e.target == DateButton) {
DateButton.setLabel(TheDate.toString());
}
return true;
}
}
Figure 13.1 is a screenshot of the MichaelSimpleClock applet. Note that the clock in the applet is wrong: it is not actually 8:00am. There is no way I would write that early in the morning.
Figure 13.1. The MichaelSimpleClock applet.
What about a real-time clock that updates as the clock changes? To accomplish this small feat, you need to include in the applet a loop that has each iteration reconstructing the internal Date instance. Then, regularly repaint that value inside the applet's paint method. You'll also need to include threading to prevent locking up your system during the applet's execution. Threading will not be covered until a later chapter, so a real-time clock was not included in this section.
Key to any programming of games and many other program types is its capability to generate random numbers. Java includes the capability to generate random numbers efficiently and effectively.
The Random class implements a pseudo-random number data type used to generate a stream of seemingly random numbers. To create a sequence of different pseudo-random values each time the application is run, create the Random object as follows:
Random r=new Random();
This will seed the random generator with the current time. On the other hand, consider the following statement:
Random r=new Random(326); // Pick any value
This will seed the random generator with the same value each time, resulting in the same sequence of pseudo-random numbers each time the application is run. The generator can be reseeded at any time using the setSeed() method.
Want to get really random numbers? Well, you can't. But a common practice to simulate actual random numbers in computer programs is to seed the random number generator with some variant of the current time or date. If, for example, you wanted to seed a random number generator with the sum of the current seconds, minutes, and hours, you could say:
int OurSeed = ADate.getSeconds() + ADate.getHours() + ADate.getMinutes(); Random = new Random(OurSeed);
This should suffice for most tasks.
Pseudo-random numbers can be generated by using one of the functions: nextInt(), nextLong(), nextFloat(), nextDouble(), or nextGaussian(). The first four functions return integers, longs, and so on. (For more information on the Gaussian distribution, see the next Note.) For example, the program Random1 in Listing 13.5 will print out five pseudo-random uniformly distributed values using these functions.
Listing 13.5. Random1.java--Random sample program.
import java.lang.Math;
import java.util.Date;
import java.util.Random;
class Random1 {
public static void main(String args[])
throws java.io.IOException
{
int count=6;
Random randGen=new Random();
System.out.println("Uniform Random Integers");
for (int i=0;i<count;i++)
System.out.print(randGen.nextInt()+" ");
System.out.println("\n");
System.out.println("Uniform Random Floats");
for (int i=0;i<count;i++)
System.out.print(randGen.nextFloat()+" ");
System.out.println("\n");
System.out.println("Gaussian Random Floats");
for (int i=0;i<count;i++)
System.out.print(randGen.nextGaussian()+" ");
System.out.println("\n");
System.out.println("Uniform Random Integers [1,6]");
for (int i=0;i<count;i++)
System.out.print((Math.abs(randGen.nextInt())%6+1)+" ");
System.out.println("\n");
}
}
The output from the preceding program looks like this:
Uniform Random Integers 1704667569 -1431446235 1024613888 438489989 710330974 -1689521238 Uniform Random Floats 0.689189 0.0579988 0.0933537 0.748228 0.400992 0.222109 Gaussian Random Floats -0.201843 -0.0111578 1.63927 0.205938 -0.365471 0.626304 Uniform Random Integers [1,6] 4 6 1 6 3 2
If you need to generate uniformly distributed random integers within a specific range, the output from nextInt(), nextLong(), or nextDouble() can be scaled to match the required range. A simpler approach is to take the remainder of the result of nextInt() divided by the number of different values plus the first value of the range. For example, if the values 10 to 20 are needed one can use the formula nextInt()%21+10. Unfortunately, although this method is much simpler than scaling the output of nextInt(), it only is guaranteed to work on truly random values. Because the pseudo-random generator might have various undesired correlations, the modulus operator might not provide acceptable results--one might get all odd numbers, for example. In other words, don't plan on simulating the detonation of your new H-bomb in Java because you might find yourself a couple of miles too close.
Uniformly distributed random numbers are generated using a modified linear congruential method with a 48-bit seed. Uniformly distributed random numbers within a given range will all appear with the same frequency. This class can also generate random numbers from a Gaussian or Normal distribution. The Gaussian frequency distribution curve is also referred to as a bell curve. For information on this, see Donald Knuth, The Art of Computer Programming, Volume 2, Section 3.2.1.
Table 13.5 summarizes the complete interface of the Random class.
Refer also to Random().
The following applet, shown in Listing 13.6, demonstrates a bit of what you can do with Random.
Listing 13.6. Using the Random Class.
import java.awt.*;
import java.util.*;
public class TheWanderer extends java.applet.Applet {
int xpos = 100;
int ypos = 100;
// Our current date.
Date D = new Date();
// The movement button
Button theButton = new Button("Click Me");
// Our random number generator.
Random R;
public void init() {
add(theButton);
setBackground(Color.white);
// Our random number generator seeded with the current seconds.
int seed = D.getSeconds();
R = new Random(seed);
}
public boolean handleEvent (Event e) {
if (e.target == theButton) {
// Move our thing.
xpos = xpos + (Math.abs(R.nextInt())%10-7);
ypos = ypos + (Math.abs(R.nextInt())%10-7);
// repaint the sucker.
repaint();
}
return super.handleEvent ;
}
public void paint(Graphics g) {
g.setColor(Color.black);
g.fillOval(xpos,ypos, 50, 50);
}
}
Figure 13.2 shows TheWanderer applet during its execution.
Figure 13.2. TheWanderer applet.
This section will describe the function of the StringTokenizer class, which also could have been appropriately grouped with other classes in Chapter 11, "Reading and Writing with Java," since it is so vital to the input and output functions demonstrated in that chapter. This class enables you to parse a string into a number of smaller strings called tokens. This class works specifically for what is called "delimited text," which means that each individual substring of the string is separated by a delimiter. The delimiter can be anything ranging from a "*" to "YabaDaba". You simply specify what you want the class to look for when tokenizing the string.
This class is included here because it has uses that would prove helpful in everything from a spreadsheet applet to an arcade game applet.
The delimiter set can be specified when the StringTokenizer object is created, or it can be specified on a per-token basis. The default delimiter set is the set of whitespace characters. The class would then find all of the separate words in a string and tokenize them. For example, the StringTokenizer1 code in Listing 13.7 prints out each word of the string on a separate line.
Listing 13.7. StringTokenizer1.java--StringTokenizer sample program.
import java.io.DataInputStream;
import java.util.StringTokenizer;
class StringTokenizer1 {
public static void main(String args[])
throws java.io.IOException
{
DataInputStream dis=new DataInputStream(System.in);
System.out.println("Enter a sentence: ");
String s=dis.readLine();
StringTokenizer st=new StringTokenizer(s);
while (st.hasMoreTokens())
System.out.println(st.nextToken());
}
}
Here is the output from this listing:
Enter a sentence: Four score and seven Four score and seven
Pure excitement. The method countTokens() returns the number of tokens remaining in the string using the current delimiter set--that is, the number of times nextToken() can be called before generating an exception. This is an efficient method because it does not actually construct the substrings that nextToken() must generate.
In addition to extending the java.lang.object class, the StringTokenizer class implements the java.util.Enumeration interface.
Table 13.6 summarizes the methods of the StringTokenizer class.
As was stated before, Java doesn't include dynamically linked list, queue, or other data structures of that type. Instead, the designers of Java envisioned the Vector class, which would be able to handle occasions when you need dynamic storage of objects. Of course, there are positive and negative consequences of this decision by the designers at Sun. On the positive side, it contributes to the simplicity of the language. The major negative point is that, as face value, it severely limits programmers from utilizing more sophisticated programs.
In any case, the Vector class implements a dynamically allocated list of objects. It attempts to optimize storage by increasing the storage capacity of the list when needed by increments larger than just one object. Typically with this mechanism, there is some excess capacity in the list. When this capacity is exhausted, the list is reallocated to add another block of objects at the end of the list. Setting the capacity of the Vector object to the needed size before inserting a large number of objects will reduce the need for incremental reallocation. Because of this mechanism, it is important to remember that the capacity (the available elements in the Vector object) and the size (the number of elements currently stored in the Vector object) usually are not the same.
For example, say a Vector with capacityIncrement equal to three has been created. As objects are added to the Vector, new space is allocated in chunks of three objects. After five elements have been added, there still will be room for one more element without the need for any additional memory allocation.
After the sixth element has been added, there is no more excess capacity. When the seventh element is added, a new allocation will be made that adds three additional elements, giving a total capacity of nine. After the seventh element is added, there will be two remaining unused elements.
The initial storage capacity and the capacity increment both can be specified in the constructor. Even though the capacity is automatically increased as needed, the ensureCapacity() method can be used to increase the capacity to a specific minimum number of elements, whereas trimToSize() can be used to reduce the capacity to the minimum needed to store the current elements. New elements can be added to the Vector using the addElement() and insertElementAt() methods. The elements passed to be stored in the Vector must be derived from type Object. Elements can be changed using the setElementAt() method. Removal of elements is accomplished with the removeElement(), removeElementAt(), and removeAllElements() methods. Elements can be accessed directly using the elementAt(), firstElement(), and lastElement() methods, whereas elements can be located using the indexOf() and lastIndexOf() methods. Information about the size and the capacity of the Vector are returned by the size() and capacity() methods respectively. The setSize() method can be used to directly change the size of the Vector.
For example, the Vector1 code in Listing 13.8 creates a Vector of integers by adding new elements to the end. It then, using a variety of techniques, prints the Vector.
Listing 13.8. Vector1.java--Vector sample program.
import java.lang.Integer;
import java.util.Enumeration;
import java.util.Vector;
class Vector1 {
public static void main(String args[]){
Vector v=new Vector(10,10);
for (int i=0;i<20;i++)
v.addElement(new Integer(i));
System.out.println("Vector in original order using an Enumeration");
for (Enumeration e=v.elements();e.hasMoreElements();)
System.out.print(e.nextElement()+" ");
System.out.println();
System.out.println("Vector in original order using elementAt");
for (int i=0;i<v.size();i++)
System.out.print(v.elementAt(i)+" ");
System.out.println();
// Print out the original vector
System.out.println("\nVector in reverse order using elementAt");
for (int i=v.size()-1;i>=0;i++)
System.out.print(v.elementAt(i)+" ");
System.out.println();
// Print out the original vector
System.out.println("\nVector as a String");
System.out.println(v.toString());
}
}
The output from this program looks like this:
Vector in original order using an Enumeration 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Vector in original order using elementAt 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Vector in reverse order using elementAt 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Vector as a String [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
The expression new Integer() was used to create integer objects to store because the fundamental types, such as int, are not objects in Java. This technique is used many times throughout this chapter.
Notice the use of the Enumeration object as one way to access the elements of a Vector. Look at the following lines:
for (Enumeration e=v.elements();e.hasMoreElements();)
System.out.print(e.nextElement()+" ");
One can see that an Enumeration object, which represents all of the elements in the Vector, is created and returned by the Vector method elements(). With this Enumeration object, the loop can check to see if there are more elements to process using the Enumeration method hasMoreElements(), and the loop can get the next element in the Vector using the Enumeration method nextElement().
The Vector2 program in Listing 13.9 illustrates some of the vector-accessing techniques. It first generates a vector of random integers; then allows the user to search for a specific value. The locations of the first and last occurrences of the value are printed by the program using the indexOf() and lastIndexOf() methods.
Listing 13.9. Vector2.java--Vector sample program.
import java.io.DataInputStream;
import java.lang.Integer;
import java.lang.Math;
import java.util.Enumeration;
import java.util.Random;
import java.util.Vector;
class Vector2 {
public static void main(String args[])
throws java.io.IOException
{
int numElements;
DataInputStream dis=new DataInputStream(System.in);
Vector v=new Vector(10,10);
Random randGen=new Random();
System.out.println("How many random elements? ");
numElements=Integer.valueOf(dis.readLine()).intValue();
for (int i=0;i<numElements;i++)
v.addElement(new Integer(Math.abs(
randGen.nextInt())%numElements));
System.out.println(v.toString());
Integer searchValue;
System.out.println("Find which value? ");
searchValue=Integer.valueOf(dis.readLine());
System.out.println("First occurrence is element "+
v.indexOf(searchValue));
System.out.println("Last occurrence is element "+
v.lastIndexOf(searchValue));
}
}
The output from this program looks like this:
How many random elements? 10 [0, 2, 8, 4, 9, 7, 8, 6, 3, 2] Find which value? 8 First occurrence is element 2 Last occurrence is element 6
In addition to extending the java.lang.Object class, the Vector class implements the java.lang.Cloneable interface. Table 13.7 summarizes the methods of the Vector class.
Refer also to Vector, Hashtable.
The Stack data structure is key to many programming efforts, ranging from building compilers to solving mazes. The Stack class in the Java library implements a Last In, First Out (LIFO) stack of objects. Even though they are based on (extends) the Vector class, Stacks are typically not accessed in a direct fashion. Instead, values are pushed onto and popped off of the top of the "stack." The net effect is that values that were most recently pushed are the first ones to be popped.
While the Stack class implements a LIFO removal strategy, the queue data structure discussed early in the chapter is based on a First In, First Out (FIFO) strategy.
The Stack1 code in Listing 13.10 pushes strings onto the stack, and then retrieves them. The strings will end up being printed in reverse order from which they were stored.
Listing 13.10. Stack1.java--Stack sample program.
import java.io.DataInputStream;
import java.util.Stack;
import java.util.StringTokenizer;
class Stack1 {
public static void main(String args[])
throws java.io.IOException
{
DataInputStream dis=new DataInputStream(System.in);
System.out.println("Enter a sentence: ");
String s=dis.readLine();
StringTokenizer st=new StringTokenizer(s);
Stack stack=new Stack();
while (st.hasMoreTokens())
stack.push(st.nextToken());
while (!stack.empty())
System.out.print((String)stack.pop()+" ");
System.out.println();
}
}
The output from this program looks like this:
Enter a sentence: The quick brown fox jumps over the lazy dog dog lazy the over jumps fox brown quick The
Even though Stack objects normally are not accessed in a direct fashion, it is possible to search the Stack for a specific value using the search() method. It accepts an object to find and returns the distance from the top of the Stack where the object was found. It will return -1 if the object is not found.
The method peek() will return the top object on the Stack without actually removing it from the Stack. The peek() method will throw an EmptyStackException if the Stack has no items.
Table 13.8 summarizes the complete interface of the Stack class.
This class is an abstract class that is used as a base for the Hashtable class. It implements a data structure that allows a collection of key and value pairs to be stored. Any type of object can be used for the keys or the values. Typically, the keys are used to find a particular corresponding value.
Because this class is an abstract class that cannot be used directly, the code examples presented cannot actually be run. They are presented only to illustrate the purpose and use of the methods declared by this class. The following code would, hypothetically, be used to create a Dictionary with these values illustrated:
Dictionary products = new Dictionary(); products.put(new Integer(342), "Widget"); products.put(new Integer(124), "Gadget"); products.put(new Integer(754), "FooBar");
The put() method is used to insert a key and value pair into the Dictionary. The two arguments both must be derived from the class Object. The key is the first argument and the value is the second.
A value can be retrieved using the get() method and a specific key to be found. It returns the null value if the specified key is not found. For example:
String name = products.get(new Integer(124));
if (name != null) {
System.out.println("Product name for code 124 is " + name);
}
Although an individual object can be retrieved with the get() method, sometimes it is necessary to access all of the keys or all of the values. There are two methods, keys() and elements(), that will return Enumerations that can be used to access the keys and the values, respectively.
Table 13.9 summarizes the complete interface of the Dictionary class.
Refer also to Enumeration, Hashtable, Properties.
The Hashtable data structure is very useful when dealing with the searching for and manipulation of data. You would want to use this class if you will be storing a large amount of data in memory and then searching it. The time needed to complete a search of a hash table is decidedly less than in the Vector class. Of course, for small amounts of data, it won't make much difference whether you use a hash table or a linear data structure, since the overhead time will be much greater than any search time would be. See the next Note for more information on search times in the different classes.
Hash table organization is based upon keys, which are computed based upon the data being stored. For example, if you were going to insert a number of words into a hash table, you could base your key upon the first letter of the word. When you came back to search for a word later on, you could then compute the key for the item being sought. By using this key, search time is drastically reduced because the items are stored based upon the value of their respective key.
The Hashtable class implements a hash table storage mechanism for storing key and value pairs. Hash tables are designed to quickly locate and retrieve information stored by using a key. Keys and values may be of any object type, but the key object's class must implement the hashCode() and equals() methods.
Big "O" notation is used to measure the "worst case scenario" time requirements in terms of searching while using different data structures. Linear searching, such as that used in the Vector class, is O(n), whereas hash table searching is O(log n). This basically means that over a large number of objects, you'll be saving a large amount of time when searching, since log of a number is always less than the number itself. For times when you will be doing a large amount of searching through data, a hash table will likely be much more efficient.
The sample Hashtable1 in Listing 13.11 creates a Hashtable object and stores 10 key and value pairs using the put() method. It then uses the get() method to return the value corresponding to a key entered by the user.
Listing 13.11. Hashtable1.java--Hashtable sample program.
import java.io.DataInputStream;
import java.lang.Integer;
import java.lang.Math;
import java.util.Random;
import java.util.Hashtable;
class Hashtable1 {
public static void main(String args[])
throws java.io.IOException
{
DataInputStream dis=new DataInputStream(System.in);
int numElements=10;
String keys[]={"Red","Green","Blue","Cyan","Magenta",
"Yellow","Black","Orange","Purple","White"};
Hashtable ht;
Random randGen=new Random();
ht=new Hashtable(numElements*2);
for (int i=0;i<numElements;i++)
ht.put(keys[i],new Integer(Math.abs(
randGen.nextInt())%numElements));
System.out.println(ht.toString());
String keyValue;
System.out.println("Which key to find? ");
keyValue=dis.readLine();
Integer value=(Integer)ht.get(keyValue);
if (value!=null) System.out.println(keyValue+" = "+value);
}
}
The output from this program looks like this:
{Cyan=4, White=0, Magenta=4, Red=5, Black=3,
Green=8, Purple=3, Orange=4, Yellow=2, _Blue=6}
Which key to find?
Red
Red = 5
In addition to the get() method, the contains() and containsKey() methods can be used to search for a particular value or key, respectively. Both return True or False depending on whether the search was successful. The contains() method must perform an exhaustive search of the table and is not as efficient as the containsKey() method, which can take advantage of the hash table's storage mechanism to find the key quickly.
Because hash tables need to allocate storage for more data than actually is stored, a measurement called the load factor indicates the number of used storage spaces as a fraction of the total available storage spaces. It is expressed as a value between 0 and 100 percent. Typically, the load factor should not be higher than about 50 percent for efficient retrieval of data from a hash table. When specifying the load factor in a program, use a fractional value in the range 0.0 to 1.0 to represent load factors in the range 0 to 100 percent.
Hash tables can be constructed in three different ways: by specifying the desired initial capacity and load factor; by specifying only the initial capacity; or by specifying neither. If the load factor is not specified, the Hashtable will be rehashed into a larger table when it is full--otherwise it is rehashed when it exceeds the load factor. The constructors will throw an IllegalArgumentException if the initial capacity is less than or equal to zero, or if the load factor is less than or equal to zero.
The clone() method can be used to create a copy (clone) of the Hashtable. However, it creates a shallow copy of the Hashtable, which means that the keys and values themselves are not clones. This local method overrides the inherited clone() method.
CAUTION:
The clone() method is a relatively expensive operation to perform in terms of memory utilization and execution time. Because the new Hashtable still refers directly to the objects (keys and values) stored in the old table, caution should be used to avoid making changes that will disrupt the original Hashtable.
The Hashtable class extends the java.util.Dictionary class and implements the java.lang.Cloneable interface. Table 13.10 summarizes the methods of the Hashtable class.
Refer also to hashCode, equals.
The Properties class is what enables end-users to customize their Java program. For example, you can easily store values such as foreground colors, background colors, font defaults, etc. and then have those values available to be reloaded. This would be most useful for Java applications, but you can also implement them for applets. If you have an applet that is regularly used by multiple users, you could keep a properties file on your server for each different user, which would be accessed each time that user loaded the applet.
The Properties class is a Hashtable, which can be repeatedly stored and restored from a stream. It is used to implement persistent properties. It also allows for an unlimited level of nesting, by searching a default property list if the required property is not found. The fact that this class is an extension of the Hashtable class means that all methods available in the Hashtable class are also available in the Properties class.
The sample program Properties1 in Listing 13.12 creates two properties lists. One will be the default property list and the other will be the user-defined property list. When the user property list is created, the default Properties object is passed. When the user property list is searched, if the key value is not found, the default Properties list will be searched.
Listing 13.12. Properties1.java--Properties sample program.
import java.io.Data7InputStream;
import java.lang.Integer;
import java.util.Properties;
class Properties1 {
public static void main(String args[])
throws java.io.IOException
{
int numElements=4;
String defaultNames[]={"Red","Green","Blue","Purple"};
int defaultValues[]={1,2,3,4};
String userNames[]={"Red","Yellow","Orange","Blue"};
int userValues[]={100,200,300,400};
DataInputStream dis=new DataInputStream(System.in);
Properties defaultProps=new Properties();
Properties userProps=new Properties(defaultProps);
for (int i=0;i<numElements;i++){
defaultProps.put(defaultNames[i],
Integer.toString(defaultValues[i]));
userProps.put(userNames[i],
Integer.toString(userValues[i]));
}
System.out.println("Default Properties");
defaultProps.list(System.out);
System.out.println("\nUser Defined Properties");
userProps.list(System.out);
String keyValue;
System.out.println("\nWhich property to find? ");
keyValue=dis.readLine();
System.out.println("Property '"+keyValue+"' is '"+
userProps.getProperty(keyValue)+"'");
}
}
Notice that the getProperties() method is used instead of the inherited get() method. The get() method only searches the current Properties object. The getProperties() method must be used in order to have the default Properties list searched. An alternative form of the getProperties() method has a second argument, which is that a default Properties list is to be searched instead of the default specified when the Properties object was created.
The propertyNames() method can be used to return an Enumeration, which can be used to index through all of the property names. This Enumeration includes the property names from the default Properties list. Likewise, the list() method, which prints the Properties list to the standard output, will list all of the properties of the current Properties object and those in the default Properties object.
Properties objects can be written to and read from a stream using the save() and load() methods, respectively. In addition to the output or input stream, the save method has an additional string argument that will be written at the beginning of the stream as a header comment.
Table 13.11 summarizes the methods of the Properties class.
This class acts as a base class for objects that you wish to have observed by other objects that implement the Observer interface. An Observable object can notify its Observers whenever the Observable object is modified using the notifyObservers() method. This method accomplishes the notification by invoking the update() method of all of its Observers, optionally passing a data object that is passed to notifyObservers. Observable objects may have any number of Observers.
Table 13.12 summarizes the complete interface of the Observable class.
This chapter described the classes that make up the Java utilities package. This package provides complete implementations of the basic data structures and some of the most useful data types (other than the fundamental numeric types) needed by programmers. Many of the data types and data structures that you will develop using Java will be based on the classes found in the utilities package. For smaller applets, many of these classes will not be necessary. However, as your applets increase in complexity, you will find these classes to be very useful. In any case, this chapter has been a good starting point for understanding the utility of these important Java classes and for understanding how to use them effectively.
