Pure Danger Tech


navigation
home

Writing a class hierarchy Comparator

29 Nov 2006

The other day I ran across the need to determine the best interface match for a particular class out of a set of possible interfaces. This is easy enough to do in general through use of Class.isAssignableFrom(). However, in the list of possible interfaces, I could also have super-interfaces as well. I wanted to bind to the most-specific interface I could.

One interesting implementation is to find all possible interface matches, then sort the classes based on their place in the hierarchy, and take the lowest one. To do this, I needed to implement a Comparator that sorted classes based on whether they are assignable from other classes, which is effectively a topological sort of the hierarchy. That is, assuming all the classes extend from some root, a class in the sorted results is always at the same or lower level in the hierarchy as all of the classes on its left.

For example, these classes would sort in this top-down order:

  • 1 – Throwable
  • 2 – Exception
  • 3 – IllegalArgumentException
  • 4 – IllegalFormatException

In case of siblings (or classes with no hierarchical relationship), the classes are sorted in order of full class name alphabetically to make things predictable. So, in the example above, if we threw in a few siblings of IllegalArgumentException and IllegalFormatException, we would see this:

  • 1 – java.lang.Throwable
  • 2 – java.lang.Exception
  • 3 – java.lang.IllegalArgumentException
  • 3 – java.lang.IllegalStateException
  • 3 – java.lang.IndexOutOfBoundsException
  • 4 – java.lang.NumberFormatException
  • 4 – java.util.IllegalFormatException
  • 4 – java.util.regex.PatternSyntaxException

This is basically a depth first walk of the hierarchy (# indicates the level in the class hierarchy). All of the level 4 classes are children of IllegalArgumentException but they are sorted after all of the level 3 classes. Also, note that at the 3 and 4 levels, classes are sorted alphabetically based on full path name (path included to make that clear).

Here’s the code for your pleasure. There are a couple of arbitrary choices in it about whether to sort classes high-low from left to right and whether to sort nulls to the beginning or the end. Easy enough to change those by swapping the 1 / -1 if you want.

public class ClassHierarchyComparator implements Comparator<Class<?>> {

    public int compare(Class<?> c1, Class<?> c2) {
        if(c1 == null) {
            if(c2 == null) {
                return 0;
            } else {
                // Sort nulls first
                return 1;
            }
        } else if(c2 == null) {
            // Sort nulls first
            return -1;
        }
        
        // At this point, we know that c1 and c2 are not null        
        if(c1.equals(c2)) {
            return 0;
        }
        
        // At this point, c1 and c2 are not null and not equal, here we 
        // compare them to see which is "higher" in the class hierarchy
        boolean c1Lower = c2.isAssignableFrom(c1);
        boolean c2Lower = c1.isAssignableFrom(c2);
        
        if(c1Lower && !c2Lower) {
            return 1;
        } else if(c2Lower && !c1Lower) {
            return -1;
        } 
        
        // Doesn't matter, sort consistently on classname
        return c1.getName().compareTo(c2.getName());
    }
}