harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Regis <xu.re...@gmail.com>
Subject Re: [jira] Created: (HARMONY-6076) [eut][classlib][luni] - Arrays.sort(T[] a, Comparator<? super T> c) is not stable
Date Tue, 10 Feb 2009 02:35:44 GMT
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.

Mime
View raw message