harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Alexey Petrenko <alexey.a.petre...@gmail.com>
Subject Re: [eut][classlib][luni] different behaviors of TreeSet.remove() between RI and Harmony
Date Wed, 21 Jan 2009 12:32:05 GMT
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.
>>
>

Mime
View raw message