timsort

[Joel Kamentz]

<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
>