The generic collection library

The generic collection library

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 https://www.ObjectSpace.com. The online documentation that comes in the JGL package is quite good and should be adequate to get you started.

The new collections

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:

Collection: a group of individual elements, often with some rule applied to them. A List must hold the elements in a particular sequence, and a Set cannot have any duplicate elements. (A bag, which is not implemented in the new collections library since Lists provide you with that functionality, has no such rules.)

Map: a group of key-value object pairs (what you've seen up until now as a Hashtable). At first glance, this might seem like it ought to be a Collection of pairs, but when you try to implement it that way the design gets awkward, so it's clearer to make it a separate concept. On the other hand, it's convenient to look at portions of a Map by creating a Collection to represent that portion. Thus, a Map can return a Set of its keys, a List of its values, or a List of its pairs. Maps, like arrays, can easily be expanded to multiple dimensions without adding new concepts: you simply make a Map whose values are Maps (and the values of those Maps can be Maps, etc.).

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 chapter 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:

It uses a name (iterator) that is historically understood and accepted in the OOP community.

It uses shorter method names than Enumeration: hasNext( ) instead of hasMoreElements( ), and next( ) instead of nextElement( ).

It adds a new method, remove( ), which removes the last element produced by the Iterator. So you can call remove( ) only once for every time you call next( ).

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

Using Collections

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.

The following example demonstrates all of these methods. Again, these work with anything that inherits from Collection; an ArrayList is used as a kind of "least-common denominator":

The first methods provide a way to fill any Collection with test data, in this case just ints converted to Strings. The second method will be used frequently throughout the rest of this chapter.

The two versions of newCollection( ) create ArrayLists containing different sets of data and return them as Collection objects, so it's clear that nothing other than the Collection interface is being used.

The print( ) method will also be used throughout the rest of this section. Since it moves through a Collection using an Iterator, which any Collection can produce, it will work with Lists and Sets and any Collection that a Map produces.

main( ) uses simple exercises to show all of the methods in Collection.

The following sections compare the various implementations of List, Set, and Map and indicate in each case (with an asterisk) which one should be your default choice. You'll notice that the legacy classes Vector, Stack, and Hashtable are not included because in all cases there are preferred classes within the new collections.