begin
   comment Test rig for CACM Algorithms 100 and 101 to illustrate their failures;

   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 goto listfull; i ≔ 1; 
        L1: if list [i,1] ⩽ t 
        then begin if list [i ,2] ≠ 0 then begin link1 ≔ m + 2; 
              link2 ≔ m + 3; go to L2 end else begin if 
              list [i,m+2] =flag then begin i ≔ flag; 
                 link1 ≔ m+3; link2 ≔ m+2; go to L3 end
            else begin i ≔ i+1; go to L1 end end end
      else begin link1 ≔ m+3; link2 ≔ m+2 end; 
        L2: if list [i,link2] ≠  flag 
        then begin k ≔ i; i ≔ ist [i,link2]; 
           if (link2 = m+2 ∧ list [i,1] ⩽ t) ∨ 
           (link2 ≠ m+2 ∧ list [i,1] > t) then go to L4
         else go to L1 end
      else begin list [i,link2] ≔ addr [1] end; 
        L3: j ≔ addr [1]; list [j,link1] ≔ i; 
        list [j ,link2] ≔ flag; if link2 = m + 2 then 
        first ≔ addr [1]; go to L5; 
        L4: 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] ≔ nfo [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] ≔ ist [first,i]; 
        for i ≔ n-1 step -1 until 1 do addr [i+1] ≔ addr [i]; 
        addr [1] ≔ first; 
        if list [first,m+3] = flag then 
        begin list [1,m+2] ≔ flag; first ≔ 1; 
           for i ≔ 1 step 1 until n do addr [i] ≔ i end
      else begin first ≔ list [first,m+3]; 
           list [first,m+2] ≔ flag end; 
        for i ≔ 1 step 1 until m+3 do list [addr[1], i] ≔ 0 
     end outlist ;
   procedure fill list (tvalues,info,m,list,n,first,flag,addr,listfull, cause failure); 
        comment Fill list with sample data using Algorithm 100: inlist;
      integer n, m, first, flag;
        integer array addr, info, list, tvalues; 
        label listfull;
        boolean cause failure;

   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;
            if cause failure then
            begin
               info[1] ≔ 0
            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)
         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 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)
         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;
      if list[1, 1] > 0 then
      begin
         outstrintnl(“list[1, 1] has incorrect v̲a̲l̲u̲e̲ f̲o̲r̲ an empty list: ”, list[1, 1])
      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];
   boolean cause failure;

   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 whether to cause failures or not;
   cause failure ≔ false;

   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 cause failure then
   begin
      outstring(1, “This run should cause one o̲r̲ more failures.\n”) 
     end
   else
   begin
      outstring(1, “Set cause failure := t̲r̲u̲e̲; t̲o̲ demonstrate failures.\n”) 
     end;
   if cause failure then
   begin 
        comment causes multiple failures;
      list[1,2] ≔ 1
   end;
   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, cause failure);

   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