[collections] ComparableComparator executes all comparisons twice!?

[Rodney Waldhoff <rw...@apache.org>]

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:   <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>

Re: [collections] ComparableComparator executes all comparisons twice!?

[Rodney Waldhoff <rw...@apache.org>]

While we're at it, I wonder if it might be better to remove a lot of the
"checking" going on inside ComparableComparator.compare.  I'm thinking
something as simple as:

public int compare(Object o1, Object o2) {
  return ((Comparable)o1).compareTo(o2);
}

and letting Java and/or the underlying Comparable objects throw NPE or CCE
as necessary.

There is some precedence here.  java.util.Collections.reverseOrder()
returns a Comparator whose compare() method is implemented as:

public int compare(Object o1, Object o2) {
 Comparable c1 = (Comparable)o1;
 Comparable c2 = (Comparable)o2;
 return -c1.compareTo(c2);
}

(By the way, I think the way we throw ClassCastException in the case of
null in the current implementation is misleading.  The
Comparable/Comparator JavaDocs don't say "throw CCE if you can't do the
comparision", but rather, "throw CCE if the argument's *type* prevents you
from doing the comparision.")

On Wed, 8 Jan 2003, Stephen Colebourne wrote:

> From: "Rodney Waldhoff" <rw...@apache.org>
>
> > I suggest that we replace the block above with simply:
> >
> >   return ((Comparable)o1).compareTo(o2);
>
> +1
>


--
To unsubscribe, e-mail:   <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>

[collections] deprecation policty (was Re: [collections] ComparableComparator executes all comparisons twice!?)

[Rodney Waldhoff <rw...@apache.org>]

Please change the subject line when thread veers off the original topic
like this one has.

On Thu, 9 Jan 2003, Ola Berg wrote:

> > ie) Unwanted code is deprecated for the next major or minor release, and
> > removed in the major release following that.
> >
> > so:
> >
> > 1.0 -> 2.0, Foo.foo is deprecated
> > 2.0 -> 2.1, Foo.bar is deprecated
> > 2.1 -> 3.0, Foo.foo and Foo.bar are both removed
> >
> > or if it is such that we just need to do N releases between deprecation
> > and removal, specify that. Basically get something simple and effective
> > standardised to stop future debates.
>
> I'd suggest:
>
> patch number 1.2.1 -> 1.2.2 = bugfix, no API or behavioural changes
>
> minor number 1.2.3 -> 1.3.0 = adding functionality/API, still backwards
> compatible (classes or methods may be added)
>
> major number 2.0.0 -> = risk for backward incompatibilities
>
> With this scheme, the removal of deprecated methods and classes needs a new
> major release number.
>
> /O
>
> --


--
To unsubscribe, e-mail:   <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>

Re: [collections] ComparableComparator executes all comparisons twice!?

[Ola Berg <ol...@arkitema.se>]

> ie) Unwanted code is deprecated for the next major or minor release, and
> removed in the major release following that.
>
> so:
>
> 1.0 -> 2.0, Foo.foo is deprecated
> 2.0 -> 2.1, Foo.bar is deprecated
> 2.1 -> 3.0, Foo.foo and Foo.bar are both removed
>
> or if it is such that we just need to do N releases between deprecation
> and removal, specify that. Basically get something simple and effective
> standardised to stop future debates.

I'd suggest:

patch number 1.2.1 -> 1.2.2 = bugfix, no API or behavioural changes

minor number 1.2.3 -> 1.3.0 = adding functionality/API, still backwards 
compatible (classes or methods may be added) 

major number 2.0.0 -> = risk for backward incompatibilities

With this scheme, the removal of deprecated methods and classes needs a new 
major release number.

/O

--
To unsubscribe, e-mail:   <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>

Re: [collections] ComparableComparator executes all comparisons twice!?

[Henri Yandell <ba...@generationjava.com>]

On Wed, 8 Jan 2003, Stephen Colebourne wrote:

> If we do go to 3.0, then could we delete the deprecated iterators and
> comparators in the main package?

And if this gets chosen as a fine way to do things, could we document it
in the DEV-GUIDE?

ie) Unwanted code is deprecated for the next major or minor release, and
removed in the major release following that.

so:

1.0 -> 2.0, Foo.foo is deprecated
2.0 -> 2.1, Foo.bar is deprecated
2.1 -> 3.0, Foo.foo and Foo.bar are both removed

or if it is such that we just need to do N releases between deprecation
and removal, specify that. Basically get something simple and effective
standardised to stop future debates.

Hen


--
To unsubscribe, e-mail:   <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>

Re: [collections] ComparableComparator executes all comparisons twice!?

[Stephen Colebourne <sc...@btopenworld.com>]

From: "Rodney Waldhoff" <rw...@apache.org>
Subject: [collections] ComparableComparator executes all comparisons twice!?

> 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).
Crazy!

> I suggest that we replace the block above with simply:
>
>   return ((Comparable)o1).compareTo(o2);
+1

>  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.
I suppose so, although personally I wouldn't be hung up on this particular
change.

> (The addition of collections.primitives probably justifies a new major
> version number anyway.)
Agreed.

If we do go to 3.0, then could we delete the deprecated iterators and
comparators in the main package?

Stephen



--
To unsubscribe, e-mail:   <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>