harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jim Yu <junjie0...@gmail.com>
Subject Re: [eut][classlib][luni] different behaviors of TreeSet.remove() between RI and Harmony
Date Thu, 22 Jan 2009 05:50:57 GMT
2009/1/21 Regis <xu.regis@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.regis@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.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.
>>>>>
>>>>>  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

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message