timsort (original) (raw)

Joshua Bloch jjb at google.com
Tue Jul 7 16:47:17 UTC 2009

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:

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>

More information about the core-libs-dev mailing list