14.2 Lists Revisited

The lists of chapter twelve were rather simple in that only a few operations were sketched and the natural step of creating a library module to encapsulate the ADT List was not taken. A number of issues arise when this next step is undertaken:

If there is only one type, a customized linked list package that takes the characteristics of the data fields into consideration in some way may be best. One way of doing this is to provide more than one set of links to sort data by more than one key field. If more than one kind of list (different types of enlisted data) are envisioned, then a more generic library package capable of easy modification to a variety of data is indicated. In the example of this section, genericity is ensured by having the definition module import the data type from some other module and then rename it to a local type name. This ensures that the module need only be changed in its first few lines to generate a new linked list for a different type of data.

In this section, doubly linked lists will be employed, though in some applications single or circular links are indicated.

In the example of this section, they will be. However, for very large lists, it might be more useful to provide procedures to search for specific items by one of their fields and then update, fetch, insert, or delete the one found.

In the example of this section, such pointers will be kept separately for insertion, deletion, and fetch/update operations. Moreover, an enumerated type is defined so that setting these pointers can be done operation by operation at a specific index number.

With these ideas in mind, here is the definition module for a relatively robust linked list type. It depends on a library module called ItemADT but this name can be changed as desired. The only thing required from that module for the definition module lists to work is the definition of the ADT itself. Observe the careful specification of predicates for each operation.

DEFINITION MODULE Lists;

(* semi- generic implementation of lists  *)
(* copyright  1995 by R. Sutcliffe *)
(* last modification 1995 05 29 *)

(* To use, change ItemADT to the module name where the ADT to be listed is defined and ItemType in the following two lines to the correct name found there. Also required: an assignment procedures for the ADT. *)

FROM ItemADT IMPORT
  ItemType;
TYPE
  DataType (* local name *) = ItemType;

TYPE
  List;
  Operation = (insert, delete, fetchup);

PROCEDURE Create (VAR list : List);
  (* Pre: none
  Post: a new list of ItemType structure is initialized with length zero.  Insert, delete and fetch/update start out at the head of the list. *)

PROCEDURE Discard (VAR list : List);
  (* Pre: list is a validly created list
    Post: list is undefined *)

PROCEDURE Length (list : List) : CARDINAL;
  (* Pre: list is a validly created list
    Post: The number of items in the list is returned. *)

PROCEDURE SetAtHead (VAR list : List; op : Operation);
  (* Pre: list is a validly created list
    Post: The position for the given insert, delete, or fetch/update operation is the first item. *)

PROCEDURE SetAtTail (VAR list : List; op : Operation);
  (* Pre: list is a validly created list
    Post: The position for the given insert, delete, or fetch/update operation is the last item. *)

PROCEDURE SetAtPos (VAR list : List; op : Operation; itemNum : CARDINAL);
  (* Pre: list is a validly created
    Post: The position for the given insert, delete, or fetch/update operation is the itemNum item. If ItemNum >= Length, it is set to the last item. If it is zero or one, it is set to the head. Note, however that a delete or fetch/update position set to one or greater moves forward with the item it previously designated if inserting is done before it.  Likewise, an Insert  or fetch/update position pulls back one numerically with the item it designated prior to a delete that occurs in front of it. *)

PROCEDURE Insert (VAR list : List; item : DataType);
  (* Pre: list is a validly created list and item is the right size to be placed in the list.
    Post: the item is inserted before the currently set insert position.  The insert position is now before the item just inserted.  For example, if inserting was being done at the head, it still is. The length is updated. *)

PROCEDURE Append (VAR list : List; item : DataType);
  (* Pre: list is a validly created list and item is the right size to be placed in the list.
    Post: the item is inserted after the last item in the list. Note that Insert cannot be used to do this. *)

PROCEDURE Update (VAR list : List; item : DataType);
  (* Pre: list is a validly created list and item is the right size to be placed in the list.
     Post: The old item at the currently set position for fetch/update is updated to item. The fetch/update position is not changed. *)

PROCEDURE Fetch (list : List; VAR item : DataType);
  (* Pre: list is a validly created list and item is the right size to receive data from the list.
    Post: item gets the data at the current position for fetch/update. The fetch/update position is not changed. *)

PROCEDURE Delete (VAR list : List);
  (* Pre: list is a validly created list
    Post: the item at the current delete position is removed from the list and the length is updated. The current delete position is now at the item after the one deleted, or it if was the last, it points to the new last. That is, if we were deleting at the head, we still are and if we were deleting at the tail, we still are.  If we delete the position for either insert or fetch/update, their new item will be the same as the new delete item.
     Note: The initial or default delete position is at the head.  Should the list shrink to zero items and then grow again, deleting will continue from either the head or the tail, depending on which was being conducted at the time the last item was deleted. -- see SetAtPos. *)

END Lists.

The new items are all implemented in the module below. The reader should note that the handling of the various list pointers is only one of several possible approaches to the subject. It may not be necessary to keep so many pointers to the list structure, but it can be convenient. Completing the commenting of this implementation has been left as an exercise.

IMPLEMENTATION MODULE Lists;

(* semi- generic implementation of lists  *)
(* copyright  1995 by R. Sutcliffe *)
(* last modification 1995 05 29 *)

FROM Storage IMPORT
  ALLOCATE, DEALLOCATE;

FROM ItemADT IMPORT
  Assign;
  
TYPE
  NodePoint = POINTER TO Node;
  Node = 
    RECORD
      data : DataType;
      next,
      last : NodePoint;
    END;

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

PROCEDURE Create (VAR list : List);

BEGIN
  NEW (list);
  WITH list^
    DO
      numItems := 0;
      head := NIL;
      tail := head;
      curInsert := head;
      curDelete := head;
      curFetchup := head;
      delAtHead := TRUE;

    END;
END Create;

PROCEDURE Discard (VAR list : List);

BEGIN
  SetAtHead (list, delete);
  WHILE list^.numItems > 0
    DO
      Delete (list);
    END;
  DISPOSE (list);
END Discard;

PROCEDURE Length (list : List) : CARDINAL;

BEGIN
  RETURN list^.numItems;
END Length;

PROCEDURE SetAtHead (VAR list : List; op : Operation);

BEGIN
  CASE op OF
    insert:
      list^.curInsert := list^.head |
    delete:
      list^.curDelete := list^.head;
      list^.delAtHead := TRUE; |
    fetchup:
      list^.curFetchup := list^.head;
    END;
END SetAtHead;

PROCEDURE SetAtTail (VAR list : List; op : Operation);

BEGIN
  CASE op OF
    insert:
      list^.curInsert := list^.tail |
    delete:
      list^.curDelete := list^.tail;
      list^.delAtHead := FALSE; |
    fetchup:
      list^.curFetchup := list^.tail;
    END;
END SetAtTail;

PROCEDURE SetAtPos (VAR list : List; op : Operation; itemNum : CARDINAL);

VAR
  count : CARDINAL;
  tempPoint : NodePoint;

BEGIN
  IF itemNum = 0 
    THEN 
      SetAtHead (list, op);
    ELSIF itemNum >= list^.numItems THEN
      SetAtTail (list, op)
    ELSE (* not setting at head or tail *)
      IF itemNum > (list^.numItems DIV 2) THEN (* past middle? *)
        count := list^.numItems;
        tempPoint := list^.tail; (* start at the back *)
        WHILE count > itemNum   (* back up if necessary *)
          DO
            tempPoint := tempPoint^.last;
            DEC (count);
          END;
      ELSE (* before middle but not at zero *)
        count := 1;
        tempPoint := list^.head; (* start at the front *)
        WHILE count < itemNum   (* go forward  if necessary *)
          DO
            tempPoint := tempPoint^.next;
            INC (count);
          END;
      END;
      CASE op OF
        insert:
          list^.curInsert := tempPoint |
        delete:
          list^.curDelete := tempPoint;
          list^.delAtHead := FALSE; |
        fetchup:
          list^.curFetchup := tempPoint;
        END;
    END;

END SetAtPos;

PROCEDURE Insert (VAR list : List; item : DataType);

VAR
  local : NodePoint;

BEGIN
  NEW (local);
  local^.data := item;
  local^.next := list^.curInsert;
  IF list^.curInsert # list^.head (*inserting at head? *)
    THEN (* no, so chain in new item *)
      local^.last := list^.curInsert^.last; (* point back to previous node *)
      list^.curInsert^.last^.next := local; (* and make it point to new one *)
    ELSE 
      local^.last := NIL; (* yes, so back pointer is NIL *)
      IF (list^.curDelete = list^.head) AND list^.delAtHead
       (* if delete is at head too, keep it there *)
        THEN
          list^.curDelete := local;
        END;
      IF list^.curFetchup = list^.head (* if fetchUp is at head too, keep it there *)
        THEN
          list^.curFetchup := local;
        END;
      IF list^.tail = NIL (* if this is the first item in *)
        THEN
          list^.tail := local;
        END;
      list^.head := local; (* revise the head *)
    END;
  IF list^.curInsert # NIL
    THEN
      list^.curInsert^.last := local;
      END;
    list^.curInsert := local; (* insert point becomes new item *)
  INC (list^.numItems);

END Insert;

PROCEDURE Append (VAR list : List; item : DataType);

VAR
  local : NodePoint;

BEGIN
  NEW (local);
  local^.data := item;
  local^.last := list^.tail;
  local^.next := NIL;
  IF list^.tail = NIL (* list currently empty *)
    THEN
      WITH list^
        DO
          head := local;
          curInsert := head;
          curDelete := head;
          curFetchup := head;
      END;
    ELSE
      list^.tail^.next := local;
    END;
  list^.tail := local;
  INC (list^.numItems);

END Append;

PROCEDURE Update (VAR list : List; item : DataType);

BEGIN
  Assign (item, list^.curFetchup^.data);
END Update;

PROCEDURE Fetch (list : List; VAR item : DataType);

BEGIN
  Assign (list^.curFetchup^.data, item);
END Fetch;

PROCEDURE Delete (VAR list : List);

VAR
  newCurDel, temp : NodePoint;

BEGIN
  IF list^.numItems = 0
    THEN
      RETURN
    END;
  temp := list^.curDelete;
  IF list^.curDelete^.last # NIL (* if not at #1 *)
    THEN
      list^.curDelete^.last^.next := list^.curDelete^.next;
    ELSE
      list^.head := list^.curDelete^.next;
    END;
  IF list^.curDelete^.next # NIL (* if not at last item *)
    THEN
      list^.curDelete^.next^.last := list^.curDelete^.last;
      newCurDel := list^.curDelete^.next;
    ELSE
      list^.tail := list^.curDelete^.last;
      newCurDel := list^.curDelete^.last;
    END;
  IF list^.curDelete = list^.curInsert (* hammered off insert item? *)
    THEN
      list^.curInsert :=  newCurDel;
    END;
  IF list^.curFetchup = list^.curInsert (* hammered off fetchup item? *)
    THEN
      list^.curFetchup :=  newCurDel;
    END;
  DEC (list^.numItems);
  list^.curDelete := newCurDel;
  DISPOSE (temp);
END Delete;

END Lists.

In order to complete the task, the ADT to be listed must be defined and implemented in a suitable module, along with the procedure Assign. The name of this module and the name of the ADT are then substituted in the top lines of the definition and implementation modules above, and (possibly) new copies saved with unique names (ListOfMyADT). All these must then be compiled before a client program can be written and linked.

If a second list type using another ADT is required (perhaps even for the same client) it is not difficult to define that other ADT and make some minor editorial changes in the first few lines (only) of the modules above, then compile again. This can be done as many times as desired without making any changes to the body of the implementation.

Here is a simple version of a typical supplier of the information. It actually uses the name ItemADT so that no changes at all are necessary to proceed.

DEFINITION MODULE ItemADT;

TYPE
  ItemType = CARDINAL;

PROCEDURE Assign (a : ItemType; VAR b : ItemType);

END ItemADT.

IMPLEMENTATION MODULE ItemADT;

PROCEDURE Assign ( a : ItemType; VAR b : ItemType);
BEGIN
  b:= a;
END Assign;

END ItemADT.

Contents