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.