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. > -- Best Regards Sean, Xiao Xia Qiu
