Code reuse and object-oriented systems

Using a helper class to enforce dynamic behavior

In my last column, I demonstrated how to build a container using the container classes available in the standard Java distribution. That column ended with the building of a container, which was tested with a simple test application. What was left unspoken in the last column was a design decision to make the indexing key of our container a String object.

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.

private SearchKey keyForObject(Object o) {
if (o instanceof SearchKey) {
    return (SearchKey) o; } if (o instanceof String) {
    return new StringSearchKey((String)
    o); } throw new RuntimeException("Dictionary key must
implement SearchKey"); }

Again, as in the first approach described in this column, if our object type is not the type we require, we throw an exception; however, we do allow for one luxury, which is to accept objects of class String directly. Being able to directly accept a string is useful because strings are so often used as index objects in dictionaries.

Using this approach, we can rewrite BinarySearchTree to check that the objects are either strings or search keys. The code below shows how the put method in BinarySearchTree is rewritten to use SearchKey keys rather than string objects.

public Object put(Object keyObj, Object value) {
        BSTNode n;
        Object r = null;
    SearchKey k = keyForObject(keyObj);
        n = search(k);
        if (n != null) {
            r = n.payload;
            remove(n);
        }
        n = new BSTNode(k, value);
        insert(n);
        return r;
    }

Note that while the interface to put states that it will accept any object, in fact it will only accept objects that implement SearchKey. Any object that is passed as a key object to the put method that is neither a string nor implements the SearchKey interface will be rejected. This rejection comes in the form of a run-time exception that is thrown by the keyForObject method when the conversion from a generic object into a SearchKey type object is attempted. This type of exception should be used only in truly exceptional situations where you will need to abort the Java thread if the exception condition exists.

The rewritten BinarySearchTree class is here, and this impacts the BSTNode class as well in that the key type is changed from String to SearchKey. The modified code for BSTNode is here. Now this looks OK, but in fact it opens up a few new challenges. Before jumping on to the challenges, let's look at the advantages of this technique.

The primary advantage of this technique is that the key function of the dictionary has been generalized into the SearchKey behavior. Thus, to use any object as a key in our binary search tree, we need only insure that the object implement this interface. This allows us to design our payload objects so that they can be both the key and the value. Consider the following redesign of DictionaryTest; we start by designing a class to store in our dictionary that can be both the key and the value. This is called ColorKey and is shown below. In a real application, the value would probably be a java.awt.Color object, but for our example we'll leave it as a string.

class ColorKey implements SearchKey {
    String key;
    String colorValue;
    public ColorKey(String k, String v) {
        key = k;
        colorValue = v;
    }
    private void verifyType(SearchKey k) {
        if (! (k instanceof ColorKey))
            throw new RuntimeException("You cannot mix keys here.");
    }
    public int compareKey(SearchKey b) {
        verifyType(b);
        return key.compareTo(((ColorKey) b).key);
    }
    public boolean equalKey(SearchKey o) {
        return (compareKey(o) == 0);
    }
    public String toString() {
        return "ColorKey:: '"+key+"' ==> '"+colorValue+"'";
    }
}

You will notice that the compareKey method is where all the work is done. This method insures that the object being passed to this method for comparison is in fact a ColorKey object (it could also be a subclass of ColorKey). If the object has the correct type, it is cast to a ColorKey, and the compareTo method of the instance variable key is used to compare this ColorKey object with the ColorKey object passed into this method.

In the DictionaryTest class, the initial array of strings was modified to initialize an array of ColorKeys as shown in the next section of code:

From DictionaryTest.java:
        ColorKey keys[] = new ColorKey[colors.length];
        for (int i = 0; i < colors.length; i++) {
            keys[i] = new ColorKey(colors[i], (i+1)+": "+colors[i]);
            d.put(keys[i], keys[i]);
        }

Of interest here is that when put is called, the same object is used for both the key and the payload. This eliminates the possibility that a properly constructed node will have the wrong key.

As I mentioned earlier, there are some problems with this approach. The first is that while any object that implements SearchKey can be passed, you can't simply compare two SearchKey objects, as they may have no common basis for comparison. Consider a simple case like IntegerKey, which is shown below.

public class IntegerKey implements SearchKey {
    int value;
    public IntegerKey(int a) { value = a; }
    private void verifyType(SearchKey o) {
        if (! (o instanceof IntegerKey))
            throw new RuntimeException("You cannot mix keys here.");
    }
    public int compareKey(SearchKey o) {
        verifyType(o);
        return (((IntegerKey) o).value - value);
    }
    public boolean equalKey(SearchKey o) {
        return compareKey(o) == 0;
    }
}

If it weren't for the exception thrown in verifyType, and if you were to use an IntegerKey object as a key for one of the values in a BinarySearchTree populated with ColorKey keys, you would never be able to fetch the number out. This whole issue of checking the type of the objects used for keys -- and for payloads, for that matter -- brings up a still thornier issue: type integrity. The issue of type integrity involves guaranteeing that the Object references in your container have the same (or compatible) types. This issue is covered in detail in the next section.

More importantly, using an interface in this way means that if you want your object to be contained in this container, and be self keying, you have to modify it to implement the SearchKey interface. For Java classes to which you don't have the source, this is impossible.

Approach three: Using Mixins

Do you remember the first implementation of BinarySearchTree from the previous column? In that version, the keys were always string objects. There is a wonderful crispness to defining the interfaces with hard-coded types; doing so can flush out a host of errors whereby you might pass the wrong variable to your put method, and thus corrupt your container, only to find out about it later. Also we have been ignoring the fact that the payload is simply an object reference that has its own type. Further, a Dictionary is used typically for storing things in it, which it retrieves later; therefore, there is a lot of type casting going on. If the wrong reference gets stored, you find out about it only when you cast the payload as you take it out. By that time there may be very few clues about how the object arrived there.

To state this a different way, the interface to get is "Object get(Object key);". Of course you've been putting a particular type of object into the container, one that you expect to get out on the other side. The typical use of get in your code will be something like the following:

MyTypeName var = (MyTypeName) dictionary.get(SomeKey);

Let's say you had been storing objects of type MyTypeName in this table but you had a bug on one line of code that accidentally stored in an object of type String. If you execute the above statement with the key object used to store that string, this line will throw a ClassCastException when you least expect it. If you don't catch this bug in testing, it will most certainly surface the day you are demonstrating your product for the new investors. So, to be on the safe side, what you really want isn't a generic container at all but a container for objects of type MyTypeName. That way, if you ever tried to hold an object in the container that was of the wrong type, you would catch the bug when it was stored. We can resolve this issue.

Obviously, most of the code in BinarySearchTree is generic code, poking at the left or right branches of a node, searching up and down, and so on. Stated another way, the places where the code needs to be specific are fairly small. The challenge then is to abstract out the fairly small part, and figure out some way to "mix it back in" when you need it.

The questions and operations for a type-specific implementation are:

  • Is the type of key valid?
  • Is the type of the value or payload valid?
  • Compare these two keys and tell me which is greater.
  • Return me an object of my type for this key.

The above specifically relate to the type of object we are storing in the dictionary. Now consider the following abstract class named ContainerOrganizer. The complete source is here:

public abstract class ContainerOrganizer {
    Dictionary localContainer;
    public void setDict(Dictionary d) { ... }
    public abstract Object keyForObject(Object o);
    public abstract boolean verifyType(Object obj, boolean ex);
    public boolean verifyType(Object o) {
        return verifyType(o, true);
    }
    public boolean equalKeys(Object k1, Object k2) {
        return compareKeys(k1, k2) == 0;
    }
   public abstract int compareKeys(Object k1, Object k2);
}

Note that the container organizer is similar in many ways to the SearchKey interface described earlier. The abstract bits are keyForObject, which is responsible for converting the object passed in the key parameter into an object that can actually key the container. If you will recall, our interface example could take either a String or a SearchKey as they were pretty similar. This is where you can mix in such things. The next abstract method is verifyType, which takes an object that is about to be placed in the payload of our node object and verifies that it is the correct type. This insures type integrity at insertion, so you don't get class casting failures later. This method has the option of throwing a RuntimeException when it gets an error, which is useful if you can assume that any time a bogus object is passed, it is a serious bug. Finally, there is the abstract method compareKeys, which, when implemented, will know how the keys you are using wish to be compared.

The impact on the container code, in terms of special-purpose code to integrate the use of a ContainerOrganizer is fairly minimal. The BSTNode class is updated to store its keys as Objects rather than String or SearchKeys. The type of the key is enforced during object creation and while searching. The BinarySearchTree code is modified to call verifyType and compareKeys in its search methods. The modified code for put is shown below. If you take a look at the source, you'll notice that the instance variable co is set to the ContainerOrganizer object passed to the constructor.

public Object put(Object key, Object value) {
        BSTNode n;
        Object s;
        co.verifyType(value);
        s = co.keyForObject(key);
        n = search(s);
        Object r = null;
        if (n != null) {
            r = n.payload;
            remove(s);
        }
        n = new BSTNode(s, value);
        insert(n);
        return r;
    }

In the code above, put first calls verifyType in the ContainerOrganizer object that has been mixed into this container. If the type of the parameter value is not valid for this container, this call will throw a run-time exception. Next it verifies and possibly translates the key object passed by calling the keyForObject method. This way, it simulates writing the put method with the signature

public Object put(MyKeyType key, MyLocalType value) { ... }

which is how we would have written it if we weren't using a generic container. The next area of impact on the container is in the search method. The implementation of the new version of this method is shown below.

private BSTNode search(BSTNode n, Object searchKey) {
        if ((n == null) || co.equalKeys(searchKey, n.key)) {
            return n;
        }
        if (co.compareKeys(searchKey, n.key) < 0) {
            return search(n.left, searchKey);
        } else {
            return search(n.right, searchKey);
        }
    }

In the code above, search calls the method compareKeys in the ContainerOrganizer object in order to establish their relationship. The method can encapsulate an arbitrarily complex mechanism for evaluating the relative value of two keys. Further, the contract for this method is always clear to the implementor.

You should now be able to see how you can write a concrete subclass of the ContainerOrganizer class, mix it into the generic BinarySearchTree class, and get back an instance of a customized BinarySearchTree. To help with this visualization I've contrived a simple example based on the classes I've been using throughout this article.

Putting these containers to use

In the first two examples we've used DictionaryTest as a program for storing and then manipulating some values in our dictionary. I'll continue using that example but will change it a little bit to illustrate the use of non-string-based keys. To begin, I've put the colors that are being sorted and stored into a new class called ColorItem. A color item is defined as follows:

public class ColorItem {
    private String name;
    private Color value;
    float vals[];
    public ColorItem(String n, Color v) {
        name = n;
        value = v;
    }
    public Color toColor() { return value; }
    public String nameOf() { return name; }
    float val[] = new float[3];
    public String toString() {
        Color.RGBtoHSB(value.getRed(), value.getGreen(), value.getBlue(),
                val);
        return "Color: "+name+", value "+val[0];
    }
}

The code above shows that this object holds an AWT Color object and a name to go with it. The names may be useful as keys, but for the example let's make the index of interest be the hue of each color. To build a BinarySearchTree that can store colors in sorted hue order, I built a ContainerOrganizer subclass called ColorOrganizer. This is defined as shown:

public class ColorOrganizer extends ContainerOrganizer {
    public boolean verifyType(Object o, boolean b) {
        if (o instanceof ColorItem)
            return true;
        if (b)
            throw new RuntimeException("Invalid Type");
        return false;
    }
    float HSBValues[] = new float[3];
    public int compareKeys(Object k1, Object k2) {
        Color a = ((ColorItem) k1).toColor();
        Color b = ((ColorItem) k2).toColor();
        float aHue, bHue;
        Color.RGBtoHSB(a.getRed(), a.getGreen(), a.getBlue(), HSBValues);
        aHue = HSBValues[0];
        Color.RGBtoHSB(b.getRed(), b.getGreen(), b.getBlue(), HSBValues);
        bHue = HSBValues[0];
        if (aHue < bHue) {
            return -1;
        } else if (aHue > bHue) {
            return 1;
        } else {
            String s1 = ((ColorItem) k1).nameOf();
            String s2 = ((ColorItem) k2).nameOf();
            return (s1.compareTo(s2));
        }
    }
    public Object keyForObject(Object s) {
        if (! (s instanceof ColorItem)) {
            throw new RuntimeException("Invalid key type.");
        }
        return s;
    }
    public ColorItem fetch(ColorItem key) {
        if (localContainer == null)
            return null;
        return (ColorItem) localContainer.get(key);
    }
}

The concrete implementation of verifyType checks to see that we're using a ColorItem to store into our tree. The method compareKeys extracts from two ColorItem objects their base colors, which it converts to hue, saturation, and brightness values. Finally, it uses the hue value to compare colors. If the two hues are identical, it then compares their name. This way, your "greenish blue" color and my "bluish green" color are always sorted next to each other, even if we chose alphabetically distinct names for them. The method keyForObject performs only a type check, as it uses the same type of object for the key as well as for the payload in our nodes. Finally, there is a simple helper method called fetch with nearly the same signature as the Dictionary get method. The difference is that the type it returns is the one we're expecting to get out of our container.

This last method takes advantage of the setDict method defined by ContainerOrganizer. When the BinarySearchTree is instantiated it puts a reference to itself in the organizer. Then instead of writing:

ColorItem c = (ColorItem) dictionary.get(key);

I can avoid typing the cast expression in my code every time I fetch an object from the container by using an implementation of fetch, as shown below.

ColorItem c = coloritem.fetch(key);

The implementation of fetch is essentially syntactic sugar, as it has to do the cast as well. The fetch method is defined to return objects of type ColorItem. If you have multiple dictionaries, using the fetch method from the mixin rather than the get method to access data, can help you avoid an illegal cast from the wrong dictionary.

Thus the mixin code is probably as close as you can get to writing a custom container for each type of object you are holding, with the least amount of custom code being written. Or alternately stated, this method probably gives you the maximum amount of re-use of the container code that was already written.

Wrapping up

I've looked at three different methods for making the container we designed last month into something a bit more generic. The third technique, mixins, is a useful way to abstract out parts of a class that might otherwise be specified with multiple inheritance. One of the proposed technologies for the 1.1 version of the JDK is the use of anonymous or "inner" classes, which are specified inside another class and have no visibility outside that class. Inner classes make excellent mixins or object adapters because they are truly exposed only to the class that is adapting the adaptable class. This makes for easier-to-read code and more reliable results, as there is little risk of some other class mistakenly using your inner class.

Each of these techniques can be used alone or in combination to increase the reusability of the code you write. It is important to remember that every line of truly reusable code you write will rarely have to be rewritten. It seems that the first forty years of computer science involved writing the same code over and over again. Ada was the first language I had heard about that explicitly stated the goal of having write-once, multiple-use packages. Both Mesa and Modula-2 (and Modula-3) had similar goals. With the platform independence of Java, this goal of reusable parts not only makes a lot of sense but has a tremendous leveraging effect for programmers everywhere.

I hope you've learned something from this column. I learn something every time I write one! Keep those cards and letters coming.

Chuck McManis is currently the director of system software at FreeGate Corp. FreeGate is a venture-funded start-up that is exploring opportunities in the Internet marketplace. Before joining FreeGate, McManis was a member of the Java group. He joined the Java group just after the formation of FirstPerson Inc. and was a member of the portable OS group (the group responsible for the OS portion of Java). Later, when FirstPerson was dissolved, he stayed with the group through the development of the alpha and beta versions of the Java platform. He created the first "all Java" home page on the Internet when he did the programming for the Java version of the Sun home page in May 1995. He also developed a cryptographic library for Java and versions of the Java class loader that could screen classes based on digital signatures. Before joining FirstPerson, Chuck worked in the operating systems area of SunSoft developing networking applications, where he did the initial design of NIS+.

Learn more about this topic

Join the discussion
Be the first to comment on this article. Our Commenting Policies
See more