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.
