8: Holding
your objects

It’s a fairly simple program that has only a fixed quantity of objects with known lifetimes.

In general, your programs will always be creating new objects based on some criteria that will be known only at the time the program is running. You won’t know until run-time the quantity or even the exact type of the objects you need. To solve the general programming problem, you need to create any number of objects, anytime, anywhere. So you can’t rely on creating a named handle to hold each one of your objects:

since you’ll never know how many of these things you’ll actually need.

To solve this rather essential problem, Java has several ways to hold objects (or rather, handles to objects). The built-in type is the array, which has been discussed before and will get additional coverage in this chapter. Also, the Java utilities library has some collection classes (also known as container classes, but that term is used by the AWT so “collection” will be used here) that provide more sophisticated ways to hold and even manipulate your objects. This will comprise the remainder of this chapter.

Most of the necessary introduction to arrays is in the last section of Chapter 4, which shows how you define and initialize an array. Holding objects is the focus of this chapter, and an array is just one way to hold objects. But there are a number of other ways to hold objects, so what makes an array special?

There are two issues that distinguish arrays from other types of collections: efficiency and type. The array is the most efficient way that Java provides to store and access a sequence of objects (actually, object handles). The array is a simple linear sequence, which makes element access fast, but you pay for this speed: when you create an array object, its size is fixed and cannot be changed for the lifetime of that array object. You might suggest creating an array of a particular size and then, if you run out of space, creating a new one and moving all the handles from the old one to the new one. This is the behavior of the Vector class, which will be studied later in the chapter. However, because of the overhead of this size flexibility, a Vector is measurably less efficient than an array.

The vector class in C++ does know the type of objects it holds, but it has a different drawback when compared with arrays in Java: the C++ vector’s operator[] doesn’t do bounds checking, so you can run past the end. (It’s possible, however, to ask how big the vector is, and the at( ) method does perform bounds checking.) In Java, you get bounds checking regardless of whether you’re using an array or a collection – you’ll get a RuntimeException if you exceed the bounds. As you’ll learn in Chapter 9, this type of exception indicates a programmer error and thus you don’t need to check for it in your code. As an aside, the reason the C++ vector doesn’t check bounds with every access is speed – in Java you have the constant performance overhead of bounds checking all the time for both arrays and collections.

The other generic collection classes that will be studied in this chapter, Vector, Stack, and Hashtable, all deal with objects as if they had no specific type. That is, they treat them as type Object, the root class of all classes in Java. This works fine from one standpoint: you need to build only one collection, and any Java object will go into that collection. (Except for primitives – these can be placed in collections as constants using the Java primitive wrapper classes, or as changeable values by wrapping in your own class.) This is the second place where an array is superior to the generic collections: when you create an array, you create it to hold a specific type. This means that you get compile-time type checking to prevent you from putting the wrong type in, or mistaking the type that you’re extracting. Of course, Java will prevent you from sending an inappropriate message to an object, either at compile-time or at run-time. So it’s not as if it’s riskier one way or the other, it’s just nicer if the compiler points it out to you, faster at run-time, and there’s less likelihood that the end user will get surprised by an exception.

For efficiency and type checking it’s always worth trying to use an array if you can. However, when you’re trying to solve a more general problem arrays can be too restrictive. After looking at arrays, the rest of this chapter will be devoted to the collection classes provided by Java.

Regardless of what type of array you’re working with, the array identifier is actually a handle to a true object that’s created on the heap. The heap object can be created either implicitly, as part of the array initialization syntax, or explicitly with a new expression. Part of the heap object (in fact, the only field or method you can access) is the read-only length member that tells you how many elements can be stored in that array object. The ‘[]’ syntax is the only other access that you have to the array object.

The following example shows the various ways that an array can be initialized, and how the array handles can be assigned to different array objects. It also shows that arrays of objects and arrays of primitives are almost identical in their use. The only difference is that arrays of objects hold handles while arrays of primitives hold the primitive values directly.

Here’s the output from the program:

The array a is initially just a null handle, and the compiler prevents you from doing anything with this handle until you’ve properly initialized it. The array b is initialized to point to an array of Weeble handles, but no actual Weeble objects are ever placed in that array. However, you can still ask what the size of the array is, since b is pointing to a legitimate object. This brings up a slight drawback: you can’t find out how many elements are actually in the array, since length tells you only how many elements can be placed in the array; that is, the size of the array object, not the number of elements it actually holds. However, when an array object is created its handles are automatically initialized to null so you can see whether a particular array slot has an object in it by checking to see whether it’s null. Similarly, an array of primitives is automatically initialized to zero for numeric types, null for char, and false for boolean.

Array c shows the creation of the array object followed by the assignment of Weeble objects to all the slots in the array. Array d shows the “aggregate initialization” syntax that causes the array object to be created (implicitly with new on the heap, just like for array c) and initialized with Weeble objects, all in one statement.

The expression

shows how you can take a handle that’s attached to one array object and assign it to another array object, just as you can do with any other type of object handle. Now both a and d are pointing to the same array object on the heap.

Java 1.1 adds a new array initialization syntax, which could be thought of as a “dynamic aggregate initialization.” The Java 1.0 aggregate initialization used by d must be used at the point of d’s definition, but with the Java 1.1 syntax you can create and initialize an array object anywhere. For example, suppose hide( ) is a method that takes an array of Weeble objects. You could call it by saying:

but in Java 1.1 you can also dynamically create the array you want to pass as the argument:

This new syntax provides a more convenient way to write code in some situations.

The second part of the above example shows that primitive arrays work just like object arrays except that primitive arrays hold the primitive values directly.

Collection classes can hold only handles to objects. An array, however, can be created to hold primitives directly, as well as handles to objects. It is possible to use the “wrapper” classes such as Integer, Double, etc. to place primitive values inside a collection, but as you’ll see later in this chapter in the WordCount.java example, the wrapper classes for primitives are only somewhat useful anyway. Whether you put primitives in arrays or wrap them in a class that’s placed in a collection is a question of efficiency. It’s much more efficient to create and access an array of primitives than a collection of wrapped primitives.

Of course, if you’re using a primitive type and you need the flexibility of a collection that automatically expands when more space is needed, the array won’t work and you’re forced to use a collection of wrapped primitives. You might think that there should be a specialized type of Vector for each of the primitive data types, but Java doesn’t provide this for you. Some sort of templatizing mechanism might someday provide a better way for Java to handle this problem.[32]

Suppose you’re writing a method and you don’t just want to return one thing, but a whole bunch of things. Languages like C and C++ make this difficult because you can’t just return an array, only a pointer to an array. This introduces problems because it becomes messy to control the lifetime of the array, which easily leads to memory leaks.

Java takes a similar approach, but you just “return an array.” Actually, of course, you’re returning a handle to an array, but with Java you never worry about responsibility for that array – it will be around as long as you need it, and the garbage collector will clean it up when you’re done.

As an example, consider returning an array of String:

The method flavorSet( ) creates an array of String called results. The size of this array is n, determined by the argument you pass into the method. Then it proceeds to choose flavors randomly from the array flav and place them into results, which it finally returns. Returning an array is just like returning any other object – it’s a handle. It’s not important that the array was created within flavorSet( ), or that the array was created anyplace else, for that matter. The garbage collector takes care of cleaning up the array when you’re done with it, and the array will persist for as long as you need it.

As an aside, notice that when flavorSet( ) chooses flavors randomly, it ensures that a random choice hasn’t been picked before. This is performed in a seemingly infinite while loop that keeps making random choices until it finds one that’s not already in the picks array. (Of course, a String comparison could also have been performed to see if the random choice was already in the results array, but String comparisons are inefficient.) If it’s successful it adds the entry and breaks out to go find the next one (i gets incremented). But if t is a number that’s already in picks, then a labeled continue is used to jump back two levels, which forces a new t to be selected. It’s particularly convincing to watch this happen with a debugger.

main( ) prints out 20 full sets of flavors, so you can see that flavorSet( ) chooses the flavors in a random order each time. It’s easiest to see this if you redirect the output into a file. And while you’re looking at the file, remember, you’re not really hungry. (You just want the ice cream, you don’t need it.)

To summarize what we’ve seen so far, your first, most efficient choice to hold a group of objects should be an array, and you’re forced into this choice if you want to hold a group of primitives. In the remainder of the chapter we’ll look at the more general case, when you don’t know at the time you’re writing the program how many objects you’re going to need, or if you need a more sophisticated way to store your objects. Java provides four types of collection classes to solve this problem: Vector, BitSet, Stack, and Hashtable. Although compared to other languages that provide collections this is a fairly meager supply, you can nonetheless solve a surprising number of problems using these tools.

Among their other characteristics – Stack, for example, implements a LIFO (last-in, first-out) sequence, and Hashtable is an associative array that lets you associate any object with any other object – the Java collection classes will automatically resize themselves. Thus, you can put in any number of objects and you don’t need to worry about how big to make the collection while you’re writing the program.

The “disadvantage” to using the Java collections is that you lose type information when you put an object into a collection. This happens because, when the collection was written, the programmer of that collection had no idea what specific type you wanted to put in the collection, and making the collection hold only your type would prevent it from being a general-purpose tool. So instead, the collection holds handles to objects of type Object, which is of course every object in Java, since it’s the root of all the classes. (Of course, this doesn’t include primitive types, since they aren’t inherited from anything.) This is a great solution, except for these reasons:

On the up side, Java won’t let you misuse the objects that you put into a collection. If you throw a dog into a collection of cats, then go through and try to treat everything in the collection as a cat, you’ll get an exception when you get to the dog. In the same vein, if you try to cast the dog handle that you pull out of the cat collection into a cat, you’ll get an exception at run-time.

Here’s an example:

You can see that using a Vector is straightforward: create one, put objects in using addElement( ), and later get them out with elementAt( ). (Note that Vector has a method size( ) to let you know how many elements have been added so you don’t inadvertently run off the end and cause an exception.)

The classes Cat and Dog are distinct – they have nothing in common except that they are Objects. (If you don’t explicitly say what class you’re inheriting from, you automatically inherit from Object.) The Vector class, which comes from java.util, holds Objects, so not only can you put Cat objects into this collection using the Vector method addElement( ), but you can also add Dog objects without complaint at either compile-time or run-time. When you go to fetch out what you think are Cat objects using the Vector method elementAt( ), you get back a handle to an Object that you must cast to a Cat. Then you need to surround the entire expression with parentheses to force the evaluation of the cast before calling the print( ) method for Cat, otherwise you’ll get a syntax error. Then, at run-time, when you try to cast the Dog object to a Cat, you’ll get an exception.

This is more than just an annoyance. It’s something that can create some difficult-to-find bugs. If one part (or several parts) of a program inserts objects into a collection, and you discover only in a separate part of the program through an exception that a bad object was placed in the collection, then you must find out where the bad insert occurred. You do this by code inspection, which is about the worst debugging tool you have. On the upside, it’s convenient to start with some standardized collection classes for programming, despite the scarcity and awkwardness.

It turns out that in some cases things seem to work correctly without casting back to your original type. The first case is quite special: the String class has some extra help from the compiler to make it work smoothly. Whenever the compiler expects a String object and it hasn’t got one, it will automatically call the toString( ) method that’s defined in Object and can be overridden by any Java class. This method produces the desired String object, which is then used wherever it was wanted.

Thus, all you need to do to make objects of your class print out is to override the toString( ) method, as shown in the following example:

You can see the redefinition of toString( ) in Mouse. In the second for loop in main( ) you find the statement:

After the ‘+’ sign the compiler expects to see a String object. elementAt( ) produces an Object, so to get the desired String the compiler implicitly calls toString( ). Unfortunately, you can work this kind of magic only with String; it isn’t available for any other type.

A second approach to hiding the cast has been placed inside Mousetrap. The caughtYa( ) method accepts not a Mouse, but an Object, which it then casts to a Mouse. This is quite presumptuous, of course, since by accepting an Object anything could be passed to the method. However, if the cast is incorrect – if you passed the wrong type – you’ll get an exception at run-time. This is not as good as compile-time checking but it’s still robust. Note that in the use of this method:

no cast is necessary.

You might not want to give up on this issue just yet. A more ironclad solution is to create a new class using the Vector, such that it will accept only your type and produce only your type:

This is similar to the previous example, except that the new GopherVector class has a private member of type Vector (inheriting from Vector tends to be frustrating, for reasons you’ll see later), and methods just like Vector. However, it doesn’t accept and produce generic Objects, only Gopher objects.

Because a GopherVector will accept only a Gopher, if you were to say:

you would get an error message at compile time. This approach, while more tedious from a coding standpoint, will tell you immediately if you’re using a type improperly.

Note that no cast is necessary when using elementAt( ) – it’s always a Gopher.

This kind of problem isn’t isolated – there are numerous cases in which you need to create new types based on other types, and in which it is useful to have specific type information at compile-time. This is the concept of a parameterized type. In C++, this is directly supported by the language in templates. At one point, Java had reserved the keyword generic to someday support parameterized types, but it’s uncertain if this will ever occur.

In any collection class, you must have a way to put things in and a way to get things out. After all, that’s the primary job of a collection – to hold things. In the Vector, addElement( ) is the way that you insert objects, and elementAt( ) is one way to get things out. Vector is quite flexible – you can select anything at any time, and select multiple elements at once using different indexes.

If you want to start thinking at a higher level, there’s a drawback: you need to know the exact type of the collection in order to use it. This might not seem bad at first, but what if you start out using a Vector, and later on in your program you decide, for efficiency, that you want to change to a List (which is part of the Java 1.2 collections library)? Or you’d like to write a piece of code that doesn’t know or care what type of collection it’s working with.

The concept of an iterator can be used to achieve this next level of abstraction. This is an object whose job is to move through a sequence of objects and select each object in that sequence without the client programmer knowing or caring about the underlying structure of that sequence. In addition, an iterator is usually what’s called a “light-weight” object; that is, one that’s cheap to create. For that reason, you’ll often find seemingly strange constraints for iterators; for example, some iterators can move in only one direction.

The Java Enumeration[33] is an example of an iterator with these kinds of constraints. There’s not much you can do with one except:

That’s all. It’s a simple implementation of an iterator, but still powerful. To see how it works, let’s revisit the CatsAndDogs.java program from earlier in the chapter. In the original version, the method elementAt( ) was used to select each element, but in the following modified version an enumeration is used:

You can see that the only change is in the last few lines. Instead of:

an Enumeration is used to step through the sequence:

With the Enumeration, you don’t need to worry about the number of elements in the collection. That’s taken care of for you by hasMoreElements( ) and nextElement( ).

As another example, consider the creation of a general-purpose printing method:

Look closely at the printing method:

Note that there’s no information about the type of sequence. All you have is an Enumeration, and that’s all you need to know about the sequence: that you can get the next object, and that you can know when you’re at the end. This idea of taking a collection of objects and passing through it to perform an operation on each one is powerful and will be seen throughout this book.

This particular example is even more generic, since it uses the ubiquitous toString( ) method (ubiquitous only because it’s part of the Object class). An alternative way to call print (although probably slightly less efficient, if you could even notice the difference) is:

which uses the “automatic conversion to String” that’s wired into Java. When the compiler sees a String, followed by a ‘+’, it expects another String to follow and calls toString( ) automatically. (In Java 1.1, the first String is unnecessary; any object will be converted to a String.) You can also perform a cast, which has the effect of calling toString( ):

In general, however, you’ll want to do something more than call Object methods, so you’ll run up against the type-casting issue again. You must assume you’ve gotten an Enumeration to a sequence of the particular type you’re interested in, and cast the resulting objects to that type (getting a run-time exception if you’re wrong).

The standard Java 1.0 and 1.1 library comes with a bare minimum set of collection classes, but they’re probably enough to get by with for many of your programming projects. (As you’ll see at the end of this chapter, Java 1.2 provides a radically redesigned and filled-out library of collections.)

The Vector is quite simple to use, as you’ve seen so far. Although most of the time you’ll just use addElement( ) to insert objects, elementAt( ) to get them out one at a time, and elements( ) to get an Enumeration to the sequence, there’s also a set of other methods that can be useful. As usual with the Java libraries, we won’t use or talk about them all here, but be sure to look them up in the electronic documentation to get a feel for what they can do.

The Java standard collections contain a toString( ) method so they can produce a String representation of themselves, including the objects they hold. Inside of Vector, for example, the toString( ) steps through the elements of the Vector and calls toString( ) for each one. Suppose you’d like to print out the address of your class. It seems to make sense to simply refer to this (in particular, C++ programmers are prone to this approach):

It turns out that if you simply create a CrashJava object and print it out, you’ll get an endless sequence of exceptions. However, if you place the CrashJava objects in a Vector and print out that Vector as shown here, it can’t handle it and you don’t even get an exception; Java just crashes. (But at least it didn’t bring down my operating system.) This was tested with Java 1.1.

What’s happening is automatic type conversion for Strings. When you say:

The compiler sees a String followed by a ‘+’ and something that’s not a String, so it tries to convert this to a String. It does this conversion by calling toString( ), which produces a recursive call. When this occurs inside a Vector, it appears that the stack overflows without the exception-handling mechanism getting a chance to respond.

If you really do want to print the address of the object in this case, the solution is to call the Object toString( ) method, which does just that. So instead of saying this, you’d say super.toString( ). (This only works if you're directly inheriting from Object or if none of your parent classes have overridden the toString( ) method).

A BitSet is really a Vector of bits, and it is used if you want to efficiently store a lot of on-off information. It’s efficient only from the standpoint of size; if you’re looking for efficient access, it is slightly slower than using an array of some native type.

In addition, the minimum size of the BitSet is that of a long: 64 bits. This implies that if you’re storing anything smaller, like 8 bits, a BitSet will be wasteful, so you’re better off creating your own class to hold your flags.

In a normal Vector, the collection will expand as you add more elements. The BitSet does this as well – sort of. That is, sometimes it works and sometimes it doesn’t, which makes it appear that the Java version 1.0 implementation of BitSet is just badly done. (It is fixed in Java 1.1.) The following example shows how the BitSet works and demonstrates the version 1.0 bug:

The random number generator is used to create a random byte, short, and int, and each one is transformed into a corresponding bit pattern in a BitSet. This works fine because a BitSet is 64 bits, so none of these cause it to increase in size. But in Java 1.0, when the BitSet is greater than 64 bits, some strange behavior occurs. If you set a bit that’s just one greater than the BitSet’s currently-allocated storage, it will expand nicely. But if you try to set bits at higher locations than that without first just touching the boundary, you’ll get an exception, since the BitSet won’t expand properly in Java 1.0. The example shows a BitSet of 512 bits being created. The constructor allocates storage for twice that number of bits. Then if you try to set bit 1024 or greater without first setting bit 1023, you’ll throw an exception in Java 1.0. Fortunately, this is fixed in Java 1.1, but avoid using the BitSet if you write code for Java 1.0.

A Stack is sometimes referred to as a “last-in, first-out” (LIFO) collection. That is, whatever you “push” on the Stack last is the first item you can “pop” out. Like all of the other collections in Java, what you push and pop are Objects, so you must cast what you pop.

What’s rather odd is that instead of using a Vector as a building block to create a Stack, Stack is inherited from Vector. So it has all of the characteristics and behaviors of a Vector plus some extra Stack behaviors. It’s difficult to know whether the designers explicitly decided that this was an especially useful way to do things, or whether it was just a naïve design.

Here’s a simple demonstration of Stack that reads each line from an array and pushes it as a String:

Each line in the months array is inserted into the Stack with push( ), and later fetched from the top of the stack with a pop( ). To make a point, Vector operations are also performed on the Stack object. This is possible because, by virtue of inheritance, a Stack is a Vector. Thus, all operations that can be performed on a Vector can also be performed on a Stack, such as elementAt( ).

A Vector allows you to select from a sequence of objects using a number, so in a sense it associates numbers to objects. But what if you’d like to select from a sequence of objects using some other criterion? A Stack is an example: its selection criterion is “the last thing pushed on the stack.” A powerful twist on this idea of “selecting from a sequence” is alternately termed a map, a dictionary, or an associative array. Conceptually, it seems like a vector, but instead of looking up objects using a number, you look them up using another object! This is often a key process in a program.

The concept shows up in Java as the abstract class Dictionary. The interface for this class is straightforward: size( ) tells you how many elements are within, isEmpty( ) is true if there are no elements, put(Object key, Object value) adds a value (the thing you want), and associates it with a key (the thing you look it up with). get(Object key) produces the value given the corresponding key, and remove(Object key) removes the key-value pair from the list. There are enumerations: keys( ) produces an Enumeration of the keys, and elements( ) produces an Enumeration of all the values. That’s all there is to a Dictionary.

A Dictionary isn’t terribly difficult to implement. Here’s a simple approach, which uses two Vectors, one for keys and one for values:

The first thing you see in the definition of AssocArray is that it extends Dictionary. This means that AssocArray is a type of Dictionary, so you can make the same requests of it that you can a Dictionary. If you make your own Dictionary, as is done here, all you need to do is fill in all the methods that are in Dictionary. (And you must override all the methods because all of them – with the exception of the constructor – are abstract.)

The Vectors keys and values are linked by a common index number. That is, if you call put( ) with a key of “roof” and a value of “blue” (assuming you’re associating the various parts of a house with the colors they are to be painted) and there are already 100 elements in the AssocArray, then “roof” will be the 101 element of keys and “blue” will be the 101 element of values. And if you look at get( ), when you pass “roof” in as the key, it produces the index number with keys.indexOf( ), and then uses that index number to produce the value in the associated values vector.

The test in main( ) is simple; it’s just a map of lowercase characters to uppercase characters, which could obviously be done in a number of more efficient ways. But it shows that AssocArray is functional.

The standard Java library contains only one embodiment of a Dictionary, called Hashtable.[34] Java’s Hashtable has the same basic interface as AssocArray (since they both inherit Dictionary), but it differs in one distinct way: efficiency. If you look at what must be done for a get( ), it seems pretty slow to search through a Vector for the key. This is where Hashtable speeds things up. Instead of the tedious linear search for the key, it uses a special value called a hash code. The hash code is a way to take some information in the object in question and turn it into a “relatively unique” int for that object. All objects have a hash code, and hashCode( ) is a method in the root class Object. A Hashtable takes the hashCode( ) of the object and uses it to quickly hunt for the key. This results in a dramatic performance improvement.[35] The way that a Hashtable works is beyond the scope of this book[36] – all you need to know is that Hashtable is a fast Dictionary, and that a Dictionary is a useful tool.

As an example of the use of a Hashtable, consider a program to check the randomness of Java’s Math.random( ) method. Ideally, it would produce a perfect distribution of random numbers, but to test this you need to generate a bunch of random numbers and count the ones that fall in the various ranges. A Hashtable is perfect for this, since it associates objects with objects (in this case, the values produced by Math.random( ) with the number of times those values appear):

In main( ), each time a random number is generated it is wrapped inside an Integer object so that handle can be used with the Hashtable. (You can’t use a primitive with a collection, only an object handle.) The containsKey( ) method checks to see if this key is already in the collection. (That is, has the number been found already?) If so, the get( ) methods gets the associated value for the key, which in this case is a Counter object. The value i inside the counter is then incremented to indicate that one more of this particular random number has been found.

If the key has not been found yet, the method put( ) will place a new key-value pair into the Hashtable. Since Counter automatically initializes its variable i to one when it’s created, it indicates the first occurrence of this particular random number.

To display the Hashtable, it is simply printed out. The Hashtable toString( ) method moves through all the key-value pairs and calls the toString( ) for each one. The Integer toString( ) is pre-defined, and you can see the toString( ) for Counter. The output from one run (with some line breaks added) is:

You might wonder at the necessity of the class Counter, which seems like it doesn’t even have the functionality of the wrapper class Integer. Why not use int or Integer? Well, you can’t use an int because all of the collections can hold only Object handles. After seeing collections the wrapper classes might begin to make a little more sense to you, since you can’t put any of the primitive types in collections. However, the only thing you can do with the Java wrappers is to initialize them to a particular value and read that value. That is, there’s no way to change a value once a wrapper object has been created. This makes the Integer wrapper immediately useless to solve our problem, so we’re forced to create a new class that does satisfy the need.

In the previous example, a standard library class (Integer) was used as a key for the Hashtable. It worked fine as a key, because it has all the necessary wiring to make it work correctly as a key. But a common pitfall occurs when using Hashtables when you create your own classes to be used as keys. For example, consider a weather predicting system that matches Groundhog objects to Prediction objects. It seems fairly straightforward: you create the two classes and use Groundhog as the key and Prediction as the value:

Each Groundhog is given an identity number, so you can look up a Prediction in the Hashtable by saying “Give me the Prediction associated with Groundhog number 3.” The Prediction class contains a boolean that is initialized using Math.random( ), and a toString( ) that interprets the result for you. In main( ), a Hashtable is filled with Groundhogs and their associated Predictions. The Hashtable is printed so you can see that it has been filled. Then a Groundhog with an identity number of 3 is used to look up the prediction for Groundhog #3.

It seems simple enough, but it doesn’t work. The problem is that Groundhog is inherited from the common root class Object (which is what happens if you don’t specify a base class, thus all classes are ultimately inherited from Object). It is Object’s hashCode( ) method that is used to generate the hash code for each object, and by default it just uses the address of its object. Thus, the first instance of Groundhog(3) does not produce a hash code equal to the hash code for the second instance of Groundhog(3) that we tried to use as a lookup.

You might think that all you need to do is write an appropriate override for hashCode( ). But it still won’t work until you’ve done one more thing: override the equals( ) that is also part of Object. This method is used by the Hashtable when trying to determine if your key is equal to any of the keys in the table. Again, the default Object.equals( ) simply compares object addresses, so one Groundhog(3) is not equal to another Groundhog(3).

Thus, to use your own classes as keys in a Hashtable, you must override both hashCode( ) and equals( ), as shown in the following solution to the problem above:

Note that this uses the Prediction class from the previous example, so SpringDetector.java must be compiled first or you’ll get a compile-time error when you try to compile SpringDetector2.java.

Groundhog2.hashCode( ) returns the ground hog number as an identifier. (In this example, the programmer is responsible for ensuring that no two ground hogs exist with the same ID number.) The hashCode( ) is not required to return a unique identifier, but the equals( ) method must be able to strictly determine whether two objects are equivalent.

Even though it appears that the equals( ) method is only checking to see whether the argument is an instance of Groundhog2 (using the instanceof keyword, which is fully explained in Chapter 11), the instanceof actually quietly does a second sanity check, to see if the object is null, since instanceof produces false if the left-hand argument is null. Assuming it’s the correct type and not null, the comparison is based on the actual ghNumbers. This time, when you run the program, you’ll see it produces the correct output. (Many of the Java library classes override the hashCode( ) and equals( ) methods to be based upon their contents.)

In the first example in this book, a type of Hashtable was used called Properties. In that example, the lines:

called the static method getProperties( ) to get a special Properties object that described the system characteristics. The method list( ) is a method of Properties that sends the contents to any stream output that you choose. There’s also a save( ) method to allow you to write your property list to a file in a way that it can be retrieved later with the load( ) method.

Although the Properties class is inherited from Hashtable, it also contains a second Hashtable that acts to hold the list of “default” properties. So if a property isn’t found in the primary list, the defaults will be searched.

The Properties class is also available for use in your programs (an example is ClassScanner.java in Chapter 17). You can find more complete details in the Java library documentation.

We can now demonstrate the true power of the Enumeration: the ability to separate the operation of traversing a sequence from the underlying structure of that sequence. In the following example, the class PrintData uses an Enumeration to move through a sequence and call the toString( ) method for every object. Two different types of collections are created, a Vector and a Hashtable, and they are each filled with, respectively, Mouse and Hamster objects. (These classes are defined earlier in the chapter; notice you must have compiled HamsterMaze.java and WorksAnyway.java for the following program to compile.) Because an Enumeration hides the structure of the underlying collection, PrintData doesn’t know or care what kind of collection the Enumeration comes from:

Note that PrintData.print( ) takes advantage of the fact that the objects in these collections are of class Object so it can call toString( ). It’s more likely that in your problem, you must make the assumption that your Enumeration is walking through a collection of some specific type. For example, you might assume that everything in the collection is a Shape with a draw( ) method. Then you must downcast from the Object that Enumeration.nextElement() returns to produce a Shape.

One of the things missing in the Java 1.0 and 1.1 libraries is algorithmic operations, even simple sorting. So it makes sense to create a Vector that sorts itself using the classic Quicksort.

A problem with writing generic sorting code is that sorting must perform comparisons based on the actual type of the object. Of course, one approach is to write a different sorting method for every different type, but you should be able to recognize that this does not produce code that is easily re-used for new types.

A primary goal of programming design is to “separate things that change from things that stay the same,” and here, the code that stays the same is the general sort algorithm, but the thing that changes from one use to the next is the way objects are compared. So instead of hard-wiring the comparison code into many different sort routines, the technique of the callback will be used. With a callback, the part of the code that varies from case to case is encapsulated inside its own class, and the part of the code that’s always the same will call back to the code that changes. That way you can make different objects to express different ways of comparison and feed them to the same sorting code.

The following interface describes how to compare two objects, and thus encapsulates “the things that change” for this particular problem:

For both methods, the lhs represents the “left hand” object and the rhs represents the “right hand” object in the comparison.

A subclass of Vector can be created that implements the Quicksort using Compare. The algorithm, which is known for its speed, will not be explained here. For details, see Practical Algorithms for Programmers, by Binstock & Rex, Addison-Wesley 1995.

You can now see the reason for the term “callback,” since the quickSort( ) method “calls back” to the methods in Compare. You can also see how this technique has produced generic, reusable code.

To use the SortVector, you must create a class that implements Compare for the kind of objects that you’re sorting. This is a place where an inner class is not essential, but it can make sense for code organization. Here’s an example for String objects:

The inner class is static because it does not need a link to an outer class in order for it to function.

You can see how, once the framework is set up, it’s easy to reuse a design like this – you simply write the class that encapsulates “the things that change” and hand an object to the SortVector.

The comparison forces the strings to lower case, so that the capital A’s end up next to the small a’s and not in some entirely different place. This example shows, however, a slight deficiency in this approach, since the test code above puts the uppercase and lowercase single letters of the same letter in the order that they appear: A a b B c C d D. This is not usually much of a problem, because you’re usually working with longer strings and in that situation the effect doesn’t show up. (The Java 1.2 collections provide sorting functionality that solves this problem.)

Inheritance (extends) is used here to create a new type of Vector – that is, SortVector is a Vector with some added functionality. The use of inheritance here is powerful but it presents problems. It turns out that some methods are final (described in Chapter 7), so you cannot override them. If you want to create a sorted Vector that accepts and produces only String objects you run into a wall, since addElement( ) and elementAt( ) are final, and these are precisely the methods you’d need to override so they accept and produce only String objects. No luck there.

On the other hand, consider composition: the placing of an object inside a new class. Rather than rewrite the above code to accomplish this, we can simply use a SortVector inside the new class. In this case, the inner class to implement the interface Compare will be created anonymously:

This quickly reuses the code from SortVector to create the desired functionality. However, not all of the public methods from SortVector and Vector appear in StrSortVector. When reusing code this way, you can make a definition in the new class for each one in the contained class, or you can start with just a few and periodically go back and add more when you need them. Eventually the new class design will settle down.

The advantage to this approach is that it will take only String objects and produce only String objects, and the checking happens at compile time instead of run time. Of course, that’s only true for addElement( ) and elementAt( ); elements( ) still produces an Enumeration that is untyped at compile time. Type checking for the Enumeration and in StrSortVector still happens, of course, it just happens at run-time by throwing exceptions if you do something wrong. It’s a trade-off: do you find out about something for sure at compile time or probably at run-time? (That is, “probably not while you’re testing the code” and “probably when the program user tries something you didn’t test for.”) Given the choices and the hassle, it’s easier to use inheritance and just grit your teeth while casting – again, if parameterized types are ever added to Java, they will solve this problem.

You can see there’s a flag called sorted in this class. You could sort the vector every time addElement( ) is called, and constantly keep it in a sorted state. But usually people add a lot of elements to a Vector before beginning to read it. So sorting after every addElement( ) would be less efficient than waiting until someone wants to read the vector and then sorting it, which is what is done here. The technique of delaying a process until it is absolutely necessary is called lazy evaluation. (There is an analogous technique called lazy initialization which waits until a field value is necessary before initializing it.)

You’ve seen in this chapter that the standard Java library has some fairly useful collections, but far from a complete set. In addition, algorithms like sorting are not supported at all. One of the strengths of C++ is its libraries, in particular the Standard Template Library (STL) that provides a fairly full set of collections as well as many algorithms like sorting and searching that work with those collections. Based on this model, the ObjectSpace company was inspired to create the Generic Collection Library for Java (formerly called the Java Generic Library, but the abbreviation JGL is still used – the old name infringed on Sun’s copyright), which follows the design of the STL as much as possible (given the differences between the two languages). The JGL seems to fulfill many, if not all, of the needs for a collection library, or as far as one could go in this direction without C++’s template mechanism. The JGL includes linked lists, sets, queues, maps, stacks, sequences, and iterators that are far more functional than Enumeration, as well as a full set of algorithms such as searching and sorting. ObjectSpace also made, in some cases, more intelligent design decisions than the Sun library designers. For example, the methods in the JGL collections are not final so it’s easy to inherit and override those methods.

The JGL has been included in some vendors’ Java distributions and ObjectSpace has made the JGL freely available for all uses, including commercial use, at http://www.ObjectSpace.com. The online documentation that comes in the JGL package is quite good and should be adequate to get you started.

To me, collection classes are one of the most powerful tools for raw programming. You might have gathered that I’m somewhat disappointed in the collections provided in Java through version 1.1. As a result, it’s a tremendous pleasure to see that collections were given proper attention in Java 1.2, and thoroughly redesigned (by Joshua Bloch at Sun). I consider the new collections to be one of the two major features in Java 1.2 (the other is the Swing library, covered in Chapter 13) because they significantly increase your programming muscle and help bring Java in line with more mature programming systems.

Some of the redesign makes things tighter and more sensible. For example, many names are shorter, cleaner, and easier to understand, as well as to type. Some names are changed to conform to accepted terminology: a particular favorite of mine is “iterator” instead of “enumeration.”

The redesign also fills out the functionality of the collections library. You can now have the behavior of linked lists, queues, and dequeues (double-ended queues, pronounced “decks”).

The design of a collections library is difficult (true of most library design problems). In C++, the STL covered the bases with many different classes. This was better than what was available prior to the STL (nothing), but it didn’t translate well into Java. The result was a rather confusing morass of classes. On the other extreme, I’ve seen a collections library that consists of a single class, “collection,” which acts like a Vector and a Hashtable at the same time. The designers of the new collections library wanted to strike a balance: the full functionality that you expect from a mature collections library, but easier to learn and use than the STL and other similar collections libraries. The result can seem a bit odd in places. Unlike some of the decisions made in the early Java libraries, these oddities were not accidents, but carefully considered decisions based on tradeoffs in complexity. It might take you a little while to get comfortable with some aspects of the library, but I think you’ll find yourself rapidly acquiring and using these new tools.

The new collections library takes the issue of “holding your objects” and divides it into two distinct concepts:

Collections and Maps may be implemented in many different ways, according to your programming needs. It’s helpful to look at a diagram of the new collections:

This diagram can be a bit overwhelming at first, but throughout the rest of this section you’ll see that there are really only three collection components: Map, List, and Set, and only two or three implementations of each one (with, typically, a preferred version). When you see this, the new collections should not seem so daunting.

The dashed boxes represent interfaces, the dotted boxes represent abstract classes, and the solid boxes are regular (concrete) classes. The dashed arrows indicate that a particular class is implementing an interface (or in the case of an abstract class, partially implementing that interface). The double-line arrows show that a class can produce objects of the class the arrow is pointing to. For example, any Collection can produce an Iterator, while a List can produce a ListIterator (as well as an ordinary Iterator, since List is inherited from Collection).

The interfaces that are concerned with holding objects are Collection, List, Set, and Map. Typically, you’ll write the bulk of your code to talk to these interfaces, and the only place where you’ll specify the precise type you’re using is at the point of creation. So you can create a List like this:

Of course, you can also decide to make x a LinkedList (instead of a generic List) and carry the precise type information around with x. The beauty (and the intent) of using the interface is that if you decide you want to change your implementation, all you need to do is change it at the point of creation, like this:

The rest of your code can remain untouched.

In the class hierarchy, you can see a number of classes whose names begin with “Abstract,” and these can seem a bit confusing at first. They are simply tools that partially implement a particular interface. If you were making your own Set, for example, you wouldn’t start with the Set interface and implement all the methods, instead you’d inherit from AbstractSet and do the minimal necessary work to make your new class. However, the new collections library contains enough functionality to satisfy your needs virtually all the time. So for our purposes, you can ignore any class that begins with “Abstract.”

Therefore, when you look at the diagram, you’re really concerned with only those interfaces at the top of the diagram and the concrete classes (those with solid boxes around them). You’ll typically make an object of a concrete class, upcast it to the corresponding interface, and then use the interface throughout the rest of your code. Here’s a simple example, which fills a Collection with String objects and then prints each element in the Collection:

All the code examples for the new collections libraries will be placed in the subdirectory newcollections, so you’ll be reminded that these work only with Java 1.2. As a result, you must invoke the program by saying:

with a similar syntax for the rest of the programs in the package.

You can see that the new collections are part of the java.util library, so you don’t need to add any extra import statements to use them.

The first line in main( ) creates an ArrayList object and then upcasts it to a Collection. Since this example uses only the Collection methods, any object of a class inherited from Collection would work, but ArrayList is the typical workhorse Collection and takes the place of Vector.

The add( ) method, as its name suggests, puts a new element in the Collection. However, the documentation carefully states that add( ) “ensures that this Collection contains the specified element.” This is to allow for the meaning of Set, which adds the element only if it isn’t already there. With an ArrayList, or any sort of List, add( ) always means “put it in.”

All Collections can produce an Iterator via their iterator( ) method. An Iterator is just like an Enumeration, which it replaces, except:

In SimpleCollection.java, you can see that an Iterator is created and used to traverse the Collection, printing each element.

The following table shows everything you can do with a Collection, and thus, everything you can do with a Set or a List. (List also has additional functionality.) Maps are not inherited from Collection, and will be treated separately.

Boolean add(Object)	*Ensures that the Collection contains the argument. Returns false if it doesn’t add the argument.
Boolean addAll(Collection)	*Adds all the elements in the argument. Returns true if any elements were added.
void clear( )	*Removes all the elements in the Collection.
Boolean contains(Object)	True if the Collection contains the argument.
Boolean containsAll(Collection)	True if the Collection contains all the elements in the argument.
Boolean isEmpty( )	True if the Collection has no elements.
Iterator iterator( )	Returns an Iterator that you can use to move through the elements in the Collection.
Boolean remove(Object)	*If the argument is in the Collection, one instance of that element is removed. Returns true if a removal occurred.
Boolean removeAll(Collection)	*Removes all the elements that are contained in the argument. Returns true if any removals occurred.
Boolean retainAll(Collection)	*Retains only elements that are contained in the argument (an “intersection” from set theory). Returns true if any changes occurred.
int size( )	Returns the number of elements in the Collection.
Object[] toArray( )	Returns an array containing all the elements in the Collection.
Object[] toArray(Object[] a)	Returns an array containing all the elements in the Collection, whose type is that of the array a rather than plain Object (you must cast the array to the right type).