Container support for objects in Java 1.0.2

The next special-purpose class is the class BSTEnumerator, which provides an implementation of a java.util.Enumeration that can be used to get each key or each object out of the tree in order. You can follow along with the code below.

class BSTEnumerator extends BSTNode implements Enumeration {
    private BSTNode currentNode;
    private boolean keys;
    BSTEnumerator(BSTNode start, boolean doKeys) {
        super();
        currentNode = start;
        keys = doKeys;
    }
    public boolean hasMoreElements() {
        return (currentNode != null);
    }
    public Object nextElement() {
        BSTNode n;
        if (currentNode == null) {
            throw new NoSuchElementException();
        }
        n = currentNode;
        currentNode = currentNode.successor();
        return (keys ? n.key : n.payload);
    }
}

As you can see, we extend BSTNode, which gives us access to the methods for moving through a tree. Further, we can look into the protected parts of the object -- the key and the payload instance variables. To implement the Enumeration interface we need only a hasMoreElements method and a nextElement method.

The hasMoreElements method returns true if the node we are holding is non-null. This design allows us to create an enumerator without having to check if there are any objects in our container; the enumerator will always provide the correct response. The second method, nextElement, simply returns the node we are holding and replaces that node with the next node in the tree (known as the successor node). What is actually returned is either the key value or the payload, depending on the state of the key's boolean. By implementing the system in this way, only these two classes -- BSTNode and BSTEnumerator -- need to know the particulars of how an internal node is constructed. Keep in mind that with the BSTEnumerator class, the reference in currentNode is in fact also currently stored inside the tree. If another thread is manipulating the tree, something unexpected may result. If this potential for multiple threads changing the tree during an enumeration is a problem, the enumerator could create a quick copy of the tree during its construction. For our purposes, however, we simply don't change the tree while we are enumerating its elements or keys.

Finally, after the node and enumerator are designed, we put together our subclass of Dictionary to be the container object. The first half of the code for BinarySearchTree is shown below in outline form.

public class BinarySearchTree extends Dictionary {
    BSTNode rootNode;
    private int elementCount;
    private BSTNode search(String searchKey) { ... }
    private void insert(BSTNode n) { ... ; elementCount++ }
    private BSTNode delete(BSTNode z) { ...; elementCount--; }

This first section of the code above shows the two state variables that our tree class maintains. These variables hold the number of elements currently held and the root node for the binary tree. The variables are followed by three methods that manipulate the contents of the tree -- search, insert, and remove . Remember that trees consist of BSTNode objects. At this point, we must implement the abstract methods of Dictionary in our class. Java requires that concrete subclasses define implementations for all of the abstract methods in their superclass. Starting with the easy ones, we have elements, keys, size, and isEmpty, as shown below.

    
    public Enumeration elements() {
    if (rootNode == null) return null;
        return new BSTEnumerator(rootNode.min(), false);
    }
    public Enumeration keys() {
    if (rootNode == null) return null;
        return new BSTEnumerator(rootNode.min(), true);
    }
    public boolean isEmpty() { return (elementCount == 0); }
    public int size() { return elementCount; }

The key and elements methods simply create a new BSTEnumerator with the keys flag appropriately set, and pass it the logical first element in the tree. Later, when nextElement is called, this node will be used to find successive nodes until all nodes have been visited. The isEmpty and size methods simply return the state of elementCount to the user. This variable is maintained in the insert and delete methods of the tree.

The next method from Dictionary that we implement is get, which we do by calling the search method -- starting at the root node and using the key the user passed us. This code is shown below, and all it does is first check to make sure there are some nodes to search and then search them. If the search is successful, it returns the payload from the node it found.

    
    public Object get(Object key) {
    if (rootNode == null) return null;
    BSTNode n = search((String) key);
        return (n != null) ? n.payload : null;
    }

Next we have the dictionary administration methods remove and put. The implementation of these methods is shown below. The only subtle implementation detail is that, implicitly, keyed containers cannot contain multiple objects for the same key. This is simply an implementation decision that Sun made in the specification of the language. It is straightforward to implement multiple objects per key but get and remove get a bit harder to write.

The remove method checks to see if the node exists. If it does, it gets back its payload, then removes it while returning the payload to the caller. The put method removes an object associated with key if it exists and then adds a new node with the new value into the tree.

    
    public Object remove(Object key) {
        BSTNode n = search((String) key);
        if (n == null)
            return null;
        Object r = n.payload;
        delete(n); // call the BST delete method
        return r;
    }
    public Object put(Object key, Object value) {
        BSTNode n;
        Object r = remove(key);
        n = new BSTNode((String) key, value);
        insert(n); // Call the BST insert method
        return r;
    } 

And with that a complete container is created to go along with Hashtable. To test it I wrote a simple test program that fills the container with some strings and then enumerates them out. Next it removes one of the objects and prints out the complete list again. At about line 32 of the test program there is the statement Dictionary d = new XXX(); where the XXX is replaced with either BinarySearchTree or Hashtable. This test program inserts the following colors into the dictionary: red, green, orange, purple, chartreuse, gray, magenta, cyan, yellow, tangerine, turquoise, brown, black, white, silver, gold, pink, bronze, beige, blue, and aquamarine. And it sets the stored object value to be a string consisting of the number of the color in the list, as well as the color's value. This gives us an idea of how the colors get rearranged when they are in the Dictionary object. The complete contents of the dictionary are enumerated with the following code.

    
    System.out.println("XXX contains:");
    for (Enumeration e = d.elements(); e.hasMoreElements(); ) {
    System.out.println(e.nextElement());
    }

The results are shown in this table:

As you can see from the above table, the objects from the BinarySearchTree-based dictionary come back in sorted order, whereas the Hashtable entries come back in an unpredictable order (unless you read the source to Hashtable, of course).

The use of String in the binary search tree container

Our first cut at designing a sorted container works fine; it implements all of the abstract methods of Dictionary. We've written a test program to show that at least in one case it is interchangeable with Hashtable. Unfortunately there is a lurking problem that we haven't yet addressed: The limitation that the key used in this container must be of type String. Let's take a moment to investigate why strings are used, as well as what the limitations of that design choice are. In the next column we will look at eliminating strings completely.

For any container to work, the key must identify an object. In our BinarySearchTree container we use a String object to identify the contained object. The object identified by the key is located using a binary search algorithm, which uses the relative value of the key you are holding versus the key you are currently looking at, to determine which key to look at next. This is implemented in the search method in BinarySearchTree shown below.

    
    private search BSTNode search(String searchKey) {
    return search(rootNode, searchKey);
    }
    private static BSTNode search(BSTNode n, String searchKey) {
        if ((n == null) || searchKey.equals(n.key)) {
            return n;
        }
        if (searchKey.compareTo(n.key) < 0) {
            return search(n.left, searchKey);
        } else {
            return search(n.right, searchKey);
        }
    }

If you recall the way that a binary tree works, each node optionally has two child nodes (hence the term "binary search tree"). The node to the left points to a node that is "less than" the current node, and the node to the right points to a node that is "greater than" the current node. The search method uses the equals method to see if the key of this node is equal to the passed key. If the keys are not equal, then search uses the compareTo method to decide if the left branch or the right branch of the tree should be followed. Once the branch determination is made, the method is recursively called on that node. If the node is null, as it will be when the key is not present in the tree, search simply returns null, indicating that the key is not present.

As you can see, the algorithm is simple and efficient, however it depends on the key object having a method compareTo to determine if the left or right branch of the tree should be followed. Unfortunately, the base class of Object, which defined hashCode for the hash table algorithm, does not define compareTo for all objects. Because of this, we cannot truly meet Dictionary's contract that a key can be any object.

Wrapping up

In this column I've walked you through the building of a container based on the Java container classes. In the process we have uncovered what is clearly a somewhat "uncomfortable" place. Next month I plan to take the BinarySearchTree class through several revisions to illustrate ways to work around these issues in Java and ways to build generic containers in particular. Until next time.

This story, "Container support for objects in Java 1.0.2" was originally published by JavaWorld.