Re: [gobo-eiffel-develop] Binary search tree

[Colin A. <col...@go...>]

On 22/04/2008, Daniel Tuser <dan...@gm...> wrote:
> Hi all
>  I would like to know whether the Gobo community and developers are
> interested in a binary search tree implementation. Recently I needed it and

Personally, I've never had the need for one. But I think it would be a
useful addition to the structure library.

>  My implementation inherits from DS_TABLE and DS_BILINEAR. The
> implementation is NOT finished, I have to revisit every single line of code
> including the comments. If you are interested I would be happy to get some
> general feedback, such that I could take it into account when revisiting the
> code. Test cases are missing so far.

You would also need to write some general documentation in the gobodoc format.

I've taken a fairly casual look. Generally it looks good.

The one thing that does stand out is that it does not conform to the
Gobo styling standards.

I'm rather puzzled by this comment:

" Direct instances should not be used in practice as the trees may
become unbalanced."

The class name (DS_BINARY_SEARCH_TREE) does not dictate balanced
trees. Nor does there seem to be anything at first glance that
requires the tree to be balanced.

So perhaps you mean to say that creating direct instances is not
advisable. (otherwise you could simply mark the class as deferred).

In DS_BINARY_SEARCH_TREE_NODE, the assertion tags on the creation
procedures don't read well to me:

			reuse_if_no_parent: parent = Void
			reuse_if_no_left_child: left_child = Void
			reuse_if_no_right_child: right_child = Void

I don't understand what is going on here. Make is not used in the
class except as a creation procedure, when the assertions are
trivially True (nor do it seem to be used in the descendants).

Some of the routines are too long to read on the screen.