Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > alt.comp.lang.pascal > #1

Generic data structures

Show all headers | View raw

Hello, all

Out  of  curiosity I am considering how to implement
abstract data structures in procedural  Pascal.   If
linkage  is  not  requried,  as  it  is in lists and
trees, passing procedure variables for  has  genera-
tion and key comparison seems sufficient:

  Type
     FGetHash = function( var data ): Word;
     FIsEqual = function( var key1; key2: Pointer ): Boolean;
     TGenDict = record
     // Implementation details not important because
     // the interface fucntions do not depend on it.
     end;
  Function NewDict( getHash: FGetHash; isEqual: FIsEqual; keySize: Word; valSize: Word ):TGenDict;
  Procedure DisposeDict( var dict: TGenDict );
  Function  Get( var dict:TGenDict; var key ): Pointer;
  Procedure Get( var dict:TGenDict; var key; var value );
  Function  Contains( var dict:TGenDict; var key ): Boolean;
  Procedure Add( var dict:TGenDict; var key; var value );
  Procedure Remove( var dict: TGenDict; var key );

With  linked  data  structures,  however, a means of
navigation must be exposed to the user, so procedure
variables  are  not  enough  if we don't want to the
overead of getting the navigation fields  via  func-
tons, e.g GetNext() for lists.

In the case of doubly linked lists, the best I could
do was to declare the list structure as follows:

  PNode    = ^TNode;
  TGenList = record
     First: PNode;
     Last:  PNode;
  end;

  Node = record
     Prev: PNode;
     Next: PNode;
  end;

and implement all relevant operations in an abstract
way:

  Procedure NewList     ( var list );
  Procedure Append      ( var list; what: Pointer );
  Procedure Prepend     ( var list; what: Pointer );
  Procedure InsertAfter ( var list; after:  Pointer; what: Pointer );
  Procedure InsertBefore( var list; before: Pointer; what: Pointer );
  Procedure Remove( var alist; what: Pointer );

To implement a specific list using this unit one has
to declare a similar structure:

  PTestNode = ^TestNode;
  TTestList = record
     First: ^TestNode;
     Last:  ^TestNode;
  end;

  TestNode = record
     Prev:   PTestNode;
     Next:   PTestNode;
     Name:   string;  { Any data    }
     Number: byte;    { fields here }
  end;

and pass it to the generic procedures, e.g.:

  var
     a, b, c, ptnode: PTestNode;
     list: TTestList;
  begin
     NewList( list );
     New( a ); New( b ); New( c );
     a^.Name   := 'A'; a^.Number := 1;
     b^.Name   := 'B'; b^.Number := 2;
     c^.Name   := 'C'; c^.Number := 3;

     Prepend( list, a );
     InsertBefore( list, list.First, b );

     WriteLn('Elements in order:');
     ptnode := list.First;
     while ptnode <> nil do begin
        PrintNode( ptnode );
        ptnode := ptnode^.Next;
     end;

     Dispose( a ); Dispose( b ); Dispose( c );
  end.

The problem with this approach is that it will break
the  program  when  the  TGenList  or Node structure
changes or when the memory layout (alignment) in the
generic list unit differs from that in the importing
unit.  Is there a better approach?

-- 
()  ascii ribbon campaign - against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

Back to alt.comp.lang.pascal | Next — Next in thread | Find similar

Thread

Generic data structures Anton Shepelev <anton.txt@gmail.com> - 2016-05-07 16:38 +0300
  Re: Generic data structures "zeLittle " <noreply@noreply.net> - 2016-10-04 23:51 +0200
  Re: Generic data structures "zeLittle " <noreply@noreply.net> - 2016-10-05 00:10 +0200

csiph-web