You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by "Regis Xu (JIRA)" <ji...@apache.org> on 2009/01/22 08:35:59 UTC
[jira] Created: (HARMONY-6076) [eut][classlib][luni] -
Arrays.sort(T[] a, Comparator c) is not stable
[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
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
Re: [jira] Created: (HARMONY-6076) [eut][classlib][luni] -
Arrays.sort(T[] a, Comparator c) is not stable
Posted by Sean Qiu <se...@gmail.com>.
Seems sensible, I've applied it at r743233.
Thanks for the patch. :-)
2009/2/11 Regis <xu...@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...@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
Re: [jira] Created: (HARMONY-6076) [eut][classlib][luni] - Arrays.sort(T[]
a, Comparator c) is not stable
Posted by Regis <xu...@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...@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.
Re: [jira] Created: (HARMONY-6076) [eut][classlib][luni] -
Arrays.sort(T[] a, Comparator c) is not stable
Posted by Sean Qiu <se...@gmail.com>.
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...@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.
>
--
Best Regards
Sean, Xiao Xia Qiu
Re: [jira] Created: (HARMONY-6076) [eut][classlib][luni] -
Arrays.sort(T[] a, Comparator c) is not stable
Posted by Jim Yu <ju...@gmail.com>.
2009/2/10 Regis <xu...@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 agree with Regis that this Comparator is incorrectly implemented,
according to the spec, the compare method must ensure 'that compare(x,
y)==0implies that sgn(compare(x,
z))==sgn(compare(y, z)) for all z.' Let's assume x = 1, y = 5, z = 3. Then
sgn(compare(x, z)) = 0, while sgn(compare(y, z)) = 1 which violates the
spec.
>
>
> I suggest remove this test, I believe it's abuse of Comparator.
> What you do think?
>
> --
> Best Regards,
> Regis.
>
--
Best Regards,
Jim, Jun Jie Yu
China Software Development Lab, IBM
Re: [jira] Created: (HARMONY-6076) [eut][classlib][luni] - Arrays.sort(T[]
a, Comparator c) is not stable
Posted by Regis <xu...@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.
[jira] Resolved: (HARMONY-6076) [eut][classlib][luni] -
Arrays.sort(T[] a, Comparator c) is not stable
Posted by "Sean Qiu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-6076?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sean Qiu resolved HARMONY-6076.
-------------------------------
Resolution: Fixed
The incorrect patch is reverted at r742850.
Could you please verify it?
Thank you very much.
> [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
> Assignee: Sean Qiu
> 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
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Assigned: (HARMONY-6076) [eut][classlib][luni] -
Arrays.sort(T[] a, Comparator c) is not stable
Posted by "Sean Qiu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-6076?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sean Qiu reassigned HARMONY-6076:
---------------------------------
Assignee: Sean Qiu
> [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
> Assignee: Sean Qiu
> 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
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-6076) [eut][classlib][luni] -
Arrays.sort(T[] a, Comparator c) is not stable
Posted by "Regis Xu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-6076?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Regis Xu updated HARMONY-6076:
------------------------------
Attachment: HARMONY-6076.diff
add regression test
> [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
> Assignee: Sean Qiu
> Fix For: 5.0M9
>
> Attachments: HARMONY-6076.diff
>
>
> 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
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-6076) [eut][classlib][luni] -
Arrays.sort(T[] a, Comparator c) is not stable
Posted by "Sean Qiu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-6076?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12672514#action_12672514 ]
Sean Qiu commented on HARMONY-6076:
-----------------------------------
Thanks for your testcase.
It is applied at r743233.
Please verify if it works as you expected.
> [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
> Assignee: Sean Qiu
> Fix For: 5.0M9
>
> Attachments: HARMONY-6076.diff
>
>
> 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
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Closed: (HARMONY-6076) [eut][classlib][luni] -
Arrays.sort(T[] a, Comparator c) is not stable
Posted by "Regis Xu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-6076?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Regis Xu closed HARMONY-6076.
-----------------------------
Verified. Thanks Sean.
> [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
> Assignee: Sean Qiu
> Fix For: 5.0M9
>
> Attachments: HARMONY-6076.diff
>
>
> 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
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.