Section 12.1. Using the Methods of Collection

12.1. Using the Methods of Collection

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.1that 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; } } 

A coding task is specified by a string, and a phone task is specified by the name and number of the person to be called. In each case we provide a constructor for the class, methods to access its fields, and a way to convert it to a string. In accordance with good practice, we have made both kinds of task immutable by declaring the fields to be final, and we have declared both subclasses to be final so that no one can later define mutable subclasses (see "Item 13: Favor immutability", in Effective Java by Joshua Bloch, Addison-Wesley).

The toString method prefaces every coding task with the string "code" and every phone task with the string "phone". Since the first precedes the second in alphabetic order, and since tasks are ordered according to the results returned by toString, it follows that coding tasks come before phone tasks in the natural ordering on tasks. This suits our needswe are geeks, after all!

For compactness, the toString method on phone tasks only returns the name of the person to call and not the phone number. We assume we never create two phone tasks with the same name and different numbers; if we did, it would be wrong to test equality using the result returned by toString.

We also define an empty task:

 public class EmptyTask extends Task {   public EmptyTask() {}   public String toString() { return ""; } } 

Since the empty string precedes all others in the natural ordering on strings, the empty task comes before all others in the natural ordering on tasks. This task will be useful when we construct range views of sorted sets (see Section 13.2).

Example 12.1 shows how we can define a series of tasks to be carried out (even if, in a real system, they would be more likely to be retrieved from a database). We've chosen ArrayList as the implementation of Collection to use in this example, but we're not going to take advantage of any of the special properties of lists; we're treating ArrayList as an implementation of Collection and nothing more. As part of the retrieval process, we have organized the tasks into various categories represented by lists, using the methodCollections.addAll introduced in Section 1.4.

Example 12-1. Example tasks and task collections for the task manager

 PhoneTask mikePhone = new PhoneTask("Mike", "987 6543"); PhoneTask paulPhone = new PhoneTask("Paul", "123 4567"); CodingTask databaseCode = new CodingTask("db"); CodingTask interfaceCode = new CodingTask("gui"); CodingTask logicCode = new CodingTask("logic"); Collection<PhoneTask> phoneTasks = new ArrayList<PhoneTask>(); Collection<CodingTask> codingTasks = new ArrayList<CodingTask>(); Collection<Task> mondayTasks = new ArrayList<Task>(); Collection<Task> tuesdayTasks = new ArrayList<Task>(); Collections.addAll(phoneTasks, mikePhone, paulPhone); Collections.addAll(codingTasks, databaseCode, interfaceCode, logicCode); Collections.addAll(mondayTasks, logicCode, mikePhone); Collections.addAll(tuesdayTasks, databaseCode, interfaceCode, paulPhone); assert phoneTasks.toString().equals("[phone Mike, phone Paul]"); assert codingTasks.toString().equals("[code db, code gui, code logic]"); assert mondayTasks.toString().equals("[code logic, phone Mike]"); assert tuesdayTasks.toString().equals("[code db, code gui, phone Paul]"); 

Now we can use the methods of Collection to work with these categories. The examples we present here use the methods in the order in which they were presented earlier.

Adding Elements We can add new tasks to the schedule:

 mondayTasks.add(new PhoneTask("Ruth", "567 1234")); assert mondayTasks.toString().equals(   "[code logic, phone Mike, phone Ruth]"); 

or we can combine schedules together:

 Collection<Task> allTasks = new ArrayList<Task>(mondayTasks); allTasks.addAll(tuesdayTasks); assert allTasks.toString().equals(   "[code logic, phone Mike, phone Ruth, code db, code gui, phone Paul]"); 

Removing Elements When a task is completed, we can remove it from a schedule:

 boolean wasPresent = mondayTasks.remove(mikePhone); assert wasPresent; assert mondayTasks.toString().equals("[code logic, phone Ruth]"); 

and we can clear a schedule out altogether because all of its tasks have been done (yeah, right):

 mondayTasks.clear(); assert mondayTasks.toString().equals("[]"); 

The removal methods also allow us to combine entire collections in various ways. For example, to see which tasks other than phone calls are scheduled for Tuesday, we can write:

 Collection<Task> tuesdayNonphoneTasks = new ArrayList<Task>(tuesdayTasks); tuesdayNonphoneTasks.removeAll(phoneTasks); assert tuesdayNonphoneTasks.toString().equals("[code db, code gui]"); 

or to see which phone calls are scheduled for that day:

 Collection<Task> phoneTuesdayTasks = new ArrayList<Task>(tuesdayTasks); phoneTuesdayTasks.retainAll(phoneTasks); assert phoneTuesdayTasks.toString().equals("[phone Paul]"); 

This last example can be approached differently to achieve the same result:

 Collection<PhoneTask> tuesdayPhoneTasks =   new ArrayList<PhoneTask>(phoneTasks); tuesdayPhoneTasks.retainAll(tuesdayTasks); assert tuesdayPhoneTasks.toString().equals("[phone Paul]"); 

Note that phoneTuesdayTasks has the type List<Task>, while tuesdayPhoneTasks has the more precise type List<PhoneTask>.

This example provides an explanation of the signatures of methods in this group and the next. We have already discussed (Section 2.6) why they take arguments of type Object or Collection<?> when the methods for adding to the collection restrict their arguments to its parametric type. Taking the example of retainAll, its contract requires the removal of those elements of this collection which do not occur in the argument collection. That gives no justification for restricting what the argument collection may contain; in the preceding example it can contain instances of any kind of Task, not just PhoneTask. And it is too narrow even to restrict the argument to collections of supertypes of the parametric type; we want the least restrictive type possible, which is Collection<?>. Similar reasoning applies to remove, removeAll, contains, and containsAll.

Querying the Contents of a Collection These methods allow us to check, for example, that the operations above have worked correctly. We are going to use assert here to make the system check our belief that we have programmed the previous operations correctly. For example the first statement will throw an AssertionError if tuesdayPhoneTasks does not contain paulPhone:

 assert tuesdayPhoneTasks.contains(paulPhone); assert tuesdayTasks.containsAll(tuesdayPhoneTasks); assert mondayTasks.isEmpty(); assert mondayTasks.size() == 0; 

Making the Collection Contents Available for Further Processing The methods in this group provide an iterator over the collection or convert it to an array.

Section 11.1 showed how the simplestand most commonexplicit use of iterators has been replaced in Java 5 by the foreach statement, which uses them implicitly. But there are uses of iteration with which foreach can't help; you must use an explicit iterator if you want to change the structure of a collection without encountering ConcurrentModificationException, or if you want to process two lists in parallel. For example, suppose that we decide that we don't have time for phone tasks on Tuesday. It may perhaps be tempting to use foreach to filter them from our task list, but that won't work for the reasons described in Section 11.1:

 // throws ConcurrentModificationException for (Task t : tuesdayTasks) {   if (t instanceof PhoneTask) {     tuesdayTasks.remove(t);   } } 

Using an iterator explicitly is no improvement if you still use the Collection methods that modify the structure:

 // throws ConcurrentModificationException for (Iterator<Task> it = tuesdayTasks.iterator() ; it.hasNext() ; ) {   Task t = it.next();   if (t instanceof PhoneTask) {     tuesdayTasks.remove(t);   } } 

But using the iterator's structure-changing methods gives the result we want:

 for (Iterator<Task> it = tuesdayTasks.iterator() ; it.hasNext() ; ) {   Task t = it.next();   if (t instanceof PhoneTask) {     it.remove();   } } 

For another example, suppose we are fastidious people that like to keep all our lists of tasks in ascending order, and we want to merge two lists of tasks into a single list, while maintaining the order. Example 12.2 shows how we can merge two collections into a third, provided that the iterators of each return their elements ascending in natural order. This method relies on the fact that the collections to be merged contain no null elements; if one is encountered, the method throws a NullPointerException. As it happens, the collections mondayTasks and tuesdayTasks in Example 12.1 are both in ascending order, and we can merge them as follows:

Example 12-2. Merging collections using natural ordering

 public class MergeCollections {   static <T extends Comparable<? super T>>     List<T> merge(Collection<? extends T> c1, Collection<? extends T> c2)   {     List<T> mergedList = new ArrayList<T>();     Iterator<? extends T> itr1 = c1.iterator();     Iterator<? extends T> itr2 = c2.iterator();     T c1Element = getNextElement(itr1);     T c2Element = getNextElement(itr2);     // each iteration will take a task from one of the iterators;     // continue until neither iterator has any further tasks     while (c1Element != null || c2Element != null) {       // use the current c1 element if either the current c2       // element is null, or both are non-null and the c1 element       // precedes the c2 element in the natural order       boolean useC1Element = c2Element == null ||               c1Element != null && c1Element.compareTo(c2Element) < 0;       if (useC1Element) {         mergedList.add(c1Element);         c1Element = getNextElement(itr1);       } else {         mergedList.add(c2Element);         c2Element = getNextElement(itr2);       }     }     return mergedList;   }   static <E> E getNextElement(Iterator<E> itr) {     if (itr.hasNext()){       E nextElement = itr.next();       if (nextElement == null) throw new NullPointerException();       return nextElement;     } else {       return null;     }   } } 

 Collection<Task> mergedTasks =   MergeCollections.merge(mondayTasks, tuesdayTasks); assert mergedTasks.toString().equals(   "[code db, code gui, code logic, phone Mike, phone Paul]");