Seems sensible, I've applied it at r743233. Thanks for the patch. :-) 2009/2/11 Regis <[email protected]>: > Sean Qiu wrote: >> >> Yes, seems this patch is not proper, I've revert the patch at >> r680223.Thanks >> for point it out. >> Could you please verify it now? >> >> >> 2009/2/10 Regis <[email protected]> >> >>> Regis Xu (JIRA) wrote: >>> >>>> [eut][classlib][luni] - Arrays.sort(T[] a, Comparator<? super T> c) is >>>> not stable >>>> >>>> >>>> ---------------------------------------------------------------------------------- >>>> >>>> Key: HARMONY-6076 >>>> URL: https://issues.apache.org/jira/browse/HARMONY-6076 >>>> Project: Harmony >>>> Issue Type: Bug >>>> Components: Classlib >>>> Affects Versions: 5.0M8 >>>> Reporter: Regis Xu >>>> Fix For: 5.0M9 >>>> >>>> >>>> spec says "This sort is guaranteed to be stable: equal elements will not >>>> be reordered as a result of the sort." >>>> but Harmony's implementation is not, which cause eut failure in >>>> org.eclipse.jdt.core.tests.compiler.test074 - 1.3 >>>> >>>> see the following test: >>>> >>>> public class TestArrays { >>>> public static void main(String[] args) { >>>> Element[] array = new Element[11]; >>>> array[0] = new Element(122); >>>> array[1] = new Element(146); >>>> array[2] = new Element(178); >>>> array[3] = new Element(208); >>>> array[4] = new Element(117); >>>> array[5] = new Element(146); >>>> array[6] = new Element(173); >>>> array[7] = new Element(203); >>>> array[8] = new Element(56); >>>> array[9] = new Element(82); >>>> array[10] = new Element(96); >>>> for (int i = 0; i < array.length; i++) { >>>> System.out.println("Element value is " + array[i].getValue() >>>> + " index is " + array[i].getIndex()); >>>> } >>>> >>>> Arrays.sort(array, new ElementComparator()); >>>> >>>> for (int i = 0; i < array.length; i++) { >>>> System.out.println("Element value is " + array[i].getValue() >>>> + " index is " + array[i].getIndex()); >>>> } >>>> } >>>> >>>> public static class Element { >>>> private int value; >>>> >>>> private int index; >>>> >>>> public int getIndex() { >>>> return index; >>>> } >>>> >>>> private static int count = 0; >>>> >>>> public int getValue() { >>>> return value; >>>> } >>>> >>>> public void setValue(int value) { >>>> this.value = value; >>>> } >>>> >>>> public Element(int value) { >>>> this.value = value; >>>> index = count++; >>>> } >>>> } >>>> >>>> public static class ElementComparator implements Comparator { >>>> >>>> public int compare(Object arg0, Object arg1) { >>>> return ((Element) arg0).getValue() - ((Element) >>>> arg1).getValue(); >>>> } >>>> >>>> } >>>> } >>>> >>>> notice array[1] and array[5] has the same value, the indexes are 1 and 5 >>>> corresponding, after a stable sort, element has index 1 should be ahead >>>> of >>>> element has index 5 >>>> >>>> output of RI: >>>> >>>> =========before sort============= >>>> Element value is 122 index is 0 >>>> Element value is 146 index is 1 >>>> Element value is 178 index is 2 >>>> Element value is 208 index is 3 >>>> Element value is 117 index is 4 >>>> Element value is 146 index is 5 >>>> Element value is 173 index is 6 >>>> Element value is 203 index is 7 >>>> Element value is 56 index is 8 >>>> Element value is 82 index is 9 >>>> Element value is 96 index is 10 >>>> >>>> =========after sort============= >>>> Element value is 56 index is 8 >>>> Element value is 82 index is 9 >>>> Element value is 96 index is 10 >>>> Element value is 117 index is 4 >>>> Element value is 122 index is 0 >>>> Element value is 146 index is 1 >>>> Element value is 146 index is 5 >>>> Element value is 173 index is 6 >>>> Element value is 178 index is 2 >>>> Element value is 203 index is 7 >>>> Element value is 208 index is 3 >>>> >>>> output of Harmony: >>>> >>>> =========before sort============= >>>> Element value is 122 index is 0 >>>> Element value is 146 index is 1 >>>> Element value is 178 index is 2 >>>> Element value is 208 index is 3 >>>> Element value is 117 index is 4 >>>> Element value is 146 index is 5 >>>> Element value is 173 index is 6 >>>> Element value is 203 index is 7 >>>> Element value is 56 index is 8 >>>> Element value is 82 index is 9 >>>> Element value is 96 index is 10 >>>> >>>> =========after sort============= >>>> Element value is 56 index is 8 >>>> Element value is 82 index is 9 >>>> Element value is 96 index is 10 >>>> Element value is 117 index is 4 >>>> Element value is 122 index is 0 >>>> Element value is 146 index is 5 >>>> Element value is 146 index is 1 >>>> Element value is 173 index is 6 >>>> Element value is 178 index is 2 >>>> Element value is 203 index is 7 >>>> Element value is 208 index is 3 >>>> >>>> notice that in Harmony index 1 and 5 is out of order after sort >>>> >>>> Hi, >>> >>> when I fixed this issue with the following patch: >>> Index: modules/luni/src/main/java/java/util/Arrays.java >>> >>> ===================================================================== >>> >>> --- modules/luni/src/main/java/java/util/Arrays.java >>> >>> +++ modules/luni/src/main/java/java/util/Arrays.java >>> >>> @@ -2520,7 +2520,7 @@ public class Arrays { >>> >>> Object fromVal = in[start]; >>> >>> Object rVal = in[r]; >>> >>> if (c.compare(fromVal, rVal) <= 0) { >>> >>> - int l_1 = find(in, rVal, 0, start + 1, med - 1, c); >>> >>> + int l_1 = find(in, rVal, -1, start + 1, med - 1, c); >>> >>> int toCopy = l_1 - start + 1; >>> >>> System.arraycopy(in, start, out, i, toCopy); >>> >>> i += toCopy; >>> >>> I found it made the test >>> ArraysTest.test_sort$Ljava_lang_ObjectLjava_util_Comparator faild: >>> junit.framework.AssertionFailedError: expected:<200> but was:<310> >>> at junit.framework.Assert.fail(Assert.java:47) >>> at junit.framework.Assert.failNotEquals(Assert.java:277) >>> at junit.framework.Assert.assertEquals(Assert.java:64) >>> at junit.framework.Assert.assertEquals(Assert.java:71) >>> at >>> >>> org.apache.harmony.luni.tests.java.util.ArraysTest.test_sort$Ljava_lang_ObjectLjava_util_Comparator(ArraysTest.java:1354) >>> >>> look into the source, the test use the Comparator for sort: >>> Comparator comparator = new Comparator(){ >>> public int compare(Object o1, Object o2) { >>> Integer e1 = (Integer)o1; >>> Integer e2 = (Integer)o2; >>> return e1 > e2 ? 1 : 0; >>> } >>> }; >>> >>> which doesn't impose a total ordering. The order under this Comparator >>> can't be defined. So the sort result is depend on implementations. >>> >>> I suggest remove this test, I believe it's abuse of Comparator. >>> What you do think? >>> >>> -- >>> Best Regards, >>> Regis. >>> >> >> >> > > Thanks Sean. I attached a test case for this regression on JIRA, could you > help to review it? Thanks. > > -- > Best Regards, > Regis. >
-- Best Regards Sean, Xiao Xia Qiu
