gobo-eiffel-develop

[gobo-eiffel-develop] Re: ant4e

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

Sven Ehrke wrote (in http://groups.yahoo.com/group/elj-win32-dev/):
> 
> Hi everyone,
> 
> I am back from my holidays and just had to do it:
> under the tools/ant4e directory of bonbon you can find a first version
> of an eiffel build tool based on the concepts of Jakarta's Ant
> tool for Java.
> All you have to do is to create a file called ebuild.xml
> (take the one which is there as a template).
> Currently only two tasks are supported:
> 
>   - the SmallEiffel compile task
>   - a general exec task
> 
> this is enough to get a project compiled, cleaned etc., so we
> could get rid of the elj.bat files.
> Look in the small Readme.txt in tools/ant4e if you're interested.
> 
> one extension I plan to include is the cluster list of system
> into the ebuild.xml. That information then could be used to
> generate to loadpath.se file and files needed for Visual Eiffel
> and ISE Eiffel.
> 
> BTW: mexp is required.
> 
> Let me know what you think.
> 
> - Sven

This is just to let people on the elj-win32-dev mailing list
know that Andreas Leitner is currently developing a similar
tool called xace (this name might change when the tool gets
part of the Gobo distribution) as part of the Gobo project.
It would be nice if the ELJ and Gobo teams could join their
efforts and build a unique tool. You can check what Andreas
has already done in the eXML mailing list archive:

  http://groups.yahoo.com/group/exml/messages

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

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

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

Hello

I am/will be coding a small tree library using eiffel. As other parts of
my software use gobo I am trying to create it to be complicant with gobo
classes and if you want we can add it to the official distribution. At
the moment I plan to include binary search trees, splay trees and red
black trees.

- Einar Karttunen

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

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

Einar Karttunen wrote:
>  
> I am/will be coding a small tree library using eiffel. As other parts of
> my software use gobo I am trying to create it to be complicant with gobo
> classes and if you want we can add it to the official distribution. At
> the moment I plan to include binary search trees, splay trees and red
> black trees.

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.

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

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

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

[Andreas L. <no...@sb...>]

On 27 Jun 2001 16:55:12 +0200, Eric Bezault wrote:
> Einar Karttunen wrote:
> >  
> > I am/will be coding a small tree library using eiffel. As other parts of
> > my software use gobo I am trying to create it to be complicant with gobo
> > classes and if you want we can add it to the official distribution. At
> > the moment I plan to include binary search trees, splay trees and red
> > black trees.
> 
> 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.
> 
> 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

Btw, Einar: Are you going to write a Tree Library as in a container that
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?

I think there is a major difference between those areas. Although we
probably need both (;

Andreas

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

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

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

Einar Karttunen wrote:
>=20
> I think of inheriting from DS_CONTAINER=2E DS_TRAVERSABLE presents
> problems as trees can be traversed in many orders=2E I plan to include
> pre-, post-, inorder and Lindst=F6m-traversing=2E

You could arbitrarily choose one of them to implement
the routines from DS_TRAVERSABLE and provide other
external cursors for the other kind of traversals=2E
For example:

  new_cursor: DS_TREE_CURSOR [G] is
        -- New external cursor for traversal
        -- (Use preorder traversal by default=2E)
     do
        Result :=3D new_preorder_cursor
     end

  new_preorder_cursor: DS_PREORDER_TREE_CURSOR [G] is
        -- New external cursor for preorder traversal
    do
        !! Result=2Emake (Current)
    ensure
        =2E=2E=2E
    end

  new_postorder_cursor: DS_POSTORDER_TREE_CURSOR [G] is
        -- New external cursor for postorder traversal
    do
        !! Result=2Emake (Current)
    ensure
        =2E=2E=2E
    end

  =2E=2E=2E

--=20
Eric Bezault
mailto:ericb@gobosoft=2Ecom
http://www=2Egobosoft=2Ecom

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

[Alexander K. <kw...@ah...>]

Eric Bezault wrote:

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

One implementation that uses red-black trees was

http://www.eiffel-forum.org/archive/objtools/containe.htm

which worked with Eiffel/S 1.3 and ISE Eiffel 3. Later the
library was ported to Visual Eiffel and is included in the standard
VE setup. I can send the latest version of the library as a separate
ZIP file if required (there were some fixes since the first release).

Regards,
Alexander Kogtenkov
Object Tools, Moscow

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

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

Andreas Leitner wrote:
> 
> Do you mean this library, Eric?
> http://www.eiffel-forum.org/archive/durian/red_black_tree.htm

Yes.

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

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

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

Hello

Currently have minimal alpha implementations of binary search trees and
splay trees. There are small problems with cursors however. The library
doesn't seem to like a structute supporting multiple cursor (it results
in problems with next_cursor etc). Does anyone know a solution to this.
Cursor validity is also a problem, when a tree is rotated then all/none
of the cursors are must be invalidated because keeping track of cursors
any other way would result in a very slow container.
If someone has time please check the alpha out
(http://beeblebrox.edu.hel.fi/~einar/tree). It needs much
refining, but should have some of the basic functionality. I will be
completing these classes and adding red-black trees in a couple of weeks.
When you notice something to correct please send me email.

- Einar Karttunen

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

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

Einar Karttunen wrote:
> 
> Currently have minimal alpha implementations of binary search trees and
> splay trees. There are small problems with cursors however. The library
> doesn't seem to like a structute supporting multiple cursor (it results
> in problems with next_cursor etc). Does anyone know a solution to this.

What's wrong with the solution I suggested to you in
this mailing list 2 weeks ago?

> Cursor validity is also a problem, when a tree is rotated then all/none
> of the cursors are must be invalidated because keeping track of cursors
> any other way would result in a very slow container.
> If someone has time please check the alpha out
> (http://beeblebrox.edu.hel.fi/~einar/tree). It needs much
> refining, but should have some of the basic functionality.

I didn't look at the functionality yet, but from what I
saw it looks like you don't like routine header comments.
Also your class text is indented with a mix of tabs and
spaces. Are you using Emacs? (Berend: no pin intended, well
just a bit ;-))

There is definitely a problem with the names you chose
for your classes and features. In Eiffel it is good
practice to avoid abbreviations, so BT and LBST don't
sound very Eiffelish. I think that `delete' is better
than `del' as a feature name. What does `p_t' mean (well,
I found out by reading the implementation, but with such
a cryptic feature name, with no header comments and no
assertions, hmmm...)? Also `get' as a feature name should
be prohibited.

In addition to header comments, it is also good pratice
to put tags to assertions.

Class DS_BT_NODE_SPLAY is not syntactically correct:

------------------
inherit
   DS_BT_NODE[G]
      redefine set_parent
creation
------------------

There is a 'end' missing after `set_parent'. BTW, the name
of this class sounds weird. Are instances of this class
nodes or splays? From the inheritance clause it seems that
they are nodes, so the name should be DS_BT_SPLAY_NODE.

Class DS_BT_NODE: when possible use `make' as the name of
the creation routine, even if it means having two routines
which apparently have the same implementation. For example:

  make (v: G) is
           -- Create a new node.
     require
          v_not_void: v /= Void
     do
          set (v)
     ensure
         item_set: item = v
     end

`find_leftmost_child' is not a good name for a function.
Verbal names should be used from procedures or boolean
queries. I suggest `leftmost_child' instead.

Invariant:
  valid_item: item /= Void
A better tag is:
  item_not_void: item /= Void

Class DS_BT, there is a syntax error:

------------------
inherit
   DS_LINEAR [G]
      rename new_cursor as new_inorder_cursor
feature -- traversal cursors
------------------

There is a 'end' missing after `new_inorder_cursor'.

PS: If you are looking for a good book to read this
summer, I would suggest OOSC2 by B. Meyer.

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

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

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

> > Cursor validity is also a problem, when a tree is rotated then all/none
> > of the cursors are must be invalidated because keeping track of cursors
> > any other way would result in a very slow container.
> > If someone has time please check the alpha out
> > (http://beeblebrox.edu.hel.fi/~einar/tree). It needs much
> > refining, but should have some of the basic functionality.
>
> I didn't look at the functionality yet, but from what I
> saw it looks like you don't like routine header comments.
> Also your class text is indented with a mix of tabs and
> spaces. Are you using Emacs? (Berend: no pin intended, well
> just a bit ;-))
Yes I am using emacs. There are few routine header comments because I
except the code to change and this is an alpha version.

> There is definitely a problem with the names you chose
> for your classes and features. In Eiffel it is good
> practice to avoid abbreviations, so BT and LBST don't
> sound very Eiffelish. I think that `delete' is better
> than `del' as a feature name. What does `p_t' mean (well,
> I found out by reading the implementation, but with such
> a cryptic feature name, with no header comments and no
> assertions, hmmm...)? Also `get' as a feature name should
> be prohibited.
I changed the naming to a more eiffelish format. Hope you like
DS_LINKED_BINARY_SEARCH_TREE instead of DS_LBST. The cryptic
feature names, were internal features (inside feature {NONE})
which will probably change in future.

> There is a 'end' missing after `set_parent'. BTW, the name
Small eiffel doesn't complain for this, so I accidentally missed it.

There is a new version in the same place, with hopefully better naming
convention and a few bugs less. There are also short forms of the classes
available.

ps. sorry for the bad english.

- Einar Karttunen

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

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

Einar Karttunen wrote:
>
> I changed the naming to a more eiffelish format. Hope you like
> DS_LINKED_BINARY_SEARCH_TREE instead of DS_LBST.

I sounds better indeed.

> > There is a 'end' missing after `set_parent'. BTW, the name
> Small eiffel doesn't complain for this,

There was no warnings or anything like that?

> There is a new version in the same place, with hopefully better naming
> convention and a few bugs less. There are also short forms of the classes
> available.

I'll try to have a look at it.
Thank you for your effort.

PS: Don't be put off by my remarks about programming styles.
I'm from a school of thoughts where it is considered that
cosmetics matters as much as functionality in reusable
library classes (see OOSC2 page 875). Sven Ehrke is already
one of my martyrs ;-)

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

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

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

On Tue, 10 Jul 2001, Eric Bezault wrote:

> Einar Karttunen wrote:
> >
> > I changed the naming to a more eiffelish format. Hope you like
> > DS_LINKED_BINARY_SEARCH_TREE instead of DS_LBST.
>
> I sounds better indeed.
But is not so nice to write...

>
> > > There is a 'end' missing after `set_parent'. BTW, the name
> > Small eiffel doesn't complain for this,
>
> There was no warnings or anything like that?
none. It complains that copy is deferred in DS_SPLAY_TREE but nothing
else.

> PS: Don't be put off by my remarks about programming styles.
> I'm from a school of thoughts where it is considered that
> cosmetics matters as much as functionality in reusable
> library classes (see OOSC2 page 875). Sven Ehrke is already
> one of my martyrs ;-)
>
No problem. Ny backround is in C++ and perl, which I think both are very
cosmetic indeed. However I have noticed that the eiffel(ish|que) way of
doing things has many advantages.

I will probably next work on implementing pre/postorder cursors.

- Einar Karttunen

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

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

Einar Karttunen wrote:
> 
> > > I changed the naming to a more eiffelish format. Hope you like
> > > DS_LINKED_BINARY_SEARCH_TREE instead of DS_LBST.
> >
> > I sounds better indeed.
> But is not so nice to write...

Remember that you are writing reusable library classes:
"write once, read many times..."

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