5.2 CONTAINERS IN JAVA

5.2 CONTAINERS IN JAVA

Java containers are based on a hierarchy of abstract data types shown in Figure 5.3. Being Java interfaces, these data types only contain method declarations; in other words, they do not contain any implementation code for the methods. The interface Collection considers a container to be a group of objects, without any assumptions about the uniqueness of the objects in the container. This interface declares methods common to all containers of types List and Set. These include such general-purpose methods like add to insert a new element into a container; clear to remove all the elements from a container; isEmpty to check whether a container is empty; iterator to return an iterator to a container; remove for removing a specific object from a container; removeAll for removing all the objects from a container that are specified via an argument container; and so on. A particularly noteworthy method declared in this interface is toArray. Since this method must be implemented by all containers of type Collection, it can be used to construct an array version of any of those containers.

Figure 5.3

A Set is a specialization of Collection in the sense that all the elements in a Set must be unique. Uniqueness of the elements is tested by the equals method defined for the element type. In other words, if e1 and e2 are any two elements in a Set, then e1.equals( e2 ) must return false. A SortedSet is a Set in which all the elements are kept in a sorted order, usually in the form of a height-balanced binary tree. For the comparison criterion needed for sorting, a SortedSet can use the compareTo method if defined for the element type^[13] or a Comparator object supplied to a SortedSet constructor.

Compared to a Set, a List is a sequence container, in the same sense that vector, deque, and list are sequence containers in C++. Therefore, a List supports a next-element operation that can be used to traverse a List from the beginning to the end, one element at a time. Containers of type List give the user precise control over where in the list a new element is inserted. Unlike a Set, it is possible to place duplicate elements in a List.

Going over to the interfaces shown on the right in Figure 5.3, a Map, like a C++ map, is a container that stores <key, value> pairs, with no duplicate keys allowed. While a C++ map always stores its <key, value> pairs in key-sorted order, Java provides a subtype SortedMap for that purpose.

As was mentioned previously, the types shown in Figure 5.3 are merely interfaces. They must be implemented by container classes that create physical storage for the data to be stored. Table 5.2 shows which interfaces are implemented by what classes. In addition to the recommended implementation classes like ArrayList and LinkedList for the interface List, we also show in Table 5.2 the older container classes Vector and Stack that have now been retrofitted to the List interface in order to make them a part of the Java Collections Framework. ArrayList is a modern replacement for Vector. Similarly, for the Map interface, we listed the recommended HashMap and TreeMap and also the historical HashTable.

Table 5.2

Interface	Implementation	Retrofitted Implementation
Set	HashSet
SortedSet	TreeSet
List	ArrayList LinkedList	Vector Stack
Map	HashMap	HashTable
SortedMap	TreeMap

The hierarchical organization of the container types shown in Figure 5.3 results in certain programming conveniences, such as easy copying over of the contents of one container into another container. This is a consequence of the fact that all container classes that implement any of the interface shown in the first column of Table 5.2 are required to have a constructor that takes an argument of type Collection. For example, the container class ArrayList is an implementation of the interface List and one of the three constructors for ArrayList is

     ArrayList( Collection c )

What that implies is that an ArrayList container can be constructed from the elements stored in any container that is of type Collection. To see the benefits of that, let's say we have a Set of objects and that we would like to apply an operation to the objects that is defined for a List but not for a Set. Since a Set is a Collection, all we have to do is to copy over all the objects from the Set into an ArrayList by invoking the constructor shown above and apply the desired operation. After that, if so desired, we can copy the objects back to a Set type container using a constructor that again takes a Collection argument.

In the rest of this section, we will show example code for some of these implementation classes to give the reader a better sense of how they are actually used. However, before getting into the individual containers, we should mention at the outset that, whereas C++ containers can store the primitive types directly, Java containers only store items of type Object or its sub-types. With regard to the subtypes of Object in Java, note that int, float, char, and so on,-the primitive types-are not subtypes of Object (see Chapter 6). However, Java provides for each primitive type a corresponding wrapper class that is a subtype of Object. For example, the Character class is a wrapper class for the primitive type char; the Integer class a wrapper for the primitive type int, and so on.

5.2.1 List

Of the two implementations of the List interface, ArrayList of the java.util package is a modern version of the Java Vector class^[14] and its properties are very much like those of the C++ vector and deque containers. The implementations Vector and Stack shown in Table 5.2 date back to the early releases of Java; more recently these classes have been retrofitted to implement the List interface to enable older Java code to run on the newer platforms.

The next program illustrates the following methods of a List:

add	: for adding a new element at the back end
add	: a two-argument vesion for adding a new element at a specified position
remove	: for removing the first occurrence of an element that is the same (in content or value) as the argument to this method
remove	: an integer argument version for removing an element from a specified position
addAll	: for splicing one list into another
listIterator:	for iterating through a List using a ListIterator object

The program also illustrates how Collections.sort can be used to sort a List.

The program starts in line (A) by declaring animals as an ArrayList. At this juncture, animals is an empty list. We could also have invoked a constructor that takes an integer argument, as in

     List animals = new ArrayList(10);

The integer argument creates a List of a specified initial capacity, in this case 10 elements. Specifying an initial capacity can reduce the overhead associated with incremental reallocation of memory as new elements are added to a list.

In a block of lines starting at (B), the program then invokes a one-argument version of add to insert new elements into the list. Line (C) intentionally introduces a duplicate element into the list. Line (D) shows a one-argument version of remove to remove from the list a single element based on its value. The remove method compares its argument with each element using the equals predicate as it traverses the list. The first element for which equals returns true is removed from the list.

Next, in lines (E) and (F), the program shows the two-argument version of add for inserting a new element into a List at a specific position. This is followed in line (G) by the use an integer argument version of remove for removing an element from a specific position.

The list animals is then sorted by invoking Collections.sort in line (H). The sort algorithm yields a natural order for the elements since by default it uses the compareTo method defined for the element type. We could also have supplied a second argument to sort; the argument would be a Comparator object that tells sort how to compare two elements.

We then demonstrate how to splice one List into another. For that purpose, we create a second list, pets, in line (I). For the sake of variety, we make this list a LinkedList. By invoking addAll in line (K) the list pets is spliced into animals at a specific position that is the first argument to addAll.

Finally, we show in lines (L) through (N) how a ListIterator is used to iterate over a list. While an Iterator can only move in the forward direction, a ListIterator is bidirectional. With an Iterator, you can set up a while loop that yields successive elements by the invocation of next while testing for the end of the list via the predicate hasNext(). Being bidirectional, a ListIterator also supports previous and hasPrevious for a backwards traversal of a list, in addition to the usual next and hasNext for a forward traversal. The methods previous and hasPrevious are analogous to the methods next and hasNext.

 
 //ListOps.Java import java.util.*; class ListOps {     public static void main( String[] args )     {         List animals = new ArrayList();                                     //(A)         animals.add( "cheetah" );                                           //(B)         animals.add( "lion" );         animals.add( "cat" );         animals.add( "fox" );         animals.add( "cat" );              //duplicate cat                  //(C)         System.out.println( animals );     //cheetah, lion, cat, fox,                            //cat         animals.remove( "lion" );                                           //(D)         System.out.println( animals );     //cheetah, cat, fox, cat         animals.add( 0, "lion" );                                           //(E)         System.out.println( animals );     //lion, cheetah, cat, fox,                                            //cat         animals.add( 3, "racoon" );                                         //(F)         System.out.println( animals );     //lion, cheetah, cat,                                            //racoon, fox, cat         animals.remove(3);                                                  //(G)         System.out.println( animals );     //lion, cheetah, cat,                                            //fox, cat         Collections.sort( animals );                                        //(H)         System.out.println( animals );     //cat, cat, cheetah,                                            //fox, lion         List pets = new LinkedList();                                       //(I)         pets.add( "cat" );                                                  //(J)         pets.add( "dog" );         pets.add( "bird" );         System.out.println( pets );        //cat, dog, bird         animals.addAll( 3, pets );                                          //(K)         System.out.println( animals );     //cat, cat, cheetah,                                            //cat, dog, bird, fox,                                            //lion         ListIterator iter = animals.listIterator();                         //(L)         while ( iter.hasNext() ) {                                          //(M)            System.out.println( iter.next() );                               //(N)      }      } } 
 

An interesting difference between C++ iterators and Java iterators is the manner in which you must imagine their position in a container. A C++ iterator, like a C++ pointer, points directly at an element of a container. To illustrate this difference, let's say you declare and initialize an iterator to a vector in C++ as follows

     vector<int> vec(4);     vector<int>::iterator iter = vec.begin();

With this initialization, iter is pointing directly at the first element of the vector, as shown in Figure 5.4.

Figure 5.4

On the other hand, in Java the operation of the next and the hasNext methods (and the previous and the hasPrevious methods) is best imagined by thinking of a Java iterator as pointing to imaginary gaps between the elements. Suppose we declare

     List animals = new ArrayList( 4 );     animals.add();     ...     ...     ListIterator iter = animals.listIterator();     while ( iter.hasNext() ) {         System.out.println( iter.next() );     } 

It is best to think of the successive positions of the iterator iter as shown in Figure 5.5. With this picture, the predicate hasNext tells us whether or not there exists a valid element immediately beyond the current position of the iterator and, if the element exists, the method next returns an object reference to the element. Similarly, for a position of the iterator of type ListIterator, the method hasPrevious will tell us whether or not there exists an element just before the current position of the iterator, and the method previous will return it. This mental picture of how an iterator traverses a container applies to all containers in the Java Collections Framework.

Figure 5.5

While we are on the subject of iterators for Java containers, we should mention that the iterators returned by the iterator and listIterator methods are fail-fast.^[15] What that means is that if you create an iterator and then proceed to structurally modify an ArrayList by the ArrayList's add or remove operations as you are iterating through the list, a runtime exception of type ConcurrentModificationException will be thrown.^[16] To illustrate this point, let us try to insert an add invocation inside the while loop in the lines (M) and (N) of the previous program. We will replace the lines (L), (M), and (N) of that program with the following code fragment

     ListIterator iter = animals.listIterator();     while ( iter.hasNext() ) {         animals.add( "zebra" );            // ERROR         System.out.println( iter.next() );     } 

If we compile and run the program with this modification, the runtime will throw a ConcurrentModificationException. If you must modify a container as you are scanning through it with an iterator, you are only allowed to use the add and remove methods defined directly for the iterator class. That makes sense because it is the Iterator object that knows where it is in the container as the container is being scanned. The container object itself would have no idea of that position.

The fail-fast property of iterators is a safety mechanism since modifying a container during an iteration loop will in general invalidate the initialization parameters of an iterator, as was also the case with C++ containers under similar conditions.^[17]

5.2.2 Set

HashSet implements the interface Set, whereas TreeSet implements the interface SortedSet. The former uses a hashing function to store the elements, whereas the latter keeps the elements in an ascending sorted order. If the hashing function used is effective, the former will give constant-time performance for data access, but there are no guarantees to that effect. On the other hand, the TreeSet implementation carries a guarantee of O(log(N)) time cost.

The following program shows some of the common operations-such as add, remove, size, and so on-one carries out on sets. The program starts by declaring in line (A) a TreeSet by

     Set animals = new TreeSet();

which creates an empty Set for us. If we had wanted to use a HashSet, we could have used the following invocation:

     Set animals = new HashSet(50);

where the integer argument to the constructor specifies the initial number of buckets to be used for hashing. This is also referred to as the initial capacity of the HashSet. The default value for the initial capacity is 101.^[18]

Lines (B) through (E) show how the add method can be used to insert elements into the set. Note the attempt to insert a duplicate element in line (F)-it simply replaces the previous element of the same value. In other words, no duplicate elements can exist simultaneously in this container. In line (G), we print out the contents of the container, and in line (H) its size by invoking the size () method. In line (I), we show how to remove an element of a set by value. Finally, in lines (K) through (M), we show how to iterate over a set by constructing an Iterator object and then invoking its hasNext () and next () methods. Here is the code:

 
 //SetOps.java import java.util.*; class SetOps {     public static void main( String[] args )     {        Set animals = new TreeSet();                                         //(A)        animals.add( "cheetah" );                                            //(B)        animals.add( "lion" );                                               //(C)        animals.add( "cat" );                                                //(D)        animals.add( "elephant" );                                           //(E)        animals.add( "cat" );                            // duplicate cat    //(F)        System.out.println( animals );                                       //(G)                                 // cat cheetah elephant lion        System.out.println( animals.size() );    // 4                        //(H)        animals.remove( "lion" );                                            //(I)        System.out.println( animals ); // cat cheetah elephant               //(J)        Iterator iter = animals.iterator();                                  //(K)        while ( iter.hasNext() )                                             //(L)           System.out.println( iter.next() );                                //(M)                                       // cat cheetah elephant     } } 
 

5.2.3 Map

The HashMap and the SortedMap implementations of the Map interface create, respectively, a hash-table based container and a binary-tree based container.

The Map container in Java acts much like the map container in C++: It stores a sequence of <key, value> pairs. However, there are important differences with regard to what can be stored as the keys and their values in a Java Map. Both the keys and the values must be class-type objects for a Java Map; both are stored as instances of the root class Object. To illustrate the consequences of this, suppose you wanted to create a Map of a telephone directory (with the implied constraint that no name would appear more than once in the directory). Unlike the map container class in C++, you will not be able to directly create a sequence of <String, int> pairs. Instead, you must now store a sequence of <String, Integer> pairs. In other words, the value part of a <key, value> pair for a given a key must be a class-type object and not a primitive. As mentioned before, the class-type objects for both the keys and the values are stored as instances of Object. Therefore, when you try to retrieve the value associated with a key, what you get back is of type Object, which you must then cast down to whatever type the value actually is. For the phone directory example, you will have to cast down the retrieved value from Object to Integer and to then invoke Integer.intValue() to actually get hold of the phone number associated with a name. This makes for code that is a bit longer compared to the case of a C++ map.

As the name implies, a HashMap is stored in the form of a hash table. This provides for fast constant-time access to the keys provided the hashing function used is effective for dispersing the keys uniformly over the buckets of the hash table. A TreeMap, on the other hand, is stored as a height-balanced binary tree (called the red-black tree), which guarantees a key-order storage for the <key, value> pairs. This makes for slower retrieval, but has the advantage of maintaining a key-order on the entries.

We will now show the Java version of the MapHist.cc program of Section 5.1.7 for constructing a word histogram for a text file. The C++ program used the STL container map for representing the histogram. The Java version of the same program shown here will give the reader a chance to compare a Java Map with a C++ map.

The program below starts out by declaring histogram as an empty TreeMap in line (A). The next order of business is to pull in all the words in the text file whose histogram is sought. Since Java input streams do not provide for word-by-word reading of an input text file, the program below achieves word-by-word reading by first reading all the characters in the input file into one large string (line B) and breaking the string down into the individual words by using the StringTokenizer class (lines C through E). If a string of delimiter characters is supplied as a second argument to the StringTokenizer constructor, it uses those characters as break points for constructing tokens.^[19] However, if this second argument is not supplied, white space characters are used as delimiters.

For each word supplied by the tokenizer in line (E), we seek its previously accumulated histogram count in line (F). If the word was not previously entered in the histogram, map.get (word) call in line (F) will return a null object. So in line (G), we first check the value returned for count. If null, we start counting for the word by depositing Integer( 1 ) as its value in the histogram. Otherwise, we simply increment the previous value. In line (H), we invoke the size () method to print out the total number of <key, value> pairs stored in the container. Finally, in line (I) we print out the string representation of the container.

For a source file containing the following text

      A hungry brown fox jumped over a lazy dog      but the lazy dog was not so lazy a dog      since the dog bit the hungry fox

the statement in line (I) causes the program to print out the following histogram:

      Total number of DISTINCT words: 16      {A=1, a=2, bit=1, brown=1, but=1, dog=4, fox=2,       hungry=2, jumped=1, lazy=3, not=1, over=1,       since=1, so=1, the=3, was=1} 

with the second part all in one line. Here is the program:

 
 //MapHist.java import java.io.*; import java.util.*; class WordHistogram {     public static void main (String args[]) throws 10Exception     {          Map histogram = new TreeMap();                                     //(A)          String allChars = getAllChars( args[0] );                          //(B)          StringTokenizer st = new StringTokenizer( allChars );              //(C)          while ( st.hasMoreTokens() ) {                                     //(D)              String word = st.nextToken();                                  //(E)              Integer count = (Integer) histogram.get( word );               //(F)              histogram.put( word, ( count==null ? new Integer(1)                      : new Integer( count.intValue() + 1 ) ) );             //(G)          }          System.out.println( "Total number of DISTINCT words: "                                 + histogram.size() );                       //(H)          System.out.println( histogram );                                   //(I)     }     static String getAllChars( String filename ) throws 10Exception {          String str = "";          int ch;          Reader input = new FileReader( filename );          while ( ( ch = input.read() ) != -1 )              str += (char) ch;              input.close();              return str;     } } 
 

Suppose we want this program to print out its output in the form of a table. This we can do by iterating over the <key, value> pairs of the Map and printing the keys in one column and the values in another column. Unfortunately, a Map container does not support an iterator directly. To iterate over a Map, we must first construct what is known as a Collection view. There are exactly three different ways, listed below, that a Map can be viewed as a Collection. The third choice below will print out the contents of a Map in the form of a table.

1. One can construct a Set of all the keys in a Map by invoking the keySet() method. One can then iterate over this set and display the keys, as in

    for (Iterator i = histogram. keySet() .iterator(); i.hasNext(); )      System.out.println( i.next() ); 

   The Set returned by keySet () is "backed" by the Map, in the sense that any changes made to this set will be reflected in the Map and vice-versa. So if a key were to be deleted in the Set view, the corresponding <key, value> would be removed from the Map.

2. One can construct a Collection of all the values in a Map in the same manner by invoking the values() method on the Map. The Collection returned is again backed by the Map.

3. One can construct a Set of all the <key, value> pairs contained in a Map by invoking the entrySet() method on the Map. Each element of the Set returned by the entrySet() method is an object of type Map.Entry, which is basically an encapsulation of a key and its corresponding value. The key and its value stored in a Map.Entry can be retrieved by the getKey() and the getValue() methods, as shown below:

         for (Iterator i = histogram. entrySet().iterator(); i.hasNext(); ){           Map.Entry pair = ( Map.Entry ) i.next();           System.out.println( pair.getKey() + ":" + pair.getValue() );      } 

   This code fragment will print out in each separate row first the key and then the value of each <key, value> pair of the container.

5.2.4 Vector

As mentioned earlier, the Vector class dates back to the early releases of Java. It has now been retrofitted to implement the List interface to enable older Java code to run on the newer platforms. (We also mentioned earlier that the most commonly used modern replacement for Vector is ArrayList.) Obviously a Vector can be manipulated through all of the methods declared in the List interface. But a Vector also possesses additional methods that it had prior to its modernization. Some of the more commonly used of those methods are illustrated in the example code below.

The next program first illustrates, in lines (B), (C), and (D), the addElement method for inserting three Objects-in this case three Character objects corresponding to the letters ‘c', ‘a', and ‘t'-into a vector. As was mentioned in the introduction to Section 5.2, Java containers store items of type Object or its subtypes. So, if you wish to store primitives in a container, you have to use the wrapper classes to first convert them into class-type objects. The program then invokes the size method on the vector in line (E) to determine the number of elements stored in the vector.

The elementAt method is used in lines (F) through (I) to fill up an array of characters from the data stored in the vector.^[20] Line (H) shows how this method can be invoked on a vector for array-like indexing to access the elements of a vector. Since, like all other Java containers, a Vector stores only class-type objects (each element as an Object), to retrieve the Character object stored, you have to cast the item returned by elementAt back to the Character type, as we do in line (H). The array thus filled is converted into a string in line (J) by invoking one of the constructors for the String class.

 
 //VectorOps.java import java.io.*; import java.util.*; class VectorOps {     public static void main( String[] args )     {         Vector charVec = new Vector();                                      //(A)         charVec.addElement( new Character( 'c' ) );                         //(B)         charVec.addElement( new Character( 'a' ) );                         //(C)         charVec.addElement( new Character( 't' ) );                         //(D)         int n = charVec.size();                    // 3                     //(E)         char[] charArray = new char[charVec.size()];                        //(F)         for ( int i=0; i<charVec.size(); i++ ) {                            //(G)              Character charac = (Character) charVec.elementAt(i);           //(H)              charArray[i] = charac.charValue();                             //(I)         }         String str = new String( charArray );                               //(J)         System.out.println( str );                 // cat                   //(K)      } } 
 

We will now illustrate how list operations are carried out on Java vectors. The functions used for such operations are

     insertElementAt     removeElementAt     addElement     removeElement 

The next program demonstrates these methods. In lines (A) through (D), the programs starts out in the same manner as the previous program-by constructing a vector containing three Character objects corresponding to the characters ‘c', ‘a', and ‘t'. Lines (E) through (H) then apply the above mentioned list operations to produce effects indicated by the commented out words shown. The rest of the program is the same as before.

 
 //VectorListOps.Java import java.io.*; import java.util.*; class VectorListOps {     public static void main( String[] args )     {         Vector charVec = new Vector();                                      //(A)         charVec.addElement( new Character( 'c' ) );                         //(B)         charVec.addElement( new Character( 'a' ) );                         //(C)         charVec.addElement( new Character( 't' ) );                         //(D)         charVec.insertElementAt(new Character('h'), 1);    // chat          //(E)         charVec.removeElementAt( 0 );                      // hat           //(F)         charVec.addElement( new Character( 's' ) );        // hats          //(G)         charVec.removeElement( new Character( 't' ) );     // has           //(H)         System.out.println( charVec.size() );              // 3         char[] charArray = new char[charVec.size()];         for ( int i=0; i<charVec.size(); i++ ) {              Character Ch = (Character) charVec.elementAt(i);              charArray[i] = Ch.charValue();      }      String str = new String( charArray );      System.out.println( str );                            // has      } } 
 

A Vector declared with no arguments allocates by default sufficient memory for storing 10 elements. So the charVec vector in the program above has initial capacity of 10 elements. In order to reduce the overhead associated with growing a vector one element at a time, Java provides two other constructors for the Vector class:

    Vector vec = new Vector( int initialCapacity );    Vector vec = new Vector(int initialCapacity, int capacityIncrement); 

The first invocation can initially create a vector of arbitrary size as specified by the parameter initialCapacity. After this initial storage is filled up, the vector will grow one element at a time should we push further elements into it. To reduce the overhead associated with this one-at-a-time incremental growth, the second constructor shown above allows us to specify the minimum increments to be made to the storage allocated to the vector. If by chance you should allocate too much initial capacity to a vector and that you'd want to trim the size of the vector down to the actual number of elements stored, you can invoke the trimToSize() method on the vector.

5.2.5 Algorithms for Java Containers

The java.util. Collections class provides the same kind of algorithmic support for the Java containers that the generic algorithms provide for the C++ containers. In this section, we will first focus on the stable sorting property of the sorting algorithm of the Collections class and then mention some of its other useful methods.

In the example programs shown earlier, we have already shown invocations such as Collections. sort( … ) for sorting the elements of a container. This sorting algorithm is stable. Stated succinctly, a sorting algorithm is stable if it does not reorder equal elements. But what does that really mean? A goal of this section is to illustrate this concept.

Stability in sorting, or lack thereof, is best illustrated by comparing the sorted order obtained through the quick-sort algorithm with the sorted order obtained through the merge-sort algorithm. An optimized implementation of quick-sort is slightly faster than an optimized implementation of merge-sort but does not guarantee stability. On the other hand, merge-sort guarantees stability.

Stability in sorting becomes an issue for class-type objects with two or more data members. Class type objects are sorted on the basis of the values of one or more of their data members. Let's say we have multiple objects in a list whose values for the data member chosen for comparison are the same, but whose values for the other data members are different. A stable sorting algorithm will leave the original order of such objects untouched. To illustrate this notion, let us consider a class Person:

     class Person {         private String name;         private int rank;             public Person( String nam, int r ) {               name = new String( nam );               rank = r;         }         public String getName() { return name; };         public String toString() { return name + " " + rank; }     } 

To sort Person objects, we may choose to do so on the basis of their names or on the basis of their rank (or perhaps some weighted combination of the two). We may even wish to first sort all the Person objects on the basis of their names, and next sort the resulting list on the basis of rank. In what follows, we will first sort a list of Person's with the merge-sort algorithm of the Collections class and then sort the same list with the quick-sort algorithm of C++'s qsort.

For sorting by Java's Collections. sort, we will use the following Comparator class:

     class PersonComparator implements Comparator {         public int compare( Object o1, Object o2 ) {             Person p1 = ( Person ) o1;             Person p2 = ( Person ) o2;             return p1.getName().compareTo( p2.getName() );         }     } 

The compare method of this class compares two Person objects on the basis of the name field. For the purpose of sorting, let's now construct a list of Person objects by

     List perList = new ArrayList();     perList.add( new Person( "Zaphod", 0 ) );     perList.add( new Person( "Zaphod", 1 ) );     perList.add( new Person( "Zaphod", 2 ) );     perList.add( new Person( "Betelgeuse", 0 ) );     perList.add( new Person( "Betelgeuse", 1 ) );     perList.add( new Person( "Betelgeuse", 2 ) );     perList.add( new Person( "Trillion", 0 ) );     perList.add( new Person( "Trillion", 1 ) );     perList.add( new Person( "Trillion", 2 ) ); 

A stable sorting algorithm will reorder the names in the list, but for each name will leave untouched the order of appearance with respect to the rank. We can sort this list by

     Collections.sort( perList, new PersonComparator() ); 

The sorted list is as follows:

     Betelgeuse 0     Betelgeuse 1     Betelgeuse 2     Trillion 0     Trillion 1     Trillion 2     Zaphod 0     Zaphod 1     Zaphod 2 

where the name is followed by the associated rank in each Person object.

On the other hand, if we sort the same original list with a quick-sort algorithm using again the name field for comparison, we get

     Betelgeuse 0     Betelgeuse 2     Betelgeuse 1     Trillion 2     Trillion 0     Trillion 1     Zaphod 0     Zaphod 2     Zaphod 1 

Notice that objects that are equal with respect to the name field are getting shuffled by the quick-sort algorithm.

The quick-sort results shown above were obtained with a C++ program that invoked the well-known qsort function with the following invocation

     qsort( perList, 9, sizeof( Person* ), comparePersons ); 

where the list of Person objects was declared as

     Person* perList[9]; 

with each element of the list instantiated by a statement like

     perList[0] = new Person( "Zaphod", 0 );     perList[1] = new Person( "Zaphod", 1 );     ...     ... 

The comparison function needed for the fourth argument of qsort was defined by

     int comparePersons( const void* arg1, const void* arg2 ) {         string str1 = (*( Person** )arg1)->name;         string str2 = (*( Person** )arg2)->name;         return ( str1 ).compare( str2 );     } 

The other algorithms provided by the Collections class perform tasks such as searching, copying, filling, finding the max or the min in a container, reversing the contents of a container, shuffling the container contents, and so on. The Collections class also contains algorithms for creating singleton collections, read-only collections, synchronized collections, and so on.

A singleton Set is a set with a single element, a singleton List a list with a single element, and so on. That a singleton collection can play a useful role in a Java program should be evident from the following program fragment:

     List list = new ArrayList();     list.add( "cat" );     list.add( "dog" );     list.add( "cat" );     ....     list.removeAll( new Collections.singleton( "cat" ) ); 

This will eliminate all occurrences of "cat" from the container list. A singleton collection is immutable, meaning that once created, it cannot be modified.

Here is a program fragment that shows how to create a read-only version of a collection, in this case a List:

     List list = new ArrayList();     list.add( "cat" );     list.add( "dog" );     list.add( "cat" );     ....     List readOnlyList = new Collections.unmodifiableList( list ); 

and a program fragment that illustrates how to create a synchronized^[21] version of a container, in this case a List:

     List list = new ArrayList();     list.add( "cat" );     list.add( "dog" );     list.add( "cat" );     ....     List syncList = new Collections.synchronizedlist( list ); 

While list by itself would not be safe for multithreaded programming, syncList will be. Thread safety is presented in Chapter 18.

Since it is possible to construct an array version of any container of type Collection by invoking the toArray method on the container, it is also possible to use the algorithms defined for the java. util. Array class to manipulate the contents of any container of type Collection. The result obtained with this approach will usually be an array that, if so desired, can be converted back into, say, a List by invoking the method Arrays.asList.

^[13]Recall from our Chapter 3 discussion on how class type objects are compared in Java that the compareTo method induces a natural order on a data type.

^[14]This is important for multithreaded programs: while Vector is synchronized, an ArrayList is not. Therefore, ArrayList must be synchronized externally. Absence of synchronization is also true of the other containers shown under Implementations in Table 5.2. Thread synchronization is discussed in Chapter 18.

^[15]This actually applies to all of the containers in the Java Collections Framework. The iterators are always fail-fast.

^[16]Since ConcurrentModificationException is a subtype of RuntimeException, it is an unchecked exception. As we will explain in greater detail in Chapter 10, methods that throw unchecked exceptions do not need to be called inside a try-catch block.

^[17]This protection also helps out with multithreaded programs if one thread has initialized an iterator and is using it to iterate through a loop while another thread is trying to modify the container structurally. Multithreading is discussed in Chapter 18.

^[18]Further tuning of a HashSet can be achieved by specifying a load factor as a second argument to the constructor. The load factor controls how full a hash-table based container is allowed to get before its capacity is automatically increased.

^[19]A token is the maximal sequence of consecutive characters that are not delimiters.

^[20]For converting a vector into an array, we could also have invoked the following shortcut:

      Character[] characterArr = new Character[ charVec.size() ];      charVec.copyInto( CharacterArr ); 

But note that characterArr is an array of Character's, whereas charArray used in the program is an array of the primitive char's.

^[21]Synchronization is discussed in Chapter 18.