Java Technology Home Page
A-Z Index

Java Developer Connection(SM)
Books

Downloads, APIs, Documentation
Java Developer Connection
Tutorials, Tech Articles, Training
Online Support
Community Discussion
News & Events from Everywhere
Products from Everywhere
How Java Technology is Used Worldwide
Print Button
 
Book Excerpt Index

Mastering JavaTM
Chapter 17: Java Collections

by John Zukowski

(December 1998)

This is an excerpt from Mastering JavaTM 1.2, published by Sybex Inc. Written by John Zukowski, a long-time contributer to the JDC, this book offers in-depth coverage of Java 2, including such topics as building forms with Swing, creating Java graphics with the 2D API, implementing drag-and-drop support, providing built-in security with the Java Cryptography architecture, integrating your Java program with CORBA, enhancing server-side performance with servlets, and building fast Java solutions. The book comes with a CD that contains all the example code and executable files, along with links to third-party tools to use with Java.

This chapter focuses on supporting advanced data structures with the Collections API.

Developing in Java frequently requires you to work with unknown quantities of objects. Even when working with fixed amounts of objects, sequential access (arrays) is not always the best access method. To support working with groups of objects, Java provides a whole slew of classes. In fact, the concept is so important that how Java handles collections of objects changed dramatically in Java 1.2. An entirely new set of around 25 classes was added to the java.util package to describe the Java Collections API framework.

This chapter reviews data structures. Starting off with the familiar array object, we look at how Java handles a single object representing a group of objects. Next, we go through the various pre-Collections API containers. Although new programs should avoid the historic collection classes, existing programs still use them. Understanding how they work, and their limitations, will help you understand why the new collection classes were added. Finally, the chapter explores the Collections framework introduced in Java 1.2.


NOTE:
If you like the Java 1.2 Collections framework, you can use a subset in Java 1.1. Download the libraries from http://java.sun.com/beans/infobus/#collections and read the informational file at http://java.sun.com/beans/infobus/#collectionsreadme.html for usage instructions.

Arrays Review

Chapter 6 provided an overview of Java arrays. Basically, an array is a fixed-size collection of objects of the same type. Besides storing objects, arrays can also store primitive datatypes. When you create an array, you specify the type of object (or primitive) to store in the array and the number of elements you wish to store. This allows array usage to be type-safe and very efficient. Since you can only store one type of data in an array, you can only get that same type back. Also, since you've allocated all the space for the array at declaration time, placing an element into an array is very fast. But therein lies the potential problem with arrays. You must allocate all their space at once, and they cannot get bigger than you anticipated—at least not without an expensive array copy operation. If you know the datatype beforehand and you know what the final size should be, you're OK with arrays. Otherwise, you need to look at one of Java's other collection classes.

Working with an array is just like working with any other object. You can access its single instance variable length to discover the array's size or you can get the element at a certain location by passing an int to the brackets ([]) of an array reference variable. Array access also always performs bounds checking and throws an ArrayIndexOutOfBoundsException if you attempt to access a nonexistent element.


WARNING:
The index into an array cannot be a long variable. This is a compile-time error, instead of a runtime exception.

The following program demonstrates array usage by performing runtime type checking to determine the array datatype. When the array is an array of integers, the square root of each element is printed. When the array is an array of doubles, the trigonometric sine function is performed:

  public class MyArrays {
    public static void printValues (Object array) {
      if (array instanceof int[]) {
        // Cast to int array
        int intArray[] = (int[])array;
        int len = intArray.length;
        for (int i=0;i<len;i++) {
          System.out.print (
           Math.sqrt (intArray[i]) + " ");
        }
      } else if (array instanceof double[]) {
        // cast to double array
        double doubleArray[] = (double[])array;
        int len = doubleArray.length;
        for (int i=0;i<len;i++) {
          System.out.print (
           Math.sin (doubleArray[i]) + " ");
        }
      }
      System.out.println ();
    }
    public static void main (String args[]) {
      int ints[] = {1, 4, 9, 16, 25, 36};
      double doubles[] = {0.0, Math.PI / 6.0,
          Math.PI / 2.0, 3.0 * Math.PI / 2.0};
      printValues (ints);
      printValues (doubles);
      try {
        ints[90] = 27;
      } catch (ArrayIndexOutOfBoundsException e) {
      System.err.println (
       "Invalid array access:  " + e.getMessage());
      }
    }
  }

The output from running the program follows:

  1.0 2.0 3.0 4.0 5.0 6.0
  0.0 0.49999999999999994 1.0 -1.0
  Invalid array access:  90

NOTE:
The second value on the second line is really 0.5 when rounded off. The print method does not provide the means to format output, and Math.sin(PI/6.0) is not 0.5, because of limitations in the sin routine and/or roundoff in PI and PI/6.0.

Vectors, Stacks, and Enumeration

The historic collection classes have existed since the beginning of Java's time. While there is nothing technically wrong with them, their usage should be limited to the maintenance of Java 1.0 and 1.1 programs. The primary, historic collection classes that provide ordered access are Vector and Stack. The interface Enumeration offers the means to step through the contents.

Working with Vectors

While arrays are required to be of fixed size and have a homogenous datatype, class Vector encapsulates a heterogeneous linked-list and array hybrid:

  • Vectors are heterogeneous because they do not insist on each element being of a certain type—many object types can be mixed within one vector.

  • Vectors are an array hybrid because they can grow dynamically when elements are added.

Here is the definition of Vector:

  public class Vector extends AbstractList
      implements List, Cloneable, Serializable {
    protected int capacityIncrement;
    protected int elementCount;
    protected Object elementData[];
    public Vector();
    public Vector(int initialCapacity);
    public Vector(
     int initialCapacity, 
     int capacityIncrement);
    public Vector(Collection c);
    public void add(int index, Object obj);
    public synchronized boolean add(Object obj);
    public synchronized boolean addAll(
     int index, 
     Collection c);
    public synchronized boolean addAll(Collection c);
    public synchronized void addElement(Object obj);
    public int capacity();
    public void clear();
    public synchronized Object clone();
    public boolean contains(Object obj);
    public synchronized boolean containsAll(Collection c);
    public synchronized void copyInto(Object anArray[]);
    public synchronized Object elementAt(int index);
    public Enumeration elements();
    public synchronized 
      void ensureCapacity(int minCapacity);
    public synchronized boolean equals(Object obj);
    public synchronized Object firstElement();
    public synchronized Object get(int index);
    public synchronized int hashCode();
    public int indexOf(Object obj);
    public synchronized int indexOf(
     Object obj, 
     int startIndex);
    public synchronized void insertElementAt(
     Object obj, 
     int index);
    public boolean isEmpty();
    public synchronized Object lastElement();
    public int lastIndexOf(Object obj);
    public synchronized int lastIndexOf(
     Object obj, 
     int startIndex);
    public synchronized Object remove(int index);
    public boolean remove (Object obj);
    public synchronized removeAll (Collection c);
    public synchronized void removeAllElements();
    public synchronized boolean 
      removeElement(Object obj);
    public synchronized void removeElementAt(int index);
    public synchronized boolean 
      retainAll (Collection c);
    public synchronized Object set(
      int index, Object obj);
    public synchronized void setElementAt(
     Object obj, 
     int index);
    public synchronized void setSize(int newSize);
    public int size();
    public synchronized Object[] toArray();
    public synchronized Object[] toArray(Object aType[]);
    public synchronized String  toString ();
    public synchronized void trimToSize();
  }

NOTE:
If you've used the historical collection classes prior to Java 1.2, you may notice that some of these have been retrofitted into the Collections API added with Java 1.2.

Since vectors can store any datatype, all vector operations work with the Object class. This means you lose the type safety provided by an array. And, whenever you access anything acquired from a vector, you have to cast it back to its original type. This, and the cost associated with dynamic growth, are the penalties associated with using Vector.

While working with arrays, you access the size with the length instance variable and set elements with an assignment (=) operation. For a vector, the length is acquired with the size() method and assignment is via the set(int position, Object obj) or setElementAt(Object obj, int position) method. Neither set() nor setElementAt() support dynamic growth. For a vector to grow without bounds, you would use either add(Object obj) or addElement(Object obj), which both add the object at the end. Retrieval of elements is via either the get(int position) or the getElement(int position) method.


TIP:
If you need to store a primitive datatype within a vector, or any other collection besides an array, you need to use the wrapper classes found in the java.lang package. For instance, to store an int, you wrap it into an Integer: Integer in = new Integer (5). Then, you can add the Integer object in to the collection.

To demonstrate the vector class, the following program works with some of its basic operations. It stores planets in a vector and then prints out each planet object, using the implicit call to Object.toString () made by println().

  import java.util.*;
  public class ThePlanets {
    static class Planet {
    private String name;
    Planet (String  s) {
      name = s;
    }
    public String  toString () {
      return getClass().getName() + "[" + name + "]";
    }
  }
  public static void main (String  args[]) {
    String  names[] = {"Mercury", "Venus", "Earth",
      "Mars", " Jupiter", "Saturn", "Uranus",
      "Neptune", "Pluto"};
    int namesLen = names.length;
    Vector planets = new Vector (namesLen);
    for (int i=0; i < namesLen; i++) {
      planets.addElement (new Planet (names[i]));
    }
    int planetsLen = planets.size();
    for (int i=0; i < planetsLen; i++) {
      System.out.println (planets.elementAt (i));
    }
    }
}

While this shows the basic vector operations, you will frequently need to do something more with each element retrieved from the vector than an operation inherited from Object. The following example extends the first by adding the number of moons to each planet definition. Instead of using the toString() method to print the planet data, specific methods of Planet are used to get information about the vector elements:

  import java.util.*;
  public class ThePlanetsAndMoons {
    static class Planet {
      private String  name;
      private int moonCount;
      Planet (String  s, int moons) {
        name = s;
        moonCount = moons;
      }
      public String  toString () {
        return getClass().getName() + 
         "[" + name + "-" + moonCount + "]";
      }
      public final String  getName() {
        return name;
      }
      public final int getMoonCount () {
        return moonCount;
      }
    }
    public static void main (String  args[]) {
      String  names[] = {"Mercury", "Venus", "Earth",
        "Mars", "Jupiter", "Saturn", "Uranus",
        "Neptune", "Pluto"};
      int moons[] = {0, 0, 1, 2, 16, 18, 17, 8, 1};
      
      
      int namesLen = names.length;
      Vector planets = new Vector (namesLen);
      for (int i=0; i < namesLen; i++) {
        planets.addElement (
         new Planet (names[i], moons[i]));
      }
      Planet p;
      int planetsLen = planets.size();
      for (int i=0; i < planetsLen; i++) {
        p = (Planet)(planets.elementAt (i));
        System.out.println (
         p.getName() + " :  " + p.getMoonCount());
      }
    }
  }

To demonstrate the potential for problems, the following defines a new class Comet and adds one to the planets vector used previously. Since Vector allows you to add anything to the vector, addElement() doesn't cause any problems. However, when you cast the value retrieved with elementAt() to a Planet, you'll get a ClassCastException thrown:

  static class Comet {
    private String name;
    Comet (String s) {
      name = s;
    }
    public String toString() {
      return getClass().getName() + "[" + name + "]";
    }
    public final String getName() {
      return name;
    }
  }
  …
  planets.addElement (new Comet ("Hale-Bopp"));
  …
    // Exception thrown here for Comet
    p = (Planet)(planets.elementAt (i));

This just goes to show that you should always know what you are getting out of a collection when you use any of them.


NOTE:
For an online multimedia tour of the solar system, stop by http://seds.lpl.arizona.edu/nineplanets/nineplanets/nineplanets.html .

TIP:
In C++, the ability to specify the use of a specific datatype for something at compile-time is supported directly in the language by templates. The concept itself is called parameterized types. Java provides support for neither parameterized types nor collections of a specific datatype.

Pushing Stacks

Class Stack implements that old faithful data structure: a simple last-in-first-out (LIFO) stack. In Java, the Stack class is actually a subclass of Vector. So, in addition to all the vector operations, you can also push objects onto the stack, pop objects off the stack, peek at the object on the top of the stack, check whether the stack is empty, and search for an object on the stack. The definition of class Stack shows off this functionality:

  public class Stack extends Vector {
    public Stack();
    public boolean empty();
    public synchronized Object peek();
    public synchronized Object pop();
    public Object push (Object obj);
    public synchronized int search (Object obj);
  }

The following provides a simple demonstration of the Stack class. Notice that the Vector methods are available since Stack is a subclass; however, they should be avoided for the sake of clarity:

  import java.util.Stack;
  public class JupiterMoons {
    public static void main (String  args[]) {
      String  names[] = {
        "Metis", "Adrastea", "Amalthea", 
        "Thebe", "Io", "Europa", "Ganymede", "Callisto", 
        "Leda", "Himalia", "Lysithea", "Elara",  
        "Ananke", "Carme", "Pasiphae", "Sinope"
      };
      int namesLen = names.length;
      Stack moons = new Stack ();
      for (int i=0; i < namesLen-1; i++) {
        moons.push (names[i]);
      }
      // Vector methods still work
      moons.addElement (names[namesLen-1]);
      while (!moons.empty()) {
        System.out.print (moons.pop() + " ");
      }
      System.out.println();
    }
  }

Running the program generates the following output:

  Sinope Pasiphae Carme Ananke Elara Lysithea 
  Himalia Leda Callisto Ganymede Europa Io Thebe 
  Amalthea Adrastea Metis

Stepping through Enumerations

While the Vector and Stack classes have natural orderings, there are times when you don't really care about the actual order a collection is traversed, only that every node is visited. Or, you may only care that you have a collection of objects, not what the underlying data structure is. This allows you to think at a higher level during your application's design. For instance, there may come a time when a vector is inefficient because you need frequent additions in the middle of a collection. If that time comes, you shouldn't need to change everything just because you want to use a LinkedList (found in Java 1.2) instead of a Vector. The appropriate Java 1.1 interface that offers that level of abstraction is Enumeration, defined here:

  public interface Enumeration {
    public abstract boolean hasMoreElements();
    public abstract Object nextElement();
  }

NOTE:
The Gamma, et al., Design Patterns book (Addison Wesley, ISBN 0-201-63361-2) describes this pattern as an Iterator. In Java 1.2, Iterator is the actual interface name used to represent the behavior.

The Enumeration interface requires any collection-oriented class to implement two methods: hasMoreElements() and nextElement(). These two methods mean that any object that supports enumerating its components can be explored using the following while loop:

  Enumeration enum = 
   someContainer.methodReturningEnumeration();
  while (enum.hasMoreElements()) {
    Object obj = enum.nextElement();
    // process this object
  }

When working with Vector, you get the set of elements with the elements() method. Since Stack is a subclass of Vector, you use elements() there, too. Now, instead of the following block of code from the earlier example:

  Planet p;
  for (int i=0, n=planets.size(); i < n; i++) {
    p = (Planet)(planets.elementAt (i));
    System.out.println (
     p.getName() + " :  " + p.getMoonCount());
  }

you would walk through the planets enumeration with this code:

  Enumeration enum = planets.elements();
  Planet p;
  while (enum.hasMoreElements()) {
    p = (Planet)(enum.nextElement());
    System.out.println (
     p.getName() + " :  " + p.getMoonCount());
  }

When creating your own types of collections, you need to implement the two methods of Enumeration interface. The following program demonstrates this by converting any array into an Enumeration; just pass your array to ArrayEnumerationFactory.makeEnumeration() and you're all set.

  import java.lang.reflect.Array;
  import java.util.Enumeration;
  final public class ArrayEnumerationFactory {
    static public Enumeration makeEnumeration (
     final Object obj) {
      Class type = obj.getClass();
    if (!type.isArray()) {
      throw new IllegalArgumentException (
       obj.getClass().toString ());
    } else {
      return (new Enumeration() {
        int size = Array.getLength(obj);
        int cursor;
        public boolean hasMoreElements() {
          return (cursor<size);
        }
        public Object nextElement() {
          return Array.get (obj, cursor++);
        }
      });
    }
  }
  public static void main (String  args[]) {
    Enumeration enum = makeEnumeration (args);
    while (enum.hasMoreElements()) {
      System.out.println (enum.nextElement());
    }
    enum = makeEnumeration (new int[] {1, 3, 4, 5});
    while (enum.hasMoreElements()) {
      System.out.println (enum.nextElement());
    }
    try {
      enum = makeEnumeration (new Double(Math.PI));
    } catch (IllegalArgumentException e) {
      System.err.println (
       "Can't enumerate that:  " + e.getMessage());
    }
  }
}

The class includes a sample test run in the main() method. Running the program with the following input:

java ArrayEnumerationFactory one two three

produces the following output:

  one
  two
  three
  1
  3
  4
  5
  Can't enumerate that:  class java.lang.Double

Dictionaries, Hashtables, and Properties

While arrays, vectors, and stacks provide ordered access to your collections' contents, maintaining that order can be costly. To provide an alternative collection methodology where order or sequential access isn't necessary, Java provides support for key-value pair collections. Instead of looking up elements by an integer position, you provide a key for every value you would like to place in your collection, like a lookup map. Figure 17.1 shows an example of this lookup scheme.

The abstract class to support this concept in the historical collections group is Dictionary. Hashtable and Properties provide two specific implementations of these capabilities.

Figure 17.1: Dictionary lookup example

Thumbing through Dictionaries

The abstract Dictionary class describes the interface for working with key-value maps. The way a dictionary works is if you provide an object as a key, it will return at most one object as its value from the collection. If the key isn't in the map, you get nothing back, or null in Java terms. The same object can be the value for multiple keys. However, the key can only be the handle for one value term. How the actual key-value pairs are stored is dependent on the specific implementation. The abstract Dictionary definition follows:

 public abstract class Dictionary {
   public Dictionary();
   public abstract Enumeration elements();
   public abstract Object get(Object);
   public abstract boolean isEmpty();
   public abstract Enumeration keys();
   public abstract Object put(Object, Object);
   public abstract Object remove(Object);
   public abstract int size();
  }

NOTE:
Technically speaking, Dictionary should be an interface as all the methods are abstract. Apparently, Dictionary predates the concept of interfaces within Java, so it is just an abstract class. Since Dictionary is one of those historical collection classes, you should really use the Map interface, introduced in Java 1.2, when working with key-value collections.

Living with Hashtables

The Hashtable class represents a concrete implementation of the Dictionary architecture, shown here:

  public class Hashtable extends Dictionary
      implements Map, Cloneable, Serializable {
    public Hashtable();
    public Hashtable(int initialCapacity);
    public Hashtable(
      int initialCapacity, float loadFactor);
    public Hashtable(Map m);
    public synchronized void clear();
    public synchronized Object clone();
    public synchronized boolean contains(Object value);
    public synchronized boolean containsKey(Object key);
    public boolean containsValue(Object value);
    public synchronized Enumeration elements();
    public Set entrySet();
    public synchronized boolean equals(Object obj);
    public synchronized Object get(Object key);
    public synchronized int hashCode();
    public boolean isEmpty();
    public Set keySet();
    public synchronized Enumeration keys();
    public synchronized Object put(
      Object key, Object value);
    public synchronized void putAll(Map m);
    protected void rehash();
    public synchronized Object remove(Object key);
    public int size();
    public synchronized String toString();
    public Collection values();
  }

The class name is so called because of the means of storing the keys. When you provide the key for a value to the hashtable, the data structure generates a hash code and uses that as the means to look up the value when it is necessary to retrieve it. As long as the algorithm for generating the hash codes always generates the same value for the same key (two keys are equivalent if equals() says so) and distributes the codes as evenly as possible, the hashtable represents an efficient means of storing key-value pairs. The means of generating a key's hash code is by the hashCode() method, either the one from Object, or an overridden version from a subclass.


NOTE:
Two entries are not necessarily equal if hashCode() returns the same value. In fact, if many entries result in the same hash code value, this is usually the result of a poor hashing algorithm. If you've overridden the hashCode() method, you should redesign how you generate hash codes for instances of your class. For instance, the length of a String is a bad hashing algorithm, as many unequal strings would have the same code.

The operations you can do with a Hashtable are mostly inherited from Dictionary (or part of the new Map interface).

  • Adding a key-value pair is done with put (Object key, Object value)

  • Getting a value for a key is done with get (Object key)

  • Removing an element is done with remove (Object key)

  • Checking the size is done with size()

  • Checking if the size is 0 is done with empty()

  • Getting the set of all keys or values is done with keys() or elements(), which both return an Enumeration

  • Getting the set of all keys or values for use with the newer Collections API is done with keySet() or entrySet(), which both return a Set

Additionally, Hashtable allows you to empty out the collection with clear(), check if a specific key is present with containsKey (Object key), or even check if a value is present with containsValue (Object value). The last operation, while possible, is very expensive since a hashtable is being used backwards.

Using the planet names as the keys and the planet diameter (in kilometers) as the values, the following demonstrates the use of Hashtable:

  import java.util.Enumeration;
  import java.util.Hashtable;
  public class PlanetDiameters {
    public static void main (String  args[]) {
      String  names[] = {"Mercury", "Venus", "Earth",
        "Mars", "Jupiter", "Saturn", "Uranus",
        "Neptune", "Pluto"};
      float diameters[] = {4800f, 12103.6f, 12756.3f,
        6794f, 142984f, 120536f, 51118f, 49532f, 2274f};
      Hashtable hash = new Hashtable();
      for (int i=0, n=names.length; i < n; i++) {
        hash.put (names[i], new Float (diameters[i]));
      }
      Enumeration enum = hash.keys();
      Object obj;
      while (enum.hasMoreElements()) {
        obj = enum.nextElement();
        System.out.println (
          obj + ":  " + hash.get(obj));
      }
    }
  }

Running the program produces the following results:

  Earth: 12756.3
  Mercury:  4800.0
  Uranus:  51118.0
  Pluto:  2274.0
  Saturn:  120536.0
  Jupiter:  142984.0
  Neptune:  49532.0
  Venus:  12103.6
  Mars:  6794.0

Notice that the resulting order has absolutely no correlation to the order the elements were added. Also, like with Vector, the get() routine returns an Object. If you need to call a method of the specific class that was added into the table, you have to cast the value returned to the appropriate class.

Examining Properties

When the objects to store in your hashtable are strings, you should consider using the Properties class. Instead of having to cast return values to the String class, the Properties class does this for you with its supporting methods:

  public class Properties extends Hashtable {
    protected Properties defaults;
    public Properties();
    public Properties(Properties defaults);
    public String getProperty(String key);
    public String getProperty(
     String key, 
     String defaultValue);
    public void list(PrintStream out);
    public void list(PrintWriter out);
    public synchronized void load(InputStream in) 
     throws IOException;
    public Enumeration propertyNames();
    public synchronized Object put(
     Object key, 
     Object value);
    public synchronized Object setProperty(
     String  key, 
     String  value);
    public synchronized void store(
     OutputStream out, 
     String  header)
     throws IOExcepition
  }

Since Properties is a Dictionary subclass, you can continue to add entries with put() and retrieve entries with get(). However, these methods work with Object values. The more natural way to work with the Properties class is with the following methods:

  • Adding a key-value String pair is done with setProperty (String key, String value).

  • Getting a value for a key is done with getProperty(String key) or getProperty(String key, String defaultValue), for when key is not set.

  • Getting the set of all keys is done with propertyNames() instead of keys(). Properties can have default values. Using propertyNames() creates an Enumeration that is the union of the keys() and the default values.

Besides the convenience methods, you can also load properties from an input stream, like a file, or save them, with load() and store() respectively. (The save() method was deprecated because it didn't throw an IOException when there were problems saving.) The way property settings are specified in a text file is separated by an equal sign (=).

If the file planet.properties contained the following values:

  Mercury=god of commerce, travel and thievery
  Venus=goddess of love and beauty
  Earth=not derived from Greek/Roman mythology
  Mars=god of War
  Jupiter=King of the Gods
  Saturn=god of agriculture
  Uranus=deity of the Heavens
  Neptune=god of the Sea
  Pluto=god of the underworld

you would have nine properties, one for each planet name. The following program would then load the file, add a new property for a fictitious 10th planet, save the properties to a new file, list all properties and values to standard output, and finally locate a specific one:

  import java.io.*;
  import java.util.Properties;
  public class PlanetProperties {
    public static void main (
     String  args[]) throws IOException {
      String  header = "A header";
      Properties props = new Properties();
      props.load (new FileInputStream (
       "planets.properties"));
      props.setProperty ("Planet X", "god of dreams");
      props.store (new FileOutputStream (
       "save.the.planets"), header);
      props.list (System.out);
      System.out.println (props.getProperty ("Pluto"));
    }
  }

The most common use of Properties is with a list of system properties. If you ask the System class for its list of properties (getProperties()), you can find out information like the version of Java the person running the program is using, the URL of where to send bug reports for that specific version of Java, and even what directory to store temporary files in. Just add System.getProperties().list (System.out); to the previous program to see.

Bit Sets

Class BitSet implements a set of bits or a vector of boolean values. Unlike many of the other bit set classes or language features in other languages, this bit set has no limits. You can therefore go way beyond the typical 32- or 256-bit limits imposed by other implementations. First, let's look at the class definition:

  public class BitSet 
      implements Cloneable, Serializable {
    public BitSet();
    public BitSet(int nbits);
    public void and(BitSet set);
    public void andNot(BitSet set);
    public void clear(int bitIndex);
    public Object clone();
    public boolean equals(Object obj);
    public boolean get(int bitIndex);
    public int hashCode();
    public int length();
    public void or(BitSet set);
    public void set(int bitIndex);
    public int size();
    public String  toString ();
    public void xor(BitSet set);
  }

BitSet operations include the following:

  • Setting, clearing, and getting single bits

  • Anding, and notting, oring, and xoring bit sets together

  • Comparing bit sets

The following program demonstrates their usage, by placing in a BitSet whether or not a planet has an even number of moons. Normally, you would store much larger groups of bits in a BitSet to truly save space:

  import java.util.*;
  public class TwoBitPlanets {
    public static void main (String  args[]) {
      String  names[] = {"Mercury", "Venus", "Earth",
      "Mars", "Jupiter", "Saturn", "Uranus",
      "Neptune", "Pluto"};
    int moons[] = {0, 0, 1, 2, 16, 18, 17, 8, 1};
    
    int namesLen = names.length;
    BitSet bits = new BitSet(namesLen);
    for (int i=0; i < namesLen; i++) {
      if ((moons[i] % 2) == 0) {
        bits.set (i);
      }
    }
    for (int i=0; i < namesLen; i++) {
      System.out.println (
       names[i] + " Even # Moons?  " + bits.get(i));
    }
  }
}

NOTE:
Although BitSet is part of the historical collection classes, the new Collections framework has no replacement. Also, the size() method of BitSet returns the size of the internal structure used, not necessarily the maximum bit number utilized. Since the bit values are stored with the help of a double, size() jumps up by 64 when necessary. More frequently you want the length() method, which returns the highest set bit position.

Collections and Iterators

The world of Java collection classes was overturned in Java 1.2. A set of about 25 classes was added to the java.util package to define the Java Collections API. Figure 17.2 shows the class hierarchy diagram showing the makeup of this framework.


Figure 17.2: The Collections Framework Class Hierarchy diagram

As the diagram shows, the four interfaces, Collection, List, Map, and Set, describe the different types of collections. For each type of collection, there are specific implementations, depending upon the type of data structure used to store the collection. These are the classes like ArrayList, TreeSet, and HashMap. The remaining classes in the hierarchy are support related. For instance, the Iterator interface replaces the Enumeration interface from the historical collection classes.

When working with the various framework classes, you always have to create specific implementations of the data structures, as the system needs to know how to store objects within the collection. However, when you access the actual collection, you should use the interface methods. This allows you to change data structures, for instance, from an array-backed collection to a hashtable-backed one, if the circumstances require it. Then, since the collection class still implements the same collection interface, no other code will need to change. For instance, the following shows how you would create a HashMap:

Map phoneBook = new HashMap();

If later you decide to maintain a sorted phone book, you can change the data structure from a HashMap to a TreeMap:

Map phoneBook = new TreeMap ();

Since you only accessed the phoneBook variable through the Map interface, the rest of your code would stay the same, and your phone list will always be sorted.

Of the four primary interfaces, Collection and Map are the basic two. A Collection is any group of objects, while Map is like Dictionary and works with key-value pairs. Two interfaces extend Collection: Set and List. A Set behaves like its mathematical definition: no duplicates; while List preserves a sequence or ordering, similar to Vector's behavior. The SortedMap and SortedSet interfaces offer sorted traversal through the elements of Map and Set respectively.

To get started with the new API, let's look at the Collection interface definition:

  public interface Collection {
    public abstract boolean add(Object obj);
    public abstract boolean addAll(Collection c);
    public abstract void clear();
    public abstract boolean contains(Object obj);
    public abstract boolean containsAll(Collection c);
    public abstract boolean equals(Object obj);
    public abstract int hashCode();
    public abstract boolean isEmpty();
    public abstract Iterator iterator();
    public abstract boolean remove(Object obj);
    public abstract boolean removeAll(Collection c);
    public abstract boolean retainAll(Collection c);
    public abstract int size();
    public abstract Object[] toArray();
    public abstract Object[] toArray(Object obj[]);
  }

Collection operations include the following:

  • Adding elements

  • Removing elements

  • Checking the contents

  • Working with the elements

Most of the operations are self-explanatory. However, a couple deserve a little explanation. The retainAll() method combines two collections by performing the set theory intersection operation. The original collection is modified to include any elements in the Collection parameter that are not already members of the collection. The toArray() method allows you to convert a Collection into an array. This may be necessary for historical purposes, where you need to send a set of data to another program that doesn't work with the collection classes yet. The following program demonstrates the capabilities of the Collection interface, using the soon-to-be-described ArrayList class as the data structure:

  import java.util.*;
  public class PlanetSet {
    public static void main (String  args[]) {
      String  names[] = {"Mercury", "Venus", "Earth",
        "Mars", "Jupiter", "Saturn", "Uranus",
        "Neptune", "Pluto"};
      int namesLen = names.length;
      Collection planets = new ArrayList();
      for (int i=0; i < namesLen; i++) {
        planets.add (names[i]);
      }
      Object s[] = planets.toArray();
      String  s[] = (
        String [])planets.toArray(new String [0]);
      for (int i=0, n=s.length; i < n; i++) {
        System.out.println (s[i]);
      }
      planets.remove (names[3]);
      System.out.println (
       names[1] + 
       " " + 
       planets.contains (names[1]));
      System.out.println (
       names[3] + 
       " " + 
       planets.contains (names[3]));
    }
  }

In order to access each element of the collection, the toArray() method was used. While this works perfectly well, the more appropriate way to do this is with the Iterator interface. This interface, defined here, replaces the Enumeration interface from the historical collection classes:

  public interface Iterator {
    public abstract boolean hasNext();
    public abstract Object next();
    public abstract void remove();
  }

As with Enumeration, you can have a similar while loop to get through all the elements. Thankfully, the method names are a little nicer and a remove() method has been added. The new remove() method is actually an optional interface method, though. Yes, this sounds contradictory — an optional interface method — but it actually is the truth. When a collection doesn't support removing entries during iteration, or ever, the method will throw the new exception UnsupportedOperationException.


WARNING:
This is not the only place you will see UnsupportedOperationException possibly thrown. Various modification methods of the collection classes are considered optional and will throw this exception. While this is a RuntimeException, programmatically trying to perform an unsupported operation is a programming error that should be encountered, and corrected, before a program reaches real users.

In the previous example, you can print the contents of every element of the collection with the following code:

  Iterator it = planets.iterator();
  while (it.hasNext()) {
    System.out.println (it.next());
  }

Now that we've described the top-level collection framework, let's take a look at some of the concrete implementations.


The Generic Collection Library

ObjectSpace offers a Java package called the Generic Collection Library for Java (JGL). (The acronym comes from a prior name that infringed on Sun's Java trademark.)

For any developer transitioning from C++, JGL offers a set of collection classes that is consistent with the C++ Standard Template Library (STL). Prior to the 1.2 JDK, it was probably the best collections-oriented package available, and many IDE vendors licensed it for inclusion with their tools.

However, although similarities to the STL were JGL's strong selling points, it required a large framework for support. The Java Collections API introduced in the 1.2 JDK is much smaller in size and appears, conceptually, to be easier to understand.

For more information on the JGL package, stop by its Web site at http://www.objectspace.com .

Sets

As previously mentioned, a set is a collection with no duplicates. Since this doesn't add any new behavior, only adding stipulations to existing behavior, the Set interface is identical to the Collection interface. To avoid duplication, adding elements to a set relies on the equals() method of the element being added to establish the uniqueness of the object.

There are two specific types of sets with which you can work. The recommended general-purpose Set data structure is HashSet. A HashSet is a Set collection backed by a hashtable. Like the Hashtable class, elements added to the hashtable need to implement the hashCode() method.

The other set structure is good under specific circumstances. The TreeSet is the other available Set implementation. As the name implies, it is backed by a (balanced) tree data structure. If ordering is important, then TreeSet is the set collection of choice. The TreeSet class relies on the methods in the SortedSet interface, shown here, when examining the tree in an ordered fashion:

  public interface SortedSet extends Set {
    public abstract Comparator comparator();
    public abstract Object first();
    public abstract SortedSet 
      headSet(Object toElement);
    public abstract Object last();
    public abstract SortedSet subSet(
     Object fromElement, 
     Object toElement);
    public abstract SortedSet tailSet(
     Object fromElement);
  }

The following program demonstrates using the Set interface. The primary goal here is to show that duplicates are not added to the set:

  import java.util.*;
  public class MoonSet {
    public static void main (String  args[]) {
      String  names[] = {"Metis", "Adrastea", "Amalthea", 
        "Thebe", "Io", "Europa", "Ganymede", "Callisto", 
        "Leda", "Himalia", "Lysithea", "Elara", "Ananke", 
        "Carme", "Pasiphae", "Sinope"
      };
      Set moons = new HashSet ();
      int namesLen = names.length;
      int index;
      for (int i=0; i < 100; i++) {
        index =  (int)(Math.random()*namesLen);
        moons.add (names[index]);
      }
      Iterator it = moons.iterator();
      while (it.hasNext()) {
        System.out.println (it.next());
      }
    }
  }

Lists and ListIterator

The List interface is your basic positional collection. When you add elements to a list, you can add each at a specific position or at the end. The following shows the interface's definition:

  public interface List extends Collection {
    public abstract void add(int index, Object element);
    public abstract boolean add(Object obj);
    public abstract boolean addAll(
      int index, Collection c);
    public abstract boolean addAll(Collection c);
    public abstract void clear();
    public abstract boolean contains(Object obj);
    public abstract boolean containsAll(Collection c);
    public abstract boolean equals(Object obj);
    public abstract Object get(int index);
    public abstract int hashCode();
    public abstract int indexOf(Object obj);
    public abstract boolean isEmpty();
    public abstract Iterator iterator();
    public abstract int lastIndexOf(Object obj);
    public abstract ListIterator listIterator();
    public abstract ListIterator listIterator(
     int startPosition);
    public abstract Object remove(int);
    public abstract boolean remove(Object obj);
    public abstract boolean removeAll(Collection c);
    public abstract boolean retainAll(Collection c);
    public abstract Object set(
      int index, Object element);
    public abstract int size();
    public abstract subList(int fromIndex, int toIndex);
    public abstract Object[] toArray();
  }

There are two specific implementations of List in the Collections framework: ArrayList and LinkedList. An ArrayList is similar in functionality to a Vector — both maintain the collection within a resizable array. When maintaining List-type collections, you will probably maintain them in an ArrayList. The downfall of ArrayList is if you must do frequent inserts and removals in the middle of the list, which is where LinkedList shines. LinkedList is a doubly linked list, with references to the previous and next elements at each node. Because of this linkage, sequential access is satisfactory, but random access is slow, relative to an ArrayList.

Class ArrayList provides two methods and three constructors, in addition to the List interface methods. In addition, ArrayList implements the Cloneable interface:

  public ArrayList();
  public ArrayList(int initialCapacity);
  public ArrayList(Collection c);
  public Object clone();
  public void ensureCapacity(int minCapacity);
  public void trimToSize();

The LinkedList class has its own set of constructors and methods to add, as well as also implementing Cloneable:

  public LinkedList();
  public LinkedList(Collection c);
  public void addFirst(Object obj);
  public void addLast(Object obj);
  public Object clone();
  public Object getFirst();
  public Object getLast();
  public Object removeFirst();
  public Object removeLast();

If you desire a stack data structure, you can use LinkedList and add elements with addFirst() and remove them with removeFirst(). For a first-in-first-out (FIFO) queue, you would add with addLast() and remove with removeFirst(); the reverse is also possible, addFirst()/removeLast(); however, it seems more natural to add to the end and remove from the beginning.

The following example revisits the planets and moon count example from the previous Vector example, listing the planets in reverse order:

  import java.util.*;
  public class PlanetsAndMoonsList {
    static class Planet {
      private String  name;
      private int moonCount;
      Planet (String  s, int moons) {
        name = s;
        moonCount = moons;
      }
      public String  toString () {
        return getClass().getName() + 
         "[" + name + "-" + moonCount + "]";
      }
      public final String  getName() {
        return name;
      }
      public final int getMoonCount () {
        return moonCount;
      }
    }
    public static void main (String  args[]) {
      String  names[] = {"Mercury", "Venus", "Earth",
        "Mars", "Jupiter", "Saturn", "Uranus",
        "Neptune", "Pluto"};
      int moons[] = {0, 0, 1, 2, 16, 18, 17, 8, 1};
      
      int namesLen = names.length;
      List planets = new ArrayList (namesLen);
      for (int i=0; i < namesLen; i++) {
        planets.add (new Planet (names[i], moons[i]));
      }
      for (int i=planets.size()-1; i >= 0; --i) {
        Planet p = (Planet)(planets.get (i));
        System.out.println (p.getName() + 
         " :  " + p.getMoonCount());
      }
    }
  }

Working with ListIterator

While the Iterator interface is available for every Collection, those collections that also implement the List interface have the ListIterator interface available to them, as well. Instead of just providing uni-directional traversal of a collection, with possible removal of elements, ListIterator is bi-directional, with possible removal, replacement, and addition of elements. Here is its definition:

  public interface ListIterator Iterator {
    public abstract void add(Object obj);
    public abstract boolean hasNext();
    public abstract boolean hasPrevious();
    public abstract Object next();
    public abstract int nextIndex();
    public abstract Object previous();
    public abstract int previousIndex();
    public abstract void remove();
    public abstract void set(Object obj);
  }

The following program demonstrates the interface by rearranging the solar system:

  import java.util.*;
  public class MovingPlanets {
    public static void main (String  args[]) {
      String  names[] = {"Mercury", "Venus", "Earth",
        "Mars", "Jupiter", "Saturn", "Uranus",
        "Neptune", "Pluto"};
      int namesLen = names.length;
      List planets = new ArrayList();
      for (int i=0; i < namesLen; i++) {
        planets.add (names[i]);
      }
      ListIterator lit = planets.listIterator();
      String  s;
      lit.next();
      lit.next();
      s = (String )lit.next();
      lit.remove();
      lit.next();
      lit.next();
      lit.next();
      lit.add(s);
      lit.next(); // Gets back just added
      lit.previous();
      lit.previous();
      s = (String )lit.previous();
      lit.remove();
      lit.next();
      lit.next();
      lit.add(s);
      
      Iterator it = planets.iterator();
      while (it.hasNext()) {
        System.out.println (it.next());
      }
    }
  }

The output from running this program follows:

  Mercury
  Venus
  Mars
  Saturn
  Earth
  Jupiter
  Uranus
  Neptune
  Pluto

TIP:
If next() or previous() went past an end of the List, NoSuchElementException would be thrown.

Maps

Like a Dictionary or phone book, a Map is used to maintain key-value pair collections. Every entry in the collection is added by providing a value and the key to look it up. If someone asks you for Joe's phone number, and you don't know his number, you look it up in a phone book. The key here is "Joe," and the value is his phone number. The actual definition of the Map interface follows:

  public interface Map {
    public abstract void clear();
    public abstract boolean containsKey(Object key);
    public abstract boolean containsValue(Object value);
    public abstract Set entrySet();
    public abstract boolean equals(Object obj);
    public abstract Object get(Object key);
    public abstract int hashCode();
    public abstract boolean isEmpty();
    public abstract Set keySet();
    public abstract Object put(
      Object key, Object value);
    public abstract void putAll(Map m);
    public abstract Object remove(Object key);
    public abstract int size();
    public abstract Collection values();
  }

Besides adding entries and looking up values, you can work with three collections of the Map: the set of keys (keySet()), the collection of values (values()), and a set of both (entrySet()). If you ask for both, each element of the collection is an instance of the Map.Entry inner-interface, defined here:

  public static interface Map.Entry {
    public abstract boolean equals(Object obj);
    public abstract Object getKey();
    public abstract Object getValue();
    public abstract int hashCode();
    public abstract Object setValue(Object value);
  }

Three concrete implementations of Map are provided with the collection classes: HashMap, WeakHashMap, and TreeMap. HashMap serves as your general-purpose map, backed by a hashtable. WeakHashMap is your map backed by a hashtable with weak references; if you do not retain a reference to a key outside the map, the garbage collector can free it.


NOTE:
Examine the java.lang.ref.WeakReference class and http://java.sun.com/products/jdk/1.2/docs/guide/refobs/ for more information about weak references.

TreeMap is your map backed by a balanced tree. When looking at its keys or values, these collections will be sorted. If sorting is a must, but you don't want the cost associated with adding a node, you can sort a HashMap after all the nodes have been added, when you truly need to get the results sorted:

  Map map = new HashMap()
  // add entries
  map = new TreeMap (map);

The following example converts the earlier planet-diameter example to use a TreeMap:

  import java.util.*;
  public class DiameterMap {
    public static void main (String  args[]) {
      String  names[] = {"Mercury", "Venus", "Earth",
        "Mars", "Jupiter", "Saturn", "Uranus",
        "Neptune", "Pluto"};
      float diameters[] = {4800f, 12103.6f, 12756.3f,
        6794f, 142984f, 120536f, 51118f, 49532f, 2274f};
      Map map = new TreeMap();
      for (int i=0, n=names.length; i < n; i++) {
        map.put (names[i],
         new Float (diameters[i]));
      }
      Iterator it = map.keySet().iterator();
      Object obj;
      while (it.hasNext()) {
        obj = it.next();
        System.out.println (obj + ":  " + map.get(obj));
      }
    }
  }

Now, the output will appear in sorted planet name (key) order:

Earth:  12756.3
Jupiter:  142984.0
Mars:  6794.0
Mercury:  4800.0
Neptune:  49532.0
Pluto:  2274.0
Saturn:  120536.0
Uranus:  51118.0
Venus:  12103.6

TreeMap is the only map that allows you to get a submap: headMap(Object toKey) returns a map of everything less than key, tailMap(Object fromKey) returns a map of everything greater than key, while subMap(Object fromKey, Object toKey) returns a map within a certain range. These are all part of the SortedMap interface, described here:

  public interface SortedMap extends Map {
    public abstract Comparator comparator();
    public abstract Object firstKey();
    public abstract SortedMap headMap(Object toKey);
    public abstract Object lastKey();
    public abstract SortedMap subMap(
     Object fromKey, 
     Object toKey);
    public abstract SortedMap tailMap(Object toKey);
  }

Synchronization and Readability

If you've used the historical collection classes of Java, you know that one of their biggest problems is performance. It's not that they were designed to be slow; they were designed to always be thread-safe. That means if you have multiple running threads accessing a single data structure, all access to the data structure is safe and synchronized appropriately. This is great when you have multiple running threads accessing a single data structure. However, when you do not require the synchronized behavior, there is no way to turn it off. All usage of classes like Hashtable and Vector are synchronized.

The collection classes added with Java 1.2 take another route. Instead of synchronizing everything, they synchronize nothing. If you need the synchronized behavior, after you have a collection to work with, you ask the Collections class to make it synchronized. Defined here, the Collections class provides this and other behavior to be described shortly. Since all the methods of Collections are static, and the constructor is private, you do not need to, nor can you, create any instances of the class:

  public class Collections {
    public static final List EMPTY_LIST;
    public static final Set EMPTY_SET;
    public static int binarySearch(
      List list, Object key);
    public static int binarySearch(
     List list, 
     Object key, 
     Comparator comp);
    public static void copy(List to, List from);
    public static Enumeration enumeration(
      Collection coll);
    public static void fill(List list, Object o);
    public static Object max(Collection coll);
    public static Object max(
     Collection coll, 
     Comparator comp);
    public static Object min(Collection coll);
    public static Object min(
     Collection coll, 
     Comparator comp);
    public static List nCopies(int count, Object obj);
    public static void reverse(List list);
    public static Comparator reverseOrder();
    public static void shuffle(List list);
    public static void shuffle(List list, Random r);
    public static Set singleton(Object o);
    public static void sort(List list);
    public static void sort(List list, Comparator comp);
    public static Collection synchronizedCollection(
     Collection coll);
    public static List synchronizedList(List list);
    public static Map synchronizedMap(Map map);
    public static Set synchronizedSet(Set set);
    public static SortedMap synchronizedSortedMap(
     SortedMap map);
    public static SortedSet synchronizedSortedSet(
     SortedSet set);
    public static Collection unmodifiableCollection(
     Collection coll);
    public static List unmodifiableList(List list);
    public static Map unmodifiableMap(Map map);
    public static Set unmodi
      unmodifiableSortedMap(SortedMap);
    public static SortedSet 
      unmodifiableSortedSet(SortedSet);
  }

For instance, to synchronize access to a Map, you would do the following:

  Map map = new HashMap()
  map = Collections.synchronizedMap (map);
  // access map from multiple threads

TIP:
When you synchronize a collection, it is good practice to not store the new collection in a new variable. If you do, it is possible you could still access the collection unsynchronized from the old one.

Besides synchronization, the Collections class also offers the ability to convert a specific collection to read-only mode. What this does is cause any method that would alter the collection to throw an UnsupportedOperationException. So, to make a collection read-only, you create it, fill it up, and then make it unmodifiable. If you make it unmodifiable before filling it up, you get an UnsupportedOperationException thrown:

  Map map = new HashMap()
  // add entries
  map = Collections.unmodifiableMap (map);

Algorithms and Sorting

The Java Collections API includes many algorithmic capabilities behind the scenes. For instance, up to this point, when various balanced tree-oriented collections were mentioned, how the tree was sorted was not. The time has come to describe this behavior and other similar capabilities. For random sorting or reordering of a List, just use Collections.shuffle().

Comparable and Comparator

Two interfaces are available to support sorting. The Comparable interface is for when a class has a natural ordering. Given many objects of the same type, the interface allows one to order all of them. The interface definition for Comparable is:

  public interface Comparable {
  public abstract int compareTo(Object obj);
  }

A negative return value signals the instance of the interface implementer comes before the parameter, zero signifies both are equal, and a positive value means the parameter comes first. When a class implements the Comparable interface, objects of the class can be used as the key for a tree-oriented collection. If an object doesn't implement Comparable, but you still wish it to be a key, you can implement the Comparator interface and have it do the comparisons for you:

  public interface Comparator {
    public abstract int compare (
      Object obj1, Object obj2);
  }


NOTE:
The Java 1.2 classes that implement the Comparable interface are: BigDecimal, BigInteger, Byte, Character, CollationKey, Date, Double, File, Float, Integer, Long, ObjectStreamField, Short, String, and URL.

To demonstrate, let's compare the results of sorting with the default String comparison and a comparator that doesn't distinguish between uppercase and lowercase characters. To help, we need the Arrays class, shown here:

  public class Arrays {
    public static List asList(Object array[]);
    public static int binarySearch(byte a[], byte key);
    public static int binarySearch(char a[], char key);
    public static int binarySearch(
      double a[], double key);
    public static int binarySearch(float a[], float key);
    public static int binarySearch(int a[], int key);
    public static int binarySearch(
      Object a[], Object key);
    public static int binarySearch(
     Object a[], 
     Object key, 
     Comparator comp);
    public static int binarySearch(long a[], long key);
    public static int binarySearch(short a[], short key);
    public static boolean equals(
      boolean[], boolean a2[]);
    public static boolean equals(byte a1[], byte a2[]);
    public static boolean equals(char a1[], char a2[]);
    public static boolean equals(
      double a1[], double a2[]);
    public static boolean equals(float a1[], float a2[]);
    public static boolean equals(int a1[], int a2[]);
    public static boolean equals(
      Object a1[], Object a2[]);
    public static boolean equals(long a1[], long a2[]);
    public static boolean equals(short a1[], short a2[]);
    public static void fill(boolean a[], boolean val);
    public static void fill(
     boolean a[], 
     int from, 
     int to, 
     boolean val);
    public static void fill(byte a[], byte val);
    public static void fill(
     byte a[], 
     int from, 
     int to, 
     byte val);
    public static void fill(char a[], char val);
    public static void fill(
     char a[], 
     int from, 
     int to, 
     char val);
    public static void fill(double a[], double val);
    public static void fill(
     double a[], 
     int from, 
     int to, 
     double val);
    public static void fill(float a[], float val);
    public static void fill(
     float a[], 
     int from, 
     int to, 
     float val);
    public static void fill(int a[], int val);
    public static void fill(
     int a[], 
     int from, 
     int to, 
     int val);
    public static void fill(
     Object a[], 
     int from, 
     int to, 
     Object val);
    public static void fill(Object a[], Object val);
    public static void fill(
     long a[], 
     int from, 
     int to, 
     long val);
    public static void fill(long a[], long val);
    public static void fill(
     short a[], 
     int from, 
     int to, 
     short val);
    public static void fill(short a[], short val);
    public static void sort(byte a[]);
    public static void sort(char a[]);
    public static void sort(double a[]);
    public static void sort(float a[]);
    public static void sort(int a[]);
    public static void sort(Object a[]);
    public static void sort(
     Object a[], 
     Comparator comp);
    public static void sort(long a[]);
    public static void sort(short a[]);
  }

The Arrays class is like Collections, all static methods and no constructor, just a collection of utilities for working with arrays.

The Arrays class provides a sort() method for sorting any array. Once an array is sorted, you could also perform a quick binary search to find an element in the array. For the following example, the program sorts a list of names with the default String Comparable interface, then sorts with the case-insensitive Comparator one:

  import java.util.*;
  public class SortingPlanets {
    static class InsensitiveComp implements Comparator {
      public int compare (Object a1, Object a2) {
        String  s1 = a1.toString ().toLowerCase();
        String  s2 = a2.toString ().toLowerCase();
        return s1.compareTo (s2);
      }
    }
    public static void main (String  args[]) {
    String  names[] = {"Mercury", "Venus", "Earth",
      "Mars", "Jupiter", "Saturn", "Uranus",
      "Neptune", "Pluto",
      "mercury", "venus", "earth",
      "mars", "jupiter", "saturn", "uranus",
      "neptune", "pluto"
    };
    Arrays.sort(names);
    int namesLen = names.length;
    for (int i=0; i<namesLen; i++) {
      System.out.print (names[i] + " ");
    }
    System.out.println ();
    Arrays.sort(names, new InsensitiveComp());
    for (int i=0; i<namesLen; i++) {
      System.out.print (names[i] + " ");
    }
    System.out.println ();
  }
}

Running the program produces the following output. Notice how the second run through ignores case:

  Earth Jupiter Mars Mercury Neptune Pluto Saturn 
  Uranus Venus earth jupiter mars mercury neptune 
  pluto saturn uranus venus
  Earth earth Jupiter jupiter Mars mars Mercury 
  mercury neptune Neptune pluto Pluto Saturn 
  saturn Uranus uranus Venus venus

WARNING:
If you perform a binarySearch() on an array, remember to sort() first. If you don't, undefined behavior occurs, including the possibility of an infinite loop.

TIP:
To sort an object array in reverse order, use Arrays.sort(anObjectArray, Collections.reverseOrder()).

Miscellaneous Utilities

Besides sorting and searching with Arrays and Collections, you can use Collections to find the minimum and maximum values of your Collection. Unlike when you use binarySearch(), you do not have to sort() your collection beforehand. Just use the min() and max() methods of Collections, which take an optional Comparator.

Going between old and new style collections is relatively easy, too. To create an Enumeration from any Collection, just use Collections.enumeration(). To go from an array to a List, use Arrays.asList().

Summary

Working with data structures in Java has many options, all depending upon your specific needs. While Java 1.2 introduces the Java Collections API, the historical collection classes are still available and readily used with all the code out there. Knowing about arrays, Vector, Dictionary, Hashtable, Properties, and BitSet will help you with Java 1.0 and 1.1 code. Understanding Collection, Set, List, and Map, along with all their implementations, will put you well on your way to success with the new Collections framework of 1.2. Where possible, using only the 1.2 collection classes (and arrays) is the way to go.

About the Author

John Zukowski is a Software Mage with MageLang Institute. In addition to being the author of Mastering Java 1.2, Java AWT Reference, and Borland JBuilder: No Experience Required. John also serves as the Focus on Java Guide at The Mining Co.


Reader Feedback

Tell us what you think of this book excerpt.

[Duke]

 Very worth reading  Worth reading  Not worth reading

If you have other comments or ideas for future book excerpts, please type them here:


Print Button
[ This page was updated: 27-Sep-2000 ]
Products & APIs | Developer Connection | Docs & Training | Online Support
Community Discussion | Industry News | Solutions Marketplace | Case Studies
Glossary | Feedback | A-Z Index
For more information on Java technology
and other software from Sun Microsystems, call:
(800) 786-7638
Outside the U.S. and Canada, dial your country's AT&T Direct Access Number first.
Sun Microsystems, Inc.
Copyright © 1995-2000 Sun Microsystems, Inc.
All Rights Reserved. Terms of Use. Privacy Policy.