java.oreilly.com -- Bite-Size Java

★ wanayoo — archive 1999 http://java.oreilly.com/bite-size/java_0199.html

Nouvelle recherche | Portail wanayoo

BITE-SIZE JAVA

Bite-Size Java Bottle Caps and Commemorative
Plates in Java 2
by Jonathan Knudsen

Jonathan Knudsen

Collections are a fundamental idea in programming. Applications frequently need to keep track of many related things, like a group of employees or a set of images. To support the concept of many at a fundamental level, of course, Java includes the concept of arrays. Arrays are awkward for some operations, especially sets of things that grow and shrink over the lifetime of an application. Ever since JDK 1.0, the Java platform has had two handy classes for keeping track of sets. The java.util.Vector class represents a dynamic list of objects, and the java.util.Hashtable class is a set of key and value pairs.

The Java 2 platform introduces a more comprehensive approach to collections called the Collections Framework. The Vector and Hashtable classes still exist, but they are now a part of the framework. In this month's column, I'll introduce you to the Collections Framework and show what it can do for you.

Collections Framework Structure

The Collections Framework is based around some fundamental interfaces in the java.util package. These interfaces are divided into two hierarchies. The first hierarchy descends from the Collection interface. This interface (and its descendants) represent a box that holds other objects. The second hierarchy is based on the Map interface, which represents a group of key and value pairs.

The Collection Interface

The mother of all collections is an interface appropriately named Collection. It serves as a box that holds other objects, its elements. It doesn't specify if duplicate objects are allowed or if the objects will be ordered in some way. These kinds of details are left to child interfaces. Nevertheless, the Collection interface does define some basic operations:

public boolean add(Object o)

This method adds the supplied object to this collection. If the operation succeeds, this method returns true. If the object already exists in this collection and the collection does not permit duplicates, false is returned. Furthermore, some collections are read-only. These collections will throw an UnsupportedOperationException if this method is called.

public boolean remove(Object o)

This method removes the supplied object to this collection. Like the add() method, this method returns true if the object is removed from the collection. If the object doesn't exist in this collection, false is returned. Read-only collections throw an UnsupportedOperationException if this method is called.

public boolean contains(Object o)

This method returns true if the collection contains the specified object.

public int size()

Use this method to find the number of elements in this collection.

public boolean isEmpty()

This method returns true if there are no elements in this collection.

public Iterator iterator()

Use this method to examine all the elements in this collection. This method returns an Iterator, which is an object that you can use to step through the collection's elements. I'll talk more about iterators in the next section.

As a special convenience, the elements of a collection can be placed into an array using the following methods:

public Object[] toArray()
public Object[] toArray(Object[] a)

These methods return an array that contains all the elements in this collection. The second version of this method returns an array of the type specified by a.

Remember, these methods are common to every Collection implementation. Any class that implements Collection or one of its child interfaces will have these methods.

Iterators and Enumerators, Oh My!

What does the java.util.Iterator interface do? It's kind of an Enumeration on steroids. As you may remember from JDK 1.0 and JDK 1.1, Enumeration is an object that lets you step through some other object's data.

public Object next()

This method returns the next element of the iterator.

public boolean hasNext()

This method returns true if you have not yet stepped through all of the iterator's elements. In other words, it returns true if you can call next() to get the next element.

These methods are just like the nextElement() and hasMoreElements() methods in Enumeration. The following example shows how you could use an Iterator to print out every element of a collection.

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

Finally, Iterator offers the ability to remove an element from a collection:

public void remove()

This method removes the last object returned from next() from the collection that created this iterator. Not all iterators implement this operation. It doesn't make sense to be able to remove an element from a read-only collection, for example. If element removal is not allowed, an UnsupportedOperationException is thrown from this method. If you call remove() before first calling next(), or if you call remove() twice in a row, you'll get an IllegalStateException.

Collection Flavors

The Collection interface has two child interfaces: Set represents a collection in which duplicate elements are not allowed, and List is a collection whose elements have a specific order. Set has a more specific child interface, SortedSet, which keeps its elements in sorted order. (I'll talk more about sorting later.)

Set has no methods besides the ones it inherits from Collection. It does, however, enforce the rule that duplicate elements are not allowed. If you try to add an element that already exists in a Set, the add() method will return false.

SortedSet adds only a few methods to Set. As you call add() and remove(), the set maintains its order. You can retrieve subsets (which are also sorted) using the subSet(), headSet(), and tailSet() methods. The first(), last(), and comparator() methods provide access to the first element, the last element, and the object used to compare elements (more on this later).

The last child interface of Set is List. The List interface adds the ability to manipulate elements at specific positions in the list:

public void add(int index, Object element)

This method adds the given object at the supplied list position. If the position is less than zero or greater than the list length, an IndexOutOfBoundsException will be thrown. The element that was previously at the supplied position and all elements after it will be moved up by one index position.

public void remove(int index)

This method removes the element at the supplied position. All subsequent elements will move down by one index position.

public void get(int index)

This method returns the element at the given position.

public void set(int index, Object element)

This method changes the element at the given position to be the supplied object.

List has other methods, but I don't have space to describe them all. In an upcoming section, I'll describe implementations of the collections interfaces.

The Map Interface

The Collections Framework also includes the concept of a Map, which is a collection of key and value pairs. The basic operations are straightforward (and familiar, if you remember the Hashtable class):

public Object put(Object key, Object value)

This method adds the specified key and value pair to this map. If the map already contains a value for the specified key, the old value is replaced.

public Object get(Object key)

Use this method to retrieve the value corresponding to key.

public Object remove(Object key)

This method removes the value corresponding to key from this map.

public int size()

Use this method to find the number of key and value pairs in this map.

You can retrieve all the keys or values in the map:

public Set keySet()

This method returns a Set that contains all of the keys in this map. A Set is returned because there are no duplicate keys--every key maps to only one value.

public Collection values()

Use this method to retrieve all of the values in this map. The returned Collection can contain duplicate elements.

Map has one child interface, SortedMap. SortedMap maintains its key and value pairs in sorted order according to the key values. It provides subMap(), headMap(), and tailMap() methods for retrieving sorted map subsets. Like SortedSet, it also provides a comparator() method that returns an object that determines how the map keys are sorted. I'll talk more about this later.

Implementations

Up until this point, I've only talked about interfaces. But you can't instantiate interfaces. The Collections Framework includes useful implementations of the collections interfaces. These implementations are listed in the table below, according to the interface they implement.

Interface
   Implementation

Set    HashSet

SortedSet    TreeSet

List    ArrayList, LinkedList, Vector

Map    HashMap, Hashtable

SortedMap    TreeMap

ArrayList offers good performance if you add to the end of the list frequently, while LinkedList offers better performance for frequent insertions and deletions. Vector, of course, is the same old Vector class from JDK 1.0, retrofitted to implement the List methods. Vector offers the advantage (and overhead) of synchronized methods, which is essential for multithreaded access. The old Hashtable has been updated so that it now implements the Map interface. It also has the advantage and overhead of synchronized operations. As you'll see, there are other, more general ways to get synchronized collections.

Slam Dunking with Collections

The java.util.Collections class is full of handy static methods that operate on Sets and Maps. (It's not the same as the java.util.Collection interface, which I've already talked about.) Since all the static methods in Collections operate on interfaces, they will work regardless of the actual implementation classes you're using. This is pretty powerful stuff. What can you do with the Collections class methods?

You can create a synchronized version of any collection using one of the following methods:

public static Collection synchronizedCollection(Collection c)
public static Set synchronizedSet(Set s)
public static List synchronizedList(List list)
public static Map synchronizedMap(Map m)
public static SortedSet synchronizedSortedSet(SortedSet s)
public static SortedMap synchronizedSortedMap(SortedMap m)

These methods create synchronized, thread-safe versions of the supplied collection. This is useful if you're planning to access the collection from more than one thread. For more information about synchronized collections, see the documentation for Collections.

Furthermore, you can use the Collections class to create read-only versions of any collection:

public static Collection unmodifiableCollection(Collection c)
public static Set unmodifiableSet(Set s)
public static List unmodifiableList(List list)
public static Map unmodifiableMap(Map m)
public static SortedSet unmodifiableSortedSet(SortedSet s)
public static SortedMap unmodifiableSortedMap(SortedMap m)

Use these methods to create an unmodifiable version of any collection.

Sorting For Free

Collections includes other methods for performing common operations like sorting. Sorting comes in two varieties:

public static void sort(List list)

This method sorts the given list. You can only use this method on lists whose elements implement the java.lang.Comparable interface. Luckily, many classes already implement this interface, including String, Date, BigInteger, and the wrapper classes for the primitive types (Integer, Double, etc.).

public static void sort(List list, Comparator c)

Use this method to sort a list whose elements don't implement the Comparable interface. The supplied java.util.Comparator does the work of comparing elements. You might, for example, write an ImaginaryNumber class and want to sort a list of them. You would then create a Comparator implementation that knew how to compare two imaginary numbers.

Collections gives you some other interesting capabilities, too. If you're interested in finding out more, check out the min(), max(), binarySearch(), and reverse() methods.

A Thrilling Example

Collections are a bread-and-butter topic, which means it's hard to make exciting examples about them. The example in this section reads a text file, parses all its words, counts the number of occurrences, sorts them, and writes the results to another file. It will give you a good feel for how to use collections in your own programs.

import java.io.*;
import java.util.*;

public class WordSort {
public static void main(String[] args) throws IOException {
    // Get the command-line arguments.
    if (args.length < 2) {
      System.out.println("Usage: WordSort inputfile outputfile");
      return;
    }
    String inputfile = args[0];
    String outputfile = args[1];

    // Create the word map. Each key is a word
    //   and each value is an Integer that represents
    //   the number of times the word occurs in the
    //   input file.
    Map map = new HashMap();

    // Read every line of the input file.
    BufferedReader in = new BufferedReader(new FileReader(inputfile));
    String line;
    while ((line = in.readLine()) != null) {
      // Examine each word on the line.
      StringTokenizer st = new StringTokenizer(line);
      while (st.hasMoreTokens()) {
        String word = st.nextToken();
        Object o = map.get(word);
        // If there's no entry for this word, add one.
        if (o == null) map.put(word, new Integer(1));
        // Otherwise, increment the count for this word.
        else {
          Integer count = (Integer)o;
          map.put(word, new Integer(count.intValue() + 1));
        }
      }
    }
    in.close();

    // Get the map's keys and sort them.
    List keys = new ArrayList(map.keySet());
    Collections.sort(keys);

    // Now write the results to the output file.
    PrintWriter out = new PrintWriter(new FileWriter(outputfile));
    Iterator iterator = keys.iterator();
    while (iterator.hasNext()) {
      Object key = iterator.next();
      out.println(key + " : " + map.get(key));
    }
    out.close();
}
}

Suppose, for example, that you have an input file named Ian Moore.txt:

Well it was my love that kept you going
Kept you strong enough to fall
And it was my heart you were breaking
When he hurt your pride
So how does it feel
How does it feel
How does it feel
How does it feel

You could run the example on this file using the following command line:

java WordSort "Ian Moore.txt" count.txt

The output file, count.txt, looks like this:

And : 1
How : 3
Kept : 1
So : 1
Well : 1
When : 1
breaking : 1
does : 4
enough : 1
fall : 1
feel : 4
going : 1
he : 1
heart : 1
how : 1
hurt : 1
it : 6
kept : 1
love : 1
my : 2
pride : 1
strong : 1
that : 1
to : 1
was : 2
were : 1
you : 3
your : 1

The results are case sensitive: "How" is recorded separately from "how." You could modify this behavior by converting words to all lower case after retrieving them from the StringTokenizer:

String word = st.nextToken().toLowerCase();