gobo-eiffel-develop

[gobo-eiffel-develop] DS_BINARY_SEARCH_TREE status ?

[Jann R. <roe...@et...>]

Hi,
I was wondering what the status of the DS_BINARY_SEARCH_TREE_* classes 
is. I was trying to use the DS_RED_BLACK_TREE_SET and found it to be 
quite buggy. I already spent several hours trying to fix the subtract 
feature. But fixing one bug always seems to uncover another one, which 
is quite frustrating.

Thanks,
Jann

Re: [gobo-eiffel-develop] DS_BINARY_SEARCH_TREE status ?

[Daniel T. <dan...@gm...>]

Jann Röder wrote:
> Hi,
> I was wondering what the status of the DS_BINARY_SEARCH_TREE_* classes 
> is. I was trying to use the DS_RED_BLACK_TREE_SET and found it to be 
> quite buggy. I already spent several hours trying to fix the subtract 
> feature. But fixing one bug always seems to uncover another one, which 
> is quite frustrating.
>   
Hi Jann
I am not aware of bugs in the implementation. All tests passed as far as 
I know. If you send me a reproduction, I may have a look at the problem.
> Thanks,
> Jann

Re: [gobo-eiffel-develop] DS_BINARY_SEARCH_TREE status ?

[Jann R. <roe...@et...>]

Hi Daniel,
I don't have a sample for all bugs. I will probably try to reproduce it 
again later, but for starters:

* subtract does not reset the found_item, thus causing weird behavior in 
has_key. The has_key implementation seems strange anyway. Why do you use 
a class variable as iterator. Locals are faster and easier to 
understand. I think the search feature should set found_item to Void in 
the beginning.

* subtract seems to remove the wrong node. It seems to remove the 
successor of the node that holds the item. In my code the postcondition 
is_disjoint fails.

* After changing subtract to remove the node which contains the item, I 
got other weird contract violations (it claimed that l_node was not in 
the same tree)

Jann

Daniel Tuser schrieb:
> Jann Röder wrote:
>> Hi,
>> I was wondering what the status of the DS_BINARY_SEARCH_TREE_* classes 
>> is. I was trying to use the DS_RED_BLACK_TREE_SET and found it to be 
>> quite buggy. I already spent several hours trying to fix the subtract 
>> feature. But fixing one bug always seems to uncover another one, which 
>> is quite frustrating.
>>   
> Hi Jann
> I am not aware of bugs in the implementation. All tests passed as far as 
> I know. If you send me a reproduction, I may have a look at the problem.
>> Thanks,
>> Jann

Re: [gobo-eiffel-develop] DS_BINARY_SEARCH_TREE status ?

[Daniel T. <dan...@gm...>]

Jann Röder wrote:
> Hi Daniel,
> I don't have a sample for all bugs. I will probably try to reproduce 
> it again later, but for starters:
I was able to reproduce the bug and know how to correct it. The problem 
is that one should never iterate like that through a 
DS_BINARY_SEARCH_TREE_CONTAINER and use `remove_node'. I will correct 
that as soon as possible. The problem is likely to be present in all set 
operations that remove items - certainly only in the binary search tree 
classes.
> * subtract does not reset the found_item, thus causing weird behavior 
> in has_key. The has_key implementation seems strange anyway. Why do 
> you use a class variable as iterator. Locals are faster and easier to 
> understand. I think the search feature should set found item to Void 
> in the beginning.
`found_node' is used to avoid redundant searches through the tree in 
`search_node'. E.g. if you first call `has (a_key)' and then `at 
(a_key)', then during the second call, the tree does not need to be 
traversed, as the result is already present in `found_node'.
At the time when I implemented all those classes I was not aware of the 
huge performance difference between attributes and local variables. I 
will change that as well in the loop.

Thanks for reporting the problem

Re: [gobo-eiffel-develop] DS_BINARY_SEARCH_TREE status ?

[Daniel T. <dan...@gm...>]

Hi Jann
The bug in `subtract' should now be corrected.

Regards
Daniel

Re: [gobo-eiffel-develop] DS_BINARY_SEARCH_TREE status ?

[Eric B. <er...@go...>]

Hi Daniel,

You might also want to have a look at this other bug report that
Jann sent to the Gobo users mailing list:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Hi,
there seems to be a bug in {DS_BINARY_SEARCH_TREE_SET}.copy .

The problem is, that internal_cursor is still Void when copy is called 
(by .twin). The Void call happens on internal_cursor.off .

Jann
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Jann Röder wrote:
> Hi Daniel,
> I don't have a sample for all bugs. I will probably try to reproduce it 
> again later, but for starters:
> 
> * subtract does not reset the found_item, thus causing weird behavior in 
> has_key. The has_key implementation seems strange anyway. Why do you use 
> a class variable as iterator. Locals are faster and easier to 
> understand. I think the search feature should set found_item to Void in 
> the beginning.
> 
> * subtract seems to remove the wrong node. It seems to remove the 
> successor of the node that holds the item. In my code the postcondition 
> is_disjoint fails.
> 
> * After changing subtract to remove the node which contains the item, I 
> got other weird contract violations (it claimed that l_node was not in 
> the same tree)
> 
> Jann
> 
> Daniel Tuser schrieb:
>> Jann Röder wrote:
>>> Hi,
>>> I was wondering what the status of the DS_BINARY_SEARCH_TREE_* classes 
>>> is. I was trying to use the DS_RED_BLACK_TREE_SET and found it to be 
>>> quite buggy. I already spent several hours trying to fix the subtract 
>>> feature. But fixing one bug always seems to uncover another one, which 
>>> is quite frustrating.
>>>   
>> Hi Jann
>> I am not aware of bugs in the implementation. All tests passed as far as 
>> I know. If you send me a reproduction, I may have a look at the problem.
>>> Thanks,
>>> Jann
> 


-- 
Eric Bezault
mailto:er...@go...
http://www.gobosoft.com

Re: [gobo-eiffel-develop] DS_BINARY_SEARCH_TREE status ?

[Daniel T. <dan...@gm...>]

Eric Bezault wrote:
> Hi Daniel,
>
> You might also want to have a look at this other bug report that
> Jann sent to the Gobo users mailing list:
>
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> Hi,
> there seems to be a bug in {DS_BINARY_SEARCH_TREE_SET}.copy .
>
> The problem is, that internal_cursor is still Void when copy is called 
> (by .twin). The Void call happens on internal_cursor.off .
>
> Jann
I missed that. I will correct it as soon as possible.

Re: [gobo-eiffel-develop] DS_BINARY_SEARCH_TREE status ?

[Daniel T. <dan...@gm...>]

Hi Jann
All the bugs you reported should now be corrected (in SVN). Please let 
me now if you still have trouble with the code. Thanks for reporting the 
bugs.

Regards,
Daniel

Re: [gobo-eiffel-develop] DS_BINARY_SEARCH_TREE status ?

[Jann R. <roe...@et...>]

Thanks Daniel for the quick fix.
My code works fine now!

Jann

Daniel Tuser schrieb:
> Hi Jann
> All the bugs you reported should now be corrected (in SVN). Please let 
> me now if you still have trouble with the code. Thanks for reporting the 
> bugs.
> 
> Regards,
> Daniel