Binary search tree

[d.tuser]

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 was not happy with BINARY_SEARCH_TREE from ISE, so I had to build a
new one.
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.

Regards
Daniel Tuser


-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[Colin Adams-3]

On 22/04/2008, Daniel Tuser <dan.tuser@...> 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.

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[d.tuser]

Colin Adams wrote:
> You would also need to write some general documentation in the gobodoc format.
>  
Ok.
> 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 know that the indexing clause does not conform to the Gobo styling
standards so far. And the class name should be in the same line as the
class keyword. Those are the two non-conforming things I know. Did you
find more?

> 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).
>  

You are right. "Not advisable" is much better.

> 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).
>  

This kind of code is actually the reason why I have to check the whole
code again. The design was not detailed when I started, as I just did
not know what was needed such that also Red-Black- and AVL-Trees could
reuse as much code as possible. So at certain positions it is not yet
good enough.
> Some of the routines are too long to read on the screen.
>  
I don't like that as well. Those are the algorithms that could also be
implemented as recursive features. I will see what I can do to improve
that. But I will not make them recursive.
A splitting into more features is also not easy as some features would
require about 4 or 5 arguments. I was already working on that but
stopped because the resulting code was not more readable. It could be
done using attributes. But it would take some time.
Do you think that has to be changed?

Another minor improvement I am going to use is the "Performance: O(...)"
comment as it is present in some Gobo classes.

Thanks for your comment.

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[Colin Adams-3]

On 24/04/2008, Daniel Tuser <dan.tuser@...> wrote:

> > Some of the routines are too long to read on the screen.
> >
> >
>  I don't like that as well. Those are the algorithms that could also be
> implemented as recursive features. I will see what I can do to improve that.
> But I will not make them recursive.
>  A splitting into more features is also not easy as some features would
> require about 4 or 5 arguments. I was already working on that but stopped
> because the resulting code was not more readable. It could be done using
> attributes. But it would take some time.

>  Do you think that has to be changed?

I would say yes, provided there is no significant performance impact.

I don't think passing 5 arguments is a reason not to do it, as the
routines receiving 5 arguments are all secret.

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[Colin Adams-3]

On 24/04/2008, Daniel Tuser <dan.tuser@...> wrote:
> Colin Adams wrote:

>  I know that the indexing clause does not conform to the Gobo styling
> standards so far. And the class name should be in the same line as the class
> keyword. Those are the two non-conforming things I know. Did you find more?

There area a load of empty feature clauses and a dummy invariant in at
least one
class.

Then I dislike the absence of a blank line after create and inherit.

Also I dislike seeing local variables with names that might class with
attributes (and so forcing unnecessary renames in descendants).
I personally now write all argument names as a_*, and all local names
as either a single chanaracter or l_*. I am converting my existing
code on a piecemeal basis.

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[d.tuser]

Colin Adams wrote:
> There area a load of empty feature clauses and a dummy invariant in at
> least one
> class.
>  
Done.
> Then I dislike the absence of a blank line after create and inherit.
>  
Done.
> Also I dislike seeing local variables with names that might class with
> attributes (and so forcing unnecessary renames in descendants).
> I personally now write all argument names as a_*, and all local names
> as either a single chanaracter or l_*. I am converting my existing
> code on a piecemeal basis.
>  
I like that suggestion and will do it like this.


Colin Adams wrote:

> On 24/04/2008, Daniel Tuser <dan.tuser@...> wrote:
>
>
>  
>>> Some of the routines are too long to read on the screen.
>>>      
>> I don't like that as well. Those are the algorithms that could also be
>> implemented as recursive features. I will see what I can do to improve that.
>> But I will not make them recursive.
>> A splitting into more features is also not easy as some features would
>> require about 4 or 5 arguments. I was already working on that but stopped
>> because the resulting code was not more readable. It could be done using
>> attributes. But it would take some time.
>>  Do you think that has to be changed?
>>    
>
> I would say yes, provided there is no significant performance impact.
>
> I don't think passing 5 arguments is a reason not to do it, as the
> routines receiving 5 arguments are all secret.
>  

5 arguments are no reason, I share that point of view. At the end it has
to be readable and understandable. I am just not sure if that is
achieved by splitting the features. But I will certainly try it.

In the Gobo documentation "author" is used in the indexing clause, but
most Gobo classes do not have it. So I won't use it.

I have several multi-line "description"s in the indexing clause that are
enclosed in "[ ]". Should I use % as seen e.g. in DS_SPARSE_TABLE?




-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[Eric Bezault]

Daniel Tuser wrote:
> In the Gobo documentation "author" is used in the indexing clause, but
> most Gobo classes do not have it. So I won't use it.

No need for "author".

> I have several multi-line "description"s in the indexing clause that are
> enclosed in "[ ]". Should I use % as seen e.g. in DS_SPARSE_TABLE?

You can use "[ ]".

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

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[Colin Adams-3]

2008/4/24 Daniel Tuser <dan.tuser@...>:
>  I know that the indexing clause does not conform to the Gobo styling
> standards so far. And the class name should be in the same line as the class
> keyword. Those are the two non-conforming things I know. Did you find more?

Also there were several routines without a header comment.

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[d.tuser]

I made several changes in the binary search tree implementation. All the
proposed modifications are included with some minor exceptions. One
example is that I don't use the l_* prefix for all locals, e.g. if there
is `i: INTEGER' it is still present and not `l_i: INTEGER'. Name clashes
should not be a problem in this case.
In class DS_BINARY_SEARCH_TREE there is a short `Todo' comment. I know,
that it is against all conventions. It is just there to show, that it is
not finished and not in a stable state.
I did not have enough time so far to modify DS_AVL_TREE and
DS_RED_BLACK_TREE. That is going to be very time consuming to split the
features.

Regards,
Daniel


-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[d.tuser]

Daniel Tuser wrote:
> I don't use the l_* prefix for all locals, e.g. if there is `i:
> INTEGER' it is still present and not `l_i: INTEGER'
I just saw that you do that as well.

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[d.tuser]

The test cases for binary search trees are now written. The attachment
also contains some modifications.
I've got a proposals for the class hierarchy of the DS_* classes. I
would like to have DS_BILINEAR_TABLE and DS_BILINEAR_SET. And
DS_SPARSE_TABLE inherits DS_BILINEAR_TABLE and DS_SPARSE_SET inherits
DS_BILINIEAR_SET. In the attachment the binary search tree
implementation already uses DS_BILINEAR_TABLE. In my opinion it makes
sense to have a common ancestor for hash table and binary search trees
that has both the table and cursor features.
I am working on a set implementation based on binary search trees. That
is why I would like to have DS_BILINEAR_SET as well. I am trying to make
it very much like hash table and hash set. The goal is actually to get
an abstraction of binary search tree that can be reused for the set
implementation.
Feedback is still welcome. Colin, are the features still too long?



-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[Colin Adams-3]

On 01/05/2008, Daniel Tuser <dan.tuser@...> wrote:

>  Feedback is still welcome. Colin, are the features still too long?

They are fine now.

I was a bit surprised to see you have been working on some of these
classes for nine years now. Of course they do require some careful
thought, but I would think you might be a little quicker than that.
:-)

(Copyright 2000 - 2008 - change to Copyright 2008, I would think. )


Eric will have to answer your other points.

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[d.tuser]

Colin Adams wrote:

> On 01/05/2008, Daniel Tuser <dan.tuser@...> wrote:
>
>  
>>  Feedback is still welcome. Colin, are the features still too long?
>>    
>
> They are fine now.
>
> I was a bit surprised to see you have been working on some of these
> classes for nine years now. Of course they do require some careful
> thought, but I would think you might be a little quicker than that.
> :-)
>
> (Copyright 2000 - 2008 - change to Copyright 2008, I would think. )
>
>  

Ok :-)

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[Eric Bezault]

Colin Adams wrote:
> Eric will have to answer your other points.

I'll try to have a look at it today. If I don't have time
to do so, then it will have to wait until next Tuesday as
I will be away from my computer during the coming days.

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


-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[d.tuser]

The two classes DS_BILINEAR_TABLE an DS_BILINEAR_SET are now integrated
in the binary search tree implementation. They would be useful in my
opinion. For the case that you do not want them, it is not hard to
remove them from the implementation.
Just to make it clear, the binary search tree implementation is still
not finished. There is still at least one bug and I didn't test it
extensively.


-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[Eric Bezault]

Daniel Tuser wrote:
> Just to make it clear, the binary search tree implementation is still
> not finished. There is still at least one bug and I didn't test it
> extensively.

In that case, I suggest that I release a new version of Gobo
first. Then I will have more time to review your code and see
how to best integrate it with the existing classes.

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

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[d.tuser]

Eric Bezault wrote:
> Daniel Tuser wrote:
>> Just to make it clear, the binary search tree implementation is still
>> not finished. There is still at least one bug and I didn't test it
>> extensively.
>
> In that case, I suggest that I release a new version of Gobo
> first. Then I will have more time to review your code and see
> how to best integrate it with the existing classes.
>
Yes. We have enough time :-).

I just found a problem related to gec. I know that you try to make gec
compatible to the compiler of Eiffel Software. The following class works
with EiffelStudio but does not compile with gec. I didn't have time to
have a closer look at the inheritance problem, so I just show you the
problem as you are preparing a release. You certainly need the binary
search tree classes from the previous post to compile the test.

class TEST_1

create

    make

feature {NONE}

    make is
           -- Creation procedure.
       local
          l_comparator: DS_COMPARABLE_COMPARATOR [STRING]
       do
          create l_comparator.make
          create tree.make (l_comparator)
       end

    tree: DS_AVL_TREE_SET [STRING]

end

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[Eric Bezault]

Daniel Tuser wrote:

> I just found a problem related to gec. I know that you try to make gec
> compatible to the compiler of Eiffel Software. The following class works
> with EiffelStudio but does not compile with gec. I didn't have time to
> have a closer look at the inheritance problem, so I just show you the
> problem as you are preparing a release. You certainly need the binary
> search tree classes from the previous post to compile the test.
>
> class TEST_1
>
> create
>
>    make
>
> feature {NONE}
>
>    make is
>           -- Creation procedure.
>       local
>          l_comparator: DS_COMPARABLE_COMPARATOR [STRING]
>       do
>          create l_comparator.make
>          create tree.make (l_comparator)
>       end
>
>    tree: DS_AVL_TREE_SET [STRING]
>
> end

I tried to compiled it with the very latest version of gec
and it compiled. So I guess the problem has been fixed since
you last tried it.

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

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[d.tuser]

Eric Bezault wrote:

> Daniel Tuser wrote:
>> I just found a problem related to gec. I know that you try to make
>> gec compatible to the compiler of Eiffel Software. The following
>> class works with EiffelStudio but does not compile with gec. I didn't
>> have time to have a closer look at the inheritance problem, so I just
>> show you the problem as you are preparing a release. You certainly
>> need the binary search tree classes from the previous post to compile
>> the test.
>>
>> class TEST_1
>> ...
>
> I tried to compiled it with the very latest version of gec
> and it compiled. So I guess the problem has been fixed since
> you last tried it.

I used the svn version and made a bootstrap to get the latest version of
gec. But maybe I somehow mixed two variants of the binary search tree
implementation. I tried to avoid that, but probably I missed something.
Maybe I can reproduce it, but it is not very likely.

-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop

[d.tuser]

Eric Bezault wrote:
> I tried to compiled it with the very latest version of gec
> and it compiled. So I guess the problem has been fixed since