Code reuse and object-oriented systems

Using a helper class to enforce dynamic behavior

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

A String object was used because it has the property of being easily sorted. No other standard object in the Java standard libraries is both as flexible and as sortable as a string. We can't go ahead and make all keys in our container a subclass of String because String is final -- it can't be subclassed. Further, some objects work well as their own key, that can save space on the heap and garbage generation, both of which are Good Things. So what do we do? Well, let's see...

Solving the key dilemma

There are three approaches to solving the key dilemma. Each has its drawbacks, so one might conclude that there is no good solution. This is not true. A good universal solution may not exist, but there are widely applicable solutions.

The first approach: To everything Stringness

The first approach takes advantage of the fact that every object defines a toString method. This method is initially defined in Object but can be overridden by subclasses.

The toString method was designed so that all objects might have some representation that could be displayed on a character device such as a terminal or window. The number classes provide overridden versions that convert a subclass of Number to a printable representation. The default implementation in Object gives you the name of the object's class and its reference number (actually its address in memory) as a string. The format of the string is classname@hex-address.

With this knowledge, we can write a helper method -- stringForKey -- and then rewrite get, put, and remove to use this method on the key objects that are passed to them. The next bit of code shows both the helper method and the rewritten get that implements this solution:

private String stringForKey(Object o) {
        if (o instanceof String)
            return (String) o;
        return o.toString();
    }
    public Object get(Object skey) {
        String s = stringForkey(skey);        
        return search(rootNode, s).payload;
    }

In the code above, this version of the method uses the instanceof operator in Java to test if the key passed is already a string; if it isn't, it uses the toString method in Object to create a string for the tree. I have included a link to the source code of BinarySearchTree written in this way.

The advantage here is that, by default, all objects have an implementation of toString, and if this method is implemented in such a way as to uniquely define objects, we could certainly use it. Unfortunately, this solution depends on Java programmers knowing that this function may be used for this purpose. If a naive programmer were to design a class with an override of toString like that shown below, our search tree would be in big trouble.

    public String toString() {
    return "A Foo Object." }

The method shown above is a perfectly legitimate implementation of toString according to the Java language specification, and yet it has the annoying side effect of causing objects of this type to be non-sortable. Every instance of this object type will return the same string representation and thus will not be distinguishable in the BinarySearchTree code.>

A second approach: Interfaces

The issues involved in using toString can be evaluated in The Java Language Specification by James Gosling, Bill Joy, and Guy Steele. Taken from the specification, the contract for toString is as follows:

"The general contract of toString is that it returns a string that 'textually represents' this object. The idea is to provide a concise but informative representation that will be useful to the person reading it."

As you can see, the specification doesn't say anything about being unique across object instances.

To get the guarantee that the programmer will know what we wanted for our keys, we can define an interface to provide a contract where Object did not write into the contract that toString could be used as a unique key. This way, we can make the contract for that interface clear to its implementers. The canonical example is to define an interface, ours is named SearchKey, that defines the contract for a key used for searching. The code for SearchKey is shown below.

public interface SearchKey { 
    /**
     * returns < 0 if search key o is less than this object. 
     *           0 if search key o is equal to this object. 
     *         > 0 if search key o is greater than this object. 
     */
    abstract int compareKey(SearchKey o);
    /** Return true if passed Search Key matches this one */
    abstract boolean equalKey(SearchKey o);
}

This interface defines the method compareKey to have semantics that are equivalent to the compareTo method in class String. I avoid reusing the same, or common, method names in the interface definition as Java is unable to distinguish between two methods with the same signature in two separate interfaces. It is poor form to choose method names that might easily collide with other interface definitions. The second method returns a boolean value indicating that two keys are equivalent.

The contract, then, is that any object implementing this interface can be used as an index key to our container. The most common implementation of equalKey might be similar to the code shown below.

public boolean equalKey(SearchKey o) {
    return (compareKey(o) == 0);
}

The interface explicitly calls out the requirements of its implementation. Therefore, programmers implementing this interface in their objects will understand the underlying contract between the container and its keys. By combining the two methods equalKey and compareKey, the invariants of the binary tree search algorithms can be maintained.

Using this interface in our container is a bit more difficult. We cannot change the method signatures of get, put, and remove, as they are constrained by the Dictionary superclass. However, we can force an error if the client fails to abide by our rules. As in the first approach, we define a private helper method to convert from the Object class reference to a SearchKey reference. This method is called keyForObject and it is shown in the code below.

Free Download - 5 Minute Product Review. When slow equals Off: Manage the complexity of Web applications - Symphoniq

Free Download - 5 Minute Product Review. Realize the benefits of real user monitoring in less than an hour. - Symphoniq