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 Wed, 11 Feb 2009 05:11:36 GMT
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 <xu.regis@gmail.com>
> 
>> 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.

Mime
View raw message