A Fresh Look at Comparisons, Take 2

[Steven Schveighoffer]

"Janice Caron" wrote
> On 18/04/2008, Steven Schveighoffer wrote:
>>  I don't really agree that opEquals or opCmp should not be inherited.  I
>>  think normal inheritance the way it is now is just fine.
>
> You do? Why?
>
> You obviously understand that if Z is a
> great-great-great-great-...-grandchild of A, then it will still use
> A's opCmp() function if not overridden? And you're OK with that?

Yes.  That is a choice of the great-great-great-...-grandchild of A's author 
:)  By not overriding opEquals or opCmp, he is saying that if you compare it 
with something else, A's implementation is the one to use.  If he wanted to 
specify that opCmp should be different he would have rewritten opCmp.

>>  You need to have opEquals in Object in order to support hashing.
>
> Please could you elaborate, as I don't understand why this is so?

A hashtable works by putting objects into buckets based on a hash-code. 
Usually you mod the hash-code so it fits in an array.

At that point, you have to deal with collisions.  So a simple method is to 
use a linked list for each bucket.

To look-up that object, you need to traverse the list, finding the object 
that equals the input.

So for example, an int[int], to lookup the int, it first converts to a 
hash-code, finds the right bucket, then traverses the linked list looking 
for the int equal to the key.  Then it returns the value.  So for anything 
to be a key, it must be able to provide a hash, and you must be able to 
check for equality.

>>  The default opCmp should be redefined to throw an exception.
>
> Again, I ask, why? Why detect something at run-time that could be
> detected at compile time?

I think the better solution is to use the interface.  But if that is not 
acceptable, at the very least, the default implementation should throw an 
exception.

>
> Moreover, if Z is a great-great-great-great-...-grandchild of A, then
> it will use A's opCmp() function - not Object's. Overriding opCmp even
> /once/ changes the defaut for the entire heirarchy from that point
> down, and at that point, Object's implementation becomes irrelevant.

The only benefit I see is that you would not have to declare that an object 
implements the interface.  Personally I don't think it's worth it, but I 
could live with it.  The way it is now is completely wrong.

>>  An alternative
>>  is that opCmp is defined in an interface.
>
> Yes, that is an alternative. I had thought of that. But then I
> realised that orderedness can be detected at compile-time without need
> for an interface, so it seemed unnecessary.

It cannot be detected at compile time:

class A
{
   int opCmp(Object o){...}
}

class B: A
{
   int opCmp(Object o)
   { throw new UnOrderedException("cannot order B");}
}

void f(A a, Object o)
{
   a < o; // can you tell at compile time whether a is a B or an A?
}

-Steve