14.5 Tables

Data is commonly displayed in the form of a table with headings for the columns. The first column can be thought of as an index into the table.

Example 1 (National Data)

Here the names of the countries are used as an index to the table in order to find the gross national products of each.

Example 2 (Numerical function)

A lookup table or, for short, a table is a finite set of ordered pairs {(x, f(x))}, that is, it is a function on a finite domain (the first column) to some range (the second column).

Lookup tables are very commonly used in a variety of applications in computing. For instance:

• The WITH statement is usually implemented as a table. The values of the enumeration type are the domain, and the addresses of the statement sequence associated with each form the range of the function.
• A compiler usually has a table with domain the various statements in the language, and range the code to output in order to execute that statement.
• Mail servers and other accounting programs on network machines keep tables of user account names and their passwords. They also have tables that relate the names of machines to their network addresses and to routes by which data packets can be sent to other machines.

There is no particular reason to limit tables to two columns. They could be n-tuples, and be thought of as functions from a finite domain to an (n-1)-tuple. However, to keep the illustrations in this section simple, attention will be confined to the easiest case. In a fashion similar to the one already in use throughout this chapter, first define the data type to be entabled. Here, example 1 above is used.

DEFINITION MODULE Countries;

(* define one data type in a generic way
for use in semi-generic structures
by R. Sutcliffe   last modified 1995 06 07 *)

FROM Strings IMPORT
  CompareResults;
CONST
  nameLength = 30;
TYPE
  Country;
  KeyType = ARRAY [0..nameLength] OF CHAR;
  FieldType = CARDINAL;
  ActionProc = PROCEDURE (Country);

PROCEDURE New (VAR c : Country);
PROCEDURE Valid (c : Country) : BOOLEAN;
  (* if new was never called for this country, this call is meaningless; if it was, returns true if variable is ok, false if either new failed or dispose has been called *)
PROCEDURE Dispose (VAR c : Country);
PROCEDURE Assign (source : Country; VAR dest : Country);
  (* asignment with value semantics *)
PROCEDURE WriteCountryData (c : Country);
PROCEDURE Compare (key1, key2: KeyType) : CompareResults;
PROCEDURE SetKey (c : Country; name : KeyType);
PROCEDURE GetKey (c : Country): KeyType;
PROCEDURE SetField (c : Country; gnp : FieldType);
PROCEDURE GetField (c : Country) : FieldType;
END Countries.

Observe that an Assign procedure has been defined. One could just write

destCountry := sourceCountry;

but that kind of assignment is an assignment of the opaque item itself, pointer to the data, so that destCountry now points to the same location as sourceCountry does. The Assign in the module above is an assignment of the value of source^ to the dereferenced location of the destination, so that the value of dest^ is changed, but not the pointer itself. Which kind of assignment is used in a program depends on whether the programmer wishes to move data or change the pointer.

Assignment by changing the pointer is said to have reference semantics (meaning), and assignment by moving the values pointed to without changing the pointers is said to have value semantics.

These ideas can be examined closely in the implementation below. Observe also the definition of the procedure WriteCountryData to print out one data item. This will be useful when it comes time to print out the entire table, for this procedure will do one line of such a printout.

IMPLEMENTATION MODULE Countries;

(* define one data type in a generic way
for use in semi-generic structures
by R. Sutcliffe   last modified 1995 06 07 *)

FROM Storage IMPORT
  ALLOCATE, DEALLOCATE;
FROM STextIO IMPORT
  WriteString, WriteLn, WriteChar;
FROM SWholeIO IMPORT
  WriteCard;
IMPORT Strings;
FROM Strings IMPORT
  CompareResults;
  
TYPE
  Country = POINTER TO CountryDataNode;
  CountryDataNode =
    RECORD
    name : KeyType;
    gnp : FieldType;
  END;

PROCEDURE New (VAR c : Country);
BEGIN
  NEW (c);
  c^.name := "";
  c^.gnp := 0;
END New;

PROCEDURE Valid (c : Country) : BOOLEAN;
BEGIN
  RETURN (c # NIL)
END Valid;

PROCEDURE Dispose (VAR c : Country);
BEGIN
  DISPOSE (c);
END Dispose;

PROCEDURE Assign (source : Country; VAR dest : Country);
  (* asignment with value semantics *)
BEGIN
  dest^ := source^;
END Assign;

PROCEDURE WriteCountryData (c : Country);
VAR
  count : CARDINAL;
BEGIN
 WriteString (c^.name);
 FOR count := 1 TO 2 + nameLength - LENGTH (c^.name)
    DO (* pad to next field *)
     WriteChar (" ");
    END;
  WriteCard (c^.gnp, 12);
  WriteLn;
END WriteCountryData;
  
PROCEDURE Compare (key1, key2: KeyType) : CompareResults;
BEGIN
  RETURN Strings.Compare (key1, key2);
END Compare;

PROCEDURE SetKey (c : Country; name : KeyType);
BEGIN
  c^.name := name;
END SetKey;

PROCEDURE GetKey (c : Country): KeyType;
BEGIN
  RETURN c^.name;
END GetKey;

PROCEDURE SetField (c : Country; gnp : FieldType);
BEGIN
  c^.gnp := gnp;
END SetField;

PROCEDURE GetField (c : Country) : FieldType;
BEGIN
  RETURN c^.gnp
END GetField;

END Countries.

The next step is to define the table type. Here, a module name of CountryTable is employed, but the same semi-generic style as before is used. If some other data type is to be entabled in this way, one need only define the type as above, then

• change the definition below to have the name <myADTs>Table
• change the import line to

FROM <myADTs> IMPORT
  <myADT>, KeyType, DataType;

• change the renaming line to

TYPE
  DataType = <myADT>;

All references to the entabled data type from that point on are done using the local name, so no other changes need to be made. As usual, the allocation of memory for the data to be entabled is the responsibility of the table module rather than the calling program. Memory deallocation at table destruction time is also done by the table module.

Provision is made in the creation of a table to specify up to two strings to act as a title for the table and/or a set of headers for the columns. When the routine WriteTitle is called, a line of dashes the length of the longest of these two strings is printed underneath them to delimit the table and give the text a more professional look.

DEFINITION MODULE CountryTable;

(* semi-generic table type
by R. Sutcliffe   last modified 1995 06 07 *)

FROM Countries IMPORT
  Country, KeyType, ActionProc;

TYPE
  DataType = Country; (* change this line and import as needed *)
  TitleString = ARRAY [0..80] OF CHAR;
  TableState = (allRight, empty, entableFailed, notFound, bad);
  Table;  (* opaque type *)
  
PROCEDURE TableStatus (t : Table) : TableState;
(* Pre : t is a valid initialized table
   Post :The State of the table is returned *)

PROCEDURE Create (VAR t : Table; s1, s2 : TitleString);
(* Pre : none
   Post : t is a newly created empty table. s1 and s2 are stored for printing up to two lines of a table title *)

PROCEDURE Find (t : Table; searchKey : KeyType; VAR data : DataType; VAR found : BOOLEAN);
(* Pre : t is a valid initialized table
   Post : searchKey has been found and the ADT item returned in data and found is TRUE or the searchKey has not been found and found is FALSE.  The State of the table is not affected by this operation. *)

PROCEDURE Entable (t : Table; data : DataType);
(* Pre : t is a valid initialized table
   Post :memory for the data is obtained, data has been entabled and the state of the table is allRight
   or the entabling failed and the state is entableFailed. *)

PROCEDURE Remove (t : Table; key : KeyType; VAR data : DataType);
(* Pre : t is a valid initialized table
   Post : data matching key has been removed and returned in data (not disposed of) and the state of the table is allRight or the removal failed and the state is notFound. *)

PROCEDURE Destroy (VAR t : Table);
(* Pre : t is a valid initialized table
   Post : the table memory is returned and the variable is invalid 
   and the memory associated with the items in the table is removed by calling the ADT module dispose procedure. *)

PROCEDURE WriteTitle (t : Table);
(* Pre : t is a valid initialized table
   Post : any non-empty strings stored for this table are written one to a line followed by a line of n-dashes equal in length to the longest of the supplied strings and another carriage return if this is non-zero. *)

PROCEDURE Traverse (t : Table; Proc : ActionProc);
(* Pre : t is a valid initialized table
   Post : the table items are traversed and Proc is performed on each one. *)

END CountryTable.

IMPLEMENTATION MODULE CountryTable;

(* semi-generic table type
by R. Sutcliffe   last modified 1995 06 07 *)

FROM Countries IMPORT
  KeyType, ActionProc, Assign, Compare, GetKey, New, Valid, Dispose;
FROM Storage IMPORT
  ALLOCATE, DEALLOCATE;
FROM STextIO IMPORT
  WriteString, WriteLn, WriteChar;
FROM Strings IMPORT
  CompareResults;

TYPE
  NodePointer = POINTER TO TableNode;
  TableNode =
    RECORD
      item : DataType;
    toPoint, fromPoint : NodePointer;
    END;
  Table = POINTER TO TableData;
  TableData =
    RECORD
    top : NodePointer;
    title1, title2 : TitleString;
    state : TableState;
  END;
  
PROCEDURE TableStatus (t : Table) : TableState;
BEGIN
  IF t # NIL
    THEN
    RETURN t^.state;
  ELSE
    RETURN bad;
  END;
END TableStatus;

PROCEDURE Create (VAR t : Table; s1, s2 : TitleString);
BEGIN
  NEW (t);
  t^.top := NIL;
  t^.title1 := s1;
  t^.title2 := s2;
  t^.state := empty; 
END Create;

PROCEDURE Find (t : Table; searchKey : KeyType; VAR data : DataType; VAR found : BOOLEAN);
VAR
  point : NodePointer;
BEGIN
  found := FALSE;
  point := t^.top;
  WHILE point # NIL
    DO
      IF Compare (searchKey, GetKey (point^.item) ) = equal
        THEN
          data := point^.item;
          found := TRUE;
          RETURN;
        ELSE
          point := point^.toPoint
        END;
    END;
END Find;

PROCEDURE MakeNode () : NodePointer;
VAR
  temp : NodePointer;
BEGIN
  NEW (temp); (* get node memory *)
  IF temp # NIL
    THEN
      New (temp^.item);  (* node OK so get data value memory *)
      IF NOT Valid (temp^.item)
        THEN (* failed so return NIL *)
          DISPOSE (temp);
        END;
    END;
  RETURN temp;
END MakeNode;

PROCEDURE Entable (t : Table; data : DataType);
VAR
  temp : NodePointer;
  state : TableState;
BEGIN
  state := TableStatus (t);
  IF (state # bad) AND (state # entableFailed)
    THEN
      temp := MakeNode ();
      IF temp # NIL
        THEN
          Assign (data, temp^.item);
          temp^.toPoint := t^.top; (* point to old top *)
          temp^.fromPoint := NIL;
          IF t^.top # NIL
            THEN
              t^.top^.fromPoint := temp;
            END;
          t^.top := temp;
          t^.state := allRight;
        ELSE
          t^.state := entableFailed
        END;
    ELSE
      t^.state := entableFailed
    END;
END Entable;

PROCEDURE Remove (t : Table; key : KeyType; VAR data : DataType);
VAR
  point : NodePointer;
BEGIN
  point := t^.top;
  WHILE point # NIL
    DO
    IF Compare (key, GetKey (point^.item) ) = equal
      THEN
        data := point^.item;
        IF point^.fromPoint # NIL
          THEN
            point^.fromPoint^.toPoint := point^.toPoint;
          ELSE
            t^.top := point^.toPoint;
          END;
        IF point^.toPoint # NIL
          THEN
            point^.toPoint^.fromPoint := point^.fromPoint
          END;
        t^.state := allRight;
        RETURN;
      ELSE
        point := point^.toPoint
      END;
    END;
 t^.state := notFound; (* get here only if not found *)
END Remove;

PROCEDURE KillNode (VAR node : NodePointer);
(* give back all memory associated with node *)
BEGIN
  IF node # NIL
    THEN
      Dispose (node^.item);
      DISPOSE (node);
    END;
END KillNode;

PROCEDURE Destroy (VAR t : Table);
VAR
  point, next : NodePointer;
BEGIN
  IF t = NIL
    THEN
      RETURN
    END;
  point := t^.top;
  WHILE point # NIL
    DO (* kill all nodes *)
      next := point^.toPoint;
      KillNode (point);
      point := next;
    END;
  DISPOSE (t); (* and memory for table info *)
END Destroy;

PROCEDURE WriteTitle (t : Table);
VAR
  len, len2, count : CARDINAL;
BEGIN
  len := LENGTH (t^.title1);
  len2 := LENGTH (t^.title2);
  IF len2 > len
    THEN
      len := len2  (* take the maximum of the two *)
    END;
  IF t^.title1 [0] # ""
    THEN
      WriteString (t^.title1);
      WriteLn;
    END;
  IF t^.title2 [0] # ""
    THEN
      WriteString (t^.title2);
      WriteLn;
    END;
  IF len # 0
    THEN
      FOR count := 1 TO len 
        DO  (* write a bar below the title *)
          WriteChar ("-");
        END;
      WriteLn;
    END;
END WriteTitle;

PROCEDURE Traverse (t : Table; Proc : ActionProc);
VAR
  point : NodePointer;
BEGIN
  point := t^.top;
  WHILE point # NIL
    DO
      Proc ( point^.item);
      point := point^.toPoint;
    END;
END Traverse;

END CountryTable.

In the test harness below, note that various aspects of the initial ADT module Countries are tested, and then the table module is checked extensively to see if the entabling, searching, and removal of items works correctly. A data type such as Table should always be checked in this way, with simple data, so as to ensure that the logic is correct, before employing the library for larger types that are more difficult to test. While the author is not so foolish as to guarantee that the libraries above are error free, it is notable that the testing of this carefully designed pair of library modules turned up only one minor logical error--all other changes made during the testing process were of a purely cosmetic nature.

MODULE TestCountryTable;

(* program to test the logic of the table library with countries and their GNP 
by R. Sutcliffe   modified 1995 06 07 *)

IMPORT
  Countries, CountryTable, STextIO, SWholeIO;
  
VAR
  table : CountryTable.Table;
  country : Countries.Country;
  str : Countries.KeyType;
  num : Countries.FieldType;
  gotIt : BOOLEAN;

PROCEDURE WriteTable;
BEGIN
  CountryTable.WriteTitle (table);
  CountryTable.Traverse (table, Countries.WriteCountryData);
END WriteTable;

BEGIN
  CountryTable.Create (table,
    "      Table of countries and their GNP", 
    "Country Name                           GNP   ");
  Countries.New (country); (* just do it once *)
  Countries.SetKey (country, "Samovia");
  Countries.SetField (country, 13000000);
  
    (* test some stuff in Countries *)
  str := Countries.GetKey (country);
  STextIO.WriteString (str);
  num := Countries.GetField (country);
  SWholeIO.WriteCard (num,10);
  STextIO.WriteLn; STextIO.WriteLn;
  
      (* now get the table filled up *)
  CountryTable.Entable (table, country);
  WriteTable;
  STextIO.WriteLn;
  Countries.SetKey (country, "Xanadu");
  Countries.SetField (country, 3000);
  CountryTable.Entable (table, country);
  WriteTable;
  STextIO.WriteLn;
  Countries.SetKey (country, "Lundy");
  Countries.SetField (country, 42000);
  CountryTable.Entable (table, country);
  WriteTable;
  STextIO.WriteLn;
  Countries.SetKey (country, "Pompey");
  Countries.SetField (country, 13000);
  CountryTable.Entable (table, country);
  WriteTable;
  STextIO.WriteLn; STextIO.WriteLn;

     (* test finds *)
  CountryTable.Find(table, "Pompey", country, gotIt);
  IF gotIt
    THEN
      str := Countries.GetKey (country);
      STextIO.WriteString ("Got  ");
      STextIO.WriteString (str);
    ELSE
      STextIO.WriteString ("no got Pompey");
    END;
  STextIO.WriteLn; STextIO.WriteLn;

  CountryTable.Find(table, "Canada", country, gotIt);
  IF gotIt
    THEN
      str := Countries.GetKey (country);
      STextIO.WriteString ("Got  ");
      STextIO.WriteString (str);
    ELSE
      STextIO.WriteString ("no got Canada");
    END;
  STextIO.WriteLn; STextIO.WriteLn;

     (* test removes *)
  CountryTable.Remove(table, "Pompey", country);
  IF CountryTable.TableStatus (table) = CountryTable.allRight
    THEN
      STextIO.WriteString ("removed  Pompey");
    ELSE
      STextIO.WriteString ("could not remove Pompey");
    END;
  STextIO.WriteLn; STextIO.WriteLn;
  
     (* now check to ensure its gone *)
  CountryTable.Find(table, "Pompey", country, gotIt);
  IF gotIt
    THEN
      str := Countries.GetKey (country);
      STextIO.WriteString ("Got  ");
      STextIO.WriteString (str);
    ELSE
      STextIO.WriteString ("no got Pompey");
    END;
  STextIO.WriteLn; STextIO.WriteLn;
  WriteTable;
  STextIO.WriteLn; STextIO.WriteLn;

     (* now try to remove something not there *)
  CountryTable.Remove(table, "Canada", country);
  IF CountryTable.TableStatus (table) = CountryTable.allRight
    THEN
      STextIO.WriteString ("removed  Canada");
    ELSE
     STextIO.WriteString ("could not remove Canada");
    END;
  STextIO.WriteLn; STextIO.WriteLn;

     (* now remove one not at the start *)
  CountryTable.Remove(table, "Xanadu", country);
  IF CountryTable.TableStatus (table) = CountryTable.allRight
    THEN
      STextIO.WriteString ("removed  Xanadu");
    ELSE
      STextIO.WriteString ("could not remove Xanadu");
    END;
  STextIO.WriteLn; STextIO.WriteLn;
  WriteTable;
  STextIO.WriteLn; STextIO.WriteLn;

       (* now see if destroy seems to work *)
  CountryTable.Destroy (table);
  IF CountryTable.TableStatus (table) = CountryTable.bad
    THEN
      STextIO.WriteString ("table deleted");
    ELSE
      STextIO.WriteString ("could not destroy");
    END;
  STextIO.WriteLn; STextIO.WriteLn;

END TestCountryTable.

When this test was run, the following results were obtained:

** Run log starts here **
Samovia  13000000

      Table of countries and their GNP
Country Name                           GNP   
---------------------------------------------
Samovia                             13000000

      Table of countries and their GNP
Country Name                           GNP   
---------------------------------------------
Xanadu                                  3000
Samovia                             13000000

      Table of countries and their GNP
Country Name                           GNP   
---------------------------------------------
Lundy                                  42000
Xanadu                                  3000
Samovia                             13000000

      Table of countries and their GNP
Country Name                           GNP   
---------------------------------------------
Pompey                                 13000
Lundy                                  42000
Xanadu                                  3000
Samovia                             13000000


Got  Pompey

no got Canada

removed  Pompey

no got Pompey

      Table of countries and their GNP
Country Name                           GNP   
---------------------------------------------
Lundy                                  42000
Xanadu                                  3000
Samovia                             13000000


could not remove Canada

removed  Xanadu

      Table of countries and their GNP
Country Name                           GNP   
---------------------------------------------
Lundy                                  42000
Samovia                             13000000


table deleted

As the output from this test illustrates, this implementation of a table had the semantics of set membership--a data item either was in the table or it was not. No sorting was done. If sorted tables are desired, the entabling routine would have to be written accordingly. This is left as an exercise for the reader.