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.