Re: [Seed7-users] Forward declarations

[Thomas M. <tho...@gm...>]

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.

-- 
GMX startet ShortView.de. Hier findest Du Leute mit Deinen Interessen!
Jetzt dabei sein: http://www.shortview.de/wasistshortview.php?mc=sv_ext_mf@gmx