You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@harmony.apache.org by Regis <xu...@gmail.com> on 2009/01/21 13:06:15 UTC
[eut][classlib][luni] different behaviors of TreeSet.remove() between
RI and Harmony
Hi,
I track the eut test testAddWorkingSet in org.eclipse.ui.tests, found
this failure was caused by Harmony TreeSet can't remove a element
already in the set. After further investigation, I found the test
changed the elements after added them to set, that corrupt the set, but
RI could remove the element successfully even the set is not ordered.
Following test demo the scenario:
public class TestTreeSet {
public static void main(String[] args) {
TreeSet set = new TreeSet();
Entry temp = new Entry(2);
set.add(new Entry(1));
set.add(temp);
set.add(new Entry(3));
set.add(new Entry(4));
set.add(new Entry(5));
set.add(new Entry(6));
temp.setValue(0);
for (Iterator iterator = set.iterator(); iterator.hasNext();) {
Entry entry = (Entry) iterator.next();
System.out.println(entry.value);
}
System.out.println(set.remove(temp));
}
public static class Entry implements Comparable {
private int value;
public Entry(int value) {
this.value = value;
}
public void setValue(int value) {
this.value = value;
}
public int getValue() {
return value;
}
public int compareTo(Object arg0) {
return value - ((Entry) arg0).value;
}
}
public static class TestComparator implements Comparator {
public int compare(Object arg0, Object arg1) {
return ((Entry) arg0).getValue() - ((Entry) arg1).getValue();
}
}
}
output of RI:
1
0
3
4
5
6
true
output of Harmony:
1
0
3
4
5
6
false
In Harmony, binary search is used to find the element, in this case, the
array is not ordered, so it can't work correctly. From spec:
"The set will not contain the specified element once the call returns"
So I think RI's behavior is more reasonable.
This can be fixed by comparing every element in set when remove, but
will cause performance downgrade, what do you think? Any suggestions/ideas?
--
Best Regards,
Regis.
Re: [eut][classlib][luni] different behaviors of TreeSet.remove()
between RI and Harmony
Posted by Alexey Petrenko <al...@gmail.com>.
> Could we apply patch to Eclipse community directly? This issue had no
> actions since it opened.
I do not know about any Eclipse committer around...
But I believe that the patch can make things faster...
SY, Alexey
Re: [eut][classlib][luni] different behaviors of TreeSet.remove()
between RI and Harmony
Posted by Regis <xu...@gmail.com>.
Alexey Petrenko wrote:
> I've reread the TreeSet spec, which says "This class guarantees that
> the sorted set will be in ascending element order, sorted according to
> the natural order of the elements (see Comparable), or by the
> comparator provided at set creation time, depending on which
> constructor is used." So if we change the sorting order by such kind
> of "dirty hack" then I would say that class behavior is unpredictable.
> Because the TreeSet itself has no way to know about these changes. And
> if we will compare all the elements while remove then it will be
> impossible for us to fit another requirement from the spec:
> "implementation provides guaranteed log(n) time cost for the basic
> operations (add, remove and contains)".
>
> So I'm voting for work with the Eclipse community to fix the issue in
> their source base.
>
> SY, Alexey
>
> 2009/1/21 Aleksey Shipilev <al...@gmail.com>:
>> Hi Regis,
>>
>> From Java class library side, the behaviour in this case is unspecified.
>>
>> I believe you hit on the known issue with EUT, please refer to
>> archived Harmony thread [1]. Reading back that thread you might notice
>> that this is the inconsistency in EUT which (by some miracle occasion)
>> works well with RI. There's the Eclipse bug against that submitted
>> [2].
>>
>> Thanks,
>> Aleksey.
>>
>> [1] http://markmail.org/message/svoktdxopww6sv7p
>> [2] https://bugs.eclipse.org/bugs/show_bug.cgi?id=212583
>>
>> On Wed, Jan 21, 2009 at 3:06 PM, Regis <xu...@gmail.com> wrote:
>>> Hi,
>>>
>>> I track the eut test testAddWorkingSet in org.eclipse.ui.tests, found this
>>> failure was caused by Harmony TreeSet can't remove a element already in the
>>> set. After further investigation, I found the test changed the elements
>>> after added them to set, that corrupt the set, but RI could remove the
>>> element successfully even the set is not ordered.
>>>
>>> Following test demo the scenario:
>>>
>>> public class TestTreeSet {
>>> public static void main(String[] args) {
>>> TreeSet set = new TreeSet();
>>> Entry temp = new Entry(2);
>>> set.add(new Entry(1));
>>> set.add(temp);
>>> set.add(new Entry(3));
>>> set.add(new Entry(4));
>>> set.add(new Entry(5));
>>> set.add(new Entry(6));
>>> temp.setValue(0);
>>>
>>> for (Iterator iterator = set.iterator(); iterator.hasNext();) {
>>> Entry entry = (Entry) iterator.next();
>>> System.out.println(entry.value);
>>> }
>>>
>>> System.out.println(set.remove(temp));
>>> }
>>>
>>> public static class Entry implements Comparable {
>>> private int value;
>>>
>>> public Entry(int value) {
>>> this.value = value;
>>> }
>>>
>>> public void setValue(int value) {
>>> this.value = value;
>>> }
>>>
>>> public int getValue() {
>>> return value;
>>> }
>>>
>>> public int compareTo(Object arg0) {
>>> return value - ((Entry) arg0).value;
>>> }
>>> }
>>>
>>> public static class TestComparator implements Comparator {
>>>
>>> public int compare(Object arg0, Object arg1) {
>>> return ((Entry) arg0).getValue() - ((Entry) arg1).getValue();
>>> }
>>>
>>> }
>>> }
>>>
>>> output of RI:
>>> 1
>>> 0
>>> 3
>>> 4
>>> 5
>>> 6
>>> true
>>>
>>> output of Harmony:
>>> 1
>>> 0
>>> 3
>>> 4
>>> 5
>>> 6
>>> false
>>>
>>> In Harmony, binary search is used to find the element, in this case, the
>>> array is not ordered, so it can't work correctly. From spec:
>>>
>>> "The set will not contain the specified element once the call returns"
>>>
>>> So I think RI's behavior is more reasonable.
>>>
>>> This can be fixed by comparing every element in set when remove, but will
>>> cause performance downgrade, what do you think? Any suggestions/ideas?
>>>
>>> --
>>> Best Regards,
>>> Regis.
>>>
>
Could we apply patch to Eclipse community directly? This issue had no
actions since it opened.
--
Best Regards,
Regis.
Re: [eut][classlib][luni] different behaviors of TreeSet.remove()
between RI and Harmony
Posted by Alexey Petrenko <al...@gmail.com>.
I've reread the TreeSet spec, which says "This class guarantees that
the sorted set will be in ascending element order, sorted according to
the natural order of the elements (see Comparable), or by the
comparator provided at set creation time, depending on which
constructor is used." So if we change the sorting order by such kind
of "dirty hack" then I would say that class behavior is unpredictable.
Because the TreeSet itself has no way to know about these changes. And
if we will compare all the elements while remove then it will be
impossible for us to fit another requirement from the spec:
"implementation provides guaranteed log(n) time cost for the basic
operations (add, remove and contains)".
So I'm voting for work with the Eclipse community to fix the issue in
their source base.
SY, Alexey
2009/1/21 Aleksey Shipilev <al...@gmail.com>:
> Hi Regis,
>
> From Java class library side, the behaviour in this case is unspecified.
>
> I believe you hit on the known issue with EUT, please refer to
> archived Harmony thread [1]. Reading back that thread you might notice
> that this is the inconsistency in EUT which (by some miracle occasion)
> works well with RI. There's the Eclipse bug against that submitted
> [2].
>
> Thanks,
> Aleksey.
>
> [1] http://markmail.org/message/svoktdxopww6sv7p
> [2] https://bugs.eclipse.org/bugs/show_bug.cgi?id=212583
>
> On Wed, Jan 21, 2009 at 3:06 PM, Regis <xu...@gmail.com> wrote:
>> Hi,
>>
>> I track the eut test testAddWorkingSet in org.eclipse.ui.tests, found this
>> failure was caused by Harmony TreeSet can't remove a element already in the
>> set. After further investigation, I found the test changed the elements
>> after added them to set, that corrupt the set, but RI could remove the
>> element successfully even the set is not ordered.
>>
>> Following test demo the scenario:
>>
>> public class TestTreeSet {
>> public static void main(String[] args) {
>> TreeSet set = new TreeSet();
>> Entry temp = new Entry(2);
>> set.add(new Entry(1));
>> set.add(temp);
>> set.add(new Entry(3));
>> set.add(new Entry(4));
>> set.add(new Entry(5));
>> set.add(new Entry(6));
>> temp.setValue(0);
>>
>> for (Iterator iterator = set.iterator(); iterator.hasNext();) {
>> Entry entry = (Entry) iterator.next();
>> System.out.println(entry.value);
>> }
>>
>> System.out.println(set.remove(temp));
>> }
>>
>> public static class Entry implements Comparable {
>> private int value;
>>
>> public Entry(int value) {
>> this.value = value;
>> }
>>
>> public void setValue(int value) {
>> this.value = value;
>> }
>>
>> public int getValue() {
>> return value;
>> }
>>
>> public int compareTo(Object arg0) {
>> return value - ((Entry) arg0).value;
>> }
>> }
>>
>> public static class TestComparator implements Comparator {
>>
>> public int compare(Object arg0, Object arg1) {
>> return ((Entry) arg0).getValue() - ((Entry) arg1).getValue();
>> }
>>
>> }
>> }
>>
>> output of RI:
>> 1
>> 0
>> 3
>> 4
>> 5
>> 6
>> true
>>
>> output of Harmony:
>> 1
>> 0
>> 3
>> 4
>> 5
>> 6
>> false
>>
>> In Harmony, binary search is used to find the element, in this case, the
>> array is not ordered, so it can't work correctly. From spec:
>>
>> "The set will not contain the specified element once the call returns"
>>
>> So I think RI's behavior is more reasonable.
>>
>> This can be fixed by comparing every element in set when remove, but will
>> cause performance downgrade, what do you think? Any suggestions/ideas?
>>
>> --
>> Best Regards,
>> Regis.
>>
>
Re: [eut][classlib][luni] different behaviors of TreeSet.remove()
between RI and Harmony
Posted by Jim Yu <ju...@gmail.com>.
2009/1/21 Regis <xu...@gmail.com>
> Aleksey Shipilev wrote:
>
>> Yeah, that was a lucky coincidence.
>>
>> I had changed:
>> - Entry temp = new Entry(2);
>> + Entry temp = new Entry(10);
>>
>> ...and both RI and Harmony prints out "false".
>>
>> Thanks,
>> Aleksey.
>>
>> On Wed, Jan 21, 2009 at 3:43 PM, Regis <xu...@gmail.com> wrote:
>>
>>> Aleksey Shipilev wrote:
>>>
>>>> Hi Regis,
>>>>
>>>> From Java class library side, the behaviour in this case is
>>>>> unspecified.
>>>>>
>>>> I believe you hit on the known issue with EUT, please refer to
>>>> archived Harmony thread [1]. Reading back that thread you might notice
>>>> that this is the inconsistency in EUT which (by some miracle occasion)
>>>> works well with RI. There's the Eclipse bug against that submitted
>>>> [2].
>>>>
>>>> Thanks,
>>>> Aleksey.
>>>>
>>>> [1] http://markmail.org/message/svoktdxopww6sv7p
>>>> [2] https://bugs.eclipse.org/bugs/show_bug.cgi?id=212583
>>>>
>>>> On Wed, Jan 21, 2009 at 3:06 PM, Regis <xu...@gmail.com> wrote:
>>>>
>>>>> Hi,
>>>>>
>>>>> I track the eut test testAddWorkingSet in org.eclipse.ui.tests, found
>>>>> this
>>>>> failure was caused by Harmony TreeSet can't remove a element already in
>>>>> the
>>>>> set. After further investigation, I found the test changed the elements
>>>>> after added them to set, that corrupt the set, but RI could remove the
>>>>> element successfully even the set is not ordered.
>>>>>
>>>>> Following test demo the scenario:
>>>>>
>>>>> public class TestTreeSet {
>>>>> public static void main(String[] args) {
>>>>> TreeSet set = new TreeSet();
>>>>> Entry temp = new Entry(2);
>>>>> set.add(new Entry(1));
>>>>> set.add(temp);
>>>>> set.add(new Entry(3));
>>>>> set.add(new Entry(4));
>>>>> set.add(new Entry(5));
>>>>> set.add(new Entry(6));
>>>>> temp.setValue(0);
>>>>>
>>>>> for (Iterator iterator = set.iterator(); iterator.hasNext();) {
>>>>> Entry entry = (Entry) iterator.next();
>>>>> System.out.println(entry.value);
>>>>> }
>>>>>
>>>>> System.out.println(set.remove(temp));
>>>>> }
>>>>>
>>>>> public static class Entry implements Comparable {
>>>>> private int value;
>>>>>
>>>>> public Entry(int value) {
>>>>> this.value = value;
>>>>> }
>>>>>
>>>>> public void setValue(int value) {
>>>>> this.value = value;
>>>>> }
>>>>>
>>>>> public int getValue() {
>>>>> return value;
>>>>> }
>>>>>
>>>>> public int compareTo(Object arg0) {
>>>>> return value - ((Entry) arg0).value;
>>>>> }
>>>>> }
>>>>>
>>>>> public static class TestComparator implements Comparator {
>>>>>
>>>>> public int compare(Object arg0, Object arg1) {
>>>>> return ((Entry) arg0).getValue() - ((Entry) arg1).getValue();
>>>>> }
>>>>>
>>>>> }
>>>>> }
>>>>>
>>>>> output of RI:
>>>>> 1
>>>>> 0
>>>>> 3
>>>>> 4
>>>>> 5
>>>>> 6
>>>>> true
>>>>>
>>>>> output of Harmony:
>>>>> 1
>>>>> 0
>>>>> 3
>>>>> 4
>>>>> 5
>>>>> 6
>>>>> false
>>>>>
>>>>> In Harmony, binary search is used to find the element, in this case,
>>>>> the
>>>>> array is not ordered, so it can't work correctly. From spec:
>>>>>
>>>>> "The set will not contain the specified element once the call returns"
>>>>>
>>>>> So I think RI's behavior is more reasonable.
>>>>>
>>>>> This can be fixed by comparing every element in set when remove, but
>>>>> will
>>>>> cause performance downgrade, what do you think? Any suggestions/ideas?
>>>>>
>>>>> --
>>>>> Best Regards,
>>>>> Regis.
>>>>>
>>>>> Thanks for your informations, Aleksey.
>>>
>>> --
>>> Best Regards,
>>> Regis.
>>>
>>>
>>
> Interesting :)
> It seems RI didn't compare the whole list too, so we must wait eclipse to
> fix this issue.
>
Since the time complexity for remove operation is guaranteed to be log(n)
according to the spec, I think RI should have used the binary search as
well : )
And the behavior difference between harmony and RI for the special case is
probably caused by the minor difference of the implementation for binary
search.
>
> --
> Best Regards,
> Regis.
>
--
Best Regards,
Jim, Jun Jie Yu
China Software Development Lab, IBM
Re: [eut][classlib][luni] different behaviors of TreeSet.remove()
between RI and Harmony
Posted by Tim Ellison <t....@gmail.com>.
Regis wrote:
> Aleksey Shipilev wrote:
>> Yeah, that was a lucky coincidence.
>>
>> I had changed:
>> - Entry temp = new Entry(2);
>> + Entry temp = new Entry(10);
>>
>> ...and both RI and Harmony prints out "false".
>>
>> Thanks,
>> Aleksey.
>>
>> On Wed, Jan 21, 2009 at 3:43 PM, Regis <xu...@gmail.com> wrote:
>>> Aleksey Shipilev wrote:
>>>> Hi Regis,
>>>>
>>>>> From Java class library side, the behaviour in this case is
>>>>> unspecified.
>>>> I believe you hit on the known issue with EUT, please refer to
>>>> archived Harmony thread [1]. Reading back that thread you might notice
>>>> that this is the inconsistency in EUT which (by some miracle occasion)
>>>> works well with RI. There's the Eclipse bug against that submitted
>>>> [2].
>>>>
>>>> Thanks,
>>>> Aleksey.
>>>>
>>>> [1] http://markmail.org/message/svoktdxopww6sv7p
>>>> [2] https://bugs.eclipse.org/bugs/show_bug.cgi?id=212583
>>>>
>>>> On Wed, Jan 21, 2009 at 3:06 PM, Regis <xu...@gmail.com> wrote:
>>>>> Hi,
>>>>>
>>>>> I track the eut test testAddWorkingSet in org.eclipse.ui.tests, found
>>>>> this
>>>>> failure was caused by Harmony TreeSet can't remove a element
>>>>> already in
>>>>> the
>>>>> set. After further investigation, I found the test changed the
>>>>> elements
>>>>> after added them to set, that corrupt the set, but RI could remove the
>>>>> element successfully even the set is not ordered.
>>>>>
>>>>> Following test demo the scenario:
>>>>>
>>>>> public class TestTreeSet {
>>>>> public static void main(String[] args) {
>>>>> TreeSet set = new TreeSet();
>>>>> Entry temp = new Entry(2);
>>>>> set.add(new Entry(1));
>>>>> set.add(temp);
>>>>> set.add(new Entry(3));
>>>>> set.add(new Entry(4));
>>>>> set.add(new Entry(5));
>>>>> set.add(new Entry(6));
>>>>> temp.setValue(0);
>>>>>
>>>>> for (Iterator iterator = set.iterator(); iterator.hasNext();) {
>>>>> Entry entry = (Entry) iterator.next();
>>>>> System.out.println(entry.value);
>>>>> }
>>>>>
>>>>> System.out.println(set.remove(temp));
>>>>> }
>>>>>
>>>>> public static class Entry implements Comparable {
>>>>> private int value;
>>>>>
>>>>> public Entry(int value) {
>>>>> this.value = value;
>>>>> }
>>>>>
>>>>> public void setValue(int value) {
>>>>> this.value = value;
>>>>> }
>>>>>
>>>>> public int getValue() {
>>>>> return value;
>>>>> }
>>>>>
>>>>> public int compareTo(Object arg0) {
>>>>> return value - ((Entry) arg0).value;
>>>>> }
>>>>> }
>>>>>
>>>>> public static class TestComparator implements Comparator {
>>>>>
>>>>> public int compare(Object arg0, Object arg1) {
>>>>> return ((Entry) arg0).getValue() - ((Entry)
>>>>> arg1).getValue();
>>>>> }
>>>>>
>>>>> }
>>>>> }
>>>>>
>>>>> output of RI:
>>>>> 1
>>>>> 0
>>>>> 3
>>>>> 4
>>>>> 5
>>>>> 6
>>>>> true
>>>>>
>>>>> output of Harmony:
>>>>> 1
>>>>> 0
>>>>> 3
>>>>> 4
>>>>> 5
>>>>> 6
>>>>> false
>>>>>
>>>>> In Harmony, binary search is used to find the element, in this
>>>>> case, the
>>>>> array is not ordered, so it can't work correctly. From spec:
>>>>>
>>>>> "The set will not contain the specified element once the call returns"
>>>>>
>>>>> So I think RI's behavior is more reasonable.
>>>>>
>>>>> This can be fixed by comparing every element in set when remove,
>>>>> but will
>>>>> cause performance downgrade, what do you think? Any suggestions/ideas?
>>>>>
>>>>> --
>>>>> Best Regards,
>>>>> Regis.
>>>>>
>>> Thanks for your informations, Aleksey.
>>>
>>> --
>>> Best Regards,
>>> Regis.
>>>
>>
>
> Interesting :)
> It seems RI didn't compare the whole list too, so we must wait eclipse
> to fix this issue.
I'll ping them...
Tim
Re: [eut][classlib][luni] different behaviors of TreeSet.remove()
between RI and Harmony
Posted by Regis <xu...@gmail.com>.
Aleksey Shipilev wrote:
> Yeah, that was a lucky coincidence.
>
> I had changed:
> - Entry temp = new Entry(2);
> + Entry temp = new Entry(10);
>
> ...and both RI and Harmony prints out "false".
>
> Thanks,
> Aleksey.
>
> On Wed, Jan 21, 2009 at 3:43 PM, Regis <xu...@gmail.com> wrote:
>> Aleksey Shipilev wrote:
>>> Hi Regis,
>>>
>>>> From Java class library side, the behaviour in this case is unspecified.
>>> I believe you hit on the known issue with EUT, please refer to
>>> archived Harmony thread [1]. Reading back that thread you might notice
>>> that this is the inconsistency in EUT which (by some miracle occasion)
>>> works well with RI. There's the Eclipse bug against that submitted
>>> [2].
>>>
>>> Thanks,
>>> Aleksey.
>>>
>>> [1] http://markmail.org/message/svoktdxopww6sv7p
>>> [2] https://bugs.eclipse.org/bugs/show_bug.cgi?id=212583
>>>
>>> On Wed, Jan 21, 2009 at 3:06 PM, Regis <xu...@gmail.com> wrote:
>>>> Hi,
>>>>
>>>> I track the eut test testAddWorkingSet in org.eclipse.ui.tests, found
>>>> this
>>>> failure was caused by Harmony TreeSet can't remove a element already in
>>>> the
>>>> set. After further investigation, I found the test changed the elements
>>>> after added them to set, that corrupt the set, but RI could remove the
>>>> element successfully even the set is not ordered.
>>>>
>>>> Following test demo the scenario:
>>>>
>>>> public class TestTreeSet {
>>>> public static void main(String[] args) {
>>>> TreeSet set = new TreeSet();
>>>> Entry temp = new Entry(2);
>>>> set.add(new Entry(1));
>>>> set.add(temp);
>>>> set.add(new Entry(3));
>>>> set.add(new Entry(4));
>>>> set.add(new Entry(5));
>>>> set.add(new Entry(6));
>>>> temp.setValue(0);
>>>>
>>>> for (Iterator iterator = set.iterator(); iterator.hasNext();) {
>>>> Entry entry = (Entry) iterator.next();
>>>> System.out.println(entry.value);
>>>> }
>>>>
>>>> System.out.println(set.remove(temp));
>>>> }
>>>>
>>>> public static class Entry implements Comparable {
>>>> private int value;
>>>>
>>>> public Entry(int value) {
>>>> this.value = value;
>>>> }
>>>>
>>>> public void setValue(int value) {
>>>> this.value = value;
>>>> }
>>>>
>>>> public int getValue() {
>>>> return value;
>>>> }
>>>>
>>>> public int compareTo(Object arg0) {
>>>> return value - ((Entry) arg0).value;
>>>> }
>>>> }
>>>>
>>>> public static class TestComparator implements Comparator {
>>>>
>>>> public int compare(Object arg0, Object arg1) {
>>>> return ((Entry) arg0).getValue() - ((Entry) arg1).getValue();
>>>> }
>>>>
>>>> }
>>>> }
>>>>
>>>> output of RI:
>>>> 1
>>>> 0
>>>> 3
>>>> 4
>>>> 5
>>>> 6
>>>> true
>>>>
>>>> output of Harmony:
>>>> 1
>>>> 0
>>>> 3
>>>> 4
>>>> 5
>>>> 6
>>>> false
>>>>
>>>> In Harmony, binary search is used to find the element, in this case, the
>>>> array is not ordered, so it can't work correctly. From spec:
>>>>
>>>> "The set will not contain the specified element once the call returns"
>>>>
>>>> So I think RI's behavior is more reasonable.
>>>>
>>>> This can be fixed by comparing every element in set when remove, but will
>>>> cause performance downgrade, what do you think? Any suggestions/ideas?
>>>>
>>>> --
>>>> Best Regards,
>>>> Regis.
>>>>
>> Thanks for your informations, Aleksey.
>>
>> --
>> Best Regards,
>> Regis.
>>
>
Interesting :)
It seems RI didn't compare the whole list too, so we must wait eclipse
to fix this issue.
--
Best Regards,
Regis.
Re: [eut][classlib][luni] different behaviors of TreeSet.remove()
between RI and Harmony
Posted by Aleksey Shipilev <al...@gmail.com>.
Yeah, that was a lucky coincidence.
I had changed:
- Entry temp = new Entry(2);
+ Entry temp = new Entry(10);
...and both RI and Harmony prints out "false".
Thanks,
Aleksey.
On Wed, Jan 21, 2009 at 3:43 PM, Regis <xu...@gmail.com> wrote:
>
> Aleksey Shipilev wrote:
>>
>> Hi Regis,
>>
>>> From Java class library side, the behaviour in this case is unspecified.
>>
>> I believe you hit on the known issue with EUT, please refer to
>> archived Harmony thread [1]. Reading back that thread you might notice
>> that this is the inconsistency in EUT which (by some miracle occasion)
>> works well with RI. There's the Eclipse bug against that submitted
>> [2].
>>
>> Thanks,
>> Aleksey.
>>
>> [1] http://markmail.org/message/svoktdxopww6sv7p
>> [2] https://bugs.eclipse.org/bugs/show_bug.cgi?id=212583
>>
>> On Wed, Jan 21, 2009 at 3:06 PM, Regis <xu...@gmail.com> wrote:
>>>
>>> Hi,
>>>
>>> I track the eut test testAddWorkingSet in org.eclipse.ui.tests, found
>>> this
>>> failure was caused by Harmony TreeSet can't remove a element already in
>>> the
>>> set. After further investigation, I found the test changed the elements
>>> after added them to set, that corrupt the set, but RI could remove the
>>> element successfully even the set is not ordered.
>>>
>>> Following test demo the scenario:
>>>
>>> public class TestTreeSet {
>>> public static void main(String[] args) {
>>> TreeSet set = new TreeSet();
>>> Entry temp = new Entry(2);
>>> set.add(new Entry(1));
>>> set.add(temp);
>>> set.add(new Entry(3));
>>> set.add(new Entry(4));
>>> set.add(new Entry(5));
>>> set.add(new Entry(6));
>>> temp.setValue(0);
>>>
>>> for (Iterator iterator = set.iterator(); iterator.hasNext();) {
>>> Entry entry = (Entry) iterator.next();
>>> System.out.println(entry.value);
>>> }
>>>
>>> System.out.println(set.remove(temp));
>>> }
>>>
>>> public static class Entry implements Comparable {
>>> private int value;
>>>
>>> public Entry(int value) {
>>> this.value = value;
>>> }
>>>
>>> public void setValue(int value) {
>>> this.value = value;
>>> }
>>>
>>> public int getValue() {
>>> return value;
>>> }
>>>
>>> public int compareTo(Object arg0) {
>>> return value - ((Entry) arg0).value;
>>> }
>>> }
>>>
>>> public static class TestComparator implements Comparator {
>>>
>>> public int compare(Object arg0, Object arg1) {
>>> return ((Entry) arg0).getValue() - ((Entry) arg1).getValue();
>>> }
>>>
>>> }
>>> }
>>>
>>> output of RI:
>>> 1
>>> 0
>>> 3
>>> 4
>>> 5
>>> 6
>>> true
>>>
>>> output of Harmony:
>>> 1
>>> 0
>>> 3
>>> 4
>>> 5
>>> 6
>>> false
>>>
>>> In Harmony, binary search is used to find the element, in this case, the
>>> array is not ordered, so it can't work correctly. From spec:
>>>
>>> "The set will not contain the specified element once the call returns"
>>>
>>> So I think RI's behavior is more reasonable.
>>>
>>> This can be fixed by comparing every element in set when remove, but will
>>> cause performance downgrade, what do you think? Any suggestions/ideas?
>>>
>>> --
>>> Best Regards,
>>> Regis.
>>>
>>
>
> Thanks for your informations, Aleksey.
>
> --
> Best Regards,
> Regis.
>
Re: [eut][classlib][luni] different behaviors of TreeSet.remove()
between RI and Harmony
Posted by Regis <xu...@gmail.com>.
Aleksey Shipilev wrote:
> Hi Regis,
>
>>>From Java class library side, the behaviour in this case is unspecified.
>
> I believe you hit on the known issue with EUT, please refer to
> archived Harmony thread [1]. Reading back that thread you might notice
> that this is the inconsistency in EUT which (by some miracle occasion)
> works well with RI. There's the Eclipse bug against that submitted
> [2].
>
> Thanks,
> Aleksey.
>
> [1] http://markmail.org/message/svoktdxopww6sv7p
> [2] https://bugs.eclipse.org/bugs/show_bug.cgi?id=212583
>
> On Wed, Jan 21, 2009 at 3:06 PM, Regis <xu...@gmail.com> wrote:
>> Hi,
>>
>> I track the eut test testAddWorkingSet in org.eclipse.ui.tests, found this
>> failure was caused by Harmony TreeSet can't remove a element already in the
>> set. After further investigation, I found the test changed the elements
>> after added them to set, that corrupt the set, but RI could remove the
>> element successfully even the set is not ordered.
>>
>> Following test demo the scenario:
>>
>> public class TestTreeSet {
>> public static void main(String[] args) {
>> TreeSet set = new TreeSet();
>> Entry temp = new Entry(2);
>> set.add(new Entry(1));
>> set.add(temp);
>> set.add(new Entry(3));
>> set.add(new Entry(4));
>> set.add(new Entry(5));
>> set.add(new Entry(6));
>> temp.setValue(0);
>>
>> for (Iterator iterator = set.iterator(); iterator.hasNext();) {
>> Entry entry = (Entry) iterator.next();
>> System.out.println(entry.value);
>> }
>>
>> System.out.println(set.remove(temp));
>> }
>>
>> public static class Entry implements Comparable {
>> private int value;
>>
>> public Entry(int value) {
>> this.value = value;
>> }
>>
>> public void setValue(int value) {
>> this.value = value;
>> }
>>
>> public int getValue() {
>> return value;
>> }
>>
>> public int compareTo(Object arg0) {
>> return value - ((Entry) arg0).value;
>> }
>> }
>>
>> public static class TestComparator implements Comparator {
>>
>> public int compare(Object arg0, Object arg1) {
>> return ((Entry) arg0).getValue() - ((Entry) arg1).getValue();
>> }
>>
>> }
>> }
>>
>> output of RI:
>> 1
>> 0
>> 3
>> 4
>> 5
>> 6
>> true
>>
>> output of Harmony:
>> 1
>> 0
>> 3
>> 4
>> 5
>> 6
>> false
>>
>> In Harmony, binary search is used to find the element, in this case, the
>> array is not ordered, so it can't work correctly. From spec:
>>
>> "The set will not contain the specified element once the call returns"
>>
>> So I think RI's behavior is more reasonable.
>>
>> This can be fixed by comparing every element in set when remove, but will
>> cause performance downgrade, what do you think? Any suggestions/ideas?
>>
>> --
>> Best Regards,
>> Regis.
>>
>
Thanks for your informations, Aleksey.
--
Best Regards,
Regis.
Re: [eut][classlib][luni] different behaviors of TreeSet.remove()
between RI and Harmony
Posted by Aleksey Shipilev <al...@gmail.com>.
Hi Regis,
>From Java class library side, the behaviour in this case is unspecified.
I believe you hit on the known issue with EUT, please refer to
archived Harmony thread [1]. Reading back that thread you might notice
that this is the inconsistency in EUT which (by some miracle occasion)
works well with RI. There's the Eclipse bug against that submitted
[2].
Thanks,
Aleksey.
[1] http://markmail.org/message/svoktdxopww6sv7p
[2] https://bugs.eclipse.org/bugs/show_bug.cgi?id=212583
On Wed, Jan 21, 2009 at 3:06 PM, Regis <xu...@gmail.com> wrote:
> Hi,
>
> I track the eut test testAddWorkingSet in org.eclipse.ui.tests, found this
> failure was caused by Harmony TreeSet can't remove a element already in the
> set. After further investigation, I found the test changed the elements
> after added them to set, that corrupt the set, but RI could remove the
> element successfully even the set is not ordered.
>
> Following test demo the scenario:
>
> public class TestTreeSet {
> public static void main(String[] args) {
> TreeSet set = new TreeSet();
> Entry temp = new Entry(2);
> set.add(new Entry(1));
> set.add(temp);
> set.add(new Entry(3));
> set.add(new Entry(4));
> set.add(new Entry(5));
> set.add(new Entry(6));
> temp.setValue(0);
>
> for (Iterator iterator = set.iterator(); iterator.hasNext();) {
> Entry entry = (Entry) iterator.next();
> System.out.println(entry.value);
> }
>
> System.out.println(set.remove(temp));
> }
>
> public static class Entry implements Comparable {
> private int value;
>
> public Entry(int value) {
> this.value = value;
> }
>
> public void setValue(int value) {
> this.value = value;
> }
>
> public int getValue() {
> return value;
> }
>
> public int compareTo(Object arg0) {
> return value - ((Entry) arg0).value;
> }
> }
>
> public static class TestComparator implements Comparator {
>
> public int compare(Object arg0, Object arg1) {
> return ((Entry) arg0).getValue() - ((Entry) arg1).getValue();
> }
>
> }
> }
>
> output of RI:
> 1
> 0
> 3
> 4
> 5
> 6
> true
>
> output of Harmony:
> 1
> 0
> 3
> 4
> 5
> 6
> false
>
> In Harmony, binary search is used to find the element, in this case, the
> array is not ordered, so it can't work correctly. From spec:
>
> "The set will not contain the specified element once the call returns"
>
> So I think RI's behavior is more reasonable.
>
> This can be fixed by comparing every element in set when remove, but will
> cause performance downgrade, what do you think? Any suggestions/ideas?
>
> --
> Best Regards,
> Regis.
>
Re: [eut][classlib][luni] different behaviors of TreeSet.remove()
between RI and Harmony
Posted by Alexey Petrenko <al...@gmail.com>.
Is binary search used for removing element only? If not then this
could affect all the other cases too...
2009/1/21 Regis <xu...@gmail.com>:
> Hi,
>
> I track the eut test testAddWorkingSet in org.eclipse.ui.tests, found this
> failure was caused by Harmony TreeSet can't remove a element already in the
> set. After further investigation, I found the test changed the elements
> after added them to set, that corrupt the set, but RI could remove the
> element successfully even the set is not ordered.
>
> Following test demo the scenario:
>
> public class TestTreeSet {
> public static void main(String[] args) {
> TreeSet set = new TreeSet();
> Entry temp = new Entry(2);
> set.add(new Entry(1));
> set.add(temp);
> set.add(new Entry(3));
> set.add(new Entry(4));
> set.add(new Entry(5));
> set.add(new Entry(6));
> temp.setValue(0);
>
> for (Iterator iterator = set.iterator(); iterator.hasNext();) {
> Entry entry = (Entry) iterator.next();
> System.out.println(entry.value);
> }
>
> System.out.println(set.remove(temp));
> }
>
> public static class Entry implements Comparable {
> private int value;
>
> public Entry(int value) {
> this.value = value;
> }
>
> public void setValue(int value) {
> this.value = value;
> }
>
> public int getValue() {
> return value;
> }
>
> public int compareTo(Object arg0) {
> return value - ((Entry) arg0).value;
> }
> }
>
> public static class TestComparator implements Comparator {
>
> public int compare(Object arg0, Object arg1) {
> return ((Entry) arg0).getValue() - ((Entry) arg1).getValue();
> }
>
> }
> }
>
> output of RI:
> 1
> 0
> 3
> 4
> 5
> 6
> true
>
> output of Harmony:
> 1
> 0
> 3
> 4
> 5
> 6
> false
>
> In Harmony, binary search is used to find the element, in this case, the
> array is not ordered, so it can't work correctly. From spec:
>
> "The set will not contain the specified element once the call returns"
>
> So I think RI's behavior is more reasonable.
>
> This can be fixed by comparing every element in set when remove, but will
> cause performance downgrade, what do you think? Any suggestions/ideas?
>
> --
> Best Regards,
> Regis.
>