I recently noticed something that I found rather surprising. Given two
Comparables compA and compB, ComparableComparator always executes both
compA.compareTo(compB) *and* compB.compareTo(compA) (and throws
ClassCastException if the two results are inconsistent). The relevant
part of the code looks like this:
int result1 = ((Comparable)o1).compareTo(o2);
int result2 = ((Comparable)o2).compareTo(o1);
// enforce comparable contract
if(result1 == 0 && result2 == 0) {
return 0;
} else if(result1 < 0 && result2 > 0) {
return result1;
} else if(result1 > 0 && result2 < 0) {
return result1;
} else {
// results inconsistent
throw new ClassCastException("o1 not comparable to o2");
}
To me this seems rather wasteful, in that
(a) this doubles the number of comparisons executed for any given
algorithm, and in many algorithms comparisons are executed quite
frequently, and
(b) conceivably Comparable.compareTo might be an expensive operation in
and of itself (so even in the case of infrequent comparisons doing it
twice as often as necessary may have an noticeable impact).
This also seems like overkill in that:
(c) The Comparable contract guarantees that the compareTo relation defines
a total order (more specifically, that sgn(c1.compareTo(c2)) ==
-sgn(c2.compareTo(c1))), so all this does is validate that the provided
implementation adheres to its advertised contract
(d) conceivably, I might choose to use ComparableCompartor with a
Comparable that violates the Comparable contract, and be willing to live
with the consequences of doing so.
This seems to me like an appropriate place to apply a "garbage in, garbage
out" strategy, and simply state "if the given Comparables fail to define a
total order, then this Comparable may also fail to implement a total
order" (or perhaps not even state it, that's certainly the contract
assumed until I saw differently).
I suggest that we replace the block above with simply:
return ((Comparable)o1).compareTo(o2);
and if a "checking" ComparableComparator is useful, that we move that
implementation out to some subclass (or to a JDK 1.4 assertion, I
suppose). Unfortunately ComparableComparator does in fact state in its
JavaDocs that it "throws ClassCastException if the compareTo of both
objects do not provide an inverse result of each other as per the
Comparable javadoc.", which does make this a small change in the
ComparableComparator contract. This change in contract would of course
imply a new major version number, per the commons versioning guidelines.
(The addition of collections.primitives probably justifies a new major
version number anyway.)
Thoughts? Objections?
- Rod
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
