15.6 Toward More Generic Structures

Throughout this book, the principles of code reusability have been heavily promoted. Where possible, routines have been made multi-purpose, and the structures employed so far (such as the list, stack, trees, etc.) have been capable of modification by using a different data module to import from and recompiling.

In order to write these more generic routines than these, we could try to construct them in such a way that they can be used without resorting to recompiling for every new data type. That is, a list is just that, and nothing more. It is conceived of as a list, not as a list of something. One very general way to work with such abstractions is to ensure that the items that are to be listed are of the type ARRAY OF LOC. If this is done, any type of data is compatible. When a new structure, such as a list, is created, the size of the items to be placed in the structure must be supplied, and then whenever space for a data item is required in the implementation module, ALLOCATE can be called directly on a pointer variable to fetch some dynamic memory. The declaration of the list and node types could look like:

TYPE
  NodePoint = POINTER TO Node;
  Node = 
    RECORD
      dataLoc : ADDRESS;
      next,
      last : NodePoint;
    END;

  List = POINTER TO ListInfo;
  ListInfo = 
    RECORD
      dataSize,
      numItems : CARDINAL;
      head,
      tail,
      curInsert,
      curDelete,
      curFetchup : NodePoint;
      delAtHead : BOOLEAN;
    END;

When memory is needed for a new node and its associated data, one could call:

ALLOCATE (local, SIZE(Node) ); (* get a new node *)
  ALLOCATE (local^.dataLoc, list^.dataSize); (* get space for actual data *)

However, a difficulty that must still be overcome is that of handling assignments. One cannot simply write (in the implementation module)

theNode.dataLoc^ := itemPassedIn;

where itemPassedIn is of type ARRAY OF LOC, as there will be a type conflict error. The relevant field is an address, not a pointer to anything in particular. To get around this problem, it is necessary to first build two routines to copy data‹one from an address into the contents of a variable represented as an ARRAY OF LOC, and the other to do the reverse. This can be done as follows:

DEFINITION MODULE CopyLocs;

(* Low level copying routines to move data around by locs *)
(* copyright © 1995 by R. Sutcliffe *)
(* last modification 1996 01 03 *)

FROM SYSTEM IMPORT
  ADDRESS, LOC;
  
PROCEDURE CopyToAdr (source: ARRAY OF LOC; adr: ADDRESS);
(* Pre: the user has SIZE (source) LOCs available to use at adr 
   Post: the source item is copied to the locations starting at the given address *)
   
PROCEDURE CopyFromAdr (adr: ADDRESS; VAR dest: ARRAY OF LOC);
(* Pre: none, though the items at adr ought to be meaningful to the program
   Post: the SIZE (dest) LOCs strting at adr are copied into dest. *)

END CopyLocs.

IMPLEMENTATION MODULE CopyLocs;

(* Low level copying routines to move data around by locs *)
(* copyright © 1995 by R. Sutcliffe *)
(* last modification 1995 03 31 *)

FROM SYSTEM IMPORT
  ADDRESS, LOC, ADDADR;
  
PROCEDURE CopyToAdr (source: ARRAY OF LOC; adr: ADDRESS);

VAR
  count: CARDINAL;

BEGIN
  FOR count := 0 TO HIGH (source) (* can't do SIZE on open array *)
    DO
      adr^ := source [count];
      adr := ADDADR (adr, 1);
    END;
END CopyToAdr;

PROCEDURE CopyFromAdr (adr: ADDRESS; VAR dest: ARRAY OF LOC);

VAR
  count: CARDINAL;

BEGIN
  FOR count := 0 TO HIGH (dest)
    DO
      dest [count] := adr^;
      adr := ADDADR (adr, 1);;
    END;
END CopyFromAdr;

END CopyLocs.