Container support for objects in Java 1.0.2

Organizing objects is easy when you put them into containers

By Chuck Mcmanis, JavaWorld.com, 11/01/96

Page 3 of 5

Using the tools in the box

As I mentioned earlier, generic program developers have two primary tools available to them: implementation inheritance (extending) and behavioral inheritance (implementing).

To use implementation inheritance, you extend (subclass) an existing class. By extension, all subclasses of the base class have the same capabilities as the root class. This is the basis for the HashCode method in the Object class. As all objects inherit from the java.lang.Object class, all objects have a method HashCode that returns a unique hash for that object. If you wish to use your objects as keys, however, keep in mind the caveat mentioned earlier about overriding HashCode.

In addition to implementation inheritance, there is behavioral inheritance (implementing), which is achieved by specifying that an object implements a particular Java interface. An object that implements an interface can be cast to an object reference of that interface type. Then that reference can be used to invoke the methods specified by that interface. Typically, interfaces are used when a class may need to process several objects of different types in a common way. For example, Java defines the Runnable interface that is used by the thread classes to work with classes in their own thread.

Building a container

To demonstrate the tradeoffs in writing generic code, I will walk you through the design and implementation of a sorted container class.

As I mentioned earlier, in the development of general-purpose applications, in many cases a good container would be useful. In my example application I needed a container that was both keyed, meaning that I wanted to retrieve contained objects by using a simple key, and sorted so that I could retrieve the contained objects in a specific order based on the key values.

When designing systems, it is important to keep in mind what parts of the system use a particular interface. In the case of containers, there are two critical interfaces -- the container itself and the keys that index the container. User programs use the container to store and organize objects; the containers themselves use the key interfaces to help them organize themselves. When designing containers, we strive to make them easy to use and to store a wide variety of objects (thus increasing their utility). We design the keys to be flexible so that a wide variety of container implementation can use the same key structures.

To solve my behavioral requirements, keying and sorting, I turn to a useful tree data structure called a binary search tree (BST). Binary trees have the useful property of being sorted, so they can be efficiently searched and can be dumped out in sorted order. The actual BST code is an implementation of the algorithms published in the book Introduction to Algorithms, by Thomas Cormen, Charles Leiserson, and Ron Rivest.

java.util.Dictionary

The Java standard classes have taken a first step toward generic keyed containers with the definition of an abstract class named java.util.Dictionary. If you look at the source code that comes with the JDK, you will see that Hashtable is a subclass of Dictionary.

The Dictionary class attempts to define the methods common to all keyed containers. Technically, what is being described could more properly be called a store as there is no required binding between the key and the object it indexes. However, the name is appropriate as nearly everyone understands the basic operation of a dictionary. An alternative name might be KeyedContainer, but that title gets tedious pretty quickly. The point is that the common superclass of a set of generic classes should express the core behavior being factored out by that class. The Dictionary methods are as follows:

By subclassing Dictionary, we use the tool of implementation inheritance to create an object that can be used by a wide variety of clients. These clients need know only how to use a Dictionary, and we can then substitute our new BST or a Hashtable without the client noticing. It is this property of abstracting out the core interface into the superclass that is crucial to reusability, general-purpose function, expressed cleanly.

Basically, Dictionary gives us two groups of behavior, accounting and administration -- accounting in the form of how many objects we've stored and bulk reading of the store, and administration in the form of get, put, and remove.

If you look at the Hashtable class source (it is included with all versions of the JDK in a file named src.zip), you will see that this class extends Dictionary and has two private internal classes, one named HashtableEntry and one named HashtableEnumerator. The implementation is straightforward. When put is called, objects are placed into a HashtableEntry object and stored into a hash table. When get is called, the key passed is hashed and the hashcode is used to locate the desired object in the hash table. These methods keep track of how many objects have been added or removed, and this information is returned in response to a size request. The HashtableEnumerator class is used to return results of the elements method or keys method.

First cut at a generic keyed container

The BinarySearchTree class is an example of a generic container that subclasses Dictionary but uses a different organizing principle. As in the Hashtable class, I've added a couple of classes to support holding the stored objects and keys and for enumerating the table.

The first is BSTNode, which is equivalent to a HashtableEntry. It is defined as shown in the code outline below. You can also look at the source.

class BSTNode {
    protected BSTNode parent;
    protected BSTNode left;
    protected BSTNode right;
    protected String  key;
    protected Object  payload;
    public BSTNode(String k, Object p) {
        key = k;
        payload = p;
    }
    protected BSTNode() { super(); }
    BSTNode successor() { return successor(this); }
    BSTNode precessor() { return predecessor(this); }
    BSTNode min() { return min(this); }
    BSTNode max() { return max(this); }
    void print(PrintStream p) { print(this, p); }
    private static BSTNode successor(BSTNode n) { ... }
    private static BSTNode predecessor(BSTNode n) { ... }
    private static BSTNode min(BSTNode n) { ... }
    private static BSTNode max(BSTNode n) { ... }
    private static void print(BSTNode n, PrintStream p) { ... }
}

Let's take a look at this code in order to clarify two things. First, there's the null-protected constructor, which is present so that subclasses of this class do not have to declare a constructor that overrides one of this class' constructors. Second, the methods successor, predecessor, min, max, and print are very short and merely call the same private equivalent so as to conserve memory space.