harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Sean Qiu <sean.xx....@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:33:36 GMT
Seems sensible, I've applied it at r743233.
Thanks for the patch. :-)

2009/2/11 Regis <xu.regis@gmail.com>:
> 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.
>



-- 
Best Regards
Sean, Xiao Xia Qiu

Mime
View raw message