begin
comment Test rig for fixed versions of CACM Algorithms 100 and 101;
comment ALGORITHM 100
ADD ITEM TO CHAIN-LINKED LIST
PHILIP J. KIVIAT
United States Steel Corp., Appl. Research Lab., Monroeville,
Penn. ;
procedure inlist(t, info, m, list, n, first, flag, addr, listfull);
integer n, m, first, flag, t;
integer array info, list, addr;
label listfull;
comment inlist adds the information pair {t,info} to the chain-
link structured matrix list (i,j), where t is an order key >= 0, and
info(k) an information vector associated with t. info(k) has
dimension m, list(i,j) has dimensions (n * (m+3)). flag denotes
the head and tail of list(i,j), and first contains the address of
the first (lowest order) entry in list(i,j). addr(k) is a vector
containing the addresses of available (empty) rows in list(i,j).
Initialization: list(i,m+2) = flag, for some i <= n. If list(i,j) is
filled exit is to listfull;
begin
integer i, j, k, link1, link2;
L0:
if addr[1]=0 then
go to listfull
else if addr[n] ≠ 0 then
begin
comment Insertion into an empty list;
i ≔ flag;
link1 ≔ m + 3;
link2 ≔ m + 2;
go to L3
end;
comment There is at least one element to compare against;
i ≔ first;
L1:
if list[i, 1]⩽t then
begin
comment Insert after first item - search forwards;
link1 ≔ m+2;
link2 ≔ m+3
end
else
begin
comment Insert before first item - search backwards;
link1 ≔ m+3;
link2 ≔ m+2
end;
if list[i, link2]≠flag then
begin
comment Check the n̲e̲x̲t̲ element for the insertion point;
k ≔ i;
i ≔ list[i, link2];
if(list[i, 1]>t)then
begin
comment Insertion point found;
go to L4
end
else
begin
comment Continue the search;
go to L1
end
end
else
begin
comment Insert a̲f̲t̲e̲r̲ i (depending on search direction).
Link i into the new element;
list[i, link2] ≔ addr[1]
end;
L3: ;
comment Insert at one of the ends of the list,
linking to element i in the opposite direction.
As a special case, i = flag when inserting into the empty list;
j ≔ addr[1];
list[j, link1] ≔ i;
list[j, link2] ≔ flag;
if link2=m+2 then
first ≔ addr[1];
go to L5;
L4: ;
comment Insert between two existing elements;
j ≔ addr[1];
list[j, link1] ≔ list[i, link1];
list[i, link1] ≔ list[k, link2] ≔ addr[1];
list[j, link2] ≔ i;
L5:
list[j, 1] ≔ t;
for i ≔ 1 step 1 until m do
list[j, i+1] ≔ info[i];
for i ≔ 1 step 1 until n-1 do
addr[i] ≔ addr[i+1];
addr[n] ≔ 0
end inlist ;
comment ALGORITHM 101
REMOVE ITEM FROM CHAIN-LINKED LIST
PHILIP J. KIVIAT
United States Steel Corp., Appl. Res. Lab., Monroeville,
Penn. ;
procedure outlist(vector, m, list, n, first, flag, addr);
integer n, m, first, flag;
integer array vector, list, addr;
comment outlist removes the first. entry (information pair with
lowest order key) from list(i,j) and puts it in vector(k);
begin
integer i;
for i ≔ 1 step 1 until m+1 do
vector[i] ≔ list[first, i];
comment Find the place to record release of the first entry;
for i ≔ n, i - 1 while i > 1 ∧ addr[i] = 0 do
;
if addr[i] = 0 then
addr[i] ≔ first
else
addr[i+1] ≔ first;
if list[first, m+3]=flag then
begin
comment The list is now empty;
list[1, m+2] ≔ flag
end
else
begin
first ≔ list[first, m+3];
list[first, m+2] ≔ flag
end
end outlist ;
procedure fill list (tvalues,info,m,list,n,first,flag,addr,listfull);
comment Fill list with sample data using Algorithm 100: inlist;
integer n, m, first, flag;
integer array addr, info, list, tvalues;
label listfull;
begin
integer i, j, t;
for i ≔ 1 step 1 until n do
begin
comment set the key;
t ≔ tvalues[i];
comment set arbitrary values to be associated with the key;
for j ≔ 1 step 1 until m do
begin
info[j] ≔ 2×i + j
end;
outstrintnl(“Adding key ”, t);
inlist(t, info, m, list, n, first, flag, addr, listfull);
showlist(list, first, m, n, flag);
checklist(list, first, m, n, flag, i);
check free(addr, n, n - i)
end
end fill list;
procedure showlist(list, first, m, n, flag);
comment show the contents of the list, the end is
assumed to be indicated by list[i, m+3] = flag;
integer array list;
integer first, m, n, flag;
begin
integer i, prev;
outstring(1, “List contents: ”);
i ≔ first;
prev ≔ flag;
next:
if i = flag then go to endofproc;
prev ≔ i;
outinteger(1, list[i, 1]);
i ≔ list[i, m+3];
go to next;
endofproc:
outstring(1, “\n”)
end showlist;
procedure checklist(list, first, m, n, flag, list length);
comment check that list is sorted from 1 ... list length
and of the indicated length;
integer array list;
integer first, m, n, flag, list length;
begin
boolean error;
error ≔ false;
if first < 1 ∨ first > n then
begin
outstrintnl(“Invalid v̲a̲l̲u̲e̲ f̲o̲r̲ first: ”, first);
error ≔ true
end
else
begin
integer checked, i, prev, t;
comment dummy key for comparison at the start of the list;
prev ≔ -1;
i ≔ first;
comment how many have been checked;
checked ≔ 0;
for checked ≔ checked + 1 while (checked ⩽ list length ∧ ¬error ∧ i ≠ flag) do
begin
t ≔ list[i, 1];
if t < prev then
begin
error ≔ true;
outstrint(“key ”, t);
outstrintnl(“out of order at position ”, i)
end;
prev ≔ t;
comment follow the n̲e̲x̲t̲ link.;
i ≔ list[i, m + 3]
end;
if checked ≠ list length + 1 then
begin
outstrint(“checking prematurely terminated after ”, checked - 1);
outstrintnl(“rather than ”, list length)
end
end
end checklist;
procedure check free(addr, n, num free);
comment check that addr has the correct number of free locations
which should be equal to num free;
integer array addr;
integer n, num free;
begin
integer i, count;
count ≔ 0;
for i ≔ 1 step 1 until n do
if addr[i] ≠ 0 then begin
count ≔ count + 1
end;
if count ≠ num free then
begin
outstrint(“Incorrect number of free locations: ”, count);
outstrintnl(“ which should be ”, num free)
end
end check free;
procedure clear list(m, list, n, first, addr, list length);
comment Clear the list sorted from 1 ... list length using
Algorithm 101: outlist;
integer array addr, list;
integer first, m, n, list length;
begin
comment Variables for the outlist procedure;
integer array vector[1:m + 1];
integer i;
outstring(1, “Clearing the list.\n”);
for i ≔ 1 step 1 until list length do
begin
outlist(vector, m, list, n, first, flag, addr);
check free(addr, n, i)
end;
if list[1, m+2] ≠ flag then
begin
outstrintnl(“list[1, m+2] has incorrect v̲a̲l̲u̲e̲ f̲o̲r̲ an empty list: ”, list[1, m+2])
end
end clear list;
procedure outstrint(str, i);
comment output str following by i;
string str;
integer i;
begin
outstring(1, str); outinteger(1, i)
end outstrint;
procedure outstrintnl(str, i);
comment output str following by i and terminate with a newline;
string str;
integer i;
begin
outstrint(str, i);
outstring(1, “\n”)
end outstrintnl;
comment Beginning of the test program;
comment Variables for the inlist procedure;
integer n, m, first, flag;
comment info[1:m], list[1:n, 1:m+3], addr[1:n];
comment 100 must be <= n, and 4 should be >= m;
integer array info[1:4], list[1:100, 1:4+3], addr[1:100];
comment Variables for the test procedure;
integer i, j;
comment 100 must be <= n;
integer array tvalues[1:100];
comment capacity of the list;
n ≔ 4;
comment amount of data associated with each key;
m ≔ 4;
comment index of the head item in list.
first := -1;
comment end-of-list marker;
flag ≔ -1;
comment set up the list of free locations;
for i ≔ 1 step 1 until n do
begin
addr[i] ≔ i
end;
comment Set necessary initial terminating marker;
list[1, m + 2] ≔ flag;
comment Set up the tvalues to be used;
tvalues[1] ≔ 7;
tvalues[2] ≔ 13;
tvalues[3] ≔ 6;
tvalues[4] ≔ 11;
if list[1, 2] ≠ 1 then
begin
comment The following is needed to avoid subscript error if list[1,2] != 0;
list[1, m + 3] ≔ flag
end;
fill list(tvalues, info, m, list, n, first, flag, addr, listfull);
comment try to fill the list beyond its capacity.
This should fail with a jump to listfull;
inlist(n + 1, info, m, list, n, first, flag, addr, listfull);
outstring(1, “Failed t̲o̲ correctly detect attempt t̲o̲ add too many entries.\n”);
go to testend;
listfull:
if i = (n+1) then
begin
outstrintnl(“List full correctly detected when attempting t̲o̲ add entry ”, i)
end;
testend:
clear list(m, list, n, first, addr, n)
end