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