Help: TREEs, NODEs, and COLLECTIONs 
Author Message
 Help: TREEs, NODEs, and COLLECTIONs

Hello,

I'm trying to get TREE[G] right with SmallEiffel:

Thinking a TREE[G] is a COLLECTION of either

TREE[G]

or

TREE_NODE[G]

I cannot get it right somehow. In SmallEiffel COLLECTION[E]'s item
type is "E", and I'd like to say that for TREE[G] it's "like Current"
(a tree consisting of trees itself). However I feel uneasy about

class TREE[G]
inherit
        COLLECTION[TREE[G]]
...

It smells a bit like the class inheriting from itself.

Similar variants like

class TREE[G->TREE_NODE[G]]
inherit
        COLLECTION[TREE_NODE[G]]

with

class TREE_NODE[G]
feature
        data : G
        parent : like Current
        children : ARRAY[like Current]

also had its problems.

How can I handle type-safety and recursion ("a tree is either empty or
an ordered collection of trees") in Eiffel in a clean way.

Any hints, or maybe even a class TREE[G] that is generic enough?

Regards,
Ulrich



Fri, 29 Oct 2004 21:56:27 GMT  
 Help: TREEs, NODEs, and COLLECTIONs

Quote:

> Hello,

> I'm trying to get TREE[G] right with SmallEiffel:

> Thinking a TREE[G] is a COLLECTION of either

> TREE[G]

> or

> TREE_NODE[G]

First, I'd try to get your TREE working without inheriting from
COLLECTION, which offers a large, complex interface. Once your basic
TREE is working, you can look at wedging it under COLLECTION.

Quote:
> I cannot get it right somehow. In SmallEiffel COLLECTION[E]'s item
> type is "E", and I'd like to say that for TREE[G] it's "like Current"
> (a tree consisting of trees itself). However I feel uneasy about

> class TREE[G]
> inherit
>    COLLECTION[TREE[G]]
> ...

> It smells a bit like the class inheriting from itself.

> Similar variants like

> class TREE[G->TREE_NODE[G]]
> inherit
>    COLLECTION[TREE_NODE[G]]

> with

> class TREE_NODE[G]
> feature
>    data : G
>    parent : like Current
>    children : ARRAY[like Current]

> also had its problems.

> How can I handle type-safety and recursion ("a tree is either empty or
> an ordered collection of trees") in Eiffel in a clean way.

I would say that a tree contains a root node. Each root points to
zero, one or to child nodes of the same type. Some of the algorithms
you want to apply to the nodes may be recursive, but don't don't get
carried away with that thought.

Without trying to present a full implementation, he's a sketch of how
I'd declare a tree:

class TREE[G->COMPARABLE]
   -- put off inheriting from COLLECTION for now
creation {ANY} make
feature {ANY}
   make is
      do
         -- create the root now, or wait until
         -- the first insertion?
         create root.make(Void)
      end

feature {ANY}
   add(element: G) is
      require G /= Void  -- element must exist
              not has (G) -- must be unique
      local node: TREE_NODE[G];
      do
         create node.make(element)
         -- stuff to insert node
      end

      -- other basic treelike functions,
      -- like has() or at()

   root: TREE_NODE[G];
end -- TREE

And here's a tree node:

class TREE_NODE[G->COMPARABLE]
creation make
feature
   make(elem: G) is
      do
         content := elem
      end

   -- features for adding or deleting
   -- child nodes

   content: G
   left, right: TREE_NODE[G]  -- recursive child references
end -- TREE_NODE

I'm constraining G to be COMPARABLE so that traditional comparison
operators  such as =, /=, <, and so on can be used to compare the
contents of each node.

Hope all that helps!

Greg



Sat, 30 Oct 2004 05:30:12 GMT  
 Help: TREEs, NODEs, and COLLECTIONs
Thinking about it, I decided to make TREE without data, i.e.

class TREE
inherit
        COLLECTION[ANY]
creation make
feature
        make(number_of_children : INTEGER) is do ... end
...
end -- class TREE

Then the real trees look like this

class XTREE
inherit TREE rename make as make_tree end
creation make

feature
make(d : X; number_of_children : INTEGER) is do make_tree(...)... end

data : X

end -- class XTREE

However SmallEiffel complains about ``Feature "make_tree" does not
belong to a creation clause of XTREE'', pointing at the rename
clause. I don't understand that. SmallEiffel also says about the same
line: "Creation Call not allowed". Other messages say ``make_tree is
not in the creation list of type XTREE''. I'm as least as confused as
the SmallEiffel compiler.

I thought this was valid EIffel...

Suggestions?

Regards,
Ulrich

Quote:


> > Hello,

> > I'm trying to get TREE[G] right with SmallEiffel:

> > Thinking a TREE[G] is a COLLECTION of either

> > TREE[G]

> > or

> > TREE_NODE[G]

> First, I'd try to get your TREE working without inheriting from
> COLLECTION, which offers a large, complex interface. Once your basic
> TREE is working, you can look at wedging it under COLLECTION.

> > I cannot get it right somehow. In SmallEiffel COLLECTION[E]'s item
> > type is "E", and I'd like to say that for TREE[G] it's "like Current"
> > (a tree consisting of trees itself). However I feel uneasy about

> > class TREE[G]
> > inherit
> >       COLLECTION[TREE[G]]
> > ...

> > It smells a bit like the class inheriting from itself.

> > Similar variants like

> > class TREE[G->TREE_NODE[G]]
> > inherit
> >       COLLECTION[TREE_NODE[G]]

> > with

> > class TREE_NODE[G]
> > feature
> >       data : G
> >       parent : like Current
> >       children : ARRAY[like Current]

> > also had its problems.

> > How can I handle type-safety and recursion ("a tree is either empty or
> > an ordered collection of trees") in Eiffel in a clean way.

> I would say that a tree contains a root node. Each root points to
> zero, one or to child nodes of the same type. Some of the algorithms
> you want to apply to the nodes may be recursive, but don't don't get
> carried away with that thought.

> Without trying to present a full implementation, he's a sketch of how
> I'd declare a tree:

> class TREE[G->COMPARABLE]
>    -- put off inheriting from COLLECTION for now
> creation {ANY} make
> feature {ANY}
>    make is
>       do
>          -- create the root now, or wait until
>          -- the first insertion?
>          create root.make(Void)
>       end

> feature {ANY}
>    add(element: G) is
>       require G /= Void  -- element must exist
>               not has (G) -- must be unique
>       local node: TREE_NODE[G];
>       do
>          create node.make(element)
>          -- stuff to insert node
>       end

>       -- other basic treelike functions,
>       -- like has() or at()

>    root: TREE_NODE[G];
> end -- TREE

> And here's a tree node:

> class TREE_NODE[G->COMPARABLE]
> creation make
> feature
>    make(elem: G) is
>       do
>          content := elem
>       end

>    -- features for adding or deleting
>    -- child nodes

>    content: G
>    left, right: TREE_NODE[G]  -- recursive child references
> end -- TREE_NODE

> I'm constraining G to be COMPARABLE so that traditional comparison
> operators  such as =, /=, <, and so on can be used to compare the
> contents of each node.

> Hope all that helps!

> Greg



Sat, 30 Oct 2004 15:00:27 GMT  
 Help: TREEs, NODEs, and COLLECTIONs

Quote:

> Thinking about it, I decided to make TREE without data, i.e.

> class TREE
> inherit
>    COLLECTION[ANY]
> creation make
> feature
>    make(number_of_children : INTEGER) is do ... end
> ...
> end -- class TREE

> Then the real trees look like this

> class XTREE
> inherit TREE rename make as make_tree end
> creation make

> feature
> make(d : X; number_of_children : INTEGER) is do make_tree(...)... end

> data : X

> end -- class XTREE

> However SmallEiffel complains about ``Feature "make_tree" does not
> belong to a creation clause of XTREE'', pointing at the rename
> clause. I don't understand that. SmallEiffel also says about the same
> line: "Creation Call not allowed". Other messages say ``make_tree is
> not in the creation list of type XTREE''. I'm as least as confused as
> the SmallEiffel compiler.

> I thought this was valid EIffel...

Something's missing.

The following minimalist example does the rename and does compile for
me:

class A creation make
feature make is do print ("A%N") end
end

-----
class B inherit A rename make as make_a
feature make is do make_a print ("B%N") end
end

So with what you've presented it's hard for me to say what's wrong.
What's X? Where's that declared? Why don't you get basic functionality
working and then worry about inheriting from COLLECTION? This early in
the game it's just making your life more complex. I still recommend
getting TREE working and then refactor as needed to conform to
COLLECTION.

Actually, conforming to COLLECTION may not be desirable anyway. A
truly useful TREE will allow you to build up a key/data relationship,
storing and retrieving the data via the keys. This is an interface
that's more like DICTIONARY, which is not a COLLECTION.

Here's an extended (but still very incomplete) version of yesterday's
example.

-- A node that can hold a key and arbitrary data
class TREE_NODE[K->COMPARABLE,V]
creation make_with
feature
   make_with(new_key: K; new_value: V) is
      do  
         key := new_key;
         content := new_value
      end

   set_left(node: like left) is
      require
         node /= Void
      do  
         left := node
      ensure
         left.is_equal(node)
      end

   set_right(node: like right) is
      require
         node /= Void
      do  
         right := node
      ensure
         right.is_equal(node)
      end
   key: K;
   content: V;
   left, right: TREE_NODE[K,V];
end

-- here's the tree
class TREE[K->COMPARABLE,V]
creation make
feature
   make is
      do  
      end

feature
   add(key: K; element: V) is
      require
         element /= Void
      do  
         if root = Void then
            create root.make_with(key,element)
         else
            insert(key,element,root)
         end
      end

   has(key: K): BOOLEAN is
      do  
         Result := has_key(key,root)
      end

feature {TREE}
   insert(key: K; element: V; node: like root) is
      -- recursive implementation of an insertion
      require
         element /= Void;
         key /= node.key
      do  
         check
            node.content /= Void
         end;
         if key < node.key then
            if node.left = Void then
               -- use the groovy create expression to make
               -- the left node.
               node.set_left( create
{TREE_NODE[K,V]}.make_with(key,element))
            else
               insert(key,element,node.left)
            end
         else
            check
               key > node.key
            end;
            if node.right = Void then
               node.set_right( create
{TREE_NODE[K,V]}.make_with(key,element))
            else
               insert(key,element,node.right)
            end
         end
      end
   has_key(key: K; node: like root): BOOLEAN is
      -- recursive implementation of a search
      do  
         if node = Void then
            Result := false
         elseif node.key = key then
            Result := true
         elseif key < node.key then
            Result := has_key(key,node.left)
         else
            check
               key > node.key
            end;
            Result := has_key(key,node.right)
         end
      end
   root: TREE_NODE[K,V];
end

-----------

-- And a minimal test program
class TEST
creation make
feature
   make is
      local foo: TREE[INTEGER,STRING];
      do  
         create foo.make;
         foo.add(1,"one");
         foo.add(2,"two")
      end
end

Don't take this as gospel, I only compiled and tested the code, I
didn't take the time to prove it correct!

Greg C



Sat, 30 Oct 2004 23:36:12 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. help with node height in a tree

2. Tree nodes and CwWidget

3. ActiveX tree control's wiat event does not abort after nodes are added

4. Building Tree for list of nodes in level order

5. <tree-node> in DUIM

6. NODE tree introspection

7. random node in tree

8. Internal Nodes of an XOR tree

9. Internal nodes of an XOR tree

10. Binary trees storing huge amounts of data in nodes

11. Bwidget tree node limits

12. Tree node in motion and scollbar

 

 
Powered by phpBB® Forum Software