Re: [gobo-eiffel-develop] Adding tree support to gobo

[Einar K. <eka...@cs...>]

On 27 Jun 2001, Andreas Leitner wrote:

> On 27 Jun 2001 16:55:12 +0200, Eric Bezault wrote:
>>>...
> > That would be great. If you can manage to integrate them
> > with the other classes of the Gobo Eiffel Structure Library
> > such as DS_CONTAINER, DS_TRAVERSABLE or DS_CURSOR, it would
> > be even better.
I think of inheriting from DS_CONTAINER. DS_TRAVERSABLE presents
problems as trees can be traversed in many orders. I plan to include
pre-, post-, inorder and Lindst=F6m-traversing. If someone has suggestion=
s
on any other containers to inherit please send a message. I will
provide external iterators. If there would be internal iterators that
would mean four iterators per tree or functions that set/get the iterator
type. I think this is not very wise but if most people want it I can
include it too.

> >
> > BTW, I think that someone already wrote a red black tree
> > in Eiffel, so perhaps you can borrow some ideas or chunks
> > of code. I don't remember the name of the author nor the
> > URL (it was part of a sound library if I recall correctly),
> > but I'm sure that Geoff Eldridge can give us a pointer since
> > it was reported in his excellent ELJ daily news (although
> > it was a long time ago).
>
>
> Do you mean this library, Eric?
> http://www.eiffel-forum.org/archive/durian/red_black_tree.htm
I will check it out. Thanks for the pointer.


> Btw, Einar: Are you going to write a Tree Library as in a container tha=
t
> holds an abitrarily nested (but non recursive) item structure, or a set
> of classes (like the RB-Tree) that implement a sorted list with a
> certain tree structure?
Currently I am only going to implement binary trees. I know other kinds o=
f
trees are important too, but I think getting the binary trees in the lib
first should be important. If someone wants to implement e.g. B-trees or
tries they are welcome to, but I don't currently have time for that.

- Einar Karttunen