Re: [Seed7-users] Forward declarations

[Conrad S. <con...@ca...>]

Hi Thomas

The below implementation is interesting, I'll try it out.

My method was to use hash table with integer keys and TreeNode structs
as values. My TreeNode struct is then simply

const type: TreeNode is new struct
     var integer: left is -1;
     var integer: right is -1;
     var integer: item is 0;
end struct;

Where a negative index means 'uninitialized'.

Cheers,
Conrad

On Tue, 2008-10-07 at 21:22 +0200, Thomas Mertes wrote:
> Conrad Steenberg <con...@gm...> wrote:
> > Hi
> > 
> > Learning seed7, so please be gentle :-)
> > 
> > I'm trying to implement a struct containing elements that are pointers
> > to (or references of) the same struct.
> > 
> > Something like
> > const type: tn is new struct
> >     var ptr struct tn: left is NIL;
> >     var ptr struct tn: right is NIL;
> >     var integer: item is 0;
> > end struct;
> > 
> > In C it would look like this:
> > typedef struct tn {
> >     struct tn*    left;
> >     struct tn*    right;
> >     int           item;
> > }
> > 
> > Is there a way to achieve this? FWIW this is for a binary tree with
> > integer items.
> 
> Currently the support for pointers in Seed7 is not very good. It is
> possible to declare pointers to existing structs, but currently it
> is not possible to declare a struct which contains a pointer to
> itself. This has to do with the missing possibility to use forward
> declarations for types. Sorry, but it will take some time to fix
> this. Other possibilities to declare cyclic pointer references are
> currently also impossible.
> 
> Luckily the OO concept of Seed7 can help here:
> Structs can contain elements with interface types and interface
> types can refer to structs of the same type.
> 
> The following example shows how to do this:
> The interface type 'element' will be used as "pointer":
> 
>   const type: element is new interface;
> 
> An implementation type for the empty element (emptyElement)
> can be used as basic implementation type from which other
> implementation types can inherit:
> 
>   const type: emptyElement is new struct
>     end struct;
> 
> That the implementation type 'emptyElement' implements the
> interface type 'element' is described with:
> 
>   type_implements_interface(emptyElement, element);
> 
> Since every Seed7 expression has exactly one type, it is
> necessary to define a special NIL value (used with element.NIL)
> for the type 'element':
> 
>   const element: (attr element) . NIL is emptyElement.value;
> 
> Now the struct with two "pointers" and an 'integer' can be
> declared:
> 
>   const type: treeElement is sub emptyElement struct
>       var element: left is element.NIL;
>       var element: right is element.NIL;
>       var integer: item is 0;
>     end struct;
> 
> Finally the type 'treeElement' is defined as implementation
> of the type 'element':
> 
>   type_implements_interface(treeElement, element);
> 
> To allow the direct access to the structure elements 'left', right'
> and 'item' for objects of type 'element' the following declarations
> are necessary:
> 
>   const func    element: (ref   element param).left  is DYNAMIC;
>   const varfunc element: (inout element param).left  is DYNAMIC;
>   const func    element: (ref   element param).right is DYNAMIC;
>   const varfunc element: (inout element param).right is DYNAMIC;
>   const func    integer: (ref   element param).item  is DYNAMIC;
>   const varfunc integer: (inout element param).item  is DYNAMIC;
> 
> When all this was declared the following code is possible:
> 
>   const proc: addItem (inout element: anElem, in integer: item) is func
>     begin
>       if anElem = element.NIL then
>         anElem := xalloc(treeElement.value);
>         anElem.item := item;
>       elsif item < anElem.item then
>         addItem(anElem.left, item);
>       elsif item > anElem.item then
>         addItem(anElem.right, item);
>       end if;
>     end func;
> 
>   const proc: listItems (in element: anElem) is func
>     begin
>       if anElem <> element.NIL then
>         listItems(anElem.left);
>         write(" " <& anElem.item);
>         listItems(anElem.right);
>       end if;
>     end func;
> 
>   const func integer: sum (in element: anElem) is func
>     result
>       var integer: result is 0;
>     begin
>       if anElem <> element.NIL then
>         result := anElem.item + sum(anElem.left) + sum(anElem.right);
>       end if;
>     end func;
> 
> New elements can be created with the function 'xalloc'.
> This way interface and implementation types help to provide the
> pointer functionality.
> 
> IMHO pointers are not always the best solution. Abstract data types
> like dynamic arrays, hash tables, struct types and set types can
> be used to declare data structures. Like structured programming
> introduced structured statements to avoid goto statements the
> structured abstract data types can be used to avoid pointers.
> 
> If you have more questions, just ask.
> 
> Greetings Thomas Mertes
> 
> Seed7 Homepage:  http://seed7.sourceforge.net
> Seed7 - The extensible programming language: User defined statements
> and operators, abstract data types, templates without special
> syntax, OO with interfaces and multiple dispatch, statically typed,
> interpreted or compiled, portable, runs under linux/unix/windows.
> 
-- 
-----------------------------------------------------------------------------
Conrad D. Steenberg Ph.D.            con...@ca...
Scientific Software Engineer         http://www.nupack.org
Pierce Bio-Engineering Lab           Mail Code 114-96
California Institute of Technology   Pasadena, CA, 91125