timsort

[Joshua Bloch]

Joel,

Yep.  As a practical matter, it's likely to do so.  But consider the case of
a 1-element array: there's no way to test the transitivity and anti-symmetry
properties.  That's not the only case where the new implementation will fail
to detect a violation, but it's a clear proof that it is, in general,
impossible to do so.

   Josh

P.S.  I'm comfortable with the system property to select the legacy
implementation.

On Tue, Jul 7, 2009 at 9:44 AM, Joel Kamentz <Joel.Kamentz at sas.com> wrote:

> <lurking> You sort of said it yourself:  something along the lines of "if
> the natural comparison ordering violates comparable contract, the method
> _may_ throw IAE"?
>
> Joel
>
> -----Original Message-----
> From: core-libs-dev-bounces at openjdk.java.net [mailto:
> core-libs-dev-bounces at openjdk.java.net] On Behalf Of Martin Buchholz
> Sent: Tuesday, July 07, 2009 12:34 PM
> To: Christopher Hegarty -Sun Microsystems Ireland
> Cc: core-libs-dev
> Subject: Re: timsort
>
> On Tue, Jul 7, 2009 at 08:57, Christopher Hegarty -Sun Microsystems
> Ireland<Christopher.Hegarty at sun.com> wrote:
> > Martin Buchholz wrote:
> >>
> >>
> >> On Tue, Jul 7, 2009 at 07:35, Christopher Hegarty -Sun Microsystems
> >> Ireland
> >>
> >>
> >>
> >>           2) With the addition of @throws IllegalArgumentException, this
> >>             condition cannot be met with the old merge sort right, i.e.
> >>        running
> >>             with -Djava.util.Arrays.useLegacyMergeSort=true. So we're
> >>        saying
> >>             that all bets are off when running with this property set?
> >>
> >>
> >>        No.  Please re-read the @throws IllegalArgumentException.
> >>        It is carefully worded to make no promises at all.  All bets are
> >>        off - period.
> >>
> >>    OK great. But just to clarify, what exactly does "if the natural
> >>    order of the array elements is found to violate the Comparable
> >>    contract" mean?
> >>
> >>
> >> "natural order" is defined in the Comparable javadoc.
> >
> > Sorry, I still don't see how this @throws can be a no-op. Is it not
> possible
> > to craft an array of Comparables that violates the Comparable contract
> and
> > therefore provoke the sort method to throw IAE?
>
> It is not feasible to check whether a particular implementation of
> Comparable
> violates the Comparable contract - there are too many ways the contract
> can be violated, and checking may be too expensive.
>
> +     * @throws IllegalArgumentException if the natural order of the array
> +     *         elements is found to violate the {@link Comparable}
> contract
>
> So the proposed spec does not and cannot require any exception to be
> thrown.
> What is proposed is *if* the implementation happens to check for violations
> and if it chooses to throw an exception, then IAE is the exception type
> that will be used.
>
> Perhaps someone could come up with clearer wording than "is found to
> violate"?
>
> Martin
>
> > -Chris.
> >>
> >>  http://download.java.net/jdk7/docs/api/java/lang/Comparable.html
> >>
> >> We could use @linkplain to the Comparable spec, as elsewhere in
> java.util.
> >>
> >> Martin
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20090707/883efcef/attachment.html>