Inhaltsverzeichnis von Java Generics and Collections

Inhaltsvorschau

Generics and collections work well with a number of other new features introduced in the latest versions of Java, including boxing and unboxing, a new form of loop, and functions that accept a variable number of arguments. We begin with an example that illustrates all of these. As we shall see, combining them is synergistic: the whole is greater than the sum of its parts.

Taking that as our motto, let's do something simple with sums: put three numbers into a list and add them together. Here is how to do it in Java with generics:


List<Integer> ints = Arrays.asList(1,2,3);

int s = 0;

for (int n : ints) { s += n; }

assert s == 6;

You can probably read this code without much explanation, but let's touch on the key features. The interface List and the class Arrays are part of the Collections Framework (both are found in the package java.util). The type List is now generic; you write List<E> to indicate a list with elements of type E. Here we write List<Integer> to indicate that the elements of the list belong to the class Integer, the wrapper class that corresponds to the primitive type int. Boxing and unboxing operations, used to convert from the primitive type to the wrapper class, are automatically inserted. The static method asList takes any number of arguments, places them into an array, and returns a new list backed by the array. The new loop form, foreach, is used to bind a variable successively to each element of the list, and the loop body adds these into the sum. The assertion statement (introduced in Java 1.4), is used to check that the sum is correct; when assertions are enabled, it throws an error if the condition does not evaluate to true.

Here is how the same code looks in Java before generics:


List ints = Arrays.asList( new Integer[] {

  new Integer(1), new Integer(2), new Integer(3)

} );

int s = 0;

for (Iterator it = ints.iterator(); it.hasNext(); ) {

  int n = ((Integer)it.next()).intValue();

  s += n;

}

assert s == 6;

Reading this code is not quite so easy. Without generics, there is no way to indicate in the type declaration what kind of elements you intend to store in the list, so instead of writing

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

An interface or class may be declared to take one or more type parameters, which are written in angle brackets and should be supplied when you declare a variable belonging to the interface or class or when you create a new instance of a class.

We saw one example in the previous section. Here is another:


List<String> words = new ArrayList<String>();

words.add("Hello ");

words.add("world!");

String s = words.get(0)+words.get(1);

assert s.equals("Hello world!");

In the Collections Framework, class ArrayList<E> implements interface List<E>. This trivial code fragment declares the variable words to contain a list of strings, creates an instance of an ArrayList, adds two strings to the list, and gets them out again.

In Java before generics, the same code would be written as follows:


List words = new ArrayList();

words.add("Hello ");

words.add("world!");

String s = ((String)words.get(0))+((String)words.get(1))

assert s.equals("Hello world!");

Without generics, the type parameters are omitted, but you must explicitly cast whenever an element is extracted from the list.

In fact, the bytecode compiled from the two sources above will be identical. We say that generics are implemented by erasure because the types List<Integer>, List<String>, and List<List<String>> are all represented at run-time by the same type, List. We also use erasure to describe the process that converts the first program to the second. The term erasure is a slight misnomer, since the process erases type parameters but adds casts.

Generics implicitly perform the same cast that is explicitly performed without generics. If such casts could fail, it might be hard to debug code written with generics. This is why it is reassuring that generics come with the following guarantee:

Cast-iron guarantee: the implicit casts added by the compilation of generics never fail.

There is also some fine print on this guaranteee: it applies only when no unchecked warnings have been issued by the compiler. Later, we will discuss at some length what causes unchecked warnings to be issued and how to minimize their effect.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Recall that every type in Java is either a reference type or a primitive type. A reference type is any class, instance, or array type. All reference types are subtypes of class Object, and any variable of reference type may be set to the value null. As shown in the following table, there are eight primitive types, and each of these has a corresponding library class of reference type. The library classes are located in the package java.lang.

Primitive	Reference
`byte`	`Byte`
`short`	`Short`
`int`	`Integer`
`long`	`Long`
`float`	`Float`
`double`	`Double`
`bool`	`Boolean`
`char`	`Character`

Conversion of a primitive type to the corresponding reference type is called boxing and conversion of the reference type to the corresponding primitive type is called

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Here, again, is our code that computes the sum of a list of integers.


List<Integer> ints = Arrays.asList(1,2,3);

int s = 0;

for (int n : ints) { s += n; }

assert s == 6;

The loop in the third line is called a foreach loop even though it is written with the keyword for. It is equivalent to the following:


for (Iterator<Integer> it = ints.iterator(); it.hasNext(); ) {

  int n = it.next();

  s += n;

}

The emphasized code corresponds to what was written by the user, and the unemphasized code is added in a systematic way by the compiler. It introduces the variable it of type Iterator<Integer> to iterate over the list ints of type List<Integer>. In general, the compiler invents a new name that is guaranteed not to clash with any name already in the code. Note that unboxing occurs when the expression it.next() of type Integer is assigned to the variable n of type int.

The foreach loop can be applied to any object that implements the interface Iterable<E> (in package java.lang), which in turn refers to the interface Iterator<E> (in package java.util). These define the methods iterator, hasNext, and next, which are used by the translation of the foreach loop (iterators also have a method remove, which is not used by the translation):


interface Iterable<E> {

  public Iterator<E> iterator();

}

interface Iterator<E> {

  public boolean hasNext();

  public E next();

  public void remove();

}

All collections, sets, and lists in the Collections Framework implement the Iterable<E> interface; and classes defined by other vendors or users may implement it as well.

The foreach loop may also be applied to an array:


public static int sumArray(int[] a) {

  int s = 0;

  for (int n : a) { s += n; }

  return s;

}

The foreach loop was deliberately kept simple and catches only the most common case. You need to explicitly introduce an iterator if you wish to use the remove method or to iterate over more than one list in parallel. Here is a method that removes negative elements from a list of doubles:

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Here is a method that accepts an array of any type and converts it to a list:


class Lists {

  public static <T> List<T> toList(T[] arr) {

    List<T> list = new ArrayList<T>();

    for (T elt : arr) list.add(elt);

    return list;

  }

}

The static method toList accepts an array of type T[] and returns a list of type List<T>, and does so for any type T. This is indicated by writing <T> at the beginning of the method signature, which declares T as a new type variable. A method which declares a type variable in this way is called a generic method. The scope of the type variable T is local to the method itself; it may appear in the method signature and the method body, but not outside the method.

The method may be invoked as follows:


List<Integer> ints = Lists.toList(new Integer[] { 1, 2, 3 });

List<String> words = Lists.toList(new String[] { "hello", "world" });

In the first line, boxing converts 1, 2, 3 from int to Integer.

Packing the arguments into an array is cumbersome. The vararg feature permits a special, more convenient syntax for the case in which the last argument of a method is an array. To use this feature, we replace T[] with T... in the method declaration:


class Lists {

  public static <T> List<T> toList(T... arr) {

    List<T> list = new ArrayList<T>();

    for (T elt : arr) list.add(elt);

    return list;

  }

}

Now the method may be invoked as follows:


List<Integer> ints = Lists.toList(1, 2, 3);

List<String> words = Lists.toList("hello", "world");

This is just shorthand for what we wrote above. At run time, the arguments are packed into an array which is passed to the method, just as previously.

Any number of arguments may precede a last vararg argument. Here is a method that accepts a list and adds all the additional arguments to the end of the list:


public static <T> void addAll(List<T> list, T... arr) {

  for (T elt : arr) list.add(elt);

}

Whenever a vararg is declared, one may either pass a list of arguments to be implicitly packed into an array, or explicitly pass the array directly. Thus, the preceding method may be invoked as follows:

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

We clarify our code by liberal use of the assert statement. Each occurrence of assert is followed by a boolean expression that is expected to evaluate to true. If assertions are enabled and the expression evaluates to false, an AssertionError is thrown, including an indication of where the error occurred. Assertions are enabled by invoking the JVM with the -ea or -enableassertions flag.

We only write assertions that we expect to evaluate to true. Since assertions may not be enabled, an assertion should never have side effects upon which any nonassertion code depends. When checking for a condition that might not hold (such as confirming that the arguments to a method call are valid), we use a conditional and throw an exception explicitly.

To sum up, we have seen how generics, boxing and unboxing, foreach loops, and varargs work together to make Java code easier to write, having illustrated this through the use of the Collections Framework.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Now that we've covered the basics, we can start to cover more-advanced features of generics, such as subtyping and wildcards. In this section, we'll review how subtyping works and we'll see how wildcards let you use subtyping in connection with generics. We'll illustrate our points with examples from the Collections Framework.

Subtyping is a key feature of object-oriented languages such as Java. In Java, one type is a subtype of another if they are related by an extends or implements clause. Here are some examples:

`Integer`	is a subtype of	`Number`
`Double`	is a subtype of	`Number`
`ArrayList<E>`	is a subtype of	`List<E>`
`List<E>`	is a subtype of	`Collection<E>`
`Collection<E>`	is a subtype of	`Iterable<E>`

Subtyping is transitive, meaning that if one type is a subtype of a second, and the second is a subtype of a third, then the first is a subtype of the third. So, from the last two lines in the preceding list, it follows that List<E> is a subtype of Iterable<E>. If one type is a subtype of another, we also say that the second is a

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Subtyping is a key feature of object-oriented languages such as Java. In Java, one type is a subtype of another if they are related by an extends or implements clause. Here are some examples:

`Integer`	is a subtype of	`Number`
`Double`	is a subtype of	`Number`
`ArrayList<E>`	is a subtype of	`List<E>`
`List<E>`	is a subtype of	`Collection<E>`
`Collection<E>`	is a subtype of	`Iterable<E>`

Subtyping is transitive, meaning that if one type is a subtype of a second, and the second is a subtype of a third, then the first is a subtype of the third. So, from the last two lines in the preceding list, it follows that List<E> is a subtype of Iterable<E>. If one type is a subtype of another, we also say that the second is a supertype of the first. Every reference type is a subtype of Object, and Object is a supertype of every reference type. We also say, trivially, that every type is a subtype of itself.

The Substitution Principle tells us that wherever a value of one type is expected, one may provide a value of any subtype of that type:

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Another method in the Collection interface is addAll, which adds all of the members of one collection to another collection:


interface Collection<E> {

  ...

  public boolean addAll(Collection<? extends E> c);

  ...

}

Clearly, given a collection of elements of type E, it is OK to add all members of another collection with elements of type E. The quizzical phrase "? extends E" means that it is also OK to add all members of a collection with elements of any type that is a subtype of E. The question mark is called a wildcard, since it stands for some type that is a subtype of E.

Here is an example. We create an empty list of numbers, and add to it first a list of integers and then a list of doubles:


List<Number> nums = new ArrayList<Number>();

List<Integer> ints = Arrays.asList(1, 2);

List<Double> dbls = Arrays.asList(2.78, 3.14);

nums.addAll(ints);

nums.addAll(dbls);

assert nums.toString().equals("[1, 2, 2.78, 3.14]");

The first call is permitted because nums has type List<Number>, which is a subtype of Collection<Number>, and ints has type List<Integer>, which is a subtype of Collection<? extends Number>. The second call is similarly permitted. In both calls, E is taken to be Number. If the method signature for addAll had been written without the wildcard, then the calls to add lists of integers and doubles to a list of numbers would not have been permitted; you would only have been able to add a list that was explicitly declared to be a list of numbers.

We can also use wildcards when declaring variables. Here is a variant of the example at the end of the preceding section, changed by adding a wildcard to the second line:


List<Integer> ints = Arrays.asList(1,2);

List<? extends Number> nums = ints;

nums.add(3.14);  // compile-time error

assert ints.toString().equals("[1, 2, 3.14]");  // uh oh!

Before, the second line caused a compile-time error (because List<Integer> is not a subtype of List<Number>), but the third line was fine (because a double is a number, so you can add a double to a

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Here is a method that copies into a destination list all of the elements from a source list, from the convenience class Collections:


public static <T> void copy(List<? super T> dst, List<? extends T> src) {

  for (int i = 0; i < src.size(); i++) {

    dst.set(i, src.get(i));

  }

}

The quizzical phrase ? super T means that the destination list may have elements of any type that is a supertype of T, just as the source list may have elements of any type that is a subtype of T.

Here is a sample call.


List<Object> objs = Arrays.<Object>asList(2, 3.14, "four");

List<Integer> ints = Arrays.asList(5, 6);

Collections.copy(objs, ints);

assert objs.toString().equals("[5, 6, four]");

As with any generic method, the type parameter may be inferred or may be given explicitly. In this case, there are four possible choices, all of which type-check and all of which have the same effect:


Collections.copy(objs, ints);

Collections.<Object>copy(objs, ints);

Collections.<Number>copy(objs, ints);

Collections.<Integer>copy(objs, ints);

The first call leaves the type parameter implicit; it is taken to be Integer, since that is the most specific choice that works. In the third line, the type parameter T is taken to be Number. The call is permitted because objs has type List<Object>, which is a subtype of List<? super Number> (since Object is a supertype of Number, as required by the super) and ints has type List<Integer>, which is a subtype of List<? extends Number> (since Integer is a subtype of Number, as required by the extends wildcard).

We could also declare the method with several possible signatures.


public static <T> void copy(List<T> dst, List<T> src)

public static <T> void copy(List<T> dst, List<? extends T> src)

public static <T> void copy(List<? super T> dst, List<T> src)

public static <T> void copy(List<? super T> dst, List<? extends T> src)

The first of these is too restrictive, as it only permits calls when the destination and source have exactly the same type. The remaining three are equivalent for calls that use implicit type parameters, but differ for explicit type parameters. For the example calls above, the second signature works only when the type parameter is

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

It may be good practice to insert wildcards whenever possible, but how do you decide which wildcard to use? Where should you use extends, where should you use super, and where is it inappropriate to use a wildcard at all?

Fortunately, a simple principle determines which is appropriate.

The Get and Put Principle: use an extends wildcard when you only get values out of a structure, use a super wildcard when you only put values into a structure, and don't use a wildcard when you both get and put.

We already saw this principle at work in the signature of the copy method:


public static <T> void copy(List<? super T> dest, List<? extends T> src)

The method gets values out of the source src, so it is declared with an extends wildcard, and it puts values into the destination dst, so it is declared with a super wildcard.

Whenever you use an iterator, you get values out of a structure, so use an extends wildcard. Here is a method that takes a collection of numbers, converts each to a double, and sums them up:


public static double sum(Collection<? extends Number> nums) {

  double s = 0.0;

  for (Number num : nums) s += num.doubleValue();

  return s;

}

Since this uses extends, all of the following calls are legal:


List<Integer> ints = Arrays.asList(1,2,3);

assert sum(ints) == 6.0;



List<Double> doubles = Arrays.asList(2.78,3.14);

assert sum(doubles) == 5.92;



List<Number> nums = Arrays.<Number>asList(1,2,2.78,3.14);

assert sum(nums) == 8.92;

The first two calls would not be legal if extends was not used.

Whenever you use the add method, you put values into a structure, so use a super wildcard. Here is a method that takes a collection of numbers and an integer n, and puts the first n integers, starting from zero, into the collection:


public static void count(Collection<? super Integer> ints, int n) {

  for (int i = 0; i < n; i++) ints.add(i);

}

Since this uses super, all of the following calls are legal:


List<Integer>

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

It is instructive to compare the treatment of lists and arrays in Java, keeping in mind the Substitution Principle and the Get and Put Principle.

In Java, array subtyping is covariant, meaning that type S[] is considered to be a subtype of T[] whenever S is a subtype of T. Consider the following code fragment, which allocates an array of integers, assigns it to an array of numbers, and then attempts to assign a double into the array:


Integer[] ints = new Integer[] {1,2,3};

Number[] nums = ints;

nums[2] = 3.14;  // array store 

 

 exception

 

 



assert Arrays.toString(ints).equals("[1, 2, 3.14]");  // uh oh!

Something is wrong with this program, since it puts a double into an array of integers! Where is the problem? Since Integer[] is considered a subtype of Number[], according to the Substitution Principle the assignment on the second line must be legal. Instead, the problem is caught on the third line, and it is caught at run time. When an array is allocated (as on the first line), it is tagged with its reified type (a run-time representation of its component type, in this case, Integer), and every time an array is assigned into (as on the third line), an array store exception is raised if the reified type is not compatible with the assigned value (in this case, a double cannot be stored into an array of Integer).

In contrast, the subtyping relation for generics is invariant, meaning that type List<S> is not considered to be a subtype of List<T>, except in the trivial case where S and T are identical. Here is a code fragment analogous to the preceding one, with lists replacing arrays:


List<Integer> ints = Arrays.asList(1,2,3);

List<Number> nums = ints; // compile-time error

nums.put(2, 3.14);

assert ints.toString().equals("[1, 2, 3.14]");  // uh oh!

Since List<Integer> is not considered to be a subtype of List<Number>, the problem is detected on the second line, not the third, and it is detected at compile time, not run time.

Wildcards reintroduce covariant subtyping for generics, in that type

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The contains method checks whether a collection contains a given object, and its generalization, containsAll, checks whether a collection contains every element of another collection. This section presents two alternate approaches to giving generic signatures for these methods. The first approach uses wildcards and is the one used in the Java Collections Framework. The second approach uses type parameters and is often a more appropriate alternative.

Wildcards Here are the types that the methods have in Java with generics:


interface Collection<E> {

  ...

  public boolean contains(Object o);

  public boolean containsAll(Collection<?> c);

  ...

}

The first method does not use generics at all! The second method is our first sight of an important abbreviation. The type Collection<?> stands for:


Collection<? extends Object>

Extending Object is one of the most common uses of wildcards, so it makes sense to provide a short form for writing it.

These methods let us test for membership and containment:


Object obj = "one";

List<Object> objs = Arrays.<Object>asList("one", 2, 3.14, 4);

List<Integer> ints = Arrays.asList(2, 4);

assert objs.contains(obj);

assert objs.containsAll(ints);

assert !ints.contains(obj);

assert !ints.containsAll(objs);

The given list of objects contains both the string "one" and the given list of integers, but the given list of integers does not contain the string "one", nor does it contain the given list of objects.

The tests ints.contains(obj) and ints.containsAll(objs) might seem silly. Of course, a list of integers won't contain an arbitrary object, such as the string "one". But it is permitted because sometimes such tests might succeed:


Object obj = 1;

List<Object> objs = Arrays.<Object>asList(1, 3);

List<Integer> ints = Arrays.asList(1, 2, 3, 4);

assert ints.contains(obj);

assert ints.containsAll(objs);

In this case, the object may be contained in the list of integers because it happens to be an integer, and the list of objects may be contained within the list of integers because every object in the list happens to be an integer.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

When a generic method is invoked, the type parameter may be chosen to match the unknown type represented by a wildcard. This is called wildcard capture.

Consider the method reverse in the convenience class java.util.Collections, which accepts a list of any type and reverses it. It can be given either of the following two signatures, which are equivalent:


public static void reverse(List<?> list);

public static void <T> reverse(List<T> list);

The wildcard signature is slightly shorter and clearer, and is the one used in the library.

If you use the second signature, it is easy to implement the method:


public static void <T> reverse(List<T> list) {

  List<T> tmp = new ArrayList<T>(list);

  for (int i = 0; i < list.size(); i++) {

    list.set(i, tmp.get(list.size()-i-1));

  }

}

This copies the argument into a temporary list, and then writes from the copy back into the original in reverse order.

If you try to use the first signature with a similar method body, it won't work:


public static void reverse(List<?> list) {

  List<Object> tmp = new ArrayList<Object>(list);

  for (int i = 0; i < list.size(); i++) {

    list.set(i, tmp.get(list.size()-i-1));  // compile-time error

  }

}

Now it is not legal to write from the copy back into the original, because we are trying to write from a list of objects into a list of unknown type. Replacing List<Object> with List<?> won't fix the problem, because now we have two lists with (possibly different) unknown element types.

Instead, you can implement the method with the first signature by implementing a private method with the second signature, and calling the second from the first:


public static void reverse(List<?> list) { rev(list); }

private static <T> void rev(List<T> list) {

  List<T> tmp = new ArrayList<T>(list);

  for (int i = 0; i < list.size(); i++) {

    list.set(i, tmp.get(list.size()-i-1));

  }

}

Here we say that the type variable T has captured the wildcard. This is a generally useful technique when dealing with wildcards, and it is worth knowing.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Wildcards may not appear at the top level in class instance creation expressions (new), in explicit type parameters in generic method calls, or in supertypes (extends and implements).

Instance Creation In a class instance creation expression, if the type is a parameterized type, then none of the type parameters may be wildcards. For example, the following are illegal:


List<?> list = new ArrayList<?>();  // compile-time error

Map<String, ? extends Number> map

  = new HashMap<String, ? extends Number>();  // compile-time error

This is usually not a hardship. The Get and Put Principle tells us that if a structure contains a wildcard, we should only get values out of it (if it is an extends wildcard) or only put values into it (if it is a super wildcard). For a structure to be useful, we must do both. Therefore, we usually create a structure at a precise type, even if we use wildcard types to put values into or get values from the structure, as in the following example:


List<Number> nums = new ArrayList<Number>();

List<? super Number> sink = nums;

List<? extends Number> source = nums;

for (int i=0; i<10; i++) sink.add(i);

double sum=0; for (Number num : source) sum+=num.doubleValue();

Here wildcards appear in the second and third lines, but not in the first line that creates the list.

Only top-level parameters in instance creation are prohibited from containing wildcards. Nested wildcards are permitted. Hence, the following is legal:


List<List<?>> lists = new ArrayList<List<?>>();

lists.add(Arrays.asList(1,2,3));

lists.add(Arrays.asList("four","five"));

assert lists.toString().equals("[[1, 2, 3], [four, five]]");

Even though the list of lists is created at a wildcard type, each individual list within it has a specific type: the first is a list of integers and the second is a list of strings. The wildcard type prohibits us from extracting elements from the inner lists at any type other than Object, but since that is the type used by toString, this code is well typed.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Now that we have the basics, let's look at some more-advanced uses of generics. This chapter describes the interfaces Comparable<T> and Comparator<T>, which are used to support comparison on elements. These interfaces are useful, for instance, if you want to find the maximum element of a collection or sort a list. Along the way, we will introduce bounds on type variables, an important feature of generics that is particularly useful in combination with the Comparable<T> interface.

The interface Comparable<T> contains a single method that can be used to compare one object to another:


interface Comparable<T> {

  public int compareTo(T o);

}

The compareTo method returns a value that is negative, zero, or positive depending upon whether the argument is less than, equal to, or greater than the given object. When a class implements Comparable, the ordering specified by this interface is called the natural ordering for that class.

Typically, an object belonging to a class can only be compared with an object belonging to the same class. For instance, Integer implements Comparable<Integer>:


Integer int0 = 0;

Integer int1 = 1;

assert int0.compareTo(int1) < 0;

The comparison returns a negative number, since 0 precedes 1 under numerical ordering. Similarly, String implements Comparable<String>:


  String str0 = "zero";

  String str1 = "one";

  assert str0.compareTo(str1) > 0;

This comparison returns a positive number, since "zero" follows "one" under alphabetic ordering.

The type parameter to the interface allows nonsensical comparisons to be caught at compile time:


Integer i = 0;

String s = "one";

assert i.compareTo(s) < 0;  // compile-time error

You can compare an integer with an integer or a string with a string, but attempting to compare an integer with a string signals a compile-time error.

Comparison is not supported between arbitrary numerical types:


Number m = new Integer(2);

Number n = new Double(3.14);

assert m.compareTo(n) < 0;

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The interface Comparable<T> contains a single method that can be used to compare one object to another:


interface Comparable<T> {

  public int compareTo(T o);

}

The compareTo method returns a value that is negative, zero, or positive depending upon whether the argument is less than, equal to, or greater than the given object. When a class implements Comparable, the ordering specified by this interface is called the natural ordering for that class.

Typically, an object belonging to a class can only be compared with an object belonging to the same class. For instance, Integer implements Comparable<Integer>:


Integer int0 = 0;

Integer int1 = 1;

assert int0.compareTo(int1) < 0;

The comparison returns a negative number, since 0 precedes 1 under numerical ordering. Similarly, String implements Comparable<String>:


  String str0 = "zero";

  String str1 = "one";

  assert str0.compareTo(str1) > 0;

This comparison returns a positive number, since "zero" follows "one" under alphabetic ordering.

The type parameter to the interface allows nonsensical comparisons to be caught at compile time:


Integer i = 0;

String s = "one";

assert i.compareTo(s) < 0;  // compile-time error

You can compare an integer with an integer or a string with a string, but attempting to compare an integer with a string signals a compile-time error.

Comparison is not supported between arbitrary numerical types:


Number m = new Integer(2);

Number n = new Double(3.14);

assert m.compareTo(n) < 0;  // compile-time error

Here the comparison is illegal, because the Number class does not implement the Compar-able interface.

Consistent with Equals Usually, we require that two objects are equal if and only if they compare as the same:


x.equals(y)  if and only if  x.compareTo(y) == 0

In this case, we say that the natural ordering is consistent with equals.

It is recommended that when designing a class you choose a natural ordering that is consistent with equals. This is particularly important if you use the interfaces

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

In this section, we show how to use the Comparable<T> interface to find the maximum element in a collection. We begin with a simplified version. The actual version found in the Collections Framework has a type signature that is a bit more complicated, and later we will see why.

Here is code to find the maximum element in a nonempty collection, from the class Collections:


public static <T extends Comparable<T>> T max(Collection<T> coll) {

    T candidate = coll.iterator().next();

    for (T elt : coll) {

        if (candidate.compareTo(elt) < 0) candidate = elt;

    }

    return candidate;

}

We first saw generic methods that declare new type variables in the signature in Section 1.4. For instance, the method asList takes an array of type E[] and returns a result of type List<E>, and does so for any type E. Here we have a generic method that declares a bound on the type variable. The method max takes a collection of type Collection<T> and returns a T, and it does this for any type T such that T is a subtype of Comparable<T>.

The highlighted phrase in angle brackets at the beginning of the type signature declares the type variable T, and we say that T is bounded by Comparable<T>. As with wildcards, bounds for type variables are always indicated by the keyword extends, even when the bound is an interface rather than a class, as is the case here. Unlike wildcards, type variables must always be bounded using extends, never super.

In this case, the bound is recursive, in that the bound on T itself depends upon T. It is even possible to have mutually recursive bounds, such as:


<T extends C<T,U>, U extends D<T,U>>

An example of mutually recursive bounds appears in Section 9.5.

The method body chooses the first element in the collection as a candidate for the maximum, and then compares the candidate with each element in the collection, setting the candidate to the element when the element is larger. We use iterator().next() rather than get(0) to get the first element, because

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The Comparable<T> interface gives fine control over what can and cannot be compared. Say that we have a Fruit class with subclasses Apple and Orange. Depending on how we set things up, we may prohibit comparison of apples with oranges or we may permit such comparison.

Example 3.2 prohibits comparison of apples with oranges. Here are the three classes it declares:


class Fruit {...}

class Apple extends Fruit implements Comparable<Apple> {...}

class Orange extends Fruit implements Comparable<Orange> {...}

Each fruit has a name and a size, and two fruits are equal if they have the same name and the same size. Following good practice, we have also defined a hash method, to ensure that equal objects have the same hash code. Apples are compared by comparing their sizes, and so are oranges. Since Apple implements Comparable<Apple>, it is clear that you can compare apples with apples, but not with oranges. The test code builds three lists, one of apples, one of oranges, and one containing mixed fruits. We may find the maximum of the first two lists, but attempting to find the maximum of the mixed list signals an error at compile time.

Example 3.1 permits comparison of apples with oranges. Compare these three class declarations with those given previously (all differences between Examples 3.2 and 3.1 are highlighted):

Example 3-1. Permitting comparison of apples with oranges


abstract class Fruit implements Comparable<Fruit> {

  protected String name;

  protected int size;

  protected Fruit(String name, int size) {

    this.name = name; this.size = size;

  }

  public boolean equals(Object o) {

    if (o instanceof Fruit) {

      Fruit that = (Fruit)o;

      return this.name.equals(that.name) && this.size == that.size;

    } else return false;

  }

  public int hash() {

    return name.hash()*29 + size;

  }

  public int compareTo(Fruit that) {

    return this.size < that.size ? - 1 :

           this.size == that.size ? 0 : 1 ;

  }

}

class Apple extends Fruit {

  public Apple(int size) { super("Apple", size); }

}

class Orange extends Fruit {

  public Orange(int size) { super("Orange", size); }

}

class Test {

  public static void main(String[] args) {



    Apple a1 = new Apple(1);  Apple a2 = new Apple(2);

    Orange o3 = new Orange(3);  Orange o4 = new Orange(4);



    List<Apple> apples = Arrays.asList(a1,a2);

    assert Collections.max(apples).equals(a2);



    List<Orange> oranges = Arrays.asList(o3,o4);

    assert Collections.max(oranges).equals(o4);



    List<Fruit> mixed = Arrays.<Fruit>asList(a1,o3);

    assert Collections.max(mixed).equals(o3);

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Sometimes we want to compare objects that do not implement the Comparable interface, or to compare objects using a different ordering from the one specified by that interface. The ordering provided by the Comparable interface is called the natural ordering, so the Comparator interface provides, so to speak, an unnatural ordering.

We specify additional orderings using the Comparator interface, which contains a single method:


interface Comparator<T> {

  public int compare(T o1, T o2);

}

The compare method returns a value that is negative, zero, or positive depending upon whether the first object is less than, equal to, or greater than the second object—just as with compareTo.

Here is a comparator that considers the shorter of two strings to be smaller. Only if two strings have the same length are they compared using the natural (alphabetic) ordering.


Comparator<String> sizeOrder =

  new Comparator<String>() {

    public int compare(String s1, String s2) {

      return

        s1.length() < s2.length() ? −1 :

        s1.length() > s2.length() ? 1 :

        s1.compareTo(s2) ;

      }

  };

Here is an example:


assert "two".compareTo("three") > 0;

assert sizeOrder.compare("two","three") < 0;

In the natural alphabetic ordering, "two" is greater than "three", whereas in the size ordering it is smaller.

The Java libraries always provide a choice between Comparable and Comparator. For every generic method with a type variable bounded by Comparable, there is another generic method with an additional argument of type Comparator. For instance, corresponding to:


public static <T extends Comparable<? super T>>

  T max(Collection<? extends T> coll)

we also have:


public static <T>

  T max(Collection<? extends T> coll, Comparator<? super T> cmp)

There are similar methods to find the minimum. For example, here is how to find the maximum and minimum of a list using the natural ordering and using the size ordering:

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Java 5 includes support for enumerated types. Here is a simple example:


enum Season { WINTER, SPRING, SUMMER, FALL }

Each enumerated type declaration can be expanded into a corresponding class in a stylized way. The corresponding class is designed so that it has exactly one instance for each of the enumerated constants, bound to a suitable static final variable. For example, the enum declaration above expands into a class called Season. Exactly four instances of this class exist, bound to four static final variables with the names WINTER, SPRING, SUMMER, and FALL.

Each class that corresponds to an enumerated type is a subclass of java.lang.Enum. Its definition in the Java documentation begins like this:


class Enum<E extends Enum<E>>

You may find this frightening at first sight—both of us certainly did! But don't panic. Actually, we've already seen something similar. The worrying phrase E extends Enum<E> is a lot like the phrase T extends Comparable<T> that we encountered in the definition of max (see Section 3.2), and we'll see that they appear for related reasons.

To understand what's going on, we need to take a look at the code. Example 3.4 shows the base class Enum and Example 3.5 shows the class Season that corresponds to the enumerated type declaration above. (The code for Enum follows the source in the Java library, but we have simplified a few points.)

Example 3-4. Base class for enumerated types


public abstract class Enum<E extends Enum<E>> implements Comparable<E> {

  private final String name;

  private final int ordinal;

  protected Enum(String name, int ordinal) {

    this.name = name; this.ordinal = ordinal;

  }

  public final String name() { return name; }

  public final int ordinal() { return ordinal; }

  public String toString() { return name; }

  public final int compareTo(E o) {

    return ordinal - o.ordinal;

  }

}

Example 3-5. Class corresponding to an enumerated type


// corresponds to

// enum Season { WINTER, SPRING, SUMMER, FALL }

final class Season extends Enum<Season> {

  private Season(String name, int ordinal) { super(name,ordinal); }

  public static final Season WINTER = new Season("WINTER",0);

  public static final Season SPRING = new Season("SPRING",1);

  public static final Season SUMMER = new Season("SUMMER",2);

  public static final Season FALL   = new Season("FALL",3);

  private static final Season[] VALUES = { WINTER, SPRING, SUMMER, FALL };

  public static Season[] values() { return VALUES.clone(); }

  public static Season valueOf(String name) {

    for (Season e : VALUES) if (e.name().equals(name)) return e;

    throw new IllegalArgumentException();

  }

}

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

We have seen many examples where a type variable or wildcard is bounded by a single class or interface. In rare situations, it may be desirable to have multiple bounds, and we show how to do so here.

To demonstrate, we use three interfaces from the Java library. The Readable interface has a read method to read into a buffer from a source, the Appendable interface has an append method to copy from a buffer into a target, and the Closeable interface has a close method to close a source or target. Possible sources and targets include files, buffers, streams, and so on.

For maximum flexibility, we might want to write a copy method that takes any source that implements both Readable and Closeable and any target that implements both Appendable and Closeable:


public static <S extends Readable & Closeable,

               T extends Appendable & Closeable>

  void copy(S src, T trg, int size)

  throws IOException

{

  CharBuffer buf = CharBuffer.allocate(size);

  int i = src.read(buf);

  while (i >= 0) {

    buf.flip();  // prepare buffer for writing

    trg.append(buf);

    buf.clear();  // prepare buffer for reading

    i = src.read(buf);

  }

  src.close();

  trg.close();

}

This method repeatedly reads from the source into a buffer and appends from the buffer into a target. When the source is empty, it closes both the source and the target. The first line specifies that S ranges over any type that implements both Readable and Closeable, and that T ranges over any type that implements Appendable and Closeable. When multiple bounds on a type variable appear, they are separated by ampersands. (You cannot use a comma, since that is already used to separate declarations of type variables.)

For example, this method may be called with two files as source and target, or with the same two files wrapped in buffers as source and target:


int size = 32;

FileReader r = new FileReader("file.in");

FileWriter w = new FileWriter("file.out");

copy(r,w,size);

BufferedReader br = new BufferedReader(new FileReader("file.in"));

BufferedWriter bw = new BufferedWriter(new FileWriter("file.out"));

copy(br,bw,size);

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

As we mentioned earlier, generics are implemented by erasure: when you write code with generics, it compiles in almost exactly the same way as the code you would have written without generics. In the case of a parameterized interface such as Comparable<T>, this may cause additional methods to be inserted by the compiler; these additional methods are called bridges.

Example 3.6 shows the Comparable interface and a simplified version of the Integer class in Java before generics. In the nongeneric interface, the compareTo method takes an argument of type Object. In the nongeneric class, there are two compareTo methods. The first is the naïve method you might expect, to compare an integer with another integer. The second compares an integer with an arbitrary object: it casts the object to an integer and calls the first method. The second method is necessary in order to override the compareTo method in the Comparable interface, because overriding occurs only when the method signatures are identical. This second method is called a bridge.

Example 3-6. Legacy code for comparable integers


interface Comparable {

  public int compareTo(Object o);

}

class Integer implements Comparable {

  private final int value;

  public Integer(int value) { this.value = value; }

  public int compareTo(Object o) {

    return compareTo((Integer)o);

  }

  public int compareTo(Integer i) {

    return (value < i.value) ? −1 : (value == i.value) ? 0 : 1;

  }

}

Example 3.7 shows what happens when the Comparable interface and the Integer class are generified. In the generic interface, the compareTo method takes an argument of type T. In the generic class, a single compareTo method takes an argument of type Integer. The bridge method is generated automatically by the compiler. Indeed, the compiled version of the code for both examples is essentially identical.

Example 3-7. Generic code for comparable integers


interface Comparable<T> {

  public int compareTo(T o);

}

class Integer implements Comparable<Integer> {

  private final int value;

  public Integer(int value) { this.value = value; }

  public int

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Java 5 supports covariant method overriding. This feature is not directly related to generics, but we mention it here because it is worth knowing, and because it is implemented using a bridging technique like that described in the previous section.

In Java 1.4 and earlier, one method can override another only if the signatures match exactly. In Java 5, a method can override another if the arguments match exactly but the return type of the overriding method is a subtype of the return type of the other method.

The clone method of class Object illustrates the advantages of covariant overriding:


class Object {

  ...

  public Object clone() { ... }

}

In Java 1.4, any class that overrides clone must give it exactly the same return type, namely Object:


class Point {

  public int x;

  public int y;

  public Point(int x, int y) { this.x=x; this.y=y; }

  public Object clone() { return new Point(x,y); }

}

Here, even though clone always returns a Point, the rules require it to have the return type Object. This is annoying, since every invocation of clone must cast its result.


Point p = new Point(1,2);

Point q = (Point)p.clone();

In Java 5, it is possible to give the clone method a return type that is more to the point:


class Point {

  public int x;

  public int y;

  public Point(int x, int y) { this.x=x; this.y=y; }

  public Point clone() { return new Point(x,y); }

}

Now we may clone without a cast:


Point p = new Point(1,2);

Point q = p.clone();

Covariant overriding is implemented using the bridging technique described in the previous section. As before, you can see the bridge if you apply reflection. Here is code that finds all methods with the name clone in the class Point:


for (Method m : Point.class.getMethods())

  if (m.getName().equals("clone"))

    System.out.println(m.toGenericString());

Running this code on the covariant version of the Point class produces the following output:


public Point Point.clone()

public bridge java.lang.Object Point.clone()

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

This chapter discusses how to declare a generic class. It describes constructors, static members, and nested classes, and it fills in some details of how erasure works.

In a generic class, type parameters appear in the header that declares the class, but not in the constructor:


class Pair<T, U> {

  private final T first;

  private final U second;

  public Pair(T first, U second) { this.first=first; this.second=second; }

  public T getFirst() { return first; }

  public U getSecond() { return second; }

}

The type parameters T and U are declared at the beginning of the class, not in the constructor. However, actual type parameters are passed to the constructor whenever it is invoked:


Pair<String, Integer> pair = new Pair<String, Integer>("one",2);

assert pair.getFirst().equals("one") && pair.getSecond() == 2;

Look Out for This! A common mistake is to forget the type parameters when invoking the constructor:


Pair<String, Integer> pair = new Pair("one",2);

This mistake produces a warning, but not an error. It is taken to be legal, because Pair is treated as a raw type, but conversion from a raw type to the corresponding parameterized type generates an unchecked warning; see Section 5.3, which explains how the -Xlint:unchecked flag can help you spot errors of this kind.

Because generics are compiled by erasure, at run time the classes List<Integer>, List<String>, and List<List<String>> are all implemented by a single class, namely List. You can see this using reflection:


List<Integer> ints = Arrays.asList(1,2,3);

List<String> strings = Arrays.asList("one","two");

assert ints.getClass() == strings.getClass();

Here the class associated with a list of integers at run time is the same as the class associated with a list of strings.

One consequence is that static members of a generic class are shared across all instantiations of that class, including instantiations at different types. Static members of a class cannot refer to the type parameter of a generic class, and when accessing a static member the class name should not be parameterized.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

In a generic class, type parameters appear in the header that declares the class, but not in the constructor:


class Pair<T, U> {

  private final T first;

  private final U second;

  public Pair(T first, U second) { this.first=first; this.second=second; }

  public T getFirst() { return first; }

  public U getSecond() { return second; }

}

The type parameters T and U are declared at the beginning of the class, not in the constructor. However, actual type parameters are passed to the constructor whenever it is invoked:


Pair<String, Integer> pair = new Pair<String, Integer>("one",2);

assert pair.getFirst().equals("one") && pair.getSecond() == 2;

Look Out for This! A common mistake is to forget the type parameters when invoking the constructor:


Pair<String, Integer> pair = new Pair("one",2);

This mistake produces a warning, but not an error. It is taken to be legal, because Pair is treated as a raw type, but conversion from a raw type to the corresponding parameterized type generates an unchecked warning; see Section 5.3, which explains how the -Xlint:unchecked flag can help you spot errors of this kind.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Because generics are compiled by erasure, at run time the classes List<Integer>, List<String>, and List<List<String>> are all implemented by a single class, namely List. You can see this using reflection:


List<Integer> ints = Arrays.asList(1,2,3);

List<String> strings = Arrays.asList("one","two");

assert ints.getClass() == strings.getClass();

Here the class associated with a list of integers at run time is the same as the class associated with a list of strings.

One consequence is that static members of a generic class are shared across all instantiations of that class, including instantiations at different types. Static members of a class cannot refer to the type parameter of a generic class, and when accessing a static member the class name should not be parameterized.

For example, here is a class, Cell<T>, in which each cell has an integer identifier and a value of type T:


class Cell<T> {

  private final int id;

  private final T value;

  private static int count = 0;

  private static synchronized int nextId() { return count++; }

  public Cell(T value) { this.value=value; id=nextId(); }

  public T getValue() { return value; }

  public int getId() { return id; }

  public static int getCount() { return count; }

}

A static field, count, is used to allocate a distinct identifier to each cell. The static nextId method is synchronized to ensure that unique identifiers are generated even in the presence of multiple threads. The static getCount method returns the current count.

Here is code that allocates a cell containing a string and a cell containing an integer, which are allocated the identifiers 0 and 1, respectively:


Cell<String> a = new Cell<String>("one");

Cell<Integer> b = new Cell<Integer>(2);

assert a.getId() == 0 && b.getId() == 1 && Cell.getCount() == 2;

Static members are shared across all instantiations of a class, so the same count is incremented when allocating either a string or an integer cell.

Because static members are independent of any type parameters, we are not permitted to follow the class name with type parameters when accessing a static member:

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Java permits nesting one class inside another. If the outer class has type parameters and the inner class is not static, then type parameters of the outer class are visible within the inner class.

Example 4.1 shows a class implementing collections as a singly-linked list. The class extends java.util.AbstractCollection, so it only needs to define the methods size, add, and iterator. The class contains an inner class, Node, for the list nodes, and an anonymous inner class implementing Iterator<E>. The type parameter E is in scope within both of these classes.

Example 4-1. Type parameters are in scope for nested, nonstatic classes


public class LinkedCollection<E> extends AbstractCollection<E> {

  private class Node {

    private E element;

    private Node next = null;

    private Node(E elt) { element = elt; }

  }

  private Node first = new Node(null);

  private Node last = first;

  private int size = 0;

  public LinkedCollection() {}

  public LinkedCollection(Collection<? extends E> c) { addAll(c); }

  public int size() { return size; }

  public boolean add(E elt) {

    last.next = new Node(elt); last = last.next; size++;

    return true;

  }

  public Iterator<E> iterator() {

    return new Iterator<E>() {

      private Node current = first;

      public boolean hasNext() {

        return current.next != null;

      }

      public E next() {

        if (current.next != null) {

          current = current.next;

          return current.element;

        } else throw new NoSuchElementException();

      }

      public void remove() {

        throw new UnsupportedOperationException();

      }

    };

  }

}

For contrast, Example 4.2 shows a similar implementation, but this time the nested Node class is static, and so the type parameter E is not in scope for this class. Instead, the nested class is declared with its own type parameter, T. Where the previous version referred to Node, the new version refers to Node<E>. The anonymous iterator class in the preceding example has also been replaced by a nested static class, again with its own type parameter.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The erasure of a type is defined as follows: drop all type parameters from parameterized types, and replace any type variable with the erasure of its bound, or with Object if it has no bound, or with the erasure of the leftmost bound if it has multiple bounds. Here are some examples:

The erasure of List<Integer>, List<String>, and List<List<String>> is List.
The erasure of List<Integer>[] is List[].
The erasure of List is itself, similarly for any raw type (see Section 5.3 for an explanation of raw types).
The erasure of int is itself, similarly for any primitive type.
The erasure of Integer is itself, similarly for any type without type parameters.
The erasure of T in the definition of asList(see Section 1.4) is Object, because T has no bound.
The erasure of T in the definition of max (see Section 3.2) is Comparable, because T has bound Comparable<? super T>.
The erasure of T in the final definition of max (see Section 3.6) is Object, because T has bound Object & Comparable<T> and we take the erasure of the leftmost bound.
The erasures of S and T in the definition of copy (see Section 3.6) are Appendable and Readable, because S has bound Appendable & Closeable and T has bound Readable & Closeable.
The erasure of LinkedCollection<E>.Node or LinkedCollection.Node<E> (see Section 4.3) is LinkedCollection.Node.

In Java, two distinct methods cannot have the same signature. Since generics are implemented by erasure, it also follows that two distinct methods cannot have signatures with the same erasure. A class cannot overload two methods whose signatures have the same erasure, and a class cannot implement two interfaces that have the same erasure.

For example, here is a class with two convenience methods. One adds together every integer in a list of integers, and the other concatenates together every string in a list of strings:

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

One motto underpinning the design of generics for Java is evolution, not revolution. It must be possible to migrate a large, existing body of code to use generics gradually (evolution) without requiring a radical, all-at-once change (revolution). The generics design ensures that old code compiles against the new Java libraries, avoiding the unfortunate situation in which half of your code needs old libraries and half of your code needs new libraries.

The requirements for evolution are much stronger than the usual backward compatibility. With simple backward compatibility, one would supply both legacy and generic versions for each application; this is exactly what happens in C#, for example. If you are building on top of code supplied by multiple suppliers, some of whom use legacy collections and some of whom use generic collections, this might rapidly lead to a versioning nightmare.

What we require is that the same client code works with both the legacy and generic versions of a library. This means that the supplier and clients of a library can make completely independent choices about when to move from legacy to generic code. This is a much stronger requirement than backward compatibility; it is called migration compatibility or platform compatibility.

Java implements generics via erasure, which ensures that legacy and generic versions usually generate identical class files, save for some auxiliary information about types. It is possible to replace a legacy class file by a generic class file without changing, or even recompiling, any client code; this is called binary compatibility.

We summarize this with the motto binary compatibility ensures migration compatibility—or, more concisely, erasure eases evolution.

This section shows how to add generics to existing code; it considers a small example, a library for stacks that extends the Collections Framework, together with an associated client. We begin with the legacy stack library and client (written for Java before generics), and then present the corresponding generic library and client (written for Java with generics). Our example code is small, so it is easy to update to generics all in one go, but in practice the library and client will be much larger, and we may want to evolve them separately. This is aided by

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

We begin with a simple library of stacks and an associated client, as presented in Example 5.1. This is legacy code, written for Java 1.4 and its version of the Collections Framework. Like the Collections Framework, we structure the library as an interface Stack (analogous to List), an implementation class ArrayStack (analogous to ArrayList), and a utility class Stacks (analogous to Collections). The interface Stack provides just three methods: empty, push, and pop. The implementation class ArrayStack provides a single constructor with no arguments, and implements the methods empty, push, and pop using methods size, add, and remove on lists. The body of pop could be shorter—instead of assigning the value to the variable, it could be returned directly—but it will be interesting to see how the type of the variable changes as the code evolves. The utility class provides just one method, reverse, which repeatedly pops from one stack and pushes onto another.

Example 5-1. Legacy library with legacy client


l/Stack.java:

  interface Stack {

    public boolean empty();

    public void push(Object elt);

    public Object pop();

  }



l/ArrayStack.java:

  import java.util.*;

  class ArrayStack implements Stack {

    private List list;

    public ArrayStack() { list = new ArrayList(); }

    public boolean empty() { return list.size() == 0; }

    public void push(Object elt) { list.add(elt); }

    public Object pop() {

      Object elt = list.remove(list.size()-1);

      return elt;

    }

    public String toString() { return "stack"+list.toString(); }

  }



l/Stacks.java:

  class Stacks {

    public static Stack reverse(Stack in) {

      Stack out = new ArrayStack();

      while (!in.empty()) {

        Object elt = in.pop();

        out.push(elt);

      }

      return out;

    }

  }



l/Client.java:

  class Client {

    public static void main(String[]  args) {

      Stack stack = new ArrayStack();

      for (int i = 0; i<4; i++) stack.push(new Integer(i));

      assert stack.toString().equals("stack[0, 1, 2, 3]");

      int top =

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Next, we update the library and client to use generics, as presented in Example 5.2. This is generic code, written for Java 5 and its version of the Collections Framework. The interface now takes a type parameter, becoming Stack<E> (analogous to List<E>), and so does the implementing class, becoming ArrayStack<E> (analogous to ArrayList<E>), but no type parameter is added to the utility class Stacks (analogous to Collections). The type Object in the signatures and bodies of push and pop is replaced by the type parameter E. Note that the constructor in ArrayStack does not require a type parameter. In the utility class, the reverse method becomes a generic method with argument and result of type Stack<T>. Appropriate type parameters are added to the client, and boxing and unboxing are now implicit.

Example 5-2. Generic library with generic client


g/Stack.java:

  interface Stack<E> {

    public boolean empty();

    public void push(E elt);

    public E pop();

  }



g/ArrayStack.java:

  import java.util.*;

  class ArrayStack<E> implements Stack<E> {

    private List<E> list;

    public ArrayStack() { list = new ArrayList<E>(); }

    public boolean empty() { return list.size() == 0; }

    public void push(E elt) { list.add(elt); }

    public E pop() {

      E elt = list.remove(list.size()-1);

      return elt;

    }

    public String toString() { return "stack"+list.toString(); }

  }



g/Stacks.java:

  class Stacks {

    public static <T> Stack<T> reverse(Stack<T> in) {

      Stack<T> out = new ArrayStack<T>();

      while (!in.empty()) {

        T elt = in.pop();

        out.push(elt);

      }

      return out;

    }

  }



g/Client.java:

  class Client {

    public static void main(String[] args) {

      Stack<Integer> stack = new ArrayStack<Integer>();

      for (int i = 0; i<4; i++) stack.push(i);

      assert stack.toString().equals("stack[0, 1, 2, 3]");

      int top = stack.pop();

      assert top == 3 && stack.toString().equals("stack[0, 1, 2]");

      Stack<Integer> reverse = Stacks.reverse(stack);

      assert stack.empty();

      assert reverse.toString().equals("stack[2, 1, 0]");

    }

  }

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Now let's consider the case where the library is updated to generics while the client remains in its legacy version. This may occur because there is not enough time to convert everything all at once, or because the library and client are controlled by different organizations. This corresponds to the most important case of backward compatibility, where the generic Collections Framework of Java 5 must still work with legacy clients written against the Collections Framework in Java 1.4.

In order to support evolution, whenever a parameterized type is defined, Java also recognizes the corresponding unparameterized version of the type, called a raw type. For instance, the parameterized type Stack<E> corresponds to the raw type Stack, and the parameterized type ArrayStack<E> corresponds to the raw type ArrayStack.

Every parameterized type is a subtype of the corresponding raw type, so a value of the parameterized type can be passed where a raw type is expected. Usually, it is an error to pass a value of a supertype where a value of its subtype is expected, but Java does permit a value of a raw type to be passed where a parameterized type is expected—however, it flags this circumstance by generating an unchecked conversion warning. For instance, you can assign a value of type Stack<E> to a variable of type Stack, since the former is a subtype of the latter. You can also assign a value of type Stack to a variable of type Stack<E>, but this will generate an unchecked conversion warning.

To be specific, consider compiling the generic source for Stack<E>, ArrayStack<E>, and Stacks from Example 5.2 (say, in directory g) with the legacy source for Client from Example 5.1 (say, in directory l). Sun's Java 5 compiler yields the following message:


% javac g/Stack.java g/ArrayStack.java g/Stacks.java l/Client.java

Note: Client.java uses unchecked or unsafe operations.

Note: Recompile with -Xlint:unchecked for details.

The unchecked warning indicates that the compiler cannot offer the same safety guarantees that are possible when generics are used uniformly throughout. However, when the generic code is generated by updating legacy code, we know that equivalent class files are produced from both, and hence (despite the unchecked warning) running a legacy client with the generic library will yield the same result as running the legacy client with the legacy library. Here we assume that the only change in updating the library was to introduce generics, and that no change to the behavior was introduced, either on purpose or by mistake.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

It usually makes sense to update the library before the client, but there may be cases when you wish to do it the other way around. For instance, you may be responsible for maintaining the client but not the library; or the library may be large, so you may want to update it gradually rather than all at once; or you may have class files for the library, but no source.

In such cases, it makes sense to update the library to use parameterized types in its method signatures, but not to change the method bodies. There are three ways to do this: by making minimal changes to the source, by creating stub files, or by use of wrappers. We recommend use of minimal changes when you have access to source and use of stubs when you have access only to class files, and we recommend against use of wrappers.

The minimal changes technique is shown in Example 5.3. Here the source of the library has been edited, but only to change method signatures, not method bodies. The exact changes required are highlighed in boldface. This is the recommended technique for evolving a library to be generic when you have access to the source.

Example 5-3. Evolving a library using minimal changes


m/Stack.java:

  interface 

 

 Stack<E> {

    public boolean empty();

    public void push(E elt);

    public E pop();

  }



m/ArrayStack.java:

  @SuppressWarnings("unchecked")

  class ArrayStack<E> implements Stack<E> {

    private List list;

    public ArrayStack() { list = new ArrayList(); }

    public boolean empty() { return list.size() == 0; }

    public void push(E elt) { list.add(elt); }  // unchecked call

    public E pop() {

      Object elt = list.remove(list.size()-1);

      return (E)elt;  // unchecked cast

    }

    public String toString() { return "stack"+list.toString(); }

  }



m/Stacks.java:

  @SuppressWarnings("unchecked")

  class Stacks {

    public static <T> Stack<T> reverse(Stack<T> in) {

      Stack out = new ArrayStack();

      while (!in.empty()) {

        Object elt = in.pop();

        out.push(elt);

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

To review, we have seen both generic and legacy versions of a library and client. These generate equivalent class files, which greatly eases evolution. You can use a generic library with a legacy client, or a legacy library with a generic client. In the latter case, you can update the legacy library with generic method signatures, either by minimal changes to the source or by use of stub files.

The foundation stone that supports all this is the decision to implement generics by erasure, so that generic code generates essentially the same class files as legacy code—a property referred to as binary compatibility. Usually, adding generics in a natural way causes the legacy and generic versions to be binary compatible. However, there are some corner cases where caution is required; these are discussed in Section 8.4.

It is interesting to compare the design of generics in Java and in C#. In Java, generic types do not carry information about type parameters at run time, whereas arrays do contain information about the array element type at run time. In C#, both generic types and arrays contain information about parameter and element types at run time. Each approach has advantages and disadvantages. In the next chapter, we will discuss problems with casting and arrays that arise because Java does not reify information about type parameters, and these problems do not arise in C#. On the other hand, evolution in C# is much more difficult. Legacy and generic collection classes are completely distinct, and any attempt to combine legacy collections and generic collections will encounter the difficulties with wrappers discussed earlier. In contrast, as we've seen, evolution in Java is straightforward.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The Oxford English Dictionary defines reify thus: "To convert mentally into a thing; to materialize." A plainer word with the same meaning is thingify. In computing, reification has come to mean an explicit representation of a type—that is, run-time type information. In Java, arrays reify information about their component types, while generic types do not reify information about their type parameters.

The previous chapter was, in a sense, about the advantages of not reifying parameter types. Legacy code makes no distinction between List<Integer> and List<String> and List<List<String>>, so not reifying parameter types is essential to easing evolution and promoting compatibility between legacy code and new code.

But now the time has come to pay the piper. Reification plays a critical role in certain aspects of Java, and the absence of reification that is beneficial for evolution also necessarily leads to some rough edges. This chapter warns you of the limitations and describes some workarounds. The chapter deals almost entirely with things you might wish you didn't need to know—and, indeed, if you never use generic types in casts, instance tests, exceptions, or arrays then you are unlikely to need the material covered here.

We begin with a precise definition of what it means for a type in Java to be reifiable. We then consider corner cases related to reification, including instance tests and casts, exceptions, and arrays. The fit between arrays and generics is the worst rough corner in the language, and we encapsulate how to avoid the worst pitfalls with the Principle of Truth in Advertising and the Principle of Indecent Exposure.

In Java, the type of an array is reified with its component type, while the type of a parameterized type is reified without its type parameters. For instance, an array of numbers will carry the reified type Number[], while a list of numbers will carry the reified type ArrayList, not ArrayList<Number>; the raw type, not the parameterized type, is reified. Of course, each element of the list will have a reified type attached to it—say

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

In Java, the type of an array is reified with its component type, while the type of a parameterized type is reified without its type parameters. For instance, an array of numbers will carry the reified type Number[], while a list of numbers will carry the reified type ArrayList, not ArrayList<Number>; the raw type, not the parameterized type, is reified. Of course, each element of the list will have a reified type attached to it—say Integer or Double—but this is not the same as reifying the parameter type. If every element in the list was an integer, we would not be able to tell whether we had an ArrayList<Integer>, ArrayList<Number>, or ArrayList<Object>; if the list was empty, we would not be able to tell what kind of empty list it was.

In Java, we say that a type is reifiable if the type is completely represented at run time — that is, if erasure does not remove any useful information. To be precise, a type is reifiable if it is one of the following:

A primitive type

(such as int)
A nonparameterized class or interface type

(such as Number, String, or Runnable)
A parameterized type in which all type arguments are unbounded wildcards

(such as List<?>, ArrayList<?>, or Map<?, ?>)
A raw type

(such as List, ArrayList, or Map)
An array whose component type is reifiable

(such as int[], Number[], List<?>[], List[], or int[][])

A type is not reifiable if it is one of the following:

A type variable

(such as T)
A parameterized type with actual parameters

(such as List<Number>, ArrayList<String>, or Map<String, Integer>)
A parameterized type with a bound

(such as List<? extends Number> or Comparable<? super String>)

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Instance tests and casts depend on examining types at run time, and hence depend on reification. For this reason, an instance test against a type that is not reifiable reports an error, and a cast to a type that is not reifiable usually issues a warning.

As an example, consider the use of instance tests and casts in writing equality. Here is a fragment of the definition of the class Integer in java.lang (slightly simplified from the actual source):


public class Integer extends Number {

  private final int value;

  public Integer(int value) { this.value=value; }

  public int intValue() { return value; }

  public boolean equals(Object o) {

    if (o instanceof Integer) {

      return value == ((Integer)o).intValue();

    } else return false;

  }

  ...

}

The equality method takes an argument of type Object, checks whether the object is an instance of class Integer, and, if so, casts it to Integer and compares the values of the two integers. This code works because Integer is a reifiable type: all of the information needed to check whether an object is an instance of Integer is available at run time.

Now consider how one might define equality on lists, as in the class AbstractList in java.util. A natural—but incorrect—way to define this is as follows:


import java.util.*;

public abstract class AbstractList<E>

  extends AbstractCollection<E> implements List<E>

{

  public boolean equals(Object o) {

    if (o instanceof List<E>) {  // compile-time error

      Iterator<E> it1 = iterator();

      Iterator<E> it2 = ((List<E>)o).iterator();  // unchecked cast

      while (it1.hasNext() && it2.hasNext()) {

        E e1 = it1.next();

        E e2 = it2.next();

        if (!(e1 == null ? e2 == null : e1.equals(e2)))

          return false;

      }

      return !it1.hasNext() && !it2.hasNext();

    } else return false;

  }

  ...

}

Again, the equality method takes an argument of type Object, checks whether the object is an instance of type List<E>, and, if so, casts it to List<E> and compares corresponding elements of the two lists. This code does

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

In a try statement, each catch clause checks whether the thrown exception matches a given type. This is the same as the check performed by an instance test, so the same restriction applies: the type must be reifiable. Further, the type in a catch clause is required to be a subclass of Throwable. Since there is little point in creating a subclass of Throwable that cannot appear in a catch clause, the Java compiler complains if you attempt to create a parameterized subclass of Throwable.

For example, here is a permissible definition of a new exception, which contains an integer value:


class IntegerException extends Exception {

  private final int value;

  public IntegerException(int value) { this.value = value; }

  public int getValue() { return value; }

}

And here is a simple example of how to use the exception:


class IntegerExceptionTest {

  public static void main(String[] args) {

    try {

      throw new IntegerException(42);

    } catch (IntegerException e) {

      assert e.getValue() == 42;

    }

  }

}

The body of the try statement throws the exception with a given value, which is caught by the catch clause.

In contrast, the following definition of a new exception is prohibited, because it creates a parameterized type:


class ParametricException<T> extends Exception {  // compile-time error

  private final T value;

  public ParametricException(T value) { this.value = value; }

  public T getValue() { return value; }

}

An attempt to compile the above reports an error:


% javac ParametricException.java

ParametricException.java:1: a generic class may not extend

java.lang.Throwable

class ParametricException<T> extends Exception {  // compile-time error

                                     ^

1 error

This restriction is sensible because almost any attempt to catch such an exception must fail, because the type is not reifiable. One might expect a typical use of the exception to be something like the following:


class ParametricExceptionTest {

  public static void main(String[] args) {

    try {

      throw new ParametricException<Integer>(42);

    } catch (

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Arrays reify their component types, meaning that they carry run-time information about the type of their components. This reified type information is used in instance tests and casts, and also used to check whether assignments into array components are permitted. Recall this example from Section 2.5.


Integer[] ints = new Integer[] {1,2,3};

Number[] nums = ints;

nums[2] = 3.14;  // array store exception

The first line allocates a new array, with reified type information indicating that it is an array of integers. The second line assigns this array to a variable containing an array of numbers; this is permitted because arrays, unlike generic types, are covariant. The assignment on the third line raises an array store exception at run time because the assigned value is of type double, and this is not compatible with the reified type attached to the array.

Because arrays must reify their component types, it is an error to create a new array unless its component type is reifiable. The two main problems you are likely to encounter are when the type of the array is a type variable, and when the type of the array is a parameterized type.

Consider the following (incorrect) code to convert a collection to an array:


import java.util.*;

class Annoying {

  public static <T> T[] toArray(Collection<T> c) {

    T[] a = new T[c.size()];  // compile-time error

    int i=0; for (T x : c) a[i++] = x;

    return a;

  }

}

This is an error, because a type variable is not a reifiable type. An attempt to compile this code reports a generic array creation error:


% javac Annoying.java

Annoying.java:4: generic array creation

    T[] a = new T[c.size()];  // compile-time error

            ^

1 error

We discuss workarounds for this problem shortly.

As a second example, consider the following (incorrect) code that returns an array containing two lists:


import java.util.*;

class AlsoAnnoying {

  public static List<Integer>[] twoLists() {

    List<Integer> a = Arrays.asList(1,2,3);

    List<Integer> b = Arrays.asList(4,5,6);

    return

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

We saw in the previous section that a naïve method to convert a collection to an array will not work. The first fix we might try is to add an unchecked cast, but we will see shortly that this leads to even more perplexing problems. The correct fix will require us to resort to reflection. Since the same issues arise when converting any generic structure to an array, it is worth understanding the problems and their solution. We will study variations of the static toArray method from the previous section; the same ideas apply to the toArray method in the Collection interface of the Collections Framework.

Here is a second attempt to convert a collection to an array, this time using an unchecked cast, and with test code added:


import java.util.*;

class Wrong {

  public static <T> T[] toArray(Collection<T> c) {

    T[] a = (T[])new Object[c.size()];  // unchecked cast

    int i=0; for (T x : c) a[i++] = x;

    return a;

  }

  public static void main(String[] args) {

    List<String> strings = Arrays.asList("one","two");

    String[] a = toArray(strings);  // class cast error

  }

}

The code in the previous section used the phrase new T[c.size()] to create the array, causing the compiler to report a generic array creation error. The new code instead allocates an array of objects and casts it to type T[], which causes the compiler to issue an unchecked cast warning:


% javac -Xlint Wrong.java

Wrong.java:4: warning: [unchecked] unchecked cast

found   : java.lang.Object[]

required: T[]

        T[] a = (T[])new Object[c.size()];  // unchecked cast

                     ^

1 warning

As you might guess from the name chosen for this program, this warning should not be ignored. Indeed, running this program gives the following result:


% java Wrong

Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object;

        at Wrong.main(Wrong.java:11)

The obscure phrase [Ljava.lang.Object is the reified type of the array, where [L indicates that it is an array of reference type, and

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Although it is an error to create an array with a component type that is not reifiable, it is possible to declare an array with such a type and to perform an unchecked cast to such a type. These features must be used with extreme caution, and it is worthwhile to understand what can go wrong if they are not used properly. In particular, a library should never publicly expose an array with a nonreifiable type.

Recall that Section 2.5 presents an example of why reification is necessary:


Integer[] ints = new Integer[] {1};

Number[] nums = ints;

nums[0] = 1.01;  // array store 

 

 exception

 

 



int n = ints[0];

This assigns an array of integers to an array of numbers, and then attempts to store a double into the array of numbers. The attempt raises an array store exception because of the check against the reified type. This is just as well, since otherwise the last line would attempt to store a double into an integer variable.

Here is a similar example, where arrays of numbers are replaced by arrays of lists of numbers:


List<Integer>[] intLists

  = (List<Integer>[])new List[] {Arrays.asList(1)}; // unchecked cast

List<? extends Number>[] numLists = intLists;

numLists[0] = Arrays.asList(1.01);

int n = intLists[0].get(0);  // class cast exception!

This assigns an array of lists of integers to an array of lists of numbers, and then attempts to store a list of doubles into the array of lists of numbers. This time the attempted store does not fail, even though it should, because the check against the reified type is inadequate: the reified information contains only the erasure of the type, indicating that it is an array of List, not an array of List<Integer>. Hence the store succeeds, and the program fails unexpectedly elsewhere.

Example 6.1 presents a similar example, divided into two classes in order to demonstrate how a poorly designed library can create problems for an innocent client. The first class, called DeceptiveLibrary, defines a static method that returns an array of lists of integers of a given size. Since generic array creation is not permitted, the array is created with components of the raw type

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

We have argued elsewhere that it is usually preferable to use a list than to use an array. There are a few places where this is not appropriate. In rare circumstances, you will need to use an array for reasons of efficiency or compatibility. Also, of course, you need to use arrays to implement ArrayList itself. Here we present the implementation of ArrayList as a model of what to do in the rare circumstance where you do need to use an array. Such implementations need to be written with care, as they necessarily involve use of unchecked casts. We will see how the Principles of Indecent Exposure and of Truth in Advertising figure in the implementation.

Example 6.2 shows the implementation. We have derived ArrayList by subclassing from AbstractList. Classes derived from this class need to define only four methods, namely get, set, add, and remove; the other methods are defined in terms of these. We also indicate that the class implements RandomAccess, indicating that clients of the class will have more efficient access using get than using the list iterator.

Example 6-2. How to define ArrayList


import java.util.*;

class ArrayList<E> extends AbstractList<E> implements RandomAccess {

  private E[] arr;

  private int size = 0;

  public ArrayList(int cap) {

    if (cap < 0)

      throw new IllegalArgumentException("Illegal Capacity: "+cap);

    arr = (E[])new Object[cap];  // unchecked cast

  }

  public ArrayList() { this(10); }

  public ArrayList(Collection<? extends E> c) { this(c.size()); addAll(c); }

  public void ensureCapacity(int mincap) {

    int oldcap = arr.length;

    if (mincap > oldcap) {

      int newcap = Math.max(mincap, (oldcap*3)/2+1);

      E[] oldarr = arr;

      arr = (E[])new Object[newcap];  // unchecked cast

      System.arraycopy(oldarr,0,arr,0,size);

    }

  }

  public int size() { return size; }

  private void checkBounds(int i, int size) {

    if (i < 0 || i >= size)

      throw new IndexOutOfBoundsException("Index: "+i+", Size: "+size);

  }

  public E get(int i) { checkBounds(i,size); return arr[i]; }

  public E set(int i, E elt) {

    checkBounds(i,size); E old = arr[i]; arr[i] = elt; return old;

  }

  public void add(int i, E elt) {

    checkBounds(i,size+1); ensureCapacity(size+1);

    System.arraycopy(arr,i,arr,i+1,size-i); arr[i] = elt;  size++;

  }

  public E remove(int i) {

    checkBounds(i,size); E old = arr[i];  arr[i] = null;  size--;

    System.arraycopy(arr,i+1,arr,i,size-i); return old;

  }

  public <T> T[] toArray(T[] a) {

    if (a.length < size)

      a =

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The convenient vararg notation allows methods to accept a variable number of arguments and packs them into an array, as discussed in Section 1.4. This notation is not as convenient as you might like, because the arrays it creates suffer from the same issues involving reification as other arrays.

In Section 1.4 we discussed the method java.util.Arrays.asList, which is declared as follows:


public static <E> List<E> asList(E... arr)

For instance, here are three calls to this method:


List<Integer> a = Arrays.asList(1, 2, 3);

List<Integer> b = Arrays.asList(4, 5, 6);

List<List<Integer>> x = Arrays.asList(a, b);  // generic array creation

Recall that an argument list of variable length is implemented by packing the arguments into an array and passing that. Hence these three calls are equivalent to the following:


List<Integer> a = Arrays.asList(new Integer[] { 1, 2, 3 });

List<Integer> b = Arrays.asList(new Integer[] { 4, 5, 6 });

List<List<Integer>> x

  = Arrays.asList(new List<Integer>[] { a, b });  // generic array creation

The first two calls are fine, but since List<Integer> is not a reifiable type, the third warns of an unchecked generic array creation at compile time.


VarargError.java:6: warning: [unchecked] unchecked generic array creation

of type java.util.List<java.lang.Integer>[] for varargs 

 

 parameter

        List<List<Integer>> x = Arrays.asList(a, b);

This warning can be confusing, particularly since that line of source code does not contain an explicit instance of array creation!

A similar problem occurs if one attempts to create a list of a generic type. Here is a method that uses Arrays.asList to create a list of length one containing a given element:


public static List<E> singleton(E elt) {

  return Arrays.asList(elt);  // generic array creation

}

This also generates a warning, which can be confusing for the same reasons.

Normally, generic array creation reports an error. As a workaround, one can create the array at a reifiable type and perform an unchecked cast. That workaround is not available for the array creation that is implicit in the use of

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

We have seen that collections are superior to arrays in a number of ways:

Collections provide more precise typing than arrays. With lists, one can write List<T>, List<? extends T>, or List<? super T>; whereas with arrays, one can only write T[], which corresponds to the second of the three options for lists. More-precise typing enables more errors to be detected at compile time rather than run time. This makes coding, debugging, testing, and maintenance easier, and also improves efficiency. (See Section 2.5.)
Collections are more flexible than arrays. Collections offer a variety of representations, including arrays, linked lists, trees, and hash tables, whereas arrays have a fixed representation, and the libraries offer a larger variety of methods and convenience algorithms on collections than on arrays. (See Section 2.5.)
Collections may have elements of any type, whereas arrays should only have components of reifiable type. When creating an array, one must adhere to the Principle of Truth in Advertising—the reified type must conform to the static type—and the Principle of Indecent Exposure—never publicly expose an array where the components do not have reifiable type. (See Sections 6.5 and 6.6).

In retrospect, there are several places in Java 5 where avoiding the use of arrays might have improved the design:

Variable-length arguments (varargs) are represented by an array, and so are subject to the same restrictions. If a vararg is bound to actual arguments of nonreifiable type then a generic array creation warning is issued (which raises the same concerns as an unchecked warning). For instance, the function Arrays.asList takes a vararg. There is no difficulty in applying this function to return a result of type List<Integer>, but it is problematic to create a result of type List<List<Integer>> or of type List<E>. This problem would not arise if lists had been used in preference to arrays. (See Section 6.8.)

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

We conclude by giving a checklist of places where reifiable types are required or recommended.

An instance test must be against a reifiable type.
A cast should usually be to a reifiable type. (A cast to a nonreifiable type usually issues an unchecked warning.)
A class that extends Throwable must not be parameterized.
An array instance creation must be at a reifiable type.
The reified type of an array must be a subtype of the erasure of its static type (see the Principle of Truth in Advertising), and a publicly exposed array should be of a reifiable type (see the Principle of Indecent Exposure).
Varargs should be of a reifiable type. (A vararg of a nonreifiable type will issue an unchecked warning.)

These restrictions arise from the fact that generics are implemented via erasure, and they should be regarded as the price one pays for the ease of evolution that we explored in the previous chapter.

For completeness, we also list restrictions connected with reflection:

Class tokens correspond to reifiable types, and the type parameter in Class<T> should be a reifiable type. (See Section 7.2.)

These are discussed in the next chapter.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Reflection is the term for a set of features that allows a program to examine its own definition. Reflection in Java plays a role in class browsers, object inspectors, debuggers, interpreters, services such as JavaBeans^™ and object serialization, and any tool that creates, inspects, or manipulates arbitrary Java objects on the fly.

Reflection has been present in Java since the beginning, but the advent of generics changes reflection in two important ways, introducing both generics!for reflection and reflection for generics.

By generics for reflection we mean that some of the types used for reflection are now generic types. In particular, the class Class becomes the generic class Class<T>. This may seem confusing at first, but once understood it can make programs using reflection much clearer. Class literals and the method Object.getClass use special tricks to return more-precise type information. Generics are used to especially good effect in the reflection of annotations. We observe that the type parameter T in Class<T> should always be bound to a reifiable type, and we present a short library that can help you avoid many common cases of unchecked casts.

By reflection for generics we mean that reflection now returns information about generic types. There are new interfaces to represent generic types, including type variables, parameterized types, and wildcard types, and there are new methods that get the generic types of fields, constructors, and methods.

We explain each of these points in turn. We don't assume any previous knowledge of reflection, but we focus on the aspects tied to generics.

Java has supported facilities for reflection since version 1.0 and class literals since version 1.1. Central to these is the class Class, which represents information about the type of an object at run time. You may write a type followed by .class as a literal that denotes the class token corresponding to that type, and the method getClass is defined on every object and returns a class token that represents the reified type information carried by that object at run-time. Here is an example:

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Java has supported facilities for reflection since version 1.0 and class literals since version 1.1. Central to these is the class Class, which represents information about the type of an object at run time. You may write a type followed by .class as a literal that denotes the class token corresponding to that type, and the method getClass is defined on every object and returns a class token that represents the reified type information carried by that object at run-time. Here is an example:


Class ki = Integer.class;

Number n = new Integer(42);

Class kn = n.getClass();

assert ki == kn;

For a given class loader, the same type is always represented by the same class token. To emphasize this point, here we compare class tokens using identity (the == operator). However, in practice, it often is more robust to use equality (the equals method).

One of the changes in Java 5 is that the class Class now takes a type parameter, so Class<T> is the type of the class token for the type T. The preceding code is now written as follows:


Class<Integer> ki = Integer.class;

Number n = new Integer(42);

Class<? extends Number> kn = n.getClass();

assert ki == kn;

Class tokens and the getClass method are treated specially by the compiler. In general, if T is a type without type parameters, then T.class has type Class<T>, and if e is an expression of type T then e.getClass() has type Class<? extends T>. (We'll see what happens when T does have type parameters in the next section.) The wildcard is needed because the type of the object referred to by the variable may be a subtype of the type of the variable, as in this case, where a variable of type Number contains an object of type Integer.

For many uses of reflection, you won't know the exact type of the class token (if you did, you probably wouldn't need to use reflection), and in those cases you can write Class<?> for the type, using an unbounded wildcard. However, in some cases the type information provided by the type parameter is invaluable, as in the variant of

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Reflection makes reified type information available to the program. Of necessity, therefore, each class token corresponds to a reifiable type. If you try to reflect a parameterized type, you get the reified information for the corresponding raw type:


List<Integer> ints = new ArrayList<Integer>();

List<String> strs  = new ArrayList<String>();

assert ints.getClass() == strs.getClass();

assert ints.getClass() == ArrayList.class;

Here the type list of integers and the type list of strings are both represented by the same class token, the class literal for which is written ArrayList.class.

Because the class always represents a reifiable type, there is no point in parameterizing the class Class with a type that is not reifiable. Hence, the two main methods for producing a class with a type parameter, namely the getClass method and class literals, are both designed to yield a reifiable type for the type parameter in all cases.

Recall that the getClass method is treated specially by the compiler. In general, if expression e has type T, then the expression e.getClass() has type Class<? extends |T|>, where |T| is the erasure of the type T. Here's an example:


List<Integer> ints = new ArrayList<Integer>();

Class<? extends List> k = ints.getClass();

assert k == ArrayList.class;

Here the expression ints has type List<Integer>, so the expression int.getClass() has type Class<? extends List>; this is the case because erasing List<Integer> yields the raw type List. The actual value of k is ArrayList.class, which has type Class<ArrayList>, which is indeed a subtype of Class<? extends List>.

Class literals are also restricted; it is not even syntactically valid to supply a type parameter to the type in a class literal. Thus, the following fragment is illegal:


class ClassLiteral {

  public Class<?> k = List<Integer>.class;  // syntax error

}

Indeed, Java's grammar makes a phrase such as the preceding one difficult to parse, and it may trigger a cascade of syntax errors:

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Every type in Java, including primitive types and array types, has a class literal and a corresponding class token.

For instance, int.class denotes the class token for the primitive type for integers (this token is also the value of the static field Integer.TYPE). The type of this class token cannot be Class<int>, since int is not a reference type, so it is taken to be Class<Integer>. Arguably, this is an odd choice, since according to this type you might expect the calls int.class.cast(o) and int.class.newInstance() to return values of type Integer, but in fact these calls raise an exception. Similarly, you might expect the call


java.lang.reflect.array.newInstance(int.class,size)

to return a value of type Integer[], but in fact the call returns a value of type int[]. These examples suggest that it might have made more sense to give the class token int.class the type Class<?>.

On the other hand, int[].class denotes the class token for arrays with components of the primitive type integer, and the type of this class token is Class<int[]>, which is permitted since int[] is a reference type.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

As we've seen, careless use of unchecked casts can lead to problems, such as violating the Principle of Truth in Advertising or the Principle of Indecent Exposure (see Sections 6.5 and 6.6). One technique to minimize the use of unchecked casts is to encapsulate these within a library. The library can be carefully scrutinized to ensure that its use of unchecked casts is safe, while code that calls the library can be free of unchecked casts. Sun is considering adding library methods similar to the ones described here.

Example 7.1 provides a library of generic functions that use reflection in a type-safe way. It defines a convenience class GenericReflection containing the following methods:


public static <T> T newInstance(T object)

public static <T> Class<? extends T> getComponentType(T[] a)

public static <T> T[] newArray(Class<? extends T> k, int size)

public static <T> T[] newArray(T[] a, int size)

Example 7-1. A type-safe library for generic reflection


class GenericReflection {

  public static <T> T newInstance(T obj)

  throws InstantiationException,

         IllegalAccessException,

         InvocationTargetException,

         NoSuchMethodException

  {

    Object newobj = obj.getClass().getConstructor().newInstance();

    return (T)newobj;  // unchecked cast

  }

  public static <T> Class<? extends T> getComponentType(T[] a) {

    Class<?> k = a.getClass().getComponentType();

    return (Class<? extends T>)k;  // unchecked cast

  }

  public static <T> T[] newArray(Class<? extends T> k, int size) {

    if (k.isPrimitive())

      throw new IllegalArgumentException

                ("Argument cannot be primitive: "+k);

    Object a = java.lang.reflect.Array.newInstance(k, size);

    return (T[])a;  // unchecked cast

  }

  public static <T> T[] newArray(T[] a, int size) {

    return newArray(getComponentType(a), size);

  }

}

The first takes an object, finds the class of that object, and returns a new instance of the class; this must have the same type as the original object. The second takes an array and returns a class token for its component type, as carried in its run-time type information. Conversely, the third allocates a new array with its component type specified by a given class token and a specified size. The fourth takes an array and a size, and allocates a new array with the same component type as the given array and the given size; it simply composes calls to the previous two methods. The code for each of the first three methods consists of a call to one or two corresponding methods in the Java reflection library and an unchecked cast to the appropriate return type.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Generics change the reflection library in two ways. We have discussed generics for reflection, where Java added a type parameter to the class Class<T>. We now discuss reflection for generics, where Java adds methods and classes that support access to generic types.

Example 7.2 shows a simple demonstration of the use of reflection for generics. It uses reflection to find the class associated with a given name, and it prints out the fields, constructors, and methods associated with the class, using the reflection library classes Field, Constructor, and Method. Two different methods are available for converting a field, constructor, or method to a string for printing: the old toString method and the new toGenericString method. The old method is maintained mainly for backward compatibility. A small sample class is shown in Example 7.3, and a sample run with this class is shown in Example 7.4.

Example 7-2. Reflection for generics


import java.lang.reflect.*;

import java.util.*;

class ReflectionForGenerics {

  public static void toString(Class<?> k) {

    System.out.println(k + " (toString)");

    for (Field f : k.getDeclaredFields())

      System.out.println(f.toString());

    for (Constructor c : k.getDeclaredConstructors())

      System.out.println(c.toString());

    for (Method m : k.getDeclaredMethods())

      System.out.println(m.toString());

    System.out.println();

  }

  public static void toGenericString(Class<?> k) {

    System.out.println(k + " (toGenericString)");

    for (Field f : k.getDeclaredFields())

      System.out.println(f.toGenericString());

    for (Constructor c : k.getDeclaredConstructors())

      System.out.println(c.toGenericString());

    for (Method m : k.getDeclaredMethods())

      System.out.println(m.toGenericString());

    System.out.println();

  }

  public static void main (String[] args)

  throws ClassNotFoundException {

    for (String name : args) {

      Class<?> k = Class.forName(name);

      toString(k);

      toGenericString(k);

    }

  }

}

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The reflection library provides a Type interface to describe a generic type. There is one class that implements this interface and four other interfaces that extend it, corresponding to the five different kinds of types:

The class Class, representing a primitive type or raw type
The interface ParameterizedType, representing an application of a generic class or interface to parameter types, from which you can extract an array of the parameter types
The interface TypeVariable, representing a type variable, from which you can extract the bounds on the type variable
The interface GenericArrayType, representing an array, from which you can extract the array component type
The interface WildcardType, representing a wildcard, from which you can extract a lower or upper bound on the wildcard

By performing a series of instance tests on each of these interfaces, you may determine which kind of type you have, and print or process the type; we will see an example of this shortly.

Methods are available to return the superclass and superinterfaces of a class as types, and to access the generic type of a field, the argument types of a constructor, and the argument and result types of a method.

You can also extract the type variables that stand for the formal parameters of a class or interface declaration, or of a generic method or constructor. The type for type variables takes a parameter, and is written TypeVariable<D>, where D represents the type of object that declared the type variable. Thus, the type variables of a class have type TypeVariable<Class<?>>, while the type variables of a generic method have type TypeVariable<Method>. Arguably, the type parameter is confusing and is not very helpful. Since it is responsible for the problem described in Section 6.6, Sun may remove it in the future.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

This chapter contains advice on how to use generics effectively in practical coding. We consider checked collections, security issues, specialized classes, and binary compatibility. The title of this section is an homage to Joshua Bloch's book, Effective Java (Addison-Wesley).

As we have seen, generic types are checked at compile time, not run time. Usually, this is just what we want, since checking at compile time reports errors earlier and incurs no run-time overhead. However, sometimes this may not be appropriate, either because we can't be sure that compile-time checks are adequate (say, because we are passing an instance of a parameterized type to a legacy client or to a client we don't trust), or because we need information about types at run time (say, because we want a reifiable type for use as an array component). A checked collection will often do the trick, and when that will not do, we can create a specialized class. We consider checked collections in this section, security issues in the next section, and specialized classes in the section after that.

Consider a legacy library that contains methods to add items to a given list and to return a new list containing given items:


class LegacyLibrary {

  public static void addItems(List list) {

    list.add(new Integer(1));  list.add("two");

  }

  public static List getItems() {

    List list = new ArrayList();

    list.add(new Integer(3));  list.add("four");

    return list;

  }

}

Now consider a client that uses this legacy library, having been told (incorrectly) that the items are always integers:


class NaiveClient {

  public static void processItems() {

    List<Integer> list = new ArrayList<Integer>();

    LegacyLibrary.addItems(list);

    List<Integer> list2 = LegacyLibrary.getItems(); // unchecked

    // sometime later ...

    int s = 0;

    for (int i : list) s += i; // class cast 

 

 exception

 

 

 



    for (int i : list2) s += i; // class cast exception

  }

}

There is no warning when passing the integer list to the method

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

As we have seen, generic types are checked at compile time, not run time. Usually, this is just what we want, since checking at compile time reports errors earlier and incurs no run-time overhead. However, sometimes this may not be appropriate, either because we can't be sure that compile-time checks are adequate (say, because we are passing an instance of a parameterized type to a legacy client or to a client we don't trust), or because we need information about types at run time (say, because we want a reifiable type for use as an array component). A checked collection will often do the trick, and when that will not do, we can create a specialized class. We consider checked collections in this section, security issues in the next section, and specialized classes in the section after that.

Consider a legacy library that contains methods to add items to a given list and to return a new list containing given items:


class LegacyLibrary {

  public static void addItems(List list) {

    list.add(new Integer(1));  list.add("two");

  }

  public static List getItems() {

    List list = new ArrayList();

    list.add(new Integer(3));  list.add("four");

    return list;

  }

}

Now consider a client that uses this legacy library, having been told (incorrectly) that the items are always integers:


class NaiveClient {

  public static void processItems() {

    List<Integer> list = new ArrayList<Integer>();

    LegacyLibrary.addItems(list);

    List<Integer> list2 = LegacyLibrary.getItems(); // unchecked

    // sometime later ...

    int s = 0;

    for (int i : list) s += i; // class cast 

 

 exception

 

 

 



    for (int i : list2) s += i; // class cast exception

  }

}

There is no warning when passing the integer list to the method addItems, because the parameterized type List<Integer> is considered a subtype of List. The conversion from List to List<Integer> of the list returned by getItems does issue an unchecked warning. At run-time, a class cast exception will be raised when attempting to extract data from these lists, since the cast to type

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

It is important to be aware that the guarantees offered by generic types apply only if there are no unchecked warnings. This means that generic types are useless for ensuring security in code written by others, since you have no way of knowing whether that code raised unchecked warnings when it was compiled.

Say we have a class that defines an order, with a subclass that defines an authenticated order:


class Order { ... }

class AuthenticatedOrder extends Order { ... }

Interfaces specify suppliers and processors of orders. Here the supplier is required to provide only authenticated orders, while the processor handles all kinds of orders:


interface OrderSupplier {

  public void addOrders(List<AuthenticatedOrder> orders);

}

interface OrderProcessor {

  public void processOrders(List<? extends Order> orders);

}

From the types involved, you might think that the following broker guarantees that only authenticated orders can pass from the supplier to the processor:


class NaiveBroker {

  public void connect(OrderSupplier supplier,

                      OrderProcessor processor)

  {

    List<AuthenticatedOrder> orders =

      new ArrayList<AuthenticatedOrder>();

    supplier.addOrders(orders);

    processor.processOrders(orders);

  }

}

But a devious supplier may, in fact, supply unauthenticated orders:


class DeviousSupplier implements OrderSupplier {

  public void addOrders(List<AuthenticatedOrder> orders) {

    List raw = orders;

    Order order = new Order();  // not authenticated

    raw.add(order);  // unchecked call

  }

}

Compiling the devious supplier will issue an unchecked warning, but the broker has no way of knowing this.

Incompetence can cause just as many problems as deviousness. Any code that issues unchecked warnings when compiled could cause similar problems, perhaps simply because the author made a mistake. In particular, legacy code may raise such problems, as described in the previous section.

The correct solution is for the broker to pass a checked list to the supplier:

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Parameterized types are not reifiable, but some operations, such as instance tests, casting, and array creation apply only to reifiable types. In such cases, one workaround is to create a specialized version of the parameterized type. Specialized versions can be created either by delegation (that is, wrappers) or by inheritance (that is, subclassing), and we discuss each in turn.

Example 8.1 shows how to specialize lists to strings; specializing to other types is similar. We begin by specializing the List interface to the desired type:

Example 8-1. Specialize to create reifiable types


interface ListString extends List<String> {}



class ListStrings {

  public static ListString wrap(final List<String> list) {

    class Random extends AbstractList<String>

      implements ListString, RandomAccess

    {

      public int size() { return list.size(); }

      public String get(int i) { return list.get(i); }

      public String set(int i, String s) { return list.set(i,s); }

      public String remove(int i) { return list.remove(i); }

      public void add(int i, String s) { list.add(i,s); }

    }

    class Sequential extends AbstractSequentialList<String>

      implements ListString

    {

      public int size() { return list.size(); }

      public ListIterator<String> listIterator(int index) {

        final ListIterator<String> it = list.listIterator(index);

        return new ListIterator<String>() {

          public void add(String s) { it.add(s); }

          public boolean hasNext() { return it.hasNext(); }

          public boolean hasPrevious() { return it.hasPrevious(); }

          public String next() { return it.next(); }

          public int nextIndex() { return it.nextIndex(); }

          public String previous() { return it.previous(); }

          public int previousIndex() { return it.previousIndex(); }

          public void remove() { it.remove(); }

          public void set(String s) { it.set(s); }

        };

      }

    }

    return list instanceof RandomAccess ? new Random() : new Sequential();

  }

}



class ArrayListString extends ArrayList<String> implements ListString {

  public ArrayListString() { super(); }

  public ArrayListString(Collection<? extends String> c) { super(c); }

  public ArrayListString(int capacity) { super(capacity); }

}

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

As we have stressed, generics are implemented via erasure in order to ease evolution. When evolving legacy code to generic code, we want to ensure that the newly-generified code will work with any existing code, including class files for which we do not have the source. When this is the case, we say that the legacy and generic versions are binary compatible.

Binary compatibility is guaranteed if the erasure of the signature of the generic code is identical to the signature of the legacy code and if both versions compile to the same bytecode. Usually, this is a natural consequence of generification, but in this section we look at some of the corner cases that can cause problems.

Some examples for this section were taken from internal Sun notes written by Mark Reinhold.

Adjusting the Erasure One corner case arises in connection with the generification of the max method in the Collections class. We discussed this case in Sections 3.2 and 3.6, but it is worth a quick review.

Here is the legacy signature of this method:


// legacy version

public static Object max(Collection coll)

And here is the natural generic signature, using wildcards to obtain maximum flexibility (see Section 3.2):


// generic version -- breaks binary compatibility

public static <T extends Comparable<? super T>>

  T max(Collection<? extends T> coll)

But this signature has the wrong erasure—its return type is Comparable rather than Object. In order to get the right signature, we need to fiddle with the bounds on the type parameter, using multiple bounds (see Section 3.6). Here is the corrected version:


// generic version -- maintains binary compatibility

public static <T extends Object & Comparable<? super T>>

  T max(Collection<? extends T> coll)

When there are multiple bounds, the leftmost bound is taken for the erasure. So the erasure of T is now Object, giving the result type we require.

Some problems with generification arise because the original legacy code contains less-specific types than it might have. For example, the legacy version of

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

This chapter reviews five well-known design patterns—Visitor, Interpreter, Function, Strategy, and Subject-Observer—and shows how they can take advantage of generics. The Function pattern generalizes the idea behind the Comparator interface. The other four patterns are described in the seminal book Design Patterns, by Gamma, Helm, Johnson, and Vlissides (Addison-Wesley).

Often, a data structure is defined by case analysis and recursion. For example, a binary tree of type Tree<E> is one of the following:

A leaf, containing a single value of type E
A branch, containing a left subtree and a right subtree, both of type Tree<E>

It is easy to think of many other examples: a shape may be either a triangle, a rectangle, a combination of two shapes, or the transposition of a shape; an XML node is either a text node, an attribute node, or an element node (which may contain other nodes); and so on.

To represent such a structure in an object-oriented language, the data structure is represented by an abstract class, and each case is represented by a subclass. The abstract class declares an abstract method for each possible operation on the data structure, and each subclass implements the method as appropriate for the corresponding case.

Example 9.1 illustrates this technique applied to trees. There is an abstract class, Tree<E>, with two abstract methods, toString and sum. (The former applies to any tree, while the latter applies only to a tree of numbers—for simplicity, this restriction is enforced by a cast at run time rather than a type at compile time, as discussed later.) There are two static factory methods, one to construct a leaf and one to construct a branch. Each of these contains a nested class that extends Tree<E> and implements each of the methods toString and sum.

Example . A simple tree and client


abstract class Tree<E> {

  abstract public String toString();

  abstract public Double sum();

  public static <E> Tree<E> leaf(final E e) {

    return new Tree<E>() {

      public String toString() {

        return e.toString();

      }

      public Double sum() {

        return ((Number)e).doubleValue();

      }

    };

  }

  public static <E> Tree<E> branch(final Tree<E> l, final Tree<E> r) {

    return new Tree<E>() {

      public String toString() {

        return "("+l.toString()+"^"+r.toString()+")";

      }

      public Double sum() {

        return l.sum() + r.sum();

      }

    };

  }

}

class TreeClient {

  public static void main(String[] args) {

    Tree<Integer> t =

      Tree.branch(Tree.branch(Tree.leaf(1),

                              Tree.leaf(2)),

                  Tree.leaf(3));

    assert t.toString().equals("((1^2)^3)");

    assert t.sum() == 6;

  }

}

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Often, a data structure is defined by case analysis and recursion. For example, a binary tree of type Tree<E> is one of the following:

A leaf, containing a single value of type E
A branch, containing a left subtree and a right subtree, both of type Tree<E>

It is easy to think of many other examples: a shape may be either a triangle, a rectangle, a combination of two shapes, or the transposition of a shape; an XML node is either a text node, an attribute node, or an element node (which may contain other nodes); and so on.

To represent such a structure in an object-oriented language, the data structure is represented by an abstract class, and each case is represented by a subclass. The abstract class declares an abstract method for each possible operation on the data structure, and each subclass implements the method as appropriate for the corresponding case.

Example 9.1 illustrates this technique applied to trees. There is an abstract class, Tree<E>, with two abstract methods, toString and sum. (The former applies to any tree, while the latter applies only to a tree of numbers—for simplicity, this restriction is enforced by a cast at run time rather than a type at compile time, as discussed later.) There are two static factory methods, one to construct a leaf and one to construct a branch. Each of these contains a nested class that extends Tree<E> and implements each of the methods toString and sum.

Example . A simple tree and client


abstract class Tree<E> {

  abstract public String toString();

  abstract public Double sum();

  public static <E> Tree<E> leaf(final E e) {

    return new Tree<E>() {

      public String toString() {

        return e.toString();

      }

      public Double sum() {

        return ((Number)e).doubleValue();

      }

    };

  }

  public static <E> Tree<E> branch(final Tree<E> l, final Tree<E> r) {

    return new Tree<E>() {

      public String toString() {

        return "("+l.toString()+"^"+r.toString()+")";

      }

      public Double sum() {

        return l.sum() + r.sum();

      }

    };

  }

}

class TreeClient {

  public static void main(String[] args) {

    Tree<Integer> t =

      Tree.branch(Tree.branch(Tree.leaf(1),

                              Tree.leaf(2)),

                  Tree.leaf(3));

    assert t.toString().equals("((1^2)^3)");

    assert t.sum() == 6;

  }

}

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

One use of trees is to represent expressions in a programming language. As in the previous section, the expression type is represented by an abstract class, with each kind of expression represented by a subclass. There is an abstract method to evaluate an expression, and each subclass implements the method as appropriate for the corresponding kind of expression.

With generics, it is possible to parameterize the expression type by the type of the expression. For example, Exp<Integer> is an expression that returns an integer, while Exp<Pair<Integer, Integer>> is an expression that returns a pair of integers.

Example 9.4 demonstrates the Interpreter pattern with generics. It begins by defining a class Pair<A, B>, with a constructor and two methods to select the left and right components of a pair. It then declares an abstract class, Exp<A>, for an expression that returns a value of type A, with an abstract method eval that returns a value of type A. In our example, there are five kinds of expression:

An integer literal, of type Exp<Integer>
A sum expression, of type Exp<Integer>, which has two subexpressions, each of type Exp<Integer>
An expression to construct a pair, of type Exp<Pair<A, B>>, which has two subexpressions of type Exp<A> and Exp<B>
An expression to select the left component of a pair, of type Exp<A>, which has a subexpression of type Exp<Pair<A, B>>
An expression to select the right component of a pair, of type Exp<B>, which has a subexpression of type Exp<Pair<A, B>>

Example . An interpreter with generics


class Pair<A, B> {

  private final A left;

  private final B right;

  public Pair(A l, B r) { left=l; right=r; }

  public A left() { return left; }

  public B right() { return right; }

}

abstract class Exp<T> {

  abstract public T eval();

  static Exp<Integer> lit(final int i) {

    return new Exp<Integer>() { public Integer eval() { return i; } };

  }

  static Exp<Integer> plus(final Exp<Integer> e1, final Exp<Integer> e2) {

    return new Exp<Integer>() { public Integer eval() {

      return e1.eval()+e2.eval();

    } };

  }

  static <A, B> Exp<Pair<A, B>> pair(final Exp<A> e1, final Exp<B> e2) {

    return new Exp<Pair<A, B>>() { public Pair<A, B> eval() {

      return new Pair<A, B>(e1.eval(), e2.eval());

    } };

  }

  static <A, B> Exp<A> left(final Exp<Pair<A, B>> e) {

    return new Exp<A>() { public A eval() { return e.eval().left(); } };

  }

  static <A, B> Exp<B> right(final Exp<Pair<A, B>> e) {

    return new Exp<B>() { public B eval() { return e.eval().right(); } };

  }

  public static void main(String[] args) {

    Exp<Integer> e = left(pair(plus(lit(3),lit(4)),lit(5)));

    assert e.eval() == 7;

  }

}

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The Function pattern converts an arbitrary method into an object. The relation between a function and the corresponding method is similar to the relation between Comparator and the compareTo method.

The generic version of the Function pattern demonstrates how to use a type variable in the throws clause of a method declaration. This may be useful when different instances of a class contain methods that may raise different checked exceptions.

Recall that the class Throwable has two major subclasses, Exception and Error, and that the first of these has another major subclass, RuntimeException. An exception is checked if it is a subclass of Exception but not a subclass of RuntimeException. The throws clause of a method may list any subclass of Throwable, but must list any checked exception that might be thrown by the method body, including any checked exceptions declared for the methods invoked within the body.

An example of the use of a type variable in a throws clause is shown in Example 9.5. The example defines a class, Function<A, B, X>, which represents a function. The class contains an abstract method, apply, that accepts an argument of type A, returns a result of type B, and may throw an exception of type X. The class also contains an applyAll method that accepts an argument of type List<A>, returns a result of type List<B>, and again may throw an exception of type X; the method invokes the apply method on each element of the argument list to produce the result list.

Example . Type parameter in a throws clause


import java.util.*;

import java.lang.reflect.*;

interface Function<A, B, X extends Throwable> {

  public B apply(A x) throws X;

}

class Functions {

  public <A, B, X extends Throwable>

  List<B> applyAll(List<A> list) throws X {

    List<B> result = new ArrayList<B>(list.size());

    for (A x : list) result.add(apply(x));

    return result;

  }

  public static void main(String[] args) {

    Function<String, Integer, Error> length =

      new Function<String, Integer, Error>() {

        public Integer apply(String s) {

          return s.length();

        }

      };

    Function<String, Class<?>, ClassNotFoundException> forName =

      new Function<String, Class<?>, ClassNotFoundException>() {

        public Class<?> apply(String s)

          throws ClassNotFoundException {

          return Class.forName(s);

        }

      };

    Function<String, Method, Exception> getRunMethod =

      new Function<String, Method, Exception>() {

        public Method apply(String s)

          throws ClassNotFoundException,NoSuchMethodException {

          return Class.forName(s).getMethod("run");

        }

      };

    List<String> strings = Arrays.asList(args);

    System.out.println(applyAll(length, strings));



    try { System.out.println(applyAll(forName, strings)); }

    catch (ClassNotFoundException e) { System.out.println(e); }



    try { System.out.println(applyAll(getRunMethod, strings)); }

    catch (ClassNotFoundException e) { System.out.println(e); }

    catch (NoSuchMethodException e) { System.out.println(e); }

    catch (RuntimeException e) { throw e; }

    catch (Exception e) { throw new AssertionError(); }

  }

}

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The Strategy pattern is used to decouple a method from an object, allowing you to supply many possible instances of the method. Our discussion of the Strategy pattern illustrates a structuring technique found in many object-oriented programs, that of parallel class hierarchies. We will illustrate the Strategy pattern by considering how tax payers may apply different tax strategies. There will be a hierarchy for tax payers, and a related hierarchy for tax strategies. For example, there is a default strategy that applies to any tax payer. One subclass of tax payer is a trust, and one subclass of the default strategy is one that applies only to trusts.

Our discussion will also illustrate a technique often used with generic types—the use of type variables with recursive bounds. We have already seen this trick at work in the definition of the Comparable interface and the Enum class; here we will apply it to clarify the connection between tax payers and their associated tax strategies. We also explain the getThis trick, which allows us to assign a more precise type to this when type variables with recursive bounds appear.

First, we'll look at a basic version of the Strategy pattern, which shows how to use generics to design parallel class hierarchies. Next, we'll look at an advanced version where objects contain their own strategies, which uses type variables with recursive bounds and explains the getThis trick.

The example in this section was developed in discussion with Heinz M. Kabutz, and also appears in his online publication, The Java Specialists' Newsletter.

Parallel Class Hierarchies A typical use of the Strategy pattern is for tax computation, as shown in Example 9.6. We have a class TaxPayer with subclasses Person and Trust. Every tax payer has an income, and, in addition, a trust may be nonprofit. For example, we may define a person with an income of $100,000.00 and two trusts with the same income, one nonprofit and one otherwise:

Example . A basic Strategy pattern with parallel class hierarchies

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

We finish with a more extended example, illustrating the generic Subject-Observer pattern. Like the Strategy pattern, the Subject-Observer pattern uses parallel class hierarchies, but this time we require two type variables with mutually recursive bounds, one to stand for the specific kind of subject and one to stand for the specific kind of observer. This is our first example of type variables with mutually recursive bounds.

The Java library implements a nongeneric version of the Subject-Observer pattern in the package java.util with the class Observable and the interface Observer (the former corresponding to the subject), signatures for which are shown in Example 9.8.

Example . Observable and Observer before generics


package java.util;

public class Observable {

  public void addObserver(Observer o) {...}

  protected void clearChanged() {...}

  public int countObservers() {...}

  public void deleteObserver(Observer o) {...}

  public boolean hasChanged() {...}

  public void notifyObservers() {...}

  public void notifyObservers(Object arg) {...}

  protected void setChanged() {...}

}



package java.util;

public interface Observer {

    public void update(Observable o, Object arg);

}

The Observable class contains methods to register observers (addObserver), to indicate that the observable has changed (setChanged), and to notify all observers of any changes (notifyObservers), among others. The notifyObservers method may accept an arbitrary argument of type Object that is to be broadcast to all the observers. The Observer interface specifies the update method that is called by notifyObservers. This method takes two parameters: the first, of type Observable, is the subject that has changed; the second, of type Object, is the broadcast argument.

The appearance of Object in a method signature often indicates an opportunity to generify. So we should expect to generify the classes by adding a type parameter, A, corresponding to the argument type. Further, we can replace

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Figure 10.1 shows the main interfaces of the Java Collections Framework, together with one other—Iterable—which is outside the Framework but is an essential adjunct to it. Its purpose is as follows:

Iterable defines the contract that a class has to fulfill for its instances to be usable with the foreach statement.

And the Framework interfaces have the following purposes:

Collection contains the core functionality required of any collection other than a map. It has no direct concrete implementations; the concrete collection classes all implement one of its subinterfaces as well.
Set is a collection, without duplicates, in which order is not significant. SortedSet automatically sorts its elements and returns them in order. NavigableSet extends this, adding methods to find the closest matches to a target element.
Queue is a collection designed to accept elements at its tail for processing, yielding them up at its head in the order in which they are to be processed. Its subinterface Deque extends this by allowing elements to be added or removed at both head and tail. Queue and Deque have subinterfaces, BlockingQueue and BlockingDeque respectively, that support concurrent access and allow threads to be blocked, indefinitely or for a maximum time, until the requested operation can be carried out.
List is a collection in which order is significant, accommodating duplicate elements.
Map is a collection which uses key-value associations to store and retrieve elements. It is extended by ConcurrentMap, which provides support for concurrent access, by SortedMap, which guarantees to return its values in ascending key order, by NavigableMap which extends SortedMap to find the closest matches to a target element, and by ConcurrentNavigableMap which extends ConcurrentMap and NavigableMap.

Chapters 12 through 16 will concentrate on each of the Collections Framework interfaces in turn. First, though, in Chapter 11, we need to cover some preliminary ideas which run through the entire Framework design.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

In this chapter, we will take time to discuss the concepts underlying the framework, before we get into the detail of the collections themselves.

An iterator is an object that implements the interface Iterator:


public Iterator<E> {

  boolean hasNext();   // return true if the iteration has more elements

 

 



  E next();            // return the next element in the iteration

  void remove();       // remove the last element returned by the iterator

}

The purpose of iterators is to provide a uniform way of accessing collection elements sequentially, so whatever kind of collection you are dealing with, and however it is implemented, you always know how to process its elements in turn. This used to require some rather clumsy code; for example, in earlier versions of Java, you would write the following to print the string representation of a collection's contents:


// coll refers to an object which implements Collection

// ----- not the preferred idiom from Java 5 on -------

for (Iterator itr = coll.iterator() ; itr.hasNext() ; ) {

  System.out.println(itr.next());

}

The strange-looking for statement was the preferred idiom before Java 5 because, by restricting the scope of itr to the body of the loop, it eliminated accidental uses of it elsewhere. This code worked because any class implementing Collection has an iterator method which returns an iterator appropriate to objects of that class. It is no longer the approved idiom because Java 5 introduced something better: the foreach statement, which you met in Part I. Using foreach, we can write the preceding code more concisely:


for (Object o : coll) {

  System.out.println(o);

}

This code will work with anything that implements the interface Iterable—that is, anything that can produce an Iterator. This is the declaration of Iterable:


public Iterable<T> {

  Iterator<T> iterator();   // return an iterator over elements of type T

}

In Java 5 the Collection interface was made to extend

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

An iterator is an object that implements the interface Iterator:


public Iterator<E> {

  boolean hasNext();   // return true if the iteration has more elements

 

 



  E next();            // return the next element in the iteration

  void remove();       // remove the last element returned by the iterator

}

The purpose of iterators is to provide a uniform way of accessing collection elements sequentially, so whatever kind of collection you are dealing with, and however it is implemented, you always know how to process its elements in turn. This used to require some rather clumsy code; for example, in earlier versions of Java, you would write the following to print the string representation of a collection's contents:


// coll refers to an object which implements Collection

// ----- not the preferred idiom from Java 5 on -------

for (Iterator itr = coll.iterator() ; itr.hasNext() ; ) {

  System.out.println(itr.next());

}

The strange-looking for statement was the preferred idiom before Java 5 because, by restricting the scope of itr to the body of the loop, it eliminated accidental uses of it elsewhere. This code worked because any class implementing Collection has an iterator method which returns an iterator appropriate to objects of that class. It is no longer the approved idiom because Java 5 introduced something better: the foreach statement, which you met in Part I. Using foreach, we can write the preceding code more concisely:


for (Object o : coll) {

  System.out.println(o);

}

This code will work with anything that implements the interface Iterable—that is, anything that can produce an Iterator. This is the declaration of Iterable:


public Iterable<T> {

  Iterator<T> iterator();   // return an iterator over elements of type T

}

In Java 5 the Collection interface was made to extend Iterable, so any set, list, or queue can be the target of foreach, as can arrays. If you write your own implementation of Iterable, that too can be used with foreach

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

We have looked briefly at the interfaces of the Collections Framework, which define the behavior that we can expect of each collection. But as we mentioned in the introduction to this chapter, there are several ways of implementing each of these interfaces. Why doesn't the Framework just use the best implementation for each interface? That would certainly make life simpler—too simple, in fact, to be anything like life really is. If an implementation is a greyhound for some operations, Murphy's Law tells us that it will be a tortoise for others. Because there is no "best" implementation of any of the interfaces, you have to make a tradeoff, judging which operations are used most frequently in your application and choosing the implementation that optimizes those operations.

The three main kinds of operations that most collection interfaces require are insertion and removal of elements by position, retrieval of elements by content, and iteration over the collection elements. The implementations provide many variations on these operations, but the main differences among them can be discussed in terms of how they carry out these three. In this section, we'll briefly survey the four main structures used as the basis of the implementations and later, as we need them, we will look at each in more detail. The four structures are:

Arrays: These are the structures familiar from the Java language—and just about every other programming language since Fortran. Because arrays are implemented directly in hardware, they have the properties of random-access memory: very fast for accessing elements by position and for iterating over them, but slower for inserting and removing elements at arbitrary positions (because that may require adjusting the position of other elements). Arrays are used in the Collections Framework as the backing structure for ArrayList, CopyOnWriteArrayList, EnumSet and EnumMap, and for many of the Queue and Deque implementations. They also form an important part of the mechanism for implementing hash tables (discussed shortly).

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

In the last section, we talked about different implementations being "good" for different operations. A good algorithm is economical in its use of two resources: time and space. Implementations of collections usually use space proportional to the size of the collection, but they can vary greatly in the time required for access and update, so that will be our primary concern. It's very hard to say precisely how quickly a program will execute, as that depends on many factors, including some that are outside the province of the programmer, such as the quality of the compiled code and the speed of the hardware. Even if we ignore these and limit ourselves to thinking only about how the execution time for an algorithm depends on its data, detailed analysis can be complex. A relatively simple example is provided in Donald Knuth's classic book Sorting and Searching (Addison-Wesley), where the worst-case execution time for a multiple list insertion sort program on Knuth's notional MIX machine is derived as


[3.5N² + 24.5N + 4M + 2]

where N is the number of elements being sorted and M is the number of lists.

As a shorthand way of describing algorithm efficiency, this isn't very convenient. Clearly we need a broader brush for general use. The one most commonly used is the O-notation (pronounced "big-oh notation"). The O-notation is a way of describing the performance of an algorithm in an abstract way, without the detail required to predict the precise performance of a particular program running on a particular machine. Our main reason for using it is that it gives us a way of describing how the execution time for an algorithm depends on the size of its data set, provided the data set is large enough. For example, in the previous expression the first two terms are comparable for low values of N; in fact, for N < 8, the second term is larger. But as N grows, the first term increasingly dominates the expression and, by the time it reaches 100, the first term is 15 times as large as the second one. Using a very broad brush, we say that the worst case for this algorithm takes time

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

In reading about software design, you are likely to come across the term contract, often without any accompanying explanation. In fact, software engineering gives this term a meaning that is very close to what people usually understand a contract to be. In everyday usage, a contract defines what two parties can expect of each other—their obligations to each other in some transaction. If a contract specifies the service that a supplier is offering to a client, the supplier's obligations are obvious. But the client, too, may have obligations—besides the obligation to pay—and failing to meet them will automatically release the supplier from her obligations as well. For example, airlines' conditions of carriage—for the class of tickets that we can afford, anyway—release them from the obligation to carry passengers who have failed to turn up on time. This allows the airlines to plan their service on the assumption that all the passengers they are carrying are punctual; they do not have to incur extra work to accommodate clients who have not fulfilled their side of the contract.

Contracts work just the same way in software. If the contract for a method states preconditions on its arguments (i.e., the obligations that a client must fulfill), the method is required to return its contracted results only when those preconditions are fulfilled. For example, binary search (see Section 17.1.4) is a fast algorithm to find a key within an ordered list, and it fails if you apply it to an unordered list. So the contract for Collections.binarySearch can say, "if the list is unsorted, the results are undefined", and the implementer of binary search is free to write code which, given an unordered list, returns random results, throws an exception, or even enters an infinite loop. In practice, this situation is relatively rare in the contracts of the core API because, instead of restricting input validity, they mostly allow for error states in the preconditions and specify the exceptions that the method must throw if it gets bad input. This design may be appropriate for general libraries such as the Collections Framework, which will be very heavily used in widely varying situations and by programmers of widely varying ability. You should probably avoid it for less-general libraries, because it restricts the flexibility of the supplier unnecessarily. In principle, all that a client should need to know is how to keep to its side of the contract; if it fails to do that, all bets are off and there should be no need to say exactly what the supplier will do.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

When a Java program is running, it is executing one or more execution streams, or threads. A thread is like a lightweight process, so a program simultaneously executing several threads can be thought of as a computer running several programs simultaneously, but with one important difference: different threads can simultaneously access the same memory locations and other system resources. On machines with multiple processors, truly concurrent thread execution can be achieved by assigning a processor to each thread. If, however, there are more threads than processors—the usual case—multithreading is implemented by time slicing, in which a processor executes some instructions from each thread in turn before switching to the next one.

There are two good reasons for using multithread programming. An obvious one, in the case of multicore and multiprocessor machines, is to share the work and get it done quicker. (This reason is becoming ever more compelling as hardware designers turn increasingly to parallelism as the way of improving overall performance.) A second one is that two operations may take varying, perhaps unknown, amounts of time, and you do not want the response to one operation to await the completion of the other. This is particularly true for the a graphical user interface (GUI), where the response to the user clicking a button should be immediate, and should not be delayed if, say, the program happens to be running a compute-intensive part of the application at the time.

Although concurrency may be essential to achieving good performance, it comes at a price. Different threads simultaneously accessing the same memory location can produce unexpected results, unless you take care to constrain their access. Consider Example 11.2, in which the class ArrayStack uses an array and an index to implement the interface Stack, which models a stack of int (despite the similarity of names, this example is different from Example 5.1). For ArrayStack to work correctly, the variable index should always point at the top element of the stack, no matter how many elements are added to or removed from the stack. This is an

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The interface Collection (see Figure 12.1) defines the core functionality that we expect of any collection other than a map. It provides methods in four groups.

Figure 12-1: Collection

Adding Elements


boolean add(E e)                           // add the element e

boolean addAll(Collection<? extends E> c)  // add the contents of c

The boolean result returned by these methods indicates whether the collection was changed by the call. It can be false for collections, such as sets, which will be unchanged if they are asked to add an element that is already present. But the method contracts specify that the elements being added must be present after execution so, if the collection refuses an element for any other reason (for example, some collections don't permit null elements), these methods must throw an exception.

The signatures of these methods show that, as you might expect, you can add elements or element collections only of the parametric type.

Removing Elements


boolean remove(Object o)             // remove the element o

void clear()                         // remove all elements

boolean removeAll(Collection<?> c)   // remove the elements in c

boolean retainAll(Collection<?> c)   // remove the elements *not* in c

If the element o is null, remove removes a null from the collection if one is present. Otherwise, if an element e is present for which o.equals(e), it removes it. If not, it leaves the collection unchanged. Where a method in this group returns a boolean, the value is true if the collection changed as a result of applying the operation.

In contrast to the methods for adding elements, these methods—and those of the next group—will accept elements or element collections of any type. We will explain this in a moment, when we look at examples of the use of these methods.

Querying the Contents of a Collection


boolean contains(Object o)           // true if o is present

boolean containsAll(Collection<?> c) // true if all elements of c

                                     // are present in the collection

boolean isEmpty()                    // true if no elements are present

int size()                           // return the element count (or

                                     // Integer.MAX_VALUE if that is less)

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

To illustrate the use of the collection classes, let's construct a tiny example. Your authors are forever trying to get organized; let's imagine that our latest effort involves writing our own to-do manager. We begin by defining a class to represent tasks, and subclasses to represent different kinds of tasks, such as writing some code or making a phone call.

Here is the definition of tasks that we shall use:


public abstract class Task implements Comparable<Task> {

  protected Task() {}

  public boolean equals(Object o) {

    if (o instanceof Task) {

      return toString().equals(o.toString());

    } else return false;

  }

  public int compareTo(Task t) {

    return toString().compareTo(t.toString());

  }

  public int hashCode() {

    return toString().hashCode();

  }

  public abstract String toString();

}

We only require four operations on tasks: equals, compareTo, hashCode and toString. Equality will be used to test whether a collection contains a given task, comparison will be used to by ordered collections (such as OrderedSet and OrderedMap) and the hash code will be used by collections based on hash tables (such as HashSet and HashMap), and the string representation of a task will be used whenever we show the contents of a collection. The first three methods are defined in terms of the toString method, which is declared abstract, so it must be defined in each subclass of Task. We consider two tasks equal if they are represented by the same string, and the natural ordering on tasks is the same as the ordering on their strings. This guarantees that the natural ordering on tasks is consistent with equality, as discussed in Section 3.1—that is, compareTo returns 0 exactly when equals returns true.

We define subclasses for two kinds of tasks, writing some code and making a phone call:


public final class CodingTask extends Task {

  private final String spec;

  public CodingTask(String spec) {

    this.spec = spec;

  }

  public String getSpec() { return spec; }

  public String toString() { return "code " + spec; }

}





public final class PhoneTask extends Task {

  private final String name;

  private final String number;

  public PhoneTask(String name, String number) {

    this.name = name;

    this.number = number;

  }

  public String getName() { return name; }

  public String getNumber() { return number; }

  public String toString() { return "phone " + name; }

}

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

There are no concrete implementations of Collection. The class AbstractCollection, which partially implements it, is one of a series of skeletal implementations—including AbstractSet, AbstractList, and so on—which provide functionality common to the different concrete implementations of each interface. These skeletal implementations are available to help the designer of new implementations of the Framework interfaces. For example, Collection could serve as the interface for bags (unordered lists), and a programmer implementing bags could extend AbstractCollection and find most of the implementation work already done.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

We will go on to look at these three main kinds of collection in the next three chapters, but we should first explain two common forms of constructor which are shared by most collection implementations. Taking HashSet as an example, these are:


public HashSet()

public HashSet(Collection<? extends E> c)

The first of these creates an empty set, and the second a set that will contain the elements of any collection of the parametric type—or one of its subtypes, of course. Using this constructor has the same effect as creating an empty set with the default constructor, and then adding the contents of a collection using addAll. This is sometimes called a "copy constructor", but that term should really be reserved for constructors which make a copy of an object of the same class, whereas constructors of the second form can take any object which implements the interface Collection<? extends E>. Joshua Bloch has suggested the term "conversion constructor".

Not all collection classes have constructors of both forms—ArrayBlockingQueue, for example, cannot be created without fixing its capacity, and SynchronousQueue cannot hold any elements at all, so no constructor of the second form is appropriate. In addition, many collection classes have other constructors besides these two, but which ones they have depends not on the interface they implement but on the underlying implementation; these additional constructors are used to configure the implementation.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

A set is a collection of items that cannot contain duplicates; adding an item if it is already present in the set has no effect. The Set interface has the same methods as those of Collection, but it is defined separately in order to allow the contract of add (and addAll, which is defined in terms of add) to be changed in this way. Returning to the task manager example in the previous chapter, suppose that on Monday you have free time to carry out your telephone tasks. You can make the appropriate collection by adding all your telephone tasks to your Monday tasks. Let mondayTasks and phoneTasks be as declared in Example 12.1. Using a set (again choosing a conveniently common implementation of Set), you can write:


Set<Task> phoneAndMondayTasks = new TreeSet<Task>(mondayTasks);

phoneAndMondayTasks.addAll(phoneTasks);

assert phoneAndMondayTasks.toString().equals(

  "[code logic, phone Mike, phone Paul]");

This works because of the way that duplicate elements are handled. The task mikePhone, which is in both mondayTasks and phoneTasks, appears as intended, only once, in phoneAndMondayTasks—you definitely don't want to have to do all such tasks twice over!

When we used the methods of Collection in the examples of Chapter 12, we emphasized that they would work with any implementation of Collection. What if we had decided that we would use one of the Set implementations from the Collections Framework? We would have had to choose between the various concrete implementations that the Framework provides, which differ both in how fast they perform the basic operations of add, contains, and iteration, and in the order in which their iterators return their elements. In this section and the next we will look at these differences, then at the end of the Chapter we will summarize the comparative performance of the different implementations.

There are six concrete implementations of Set in the Collections Framework. Figure 13.1 shows their relationship to Set and its subinterfaces SortedSet

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

When we used the methods of Collection in the examples of Chapter 12, we emphasized that they would work with any implementation of Collection. What if we had decided that we would use one of the Set implementations from the Collections Framework? We would have had to choose between the various concrete implementations that the Framework provides, which differ both in how fast they perform the basic operations of add, contains, and iteration, and in the order in which their iterators return their elements. In this section and the next we will look at these differences, then at the end of the Chapter we will summarize the comparative performance of the different implementations.

There are six concrete implementations of Set in the Collections Framework. Figure 13.1 shows their relationship to Set and its subinterfaces SortedSet and NavigableSet. In this section, we will look at HashSet, LinkedHashSet, CopyOnWriteArraySet and EnumSet.

Figure 13-1: Implementations of the Set interface

We will discuss SortedSet and NavigableSet, together with their implementations, TreeSet and ConcurrentSkipListSet, in Section 13.2.

This class is the most commonly used implementation of Set. As the name implies, it is implemented by a hash table, an array in which elements are stored at a position derived from their contents. Since hash tables store and retrieve elements by their content, they are well suited to implementing the operations of Set (the Collections Framework also uses them for various implementations of Map). For example, to implement contains(Object o) you would look for the element o and return true if it were found.

An element's position in a hash table is calculated by a hash function of its contents. Hash functions are designed to give, as far as possible, an even spread of results (hash codes) over the element values that might be stored. For example, here is code like that used in the

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Set has one subinterface, SortedSet (Figure 13.4), which adds to the Set contract a guarantee that its iterator will traverse the set in ascending element order. SortedSet was itself extended in Java 6 by the interface NavigableSet (see Figure 13.5), which adds methods to find the closest matches to a target element. The only implementation of SortedSet before Java 6 was TreeSet, which has been retrofitted with the methods required to implement the new interface. Since there is no platform implementation of SortedSet in Java 6 that does not also implement NavigableSet, it makes sense to discuss them in the same section. For new client code developed for the Java 6 platform, there is no need to use the SortedSet interface at all, but for the benefit of readers still constrained to use Java 5 we shall present the methods of the two interfaces separately in this section.

Figure 13-4: SortedSet

Figure 13-5: NavigableSet

In Chapter 3 we saw that element ordering can either be defined by the element class itself, if that implements Comparable, or it can be imposed by an external Comparator, supplied by a constructor such as this one, for TreeSet:


TreeSet(Comparator<? super E> comparator)

Task does implement Comparable (its natural ordering is the natural ordering of its string representation), so we don't need to supply a separate comparator. Now merging two ordered lists, which was quite tricky using parallel iterators, is trivial if we get a SortedSet to do the work. Using the task collections of Example 12.1, it requires two lines of code:


Set<Task> naturallyOrderedTasks = new TreeSet<Task>(mondayTasks);

naturallyOrderedTasks.addAll(tuesdayTasks);

assert naturallyOrderedTasks.toString().equals (

  "[code db, code gui, code logic, phone Mike, phone Paul]");

This simplicity comes at a price, though; merging two sorted lists of size

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Table 13.1 shows the comparative performance of the different Set implementations. When you are choosing an implementation, of course, efficiency is only one of the factors you should take into account. Some of these implementations are specialized for specific situations; for example, EnumSet should always (and only) be used to represent sets of enum. Similarly, CopyOnWriteArraySet should only be used where set size will remain relatively small, read operations greatly outnumber writes, thread safety is required, and read-only iterators are acceptable.

Table 13.1: Comparative performance of different Set implementations
	`add`	`contains`	`next`	notes
`HashSet`	O(1)	O(1)	O(h/n)	h is the table capacity
`LinkedHashSet`	O(1)	O(1)	O(1)
`CopyOnWriteArraySet`	O(n)	O(n)	O(1)
`EnumSet`	O(1)	O(1)	O(1)
`TreeSet`

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

A queue is a collection designed to hold elements for processing, yielding them up in the order in which they are to be processed. The corresponding Collections Framework interface Queue (see Figure 14.1) has a number of different implementations embodying different rules about what this order should be. Many of the implementations use the rule that tasks are to be processed in the order in which they were submitted (First In First Out, or FIFO), but other rules are possible—for example, the Collections Framework includes queue classes whose processing order is based on task priority. The Queue interface was introduced in Java 5, motivated in part by the need for queues in the concurrency utilities included in that release. A glance at the hierarchy of implementations shown in Figure 14.2 shows that, in fact, nearly all of the Queue implementations in the Collections Framework are in the package java.util.concurrent.

Figure 14-1: Queue

Figure 14-2: Implementations of Queue in the Collections Framework

One classic requirement for queues in concurrent systems comes when a number of tasks have to be executed by a number of threads working in parallel. An everyday example of this situation is that of a single queue of airline passengers being handled by a line of check-in operators. Each operator works on processing a single passenger (or a group of passengers) while the remaining passengers wait in the queue. As they arrive, passengers join the tail of the queue, wait until they reach its head, and are then assigned to the next operator who becomes free. A good deal of fine detail is involved in implementing a queue such as this; operators have to be prevented from simultaneously attempting to process the same passenger, empty queues have to be handled correctly, and in computer systems there has to be a way of defining queues with a maximum size, or bound. (This last requirement may not often be imposed in airline terminals, but it can be very useful in systems in which there is a maximum waiting time for a task to be executed.) The

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Let's look at examples of the use of these methods. Queues should provide a good way of implementing a task manager, since their main purpose is to yield up elements, such as tasks, for processing. For the moment we shall use ArrayDeque as the fastest and most straightforward implementation of Queue (and also of Deque, of course). But, as before, we shall confine ourselves to the methods of the interface—though you should note that, in choosing a queue implementation, you are also choosing an ordering. With ArrayDeque, you get FIFO ordering—well, our attempts to get organized using fancy scheduling methods never seem to work very well; perhaps it's time to try something simpler.

ArrayDeque is unbounded, so we could use either add or offer to set up the queue with new tasks.


Queue<Task> taskQueue = new ArrayDeque<Task>();

taskQueue.offer(mikePhone);

taskQueue.offer(paulPhone);

Any time we feel ready to do a task, we can take the one that has reached the head of the queue:


Task nextTask = taskQueue.poll();

if (nextTask != null) {

  // process nextTask

}

The choice between using poll and remove depends on whether we want to regard queue emptiness as an exceptional condition. Realistically—given the nature of the application—that might be a sensible assumption, so this is an alternative:


try {

  Task nextTask = taskQueue.remove();

  // process nextTask

} catch (NoSuchElementException e) {

  // but we *never* run out of tasks!

}

This scheme needs some refinement to allow for the nature of different kinds of tasks. Phone tasks fit into relatively short time slots, whereas we don't like to start coding unless there is reasonably substantial time to get into the task. So if time is limited—say, until the next meeting—we might like to check that the next task is of the right kind before we take it off the queue:


Task nextTask = taskQueue.peek();

if (nextTask instanceof PhoneTask) {

  taskQueue.remove();

  // process nextTask

}

These inspection and removal methods are a major benefit of the

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

PriorityQueue is one of the two nonlegacy Queue implementations not designed primarily for concurrent use (the other one is ArrayDeque). It is not thread-safe, nor does it provide blocking behavior. It gives up its elements for processing according to an ordering like that used by NavigableSet—either the natural order of its elements if they implement Comparable, or the ordering imposed by a Comparator supplied when the PriorityQueue is constructed. So PriorityQueue would be an alternative design choice (obviously, given its name) for the priority-based to-do manager that we outlined in Section 13.2 using NavigableSet. Your application will dictate which alternative to choose: if it needs to examine and manipulate the set of waiting tasks, use NavigableSet. If its main requirement is efficient access to the next task to be performed, use PriorityQueue.

Choosing PriorityQueue allows us to reconsider the ordering: since it accommodates duplicates, it does not share the requirement of NavigableSet for an ordering consistent with equals. To emphasize the point, we will define a new ordering for our to-do manager that depends only on priorities. Contrary to what you might expect, PriorityQueue gives no guarantee of how it presents multiple elements with the same value. So if, in our example, several tasks are tied for the highest priority in the queue, it will choose one of them arbitrarily as the head element.

The constructors for PriorityQueue are:


PriorityQueue()       // natural ordering, default initial capacity (11)

PriorityQueue(Collection<? extends E> c)

                      // natural ordering of elements taken from c, unless

                      // c is a PriorityQueue or SortedSet, in which case

                      // copy c's ordering

PriorityQueue(int initialCapacity)

                      // natural ordering, specified initial capacity

PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

                      // Comparator ordering, specified initial capacity

PriorityQueue(PriorityQueue<? extends E> c)

                      // ordering and elements copied from c

PriorityQueue(SortedSet<? extends E> c)

                      // ordering and elements copied from c

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Java 5 added a number of classes to the Collections Framework for use in concurrent applications. Most of these are implementations of the Queue subinterface BlockingQueue (see Figure 14.5), designed primarily to be used in producer-consumer queues.

Figure 14-5: BlockingQueue

One common example of the use of producer-consumer queues is in systems that perform print spooling; client processes add print jobs to the spool queue, to be processed by one or more print service processes, each of which repeatedly "consumes" the task at the head of the queue.

The key facilities that BlockingQueue provides to such systems are, as its name implies, enqueuing and dequeueing methods that do not return until they have executed successfully. So, for example, a print server does not need to constantly poll the queue to discover whether any print jobs are waiting; it need only call the poll method, supplying a timeout, and the system will suspend it until either a queue element becomes available or the timeout expires. BlockingQueue defines seven new methods, in three groups:

Adding an Element


boolean offer(E e, long timeout, TimeUnit unit)

                // insert e, waiting up to the timeout

void put(E e)   // add e, waiting as long as necessary

The nonblocking overload of offer defined in Queue will return false if it cannot immediately insert the element. This new overload waits for a time specified using java.util.concurrent.TimeUnit, an Enum which allows timeouts to be defined in units such as milliseconds or seconds.

Taking these methods together with those inherited from Queue, there are four ways in which the methods for adding elements to a BlockingQueue can behave: offer returns false if it does not succeed immediately, blocking offer returns false if it does not succeed within its timeout, add throws an exception if it does not succeed immediately, and put blocks until it succeeds.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

A deque (pronounced "deck") is a double-ended queue. Unlike a queue, in which elements can be inserted only at the tail and inspected or removed only at the head, a deque can accept elements for insertion and present them for inspection or removal at either end. Also unlike Queue, Deque's contract specifies the ordering it will use in presenting its elements: it is a linear structure in which elements added at the tail are yielded up in the same order at the head. Used as a queue, then, a Deque is always a FIFO structure; the contract does not allow for, say, priority deques. If elements are removed from the same end (either head or tail) at which they were added, a Deque acts as a stack or LIFO (Last In First Out) structure.

Deque and its subinterface BlockingDeque were introduced in Java 6. The fast Deque implementation ArrayDeque uses a circular array (see Section 14.3.2), and is now the implementation of choice for stacks and queues. Concurrent deques have a special role to play in parallelization, discussed in Section 14.4.2.

The Deque interface (see Figure 14.7) extends Queue with methods symmetric with respect to head and tail. For clarity of naming, the Queue methods that implicitly refer to one end of the queue acquire a synonym that makes their behavior explicit for Deque. For example, the methods peek and offer, inherited from Queue, are equivalent to peekFirst and offerLast. (First and last refer to the head and tail of the deque; the JavaDoc for Deque also uses "front" and "end".)

Figure 14-7: Deque

Collection-like Methods


void addFirst(E e)      // insert e at the head if there is enough space

void addLast(E e)       // insert e at the tail if there is enough space

void push(E e)          // insert e at the head if there is enough space

boolean removeFirstOccurrence(Object o);

                        // remove the first occurrence of o

boolean removeLastOccurrence(Object o);

                        // remove the last occurrence of o

Iterator<E> descendingIterator()

                        // get an iterator, returning deque elements in

                        // reverse order

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Table 14.1 shows the sequential performance, disregarding locking and CAS overheads, for some sample operations of the Deque and Queue implementations we have discussed. These results should be interesting to you in terms of understanding the behavior of your chosen implementation but, as we mentioned at the start of the chapter, they are unlikely to be the deciding factor. Your choice is more likely to be dictated by the functional and concurrency requirements of your application.

Table 14-1: Comparative performance of different Queue and Deque implementations
	`offer`	`peek`	`poll`	`size`
`PriorityQueue`	O(log n)	O(1)	O(log n)	O(1)
`ConcurrentLinkedQueue`	O(1)	O(1)	O(1)	O(n)
`ArrayBlockingQueue`	O(1)	O(1)	O(1)	O(1)
`LinkedBlockingQueue`	O(1)	O(1)	O(1)	O(1)

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Lists are probably the most widely used Java collections in practice. A list is a collection which—unlike a set—can contain duplicates, and which—unlike a queue—gives the user full visibility and control over the ordering of its elements. The corresponding Collections Framework interface is List (see Figure 15.1).

Figure 15-1: List

In addition to the operations inherited from Collection, the List interface includes operations for the following:

Positional Access Methods that access elements based on their numerical position in the list:


void add(int index, E e)           // add element e at given index

boolean addAll(int index, Collection<? extends E> c)

                                   // add contents of c at given index

E get(int index)                   // return element with given index

E remove(int index)                // remove element with given index

E set(int index, E e)              // replace element with given index by e

Search Methods that search for a specified object in the list and return its numerical position. These methods return −1 if the object is not present:


int indexOf(Object o)              // return index of first occurrence of o

int lastIndexOf(Object o)          // return index of last occurrence of o

Range-View A method that gets a view of a range of the list:


List<E> subList(int fromIndex, int toIndex)

                                   // return a view of a portion of the list

The method subList works in a similar way to the subSet operations on SortedSet (see Section 13.2), but uses the position of elements in the list rather than their values: the returned list contains the list elements starting at fromIndex, up to but not including toIndex. The returned list has no separate existence—it is just a view of part of the list from which it was obtained, so changes in it are reflected in the original list. There is an important difference from subSet, though; changes you make to the sublist write through to the backing list, but the reverse is not always true. If elements have been inserted into or removed from the backing list by directly calling one of its "structure changing" methods (Section 12.1), any subsequent attempts to use the sublist will result in a

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Let's look at examples of the use of some of these methods in the to-do manager. In the last chapter we considered representing the organization of a single day's tasks in a queue-based class with shutdown capabilities. One useful way of enlarging the scope of the application is to have a number of objects of this type, each one representing the tasks that are scheduled for a day in the future. We will store references to these objects in a List, which (to keep things simple and to avoid grappling with the distasteful details of java.util.Calendar) will be indexed on the number of days in the future that it represents. So the queue of tasks scheduled for today will be stored at element 0 of the list, the queue scheduled for tomorrow at element 1, and so on. Example 15.1 shows the scheduler.

Example . A list-based task scheduler


public class TaskScheduler {

  private List<StoppableTaskQueue> schedule;

  private final int FORWARD_PLANNING_DAYS = 365;



  public TaskScheduler() {

    List<StoppableTaskQueue> temp = new ArrayList<StoppableTaskQueue>();

    for (int i = 0 ; i < FORWARD_PLANNING_DAYS ; i++) {

      temp.add(new StoppableTaskQueue());

    }

    schedule = new CopyOnWriteArrayList<StoppableTaskQueue>(temp);    //1

  }



  public PriorityTask getTask() {

    for (StoppableTaskQueue daysTaskQueue : schedule) {

      PriorityTask topTask = daysTaskQueue.getTask();

      if (topTask != null) return topTask;

    }

    return null;    // no outstanding tasks - at all!?

  }



  // at midnight, remove and shut down the queue for day 0, assign its tasks

  // to the new day 0, and create a new day's queue at the planning horizon

  public void rollOver() throws InterruptedException{

    StoppableTaskQueue oldDay = schedule.remove(0);

    Collection<PriorityTask> remainingTasks = oldDay.shutDown();

    StoppableTaskQueue firstDay = schedule.get(0);

    for (PriorityTask t : remainingTasks) {

      firstDay.addTask(t);

    }

    StoppableTaskQueue lastDay = new StoppableTaskQueue();

    schedule.add(lastDay);

  }



  public void addTask(PriorityTask task, int day) {

    if (day < 0 || day >= FORWARD_PLANNING_DAYS)

      throw new IllegalArgumentException("day out of range");

    StoppableTaskQueue daysTaskQueue = schedule.get(day);

    if (daysTaskQueue.addTask(task)) return;                        //2

    // StoppableTaskQueue.addTask returns false only when called on

    // a queue that has been shut down. In that case, it will also

    // have been removed by now, so it's safe to try again.

    if (! schedule.get(0).addTask(task)) {

      throw new IllegalStateException("failed to add task " + task);

    }

  }

}

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

There are three concrete implementations ofList in the Collections Framework (see Figure 15.3), differing in how fast they perform the various operations defined by the interface and how they behave in the face of concurrent modification; unlike Set and Queue, however, List has no subinterfaces to specify differences in functional behavior. In this and the following section we look at each implementation in turn and provide a performance comparison.

Figure 15-3: Implementations of the List interface

Arrays are provided as part of the Java language and have a very convenient syntax, but their key disadvantage—that, once created, they cannot be resized—makes them increasingly less popular than List implementations, which (if resizable at all) are indefinitely extensible. The most commonly used implementation of List is, in fact, ArrayList—that is, a List backed by an array.

The standard implementation of ArrayList stores the List elements in contiguous array locations, with the first element always stored at index 0 in the array. It requires an array at least large enough (with sufficient capacity) to contain the elements, together with a way of keeping track of the number of "occupied" locations (the size of the List). If an ArrayList has grown to the point where its size is equal to its capacity, attempting to add another element will require it to replace the backing array with a larger one capable of holding the old contents and the new element, and with a margin for further expansion (the standard implementation actually uses a new array that is double the length of the old one). As we explained in Section 11.3, this leads to an amortized cost of O(1).

The performance of ArrayList reflects array performance for "random-access" operations: set and get take constant time. The downside of an array implementation is in inserting or removing elements at arbitrary positions, because that may require adjusting the position of other elements. (We have already met this problem with the

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Table 15.1 gives the comparative performance for some sample operations on List classes. Even though the choice here is much narrower than with lists or even sets, the same process of elimination can be used. As with queues, the first question to ask is whether your application requires thread safety. If so, you should use CopyOnWriteArrayList, if you can—that is, if writes to the list will be relatively infrequent. If not, you will have to use a synchronized wrapper (see Section 17.3.1) around ArrayList or LinkedList.

Table 15.1: Comparative performance of different List implementations
	`get`	`add`	`contains`	`next`	`remove(0)`	`iterator.remove`
`ArrayList`	O(1)	O(1)	O(n)	O(1)	O(n)	O(n)
`LinkedList`	O(n)	O(1)	O(n)	O(1)	O(1)	O(1)
`CopyOnWrite-ArrayList`	O(1)

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The Map interface is the last of the major Collections Framework interfaces, and the only one that does not inherit from Collection. It defines the operations that are supported by a set of key-to-value associations in which the keys are unique. These operations are shown in Figure 16.1 and fall into the following four groups, broadly parallel to the four operation groups of Collection—adding elements, removing elements, querying collection contents, and providing different views of the contents of a collection.

Figure 16-1: Map

Adding Associations


V put(K key, V value)         // add or replace a key-value association

                              // return the old value (may be null) if the

                              // key was present; otherwise returns null

void putAll(Map<? extends K,? extends V> m)

                              // add each of the key-value associations in

                              // the supplied map into the receiver

The operations in this group are optional; calling them on an unmodifiable map will result in an UnsupportedOperationException.

Removing Associations


void clear()                  // remove all associations from this map

V remove(Object key)          // remove the association, if any, with the

                              // given key; returns the value with which it

                              // was associated, or null

The signature of Map.remove is like that of the Collection.remove (see Section 12.1) in that it takes a parameter of type Object rather than the generic type. We discussed alternatives to this design in Section 2.6.

Like the addition operations of the previous group, these removal operations are optional.

Querying the Contents of a Map


V get(Object k)                 // return the value corresponding to k, or

                                // null if k is not present as a key

boolean containsKey(Object k)   // return true if k is present as a key

boolean containsValue(Object v) // return true if v is present as a value

int size()                      // return the number of associations

boolean isEmpty()               // return true if there are no associations

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

One problem with basing the to-do manager on priority queues, as we have done in the last two chapters, is that priority queues are unable to preserve the order in which elements are added to them (unless that can be incorporated in the priority ordering, for example as a timestamp or sequence number). To avoid this, we could use as an alternative model a series of FIFO queues, each one assigned to a single priority. A Map would be suitable for holding the association between priorities and task queues; EnumMap in particular is a highly efficient Map implementation specialized for use with keys which are members of an enum.

This model will rely on a Queue implementation that maintains FIFO ordering. To focus on the use of the Map methods, let's assume a single-threaded client and use a series of ArrayDeques as the implementation:


Map<Priority,ArrayDeque<Task>> taskMap =

  new EnumMap<Priority,ArrayDeque<Task>>(Priority.class);

for (Priority p : Priority.values()) {

  taskMap.put(p, new ArrayDeque<Task>());

}

// populate the lists, for example:

taskMap.get(Priority.MEDIUM).add(mikePhone);

taskMap.get(Priority.HIGH).add(databaseCode);

Now, to get to one of the task queues—say, the one with the highest-priority tasks—we can write:


Queue<Task> highPriorityTaskList = taskMap.get(Priority.HIGH);

Polling this queue will now give us the high priority to-dos, in the order in which they were entered into the system.

To see the use of some of the other methods of Map, let's extend the example a little to allow for the possibility that some of these tasks might actually earn us some money by being billable. One way of representing this would be by defining a class Client:


class Client {...}

Client acme = new Client("Acme Corp.",...);

and creating a mapping from tasks to clients:


Map<Task,Client> billingMap = new HashMap<Task,Client>();

billingMap.put(interfaceCode, acme);

We need to ensure that the system can still handle nonbillable tasks. We have a choice here: we can either simply not add the name of a nonbillable task into the

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The implementations, eight in all, that the Collections Framework provides for Map are shown in Figure 16.2. We shall discuss HashMap, LinkedHashMap, WeakHashMap, IdentityHashMap, and EnumMap here; the interfaces NavigableMap, ConcurrentMap, and ConcurrentNavigableMap are discussed, along with their implementations, in the sections following this one.

Figure 16-2: The structure of Map implementations in the Collections Framework

For constructors, the general rule for Map implementations is like that for Collection implementations (see Section 12.3). Every implementation excluding EnumMap has at least two constructors; taking HashMap as an example, they are:


public HashMap()

public HashMap(Map<? extends K,? extends V> m)

The first of these creates an empty map, and the second a map that will contain the key-value mappings contained in the supplied map m. The keys and values of map m must have types that are the same as (or are subtypes of) the keys and values, respectively, of the map being created. Using this second constructor has the same effect as creating an empty map with the default constructor, and then adding the contents of map m using putAll. In addition to these two, the standard implementations have other constructors for configuration purposes.

In discussing HashSet in Section 13.1.1, we mentioned that it delegates all its operations to a private instance of HashMap. Figure 16.3(a) is similar to Figure 13.2, but without the simplification that removed the value elements from the map (all elements in a HashSet are stored as keys with the same constant value). The discussion in Section 13.1 of hash tables and their performance applies equally to HashMap. In particular, HashMap provides constant-time performance for put and get. Although in principle constant-time performance is only attainable with no collisions, it can be closely approached by the use of rehashing to control the load and thereby to minimize the number of collisions.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Like SortedSet, the subinterface SortedMap (see Figure 16.5) adds to its contract a guarantee that its iterators will traverse the map in ascending key order. Its definition is similar to that of SortedSet, with methods such as firstKey and headMap corresponding to the SortedSet methods first and headSet. Also like SortedSet, the SortedMap interface has been extended in Java 6 by the subinterface NavigableMap (see Figure 16.6). This section is structured like Section 13.2 for the same reasons: SortedMap has been made obsolete by NavigableMap, but it may be helpful for developers prevented for the moment from using Java 6 to have the two interfaces treated separately.

Figure 16-5: SortedMap

Figure 16-6: NavigableMap

A SortedMap imposes an ordering on its keys, either that of their natural ordering or of a Comparator; but in either case the compare method must be consistent with equals, as the SortedMap will use compare to determine when a key is already in the map.

The extra methods defined by the SortedMap interface fall into three groups:

Getting the First and Last Elements


K firstKey()

K lastKey()

If the set is empty, these operations throw a NoSuchElementException.

Retrieving the Comparator


Comparator<? super K> comparator()

This method returns the map's key comparator if it has been given one, instead of relying on the natural ordering of the keys. Otherwise, it returns null.

Finding Subsequences


SortedMap<K,V> subMap(K fromKey, K toKey)

SortedMap<K,V> headMap(K toKey)

SortedMap<K,V> tailMap(K fromKey)

These operations work like the corresponding operations in SortedSet: the key arguments do not themselves have to be present in the map, and the sets returned include the fromKey

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Maps are often used in high-performance server applications—for example, as cache implementations—so a high-throughput thread-safe map implementation is an essential part of the Java platform. This requirement cannot be met by synchronized maps such as those provided by Collections.synchronizedMap, because with full synchronization each operation needs to obtain an exclusive lock on the entire map, effectively serializing access to it. Locking only a part of the collection at a time—lock striping—can achieve very large gains in throughput, as we shall see shortly with ConcurrentHashMap. But because there is no single lock for a client to hold to gain exclusive access, client-side locking no longer works, and clients need assistance from the collection itself to carry out atomic actions.

That is the purpose of the interface ConcurrentMap. It provides declarations for methods that perform compound operations atomically. There are four of these methods:


V putIfAbsent(K key, V value)

        // associate key with value only if key is not currently present.

        // return the old value (may be null) if the key was present,

        // otherwise return null

boolean remove(Object key, Object value)

        // remove key only if it is currently mapped to value.  Returns

        // true if the value was removed, false otherwise

V replace(K key, V value)

        // replace entry for key only if it is currently present.  Return

        // the old value (may be null) if the key was present, otherwise

        // return null

boolean replace(K key, V oldValue, V newValue)

        // replace entry for key only if it is currently mapped to oldValue.

        // return true if the value was replaced, false otherwise

ConcurrentHashMap provides an implementation of ConcurrentMap and offers a highly effective solution to the problem of reconciling throughput with thread safety. It is optimized for reading, so retrievals do not block even while the table is being updated (to allow for this, the contract states that the results of retrievals will reflect the latest update operations completed before the start of the retrieval). Updates also can often proceed without blocking, because a

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

ConcurrentNavigableMap (see Figure 16.7) inherits from both ConcurrentMap and NavigableMap, and contains just the methods of these two interfaces with a few changes to make the return types more precise. The range-view methods inherited from SortedMap and NavigableMap now return views of type ConcurrentNavigableMap. The compatibility concerns that prevented NavigableMap from overriding the methods of SortedMap don't apply here to overriding the range-view methods of NavigableMap or SortedMap; because neither of these has any implementations that have been retrofitted to the new interface, the danger of breaking implementation subclasses does not arise. For the same reason, it is now possible to override keySet to return NavigableSet.

Figure 16-7: ConcurrentNavigableMap

The relationship between ConcurrentSkipListMap and ConcurrentSkipListSet is like that between TreeMap and TreeSet; a ConcurrentSkipListSet is implemented by a ConcurrentSkipListMap in which every key is associated with the same standard value, so the mechanism and performance of the skip list implementation given in Section 13.2.2 applies equally here: the basic operations (get, put, and remove) perform in O(log n) time); iterators over the collection views execute next in constant time. These iterators are fail-fast.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Table 16.1 shows the relative performance of the different platform implementations of Map (the column headed "next" shows the cost of the next operation of iterators over the key set). As with the implementations of queue, your choice of map class is likely to be influenced more by the functional requirements of your application and the concurrency properties that you need.

Table 16.1: Comparative performance of different Map implementations
	`get`	`containsKey`	`next`	Notes
`HashMap`	O(1)	O(1)	O(h/n)	h is the table capacity
`LinkedHashMap`	O(1)	O(1)	O(1)
`IdentityHashMap`	O(1)	O(1)	O(h/n)	h is the table capacity
`EnumMap`	O(1)	O(1)	O(1)
`TreeMap`	O(log n)	O(log n)

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The class java.util.Collections consists entirely of static methods that operate on or return collections. There are three main categories: generic algorithms, methods that return empty or prepopulated collections, and methods that create wrappers. We discuss these three categories in turn, followed by a number of other methods which do not fit into a neat classification.

All the methods of Collections are public and static, so for readability we will omit these modifiers from the individual declarations.

The generic algorithms fall into four major categories: changing element order in a list, changing the contents of a list, finding extreme values in a collection, and finding specific values in a list. They represent reusable functionality, in that they can be applied to Lists (or in some cases to Collections) of any type. Generifying the types of these methods has led to some fairly complicated declarations, so each section discusses the declarations briefly after presenting them.

There are seven methods for reordering lists in various ways. The simplest of these is swap, which exchanges two elements and, in the case of a List which implements RandomAccess, executes in constant time. The most complex is sort, which transfers the elements into an array, applies a merge sort to them in time O(n log n), and then returns them to the List. All of the remaining methods execute in time O(n).


void reverse(List<?> list)

          // reverse the order of the elements

void rotate(List<?> list, int distance)

          // rotate the elements of the list; the element at index

          // i is moved to index (distance + i) % list.size()

void shuffle(List<?> list)

          // randomly permute the list elements

void shuffle(List<?> list, Random rnd)

          // randomly permute the list using the randomness source rnd

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

          // sort the supplied list using natural ordering

<T> void sort(List<T> list, Comparator<? super T> c)

          // sort the supplied list using the supplied ordering

void swap(List<?> list, int i, int j)

          // swap the elements at the specified positions

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The generic algorithms fall into four major categories: changing element order in a list, changing the contents of a list, finding extreme values in a collection, and finding specific values in a list. They represent reusable functionality, in that they can be applied to Lists (or in some cases to Collections) of any type. Generifying the types of these methods has led to some fairly complicated declarations, so each section discusses the declarations briefly after presenting them.

There are seven methods for reordering lists in various ways. The simplest of these is swap, which exchanges two elements and, in the case of a List which implements RandomAccess, executes in constant time. The most complex is sort, which transfers the elements into an array, applies a merge sort to them in time O(n log n), and then returns them to the List. All of the remaining methods execute in time O(n).


void reverse(List<?> list)

          // reverse the order of the elements

void rotate(List<?> list, int distance)

          // rotate the elements of the list; the element at index

          // i is moved to index (distance + i) % list.size()

void shuffle(List<?> list)

          // randomly permute the list elements

void shuffle(List<?> list, Random rnd)

          // randomly permute the list using the randomness source rnd

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

          // sort the supplied list using natural ordering

<T> void sort(List<T> list, Comparator<? super T> c)

          // sort the supplied list using the supplied ordering

void swap(List<?> list, int i, int j)

          // swap the elements at the specified positions

For each of these methods, except sort and swap, there are two algorithms, one using iteration and another using random access. The method sort transfers the List elements to an array, where they are sorted using—in the current implementation—a mergesort algorithm with n log n performance. The method swap always uses random access. The standard implementations for the other methods in this section use either iteration or random access, depending on whether the list implements the

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The Collections class provides convenient ways of creating some kinds of collections containing zero or more references to the same object. The simplest possible such collections are empty:


<T> List<T> emptyList()    // return the empty list (immutable) 

 



<K,V> Map<K,V> emptyMap()  // return the empty map (immutable)

<T> Set<T> emptySet()      // return the empty set (immutable)

Empty collections can be useful in implementing methods to return collections of values, where they can be used to signify that there were no values to return. Each method returns a reference to an instance of a singleton inner class of Collections. Because these instances are immutable, they can safely be shared, so calling one of these factory methods does not result in object creation. The Collections fields EMPTY_SET, EMPTY_LIST, and EMPTY_MAP were commonly used for the same purpose in Java before generics, but are less useful now because their raw types generate unchecked warnings whenever they are used.

The Collections class also provides you with ways of creating collection objects containing only a single member:


<T> Set<T> singleton(T o)

        // return an immutable set containing only the specified object

<T> List<T> singletonList(T o)

        // return an immutable list containing only the specified object

<K,V> Map<K,V> singletonMap(K key, V value)

        // return an immutable map, mapping only the key K to the value V

Again, these can be useful in providing a single input value to a method that is written to accept a Collection of values.

Finally, it is possible to create a list containing a number of copies of a given object.


<T> List<T> nCopies(int n, T o)

        // return an immutable list containing n references to the object o

Because the list produced by nCopies is immutable, it need contain only a single physical element to provide a list view of the required length. Such lists are often used as the basis for building further collections—for example, as the argument to a constructor or an

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The Collections class provides wrapper objects that modify the behavior of standard collections classes in one of three ways—by synchronizing them, by making them unmodifiable, or by checking the type of elements being added to them. These wrapper objects implement the same interfaces as the wrapped objects, and they delegate their work to them. Their purpose is to restrict the circumstances under which that work will be carried out. These are examples of the use of protection proxies (see Design Patterns by Gamma, Helm, Johnson, and Vlissides, Addison-Wesley), a variant of the Proxy pattern in which the proxy controls access to the real subject.

Proxies can be created in different ways. Here, they are created by factory methods that wrap the supplied collection object in an inner class of Collections that implements the collection's interface. Subsequently, method calls to the proxy are (mostly) delegated to the collection object, but the proxy controls the conditions of the call: in the case of the synchronized wrappers, all method calls are delegated but the proxy uses synchronization to ensure that the collection is accessed by only one thread at a time. In the case of unmodifiable and checked collections, method calls that break the contract for the proxy fail, throwing the appropriate exception.

As we explained in Section 11.5, most of the Framework classes are not thread-safe—by design—in order to avoid the overhead of unnecessary synchronization (as incurred by the legacy classes Vector and Hashtable). But there are occasions when you do need to program multiple threads to have access to the same collection, and these synchronized wrappers are provided by the Collections class for such situations.

There are six synchronized wrapper factory methods, corresponding to the six pre-Java 6 interfaces of the Collections Framework. (No synchronized wrappers were provided in Java 6 for NavigableSet or NavigableMap. If they had been provided, there would be very few situations in which you would choose them over the thread-safe collections

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The Collections class provides a number of utility methods, some of which we have already seen in use. Here we review them in alphabetical order.

addAll


<T> boolean addAll(Collection<? super T> c, T... elements)

        // adds all of the specified elements to the specified collection.

We have used this method a number of times as a convenient and efficient way of initializing a collection with individual elements, or with the contents of an array.

asLifoQueue


<T> Queue<T> asLifoQueue(Deque<T> deque)

        // returns a view of a Deque as a Last-in-first-out (Lifo) Queue.

Recall from Chapter 14 that while queues can impose various different orderings on their elements, there is no standard Queue implementation that provides LIFO ordering. Dequeue implementations, on the other hand, all support LIFO ordering if elements are removed from the same end of the dequeue as they were added. The method asLifoQueue allows you to use this functionality through the conveniently concise Queue interface.

disjoint


boolean disjoint(Collection<?> c1, Collection<?> c2)

        // returns true if c1 and c2 have no elements in common

Care is needed in using this method; implementations may iterate over either collection, testing elements of one for containment in the other. So if the two collections determine containment differently, the result of this method is undefined. This could arise if, say, one collection is a SortedSet, for which containment is decided by natural ordering or a comparator, and the other is a Set, for which containment is decided by the equals method of its elements.

frequency


int frequency(Collection<?> c, Object o)

        // returns the number of elements in c that are equal to o

If the supplied value o is null, then frequency returns the number of null elements in the collection c.

newSetFromMap

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsverzeichnis

Themen

Buchreihen

Special Interest

International Sites