How to Succeed When Decorating a Tree

Today I will talk about how hanging something on a (Java) tree can unexpectedly fail.

Suppose we have a class Bauble, with equals() and hashCode() methods properly in place.

public class Bauble {
    String color;
    String decoration;
    int size;
    
    public Bauble(String color, String decoration, int size) {
        this.color = color;
        this.decoration = decoration;
        this.size = size;
    }
    @Override
    public int hashCode() {
        ...
    }
    @Override
    public boolean equals(Object obj) {
        ...
    }
    @Override
    public String toString() {
        return "Bauble [color=" + color + ", decoration=" 
            + decoration + ", size=" + size + "]";
    }
}

Take a look at this little program. What is the result?

public class ChristmasDecoration {
    public static void main(String[] args){
        Set<Bauble> tree = new TreeSet<Bauble>();
        
        Bauble b1 = new Bauble("red", "plain", 5);
        Bauble b2 = new Bauble("green", "plain", 5);
        Bauble b3 = new Bauble("yellow", "blue *", 3);
        
        tree.add(b1);
        tree.add(b2);
        tree.add(b3);
        
        System.out.println(tree.size());
    }
}

I'm sure you suspect that the answer isn't simply 3. Well, run the program.

Exception in thread "main" java.lang.ClassCastException: \
        Bauble cannot be cast to java.lang.Comparable
    at java.util.TreeMap.put(TreeMap.java:542)
    at java.util.TreeSet.add(TreeSet.java:238)
    at ChristmasDecoration.main(ChristmasDecoration.java:10)

What happened? TreeSet is a sorted set which means that the elements in the set are kept in a certain order. If you use the TreeSet() constructor, then the order used by the set is a natural ordering for set's elements. The natural ordering in Java is provided by the method compareTo() in the java.lang.Comparable interface. The TreeSet tries to cast your Bauble element into java.lang.Comparable and fails.

A solution is to implement the java.lang.Comparable interface and add compareTo() method, for example like this:

class Bauble implements java.lang.Comparable<Bauble> {
    // ...
    @Override
    public int compareTo(Bauble o) {
        if (o == null) {
            throw new NullPointerException();
        }
        if (this == o) {
            return 0;
        }
        if (color == null) {
            return -1;
        }
        if (o.color == null) {
            return 1;
        }
        int colorCmp = color.compareTo(o.color);
        if (colorCmp != 0) {
            return colorCmp;
        }
        if (decoration == null) {
            return -1;
        }
        if (o.decoration == null) {
            return 1;
        }
        int decorationCmp = decoration.compareTo(o.decoration);
        if (decorationCmp != 0) {
            return decorationCmp;
        }
        return size.compareTo(o.size);
    }
}

But I use a library/generated code!

What if you want to have an ordered set of objects like java.sql.Connection? Or a set of OneWebSQL-generated Java beans? They do not implement the java.lang.Comparable interface and you cannot change their code.

The solution is to use an appropriate java.util.Comparator. Implement your own comparator which compares the given objects in a manner you specify. Give the comparator to the TreeSet constructor.

public class BaubleComparator implements java.util.Comparator<Bauble> {
    @Override
    public int compare(Bauble o1, Bauble o2) {
        if (o1 == null) {
            throw new NullPointerException();
        }
        if (o2 == null) {
            throw new NullPointerException();
        }
        if (o1 == o2) {
            return 0;
        }
        if (o1.color == null) {
            return -1;
        }
        if (o2.color == null) {
            return 1;
        }
        int colorCmp = o1.color.compareTo(o2.color);
        if (colorCmp != 0) {
            return colorCmp;
        }
        if (o1.decoration == null) {
            return -1;
        }
        if (o2.decoration == null) {
            return 1;
        }
        int decorationCmp = o1.decoration.compareTo(o2.decoration);
        if (decorationCmp != 0) {
            return decorationCmp;
        }
        return o1.size.compareTo(o2.size);
    }
}

...
Set<Bauble> betterTree = new TreeSet<Bauble>(new BaubleComparator());
...

Rule to remember: Elements in a TreeSet must be instances of java.lang.Comparable OR you must explicitly provide a Comparator when you create a TreeSet. The same rule applies to TreeMap.

This is something which should be emphasised when you learn about TreeSets and TreeMaps. Yet somehow it isn't emphasised enough and most Java developers have to discover it through trial and error.

Why is the API designed that way? Without a compile-time error or warning? The TreeSet API was designed when there were no generics in Java. There was virtually no way in Java to say "I want elements of a TreeSet to be of type java.lang.Comparable". Perhaps if generics were already there, the Collections API would be different. When generics arrived, it was too late to make the changes. The priority was to be backward-compatible and the TreeSet API stripped of generics had to stay the same.

What are Java mysteries you had to discover on your own?

The blog will be on hiatus until after Christmas so:

Merry Christmas! No unexpected exceptions in the New Year!