harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Regis <xu.re...@gmail.com>
Subject Re: [eut][classlib][luni] different behaviors of TreeSet.remove() between RI and Harmony
Date Wed, 21 Jan 2009 12:47:01 GMT
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 <aleksey.shipilev@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.regis@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.

Mime
View raw message