DS_BINARY_SEARCH_TREE status ?

[Jann Röder-2]

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

------------------------------------------------------------------------------
Enter the BlackBerry Developer Challenge  
This is your chance to win up to $100,000 in prizes! For a limited time,
vendors submitting new applications to BlackBerry App World(TM) will have
the opportunity to enter the BlackBerry Developer Challenge. See full prize
details at: http://p.sf.net/sfu/blackberry
_______________________________________________
gobo-eiffel-develop mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[Daniel Tuser-2]

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

------------------------------------------------------------------------------
Enter the BlackBerry Developer Challenge  
This is your chance to win up to $100,000 in prizes! For a limited time,
vendors submitting new applications to BlackBerry App World(TM) will have
the opportunity to enter the BlackBerry Developer Challenge. See full prize
details at: http://p.sf.net/sfu/blackberry
_______________________________________________
gobo-eiffel-develop mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[Jann Röder-2]

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

------------------------------------------------------------------------------
Enter the BlackBerry Developer Challenge  
This is your chance to win up to $100,000 in prizes! For a limited time,
vendors submitting new applications to BlackBerry App World(TM) will have
the opportunity to enter the BlackBerry Developer Challenge. See full prize
details at: http://p.sf.net/sfu/blackberry
_______________________________________________
gobo-eiffel-develop mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[Eric Bezault]

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:[hidden email]
http://www.gobosoft.com

------------------------------------------------------------------------------
Enter the BlackBerry Developer Challenge  
This is your chance to win up to $100,000 in prizes! For a limited time,
vendors submitting new applications to BlackBerry App World(TM) will have
the opportunity to enter the BlackBerry Developer Challenge. See full prize
details at: http://p.sf.net/sfu/blackberry
_______________________________________________
gobo-eiffel-develop mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[Daniel Tuser-2]

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

------------------------------------------------------------------------------
Enter the BlackBerry Developer Challenge  
This is your chance to win up to $100,000 in prizes! For a limited time,
vendors submitting new applications to BlackBerry App World(TM) will have
the opportunity to enter the BlackBerry Developer Challenge. See full prize
details at: http://p.sf.net/sfu/blackberry
_______________________________________________
gobo-eiffel-develop mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[Daniel Tuser-2]

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.

------------------------------------------------------------------------------
Enter the BlackBerry Developer Challenge  
This is your chance to win up to $100,000 in prizes! For a limited time,
vendors submitting new applications to BlackBerry App World(TM) will have
the opportunity to enter the BlackBerry Developer Challenge. See full prize
details at: http://p.sf.net/sfu/blackberry
_______________________________________________
gobo-eiffel-develop mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[Daniel Tuser-2]

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

Regards
Daniel

------------------------------------------------------------------------------
Enter the BlackBerry Developer Challenge  
This is your chance to win up to $100,000 in prizes! For a limited time,
vendors submitting new applications to BlackBerry App World(TM) will have
the opportunity to enter the BlackBerry Developer Challenge. See full prize
details at: http://p.sf.net/sfu/blackberry
_______________________________________________
gobo-eiffel-develop mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[Daniel Tuser-2]

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

------------------------------------------------------------------------------
Enter the BlackBerry Developer Challenge  
This is your chance to win up to $100,000 in prizes! For a limited time,
vendors submitting new applications to BlackBerry App World(TM) will have
the opportunity to enter the BlackBerry Developer Challenge. See full prize  
details at: http://p.sf.net/sfu/Challenge
_______________________________________________
gobo-eiffel-develop mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[Jann Röder-2]

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

------------------------------------------------------------------------------
Enter the BlackBerry Developer Challenge  
This is your chance to win up to $100,000 in prizes! For a limited time,
vendors submitting new applications to BlackBerry App World(TM) will have
the opportunity to enter the BlackBerry Developer Challenge. See full prize  
details at: http://p.sf.net/sfu/Challenge
_______________________________________________
gobo-eiffel-develop mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop