Collections

Collections are data structures that are fundamental to all types of programming. Whenever we need to refer to a group of objects, we have some kind of collection. At the core language level, Java supports collections in the form of arrays. But arrays are static and because they have a fixed length, they are awkward for groups of things that grow and shrink over the lifetime of an application. Arrays also do not represent abstract relationships between objects well. In the early days, the Java platform had only two basic classes to address these needs: the java.util.Vector class, which represents a dynamic list of objects, and the java.util.Hashtable class, which holds a map of key/value pairs. Today, Java has a more comprehensive approach to collections called the Collections Framework. The older classes still exist, but they have been retrofitted into the framework (with some eccentricities) and are generally no longer used.

Though conceptually simple, collections are one of the most powerful parts of any programming language. Collections implement data structures that lie at the heart of managing complex problems. A great deal of basic computer science is devoted to describing the most efficient ways to implement certain types of algorithms over collections. Having these tools at your disposal and understanding how to use them can make your code both much smaller and faster. It can also save you from reinventing the wheel.

The original Collections Framework had two major drawbacks. The first was that collections were by necessity untyped and worked only with undifferentiated Objects instead of specific types like Dates and Strings. This meant that you had to perform a type cast every time you took an object out of a collection. This flew in the face of Java’s compile-time type safety. But in practice, this was less a problem than it was just plain cumbersome and tedious. The second issue was that, for practical reasons, collections could work only with objects and not with primitive types. This meant that any time you wanted to put a number or other primitive type into a collection, you had to store it in a wrapper class first and unpack it later upon retrieving it. The combination of these factors made code working with collections less readable and more dangerous to boot.

This all changed with the introduction of generic types and autoboxing of primitive values. First, the introduction of generic types (again, more on this in “Type Limitations”) has made it possible for truly typesafe collections to be under the control of the programmer. Second, the introduction of autoboxing and unboxing of primitive types means that you can generally treat objects and primitives as equals where collections are concerned. The combination of these new features can significantly reduce the amount of code you write and add safety as well. As we’ll see, all of the collections classes now take advantage of these features.

The Collections Framework is based around a handful of interfaces in the java.util package. These interfaces are divided into two hierarchies. The first hierarchy descends from the Collection interface. This interface (and its descendants) represents a container that holds other objects. The second, separate hierarchy is based on the Map interface, which represents a group of key/value pairs where the key can be used to retrieve the value in an efficient way.

    Map<String, Date> dateMap = new HashMap<String, Date>();
    dateMap.put( "today", new Date() );
    Date today = dateMap.get( "today" );

Type Limitations

Generics are about abstraction. Generics let you create classes and methods that work in the same way on different types of objects. The term generic comes from the idea that we’d like to be able to write general algorithms that can be broadly reused for many types of objects rather than having to adapt our code to fit each circumstance. This concept is not new; it is the impetus behind object-oriented programming itself. Java generics do not so much add new capabilities to the language as they make reusable Java code easier to write and easier to read.

Generics take reuse to the next level by making the type of the objects with which we work into an explicit parameter of the generic code. For this reason, generics are also referred to as parameterized types. In the case of a generic class, the developer specifies a type as a parameter (an argument) whenever she uses the generic type. The class is parameterized by the supplied type to which the code adapts itself.

In other languages, generics are sometimes referred to as templates, which is more of an implementation term. Templates are like intermediate classes, waiting for their type parameters so that they can be used. Java takes a different path, which has both benefits and drawbacks that we’ll describe in detail in this chapter.

There is much to say about Java generics. Some of the fine points may seem a bit obscure at first, but don’t get discouraged. The vast majority of what you’ll do with generics—using existing classes such as List and Set, for example—is easy and intuitive. Designing and creating your own generics requires a more careful understanding and will come with a little patience and tinkering.

Indeed, we begin our discussion in that intuitive space with the most compelling case for generics: the container classes and collections we just covered. Next, we take a step back and look at the good, bad, and ugly of how Java generics work. We conclude by looking at a couple of real-world generic classes in the Java API.

    Date date = new Date();
    List list = new ArrayList();
    list.add( date );
    ...
    Date firstElement = (Date)list.get(0); // Is the cast correct?  Maybe.

jshell> import java.util.ArrayList;

jshell> import javax.swing.JLabel;

jshell> ArrayList things = new ArrayList();
things ==> []

jshell> things.add("Hi there");
|  Warning:
|  unchecked call to add(E) as a member of the raw type java.util.ArrayList
|  things.add("Hi there");
|  ^--------------------^
$3 ==> true

jshell> things.add(new JLabel("Hi there"));
|  Warning:
|  unchecked call to add(E) as a member of the raw type java.util.ArrayList
|  things.add(new JLabel("Hi there"));
|  ^--------------------------------^
$5 ==> true

jshell> things
things ==> [Hi there, javax.swing.JLabel[...,text=Hi there,...]]

    public void add( Object o ) { ... } // still here
    public void add( Date d ) { ... }   // overloaded method

Enter Generics

As we noted in introducing the type limitations in the previous section, generics are an enhancement to the syntax of classes that allow us to specialize the class for a given type or set of types. A generic class requires one or more type parameters wherever we refer to the class type and uses them to customize itself.

If you look at the source or Javadoc for the List class, for example, you’ll see it defined something like this:

    public class List< E > {
       ...
       public void add( E element ) { ... }
       public E get( int i ) { ... }
    }

The identifier E between the angle brackets (<>) is a type parameter.¹ It indicates that the class List is generic and requires a Java type as an argument to make it complete. The name E is arbitrary, but there are conventions that we’ll see as we go on. In this case, the type variable E represents the type of elements we want to store in the list. The List class refers to the type variable within its body and methods as if it were a real type, to be substituted later. The type variable may be used to declare instance variables, arguments to methods, and the return type of methods. In this case, E is used as the type for the elements we’ll be adding via the add() method and the return type of the get() method. Let’s see how to use it.

The same angle bracket syntax supplies the type parameter when we want to use the List type:

    List<String> listOfStrings;

In this snippet, we declared a variable called listOfStrings using the generic type List with a type parameter of String. String refers to the String class, but we could have specialized List with any Java class type. For example:

    List<Date> dates;
    List<java.math.BigDecimal> decimals;
    List<Foo> foos;

Completing the type by supplying its type parameter is called instantiating the type. It is also sometimes called invoking the type, by analogy with invoking a method and supplying its arguments. Whereas with a regular Java type, we simply refer to the type by name, a generic type must be instantiated with parameters wherever it is used.² Specifically, this means that we must instantiate the type everywhere types can appear as the declared type of a variable (as shown in this code snippet), as the type of a method argument, as the return type of a method, or in an object allocation expression using the new keyword.

Returning to our listOfStrings, what we have now is effectively a List in which the type String has been substituted for the type variable E in the class body:

    public class List< String > {
       ...
       public void add( String element ) { ... }
       public String get( int i ) { ... }
    }

We have specialized the List class to work with elements of type String and only elements of type String. This method signature is no longer capable of accepting an arbitrary Object type.

List is just an interface. To use the variable, we’ll need to create an instance of some actual implementation of List. As we did in our introduction, we’ll use ArrayList. As before, ArrayList is a class that implements the List interface, but in this case, both List and ArrayList are generic classes. As such, they require type parameters to instantiate them where they are used. Of course, we’ll create our ArrayList to hold String elements to match our List of Strings:

    List<String> listOfStrings = new ArrayList<String>
    // Or shorthand in Java 7.0 and later
    List<String> listOfStrings = new ArrayList<>();

As always, the new keyword takes a Java type and parentheses with possible arguments for the class’s constructor. In this case, the type is ArrayList<String>—the generic ArrayList type instantiated with the String type.

Declaring variables as shown in the first line of the preceding example is a bit cumbersome because it requires us to type the generic parameter type twice (once on the left side in the variable type and once on the right in the initialing expression). And in complicated cases, the generic types can get very lengthy and nested within one another. Starting with Java 7, the compiler is smart enough to infer the type of the initializing expression from the type of the variable to which you are assigning it. This is called generic type inference and boils down to the fact that you can use shorthand on the right side of your variable declarations by leaving out the contents of the <> notation, as shown in the example’s second version.

We can now use our specialized List with strings. The compiler prevents us from even trying to put anything other than a String object (or a subtype of String if there were any) into the list and allows us to fetch them with the get() method without requiring any cast:

jshell> ArrayList<String> listOfStrings = new ArrayList<>();
listOfStrings ==> []

jshell> listOfStrings.add("Hey!");
$8 ==> true

jshell> listOfStrings.add(new JLabel("Hey there"));
|  Error:
|  incompatible types: javax.swing.JLabel cannot be converted to java.lang.String
|  listOfStrings.add(new JLabel("Hey there"));
|                    ^---------------------^

jshell> String s = strings.get(0);
s ==> "Hey!"

Let’s take another example from the Collections API. The Map interface provides a dictionary-like mapping that associates key objects with value objects. Keys and values do not have to be of the same type. The generic Map interface requires two type parameters: one for the key type and one for the value type. The Javadoc looks like this:

    public class Map< K, V > {
        ...
        public V put( K key, V value ) { ... } // returns any old value
        public V get( K key ) { ... }
    }

We can make a Map that stores Employee objects by Integer “employee ID” numbers like this:

    Map< Integer, Employee > employees = new HashMap< Integer, Employee >();
    Integer bobsId = 314; // hooray for autoboxing!
    Employee bob = new Employee("Bob", ... );

    employees.put( bobsId, bob );
    Employee employee = employees.get( bobsId );

Here, we used HashMap, which is a generic class that implements the Map interface, and instantiated both types with the type parameters Integer and Employee. The Map now works only with keys of type Integer and holds values of type Employee.

The reason we used Integer here to hold our number is that the type parameters to a generic class must be class types. We can’t parameterize a generic class with a primitive type, such as int or boolean. Fortunately, autoboxing of primitives in Java (see “Wrappers for Primitive Types”) makes it almost appear as if we can by allowing us to use primitive types as though they were wrapper types.

Dozens of other APIs beyond collections use generics to let you adapt them to specific types. We’ll talk about them as they occur throughout the book.

“There Is No Spoon”

In the movie The Matrix,³ the hero Neo is offered a choice. Take the blue pill and remain in the world of fantasy, or take the red pill and see things as they really are. In dealing with generics in Java, we are faced with a similar ontological dilemma. We can go only so far in any discussion of generics before we are forced to confront the reality of how they are implemented. Our fantasy world is one created by the compiler to make our lives writing code easier to accept. Our reality (though not quite the dystopian nightmare in the movie) is a harsher place, filled with unseen dangers and questions. Why don’t casts and tests work properly with generics? Why can’t I implement what appear to be two different generic interfaces in one class? Why is it that I can declare an array of generic types, even though there is no way in Java to create such an array?!? We’ll answer these questions and more in this chapter, and you won’t even have to wait for the sequel. You’ll be bending spoons (well, types) in no time. Let’s get started.

The design goals for Java generics were formidable: add a radical new syntax to the language that safely introduces parameterized types with no impact on performance and, oh, by the way, make it backward-compatible with all existing Java code and don’t change the compiled classes in any serious way. It’s actually quite amazing that these conditions could be satisfied at all and no surprise that it took a while. But as always, compromises were required, which lead to some headaches.

    % javap java.util.List

    public interface java.util.List extends java.util.Collection{
        ...
        public abstract boolean add(java.lang.Object);
        public abstract java.lang.Object get(int);

    List<Date> dateList  = new ArrayList<Date>();
    System.out.println( dateList instanceof List ); // true!

    dateList.add( new Object() ); // Compile-time Error!

    System.out.println( dateList instanceof List<Date> ); // Compile-time Error!
    // Illegal, generic type for instanceof

    public abstract class DualList implements List<String>, List<Date> { }
    // Error: java.util.List cannot be inherited with different arguments:
    //    <java.lang.String> and <java.util.Date>

    // nongeneric Java code using the raw type
    List list = new ArrayList(); // assignment ok
    list.add("foo"); // Compiler warning on usage of raw type

    % javac MyClass.java
    Note: MyClass.java uses unchecked or unsafe operations.
    Note: Recompile with -Xlint:unchecked for details.

    % javac -Xlint:unchecked MyClass.java
    warning: [unchecked] unchecked call to add(E) as a member of the raw type
             java.util.
    List:   list.add("foo");

    class Bounded< E extends Date > {
        public void addElement( E element ) { ... }
    }

    public void addElement( Date element ) { ... }

Parameterized Type Relationships

We know now that parameterized types share a common, raw type. This is why our parameterized List<Date> is just a List at runtime. In fact, we can assign any instantiation of List to the raw type if we want:

    List list = new ArrayList<Date>();

We can even go the other way and assign a raw type to a specific instantiation of the generic type:

    List<Date> dates = new ArrayList(); // unchecked warning

This statement generates an unchecked warning on the assignment, but thereafter the compiler trusts that the list contained only Dates prior to the assignment. It is also permissible, albeit pointless, to perform a cast in this statement. We’ll talk about casting to generic types shortly in “Casts”.

Whatever the runtime types, the compiler is running the show and does not let us assign things that are clearly incompatible:

    List<Date> dates = new ArrayList<String>(); // Compile-time Error!

Of course, the ArrayList<String> does not implement the methods of List<Date> conjured by the compiler, so these types are incompatible.

But what about more interesting type relationships? The List interface, for example, is a subtype of the more general Collection interface. Is a particular instantiation of the generic List also assignable to some instantiation of the generic Collection? Does it depend on the type parameters and their relationships? Clearly, a List<Date> is not a Collection<String>. But is a List<Date> a Collection<Date>? Can a List<Date> be a Collection<Object>?

We’ll just blurt out the answer here first, then walk through it and explain. The rule is that for the simple types of generic instantiations we’ve discussed so far, inheritance applies only to the “base” generic type and not to the parameter types. Furthermore, assignability applies only when the two generic types are instantiated on exactly the same parameter type. In other words, there is still one-dimensional inheritance, following the base generic class type, but with the additional restriction that the parameter types must be identical.

For example, recalling that a List is a type of Collection, we can assign instantiations of List to instantiations of Collection when the type parameter is exactly the same:

    Collection<Date> cd;
    List<Date> ld = new ArrayList<Date>();
    cd = ld; // Ok!

This code snippet says that a List<Date> is a Collection<Date>—pretty intuitive. But trying the same logic on a variation in the parameter types fails:

    List<Object> lo;
    List<Date> ld = new ArrayList<Date>();
    lo = ld; // Compile-time Error!  Incompatible types.

Although our intuition tells us that the Dates in that List could all live happily as Objects in a List, the assignment is an error. We’ll explain precisely why in the next section, but for now just note that the type parameters are not exactly the same and that there is no inheritance relationship among parameter types in generics. This is a case where thinking of the instantiation in terms of types and not in terms of what they do helps. These are not really a “list of dates” and a “list of objects,” but more like a DateList and an ObjectList, the relationship of which is not immediately obvious.

Try to pick out what’s OK and what’s not OK in the following example:

    Collection<Number> cn;
    List<Integer> li = new ArrayList<Integer>();
    cn = li; // Compile-time Error!  Incompatible types.

It is possible for an instantiation of List to be an instantiation of Collection, but only if the parameter types are exactly the same. Inheritance doesn’t follow the parameter types and this example fails.

One more thing: earlier we mentioned that this rule applies to the simple types of instantiations we’ve discussed so far in this chapter. What other types are there? Well, the kinds of instantiations we’ve seen so far where we plug in an actual Java type as a parameter are called concrete type instantiations. Later we’ll talk about wildcard instantiations, which are akin to mathematical set operations on types. We’ll see that it’s possible to make more exotic instantiations of generics where the type relationships are actually two-dimensional, depending both on the base type and the parameterization. But don’t worry: this doesn’t come up very often and is not as scary as it sounds.

    DateList dateList = new DateList();
    ObjectList objectList = dateList; // Can't really do this
    objectList.add( new Foo() ); // should be runtime error!

    Date [] dates = new Date[10];
    Object [] objects = dates;
    objects[0] = "not a date"; // Runtime ArrayStoreException!

Casts

We’ve now talked about relationships between generic types and even between generic types and raw types. But we haven’t really explored the concept of a casts in the world of generics yet. No cast was necessary when we interchanged generics with their raw types. Instead, we just crossed a line that triggers unchecked warnings from the compiler:

    List list = new ArrayList<Date>();
    List<Date> dl = list;  // unchecked warning

Normally, we use a cast in Java to work with two types that could be assignable. For example, we could attempt to cast an Object to a Date because it is plausible that the Object is a Date value. The cast then performs the check at runtime to see if we are correct. Casting between unrelated types is a compile-time error. For example, we can’t even try to cast an Integer to a String. Those types have no inheritance relationship. What about casts between compatible generic types?

    Collection<Date> cd = new ArrayList<Date>();
    List<Date> ld = (List<Date>)cd; // Ok!

This code snippet shows a valid cast from a more general Collection<Date> to a List<Date>. The cast is plausible here because a Collection<Date> is assignable from and could actually be a List<Date>. Similarly, the following cast catches our mistake where we have aliased a TreeSet<Date> as a Collection<Date> and tried to cast it to a List<Date>:

    Collection<Date> cd = new TreeSet<Date>();
    List<Date> ld = (List<Date>)cd; // Runtime ClassCastException!
    ld.add( new Date() );

There is one case where casts are not effective with generics, however, and that is when we are trying to differentiate the types based on their parameter types:

    Object o = new ArrayList<String>();
    List<Date> ld = (List<Date>)o; // unchecked warning, ineffective
    Date d = ld.get(0); // unsafe at runtime, implicit cast may fail

Here, we aliased an ArrayList<String> as a plain Object. Next, we cast it to a List<Date>. Unfortunately, Java does not know the difference between a List<String> and a List<Date> at runtime, so the cast is fruitless. The compiler warns us of this by generating an unchecked warning at the location of the cast; we should be aware that when we try to use the cast object later, we might find out that it is incorrect. Casts on generic types are ineffective at runtime because of erasure and the lack of type information.

    public Object[] toArray()
    public <E> E[] toArray( E[] a )

    Collection<String> myCollection = ...;
    String [] myStrings = myCollection.toArray( new String[0] );

    String [] myStrings = ...;    List list = Arrays.asList( myStrings );

    public void printElements(Collection c, PrintStream out) {
        Iterator iterator = c.iterator();
        while ( iterator.hasNext() ) {
            out.println( iterator.next() );
        }
    }

    Collection<Date> col = ...
    for( Date date : col )
       System.out.println( date );

A closer look: The sort() Method

Poking around in the java.util.Collections class, we find all kinds of static utility methods for working with collections. Among them is this goody—the static generic method sort():

    <T extends Comparable<? super T>> void sort( List<T> list ) { ... }

Another nut for us to crack. Let’s focus on the last part of the bound:

    Comparable<? super T>

This is a wildcard instantiation of the Comparable interface, so we can read the extends as implements if it helps. Comparable holds a compareTo() method for some parameter type. A Comparable<String> means that the compareTo() method takes type String. Therefore, Comparable<? super T> is the set of instantiations of Comparable on T and all of its superclasses. A Comparable<T> suffices and, at the other end, so does a Comparable<Object>. What this means in English is that the elements must be comparable to their own type or some supertype of their own type for the sort() method to make use of them. This is sufficient to ensure that the elements can all be compared to one another, but not as restrictive as saying that they must all implement the compareTo() method themselves. Some of the elements may inherit the Comparable interface from a parent class that knows how to compare only to a supertype of T, and that is exactly what is allowed here.

Application: Apples and trees on the field

There is a lot of theory in this chapter. Don’t be afraid of theory—it can help you predict behavior in novel scenarios and inspire solutions to new problems. But practice is just as important so let’s put some of these collections into practice by revisiting our game that we started in “Classes”. In particular, it’s time to store more than one object of each type.

In Chapter 11 we’ll cover networking and consider creating a multi-player setup that would require storing multiple physicists. For now, we still have our one physicist able to throw one apple at a time. But we can populate our field with several trees for target practice. Newton will have his revenge!

Let’s add six trees, although we’ll use a pair of loops so you can easily increase the tree count if you wish. Our Field currently stores a lone tree instance. We can make that a typed list. From there we can approach adding and removing trees in a number of ways. We can create some methods for Field that work with the list and maybe enforce some other game rules (like managing a maximum number of trees). We could just use the list directly since the List class already has nice methods for most of the things we want to do. Or we could use some combination of those approaches: special methods where it makes sense and direct manipulation everywhere else.

Since we do have some game rules that are peculiar to our Field, we’ll take the first approach here. (But look at the examples and think about how you might alter them to use the list of trees directly.) We’ll start with an addTree() method. One benefit of this approach is that we can also relocate the creation of the tree instance to our method rather than creating and manipulating the tree separately. Here’s one way to add a tree at a desired point on the field:

    public void addTree(int x, int y) {
        Tree tree = new Tree();
        tree.setPosition(x,y);
        trees.add(tree);
    }

With that method in place, we could add a couple of trees quite quickly:

    Field field = new Field();
    ...
    field.addTree(100,100);
    field.addTree(200,100);

Those two lines add a pair of trees side by side. Let’s go ahead and write the loops we want to create our six trees:

    Field field = new Field();
    ...
    for (int row = 1; row <= 2; row++) {
        for (int col = 1; col <=3; col++) {
            field.addTree(col * 100, row * 100);
        }
    }

Hopefully you can see now how easy it would be to add eight or nine or 100 trees if you wanted. As we noted before, computers are really good at repetition.

Hooray for creating our forest of apple targets! We left off a few critical details, though. The most important of which is showing that forest on the screen. We need to upgrade our drawing method for the Field class so that it understands and uses our list of trees correctly. Eventually we’ll do the same for our phsycists and apples as we add more and more functionality to our game. We’ll also need a way to remove elements that are no longer active. But first our forest!

    protected void paintComponent(Graphics g) {
        g.setColor(fieldColor);
        g.fillRect(0,0, getWidth(), getHeight());
        for (Tree t : trees) {
            t.draw(g);
        }
        physicist.draw(g);
        apple.draw(g);
    }

Since we are already in the Field class where our trees are stored, there is no need to write any separate function for pulling out an individual tree and painting it. We can use the nifty alternate for loop structure and quickly get all of our trees on the field as shown in Figure 7-1. Neat!

Figure 7-1. Rendering all the trees in our List

Conclusion

Java collections and generics are very powerful and useful additions to the language. Although some of the details we delved into in the latter half of this chapter may seem daunting, the common usage is very simple and compelling: generics make collections better. As you begin to write more code using generics, you will find that your code becomes more readable and more understandable. Collections allow for elegant, efficient storage. Generics make explicit what previously had to be inferred from usage.