import java.util.*;

class ThizBin1 { }

public class Version1 {
  public static void main(String[] args) {
    Queue<ThizBin1> qf = new PriorityQueue<ThizBin1>();
    qf.offer(new ThizBin1());
    qf.offer(new ThizBin1());
  }
}

Exception in thread "main" java.lang.ClassCastException: ThizBin1
        at java.util.PriorityQueue.fixUp(Unknown Source)
        at java.util.PriorityQueue.offer(Unknown Source)
        at Version1.main(Version1.java:9)

The problem in the example is that the PriorityQueue doesn't know what to do with the 2nd element that's offered because it can't establish the relative priority. We may guess that the ClassCastException comes when the PriorityQueue tries to cast the object in question to a Comparable. But the above error message doesn't give you any clue to that. You must have the necessary knowledge to figure out this message because you aren't given any help at either compile time or runtime.

This is rather reminiscent of C++ templates. When you make a mistake with a template, you get an error, although at compile time rather than runtime; a dauntingly long and usually incomprehensible sequence of messages. The experienced C++ programmer has come to recognize this as meaning "something is screwed up involving template code, but don't try to figure it out from this message -- instead, go back and stare at the code." The messages are generally too cryptic to figure out, although g++ has been producing more useful error messages and Leor Zolman has created an STL error message decryptor for C++ called STLFilt. The primary complaints that people (especially those criticizing C++ without much direct experience with it) have had about templates actually comes down to bad error messages, and the fact that the C++ compiler writers didn't build the equivalent of STLFilt into their compilers themselves points to a rather significant disconnect between compiler writers and their consumers. On the other hand, the C++ committee is now adding a feature to templates that will allow even better template error messages in the next version of C++. (These are called template concepts and are briefly described here.)

My observation about the above Java example is that it doesn't represent a graceful failure. Despite all the arguments about how generics allow static type checking, this doesn't take advantage of that. I personally have no problem with discovering some problems at runtime (indeed, I suspect that it might even be mathematically provable that you can only discover a relatively small set of problems at compile time). But the above error message doesn't give you much help in that direction, and would likely send the less-experienced programmer down many blind alleys in attempting to discover the problem.

Moving on, I decided to see if I could add Comparable without using the generic syntax for Comparable, which is a little confusing to programmers at this point in the book. This produced version 2 of the example:

import java.util.*;

class ThizBin2 implements Comparable {
  static int counter = 0;
  int id = counter++;
  public int compareTo(Object o) { return 0; }
  public String toString() { return Integer.toString(id); }
}

public class Version2 {
  public static void main(String[] args) {
    Queue<ThizBin2> qf = new PriorityQueue<ThizBin2>();
    for(int i = 0; i < 11; i++)
      qf.offer(new ThizBin2());
    while(!qf.isEmpty())
      System.out.println(qf.poll());
  }
}

In the above case, all ThizBin2 objects end up being comparably equivalent. It's certainly legal for two objects to compare as equivalent, but it's interesting to see what the PriorityQueue does with such objects:

0
10
9
8
7
6
5
4
3
2
1

Because they are comparably equivalent, it doesn't technically matter what order they appear, but it's still somewhat surprising that the fallback position isn't just to leave them in insertion order. This decision, if it was made consciously, was probably that it wasn't worth messing up the algorithm for such a special case.

For the final version of the exercise (which was ultimately a failure, since it ended up being too complicated for that point in the book), I embedded an Integer object in the ThizBin3 class, and effectively "passed" the Integer Comparable through as the Comparable for ThizBin3:

import java.util.*;

class ThizBin3 implements Comparable<ThizBin3> {
  static Random rand = new Random();
  Integer priority;
  ThizBin3() { priority = rand.nextInt(100); }
  public int compareTo(ThizBin3 t) {
    return priority.compareTo(t.priority);
  }
  public String toString() { return priority.toString(); }
}

public class Version3 {
  public static void main(String[] args) {
    Queue<ThizBin3> qf = new PriorityQueue<ThizBin3>();
    for(int i = 0; i < 10; i++)
      qf.offer(new ThizBin3());
    while(!qf.isEmpty())
      System.out.println(qf.poll());
  }
}

5
7
15
34
41
44
45
69
74
83

class MyCollection< E extends Comparable< E > > extends PriorityQueue< E > { /* or some other sorted collection */
    MyCollection( final Collection< E > c ) { super( e ); }
    MyCollection() {}
}

class Less<T>{
    public <T> Less(Comparator<T> comp) { ... }
    public <T extends Comparable<T>>Less() {
        this(new ComparableComparator<T>());
    }
}

Less<Integer> = new Less<Integer>();

Less<Foo> = new Less<Foo>(FooComparator comp);

Less<String> lessStandard = Less.<String>newInstance();

package davidhallexamples;
 
import java.util.*;
 
public class Less< T > {
    private static final Comparator< Comparable< Object > > naturalComparator = new Comparator<  Comparable< Object >  >() {
        public int compare( final Comparable< Object > lhs, final Comparable< Object > rhs ) {
            return lhs.compareTo( rhs );
        }
    };
    
    private final Comparator< T > c;
    
    public Less( final Comparator< T > c ) {
        if ( c == null ) throw new NullPointerException( "Null comparator" );
        this.c = c;
    }
    
    @SuppressWarnings( "unchecked" )
    public Less( final Class< T > clazz ) {
        this( (Comparator< T >)naturalComparator ); // Unchecked cast - OK - ignore
        if ( !Comparable.class.isAssignableFrom( clazz ) ) throw new IllegalArgumentException( "Given class, " +  clazz.getName() + ", does not implement Comparable" );
    }
    
    public static < T > Less< T > instance( final Class< T > clazz ) {
        return new Less< T >( clazz );
    }
    
    public static < T > Less< T > instance( final Comparator< T > comp ) {
        return new Less< T >( comp );
    }
    
    public boolean f( final T lhs, final T rhs ) {
        return c.compare( lhs, rhs ) < 0;
    }
    
    public static void main( final String[] notUsedInExample ) {
        final Less< String > lessString = instance( String.class );
        System.out.println( lessString.f( "A", "B" ) );
        final Less< Date > lessDate = instance( Date.class );
        System.out.println( lessDate.f( new java.sql.Time( 1 ), new java.sql.Time( 2 ) ) );
        final Less< java.sql.Time > lessTime = instance( java.sql.Time.class );
        System.out.println( lessTime.f( new java.sql.Time( 1 ), new java.sql.Time( 2 ) ) );
        final Less< Object > lessError = instance( Object.class ); // runtime exception
    }
}

true
true
true
Exception in thread "main" java.lang.IllegalArgumentException: Given class, java.lang.Object, does not implement Comparable
        at davidhallexamples.Less.<init>(Less.java:22)
        at davidhallexamples.Less.instance(Less.java:26)
        at davidhallexamples.Less.main(Less.java:44)
Java Result: 1