## 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)

 Country Gross National Product Samovia \$13 000 000 Xanadu \$3 000 Lundy \$42 000 Pompey \$13 000

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)

 x f(x) 1 8.9 2 4.5 3 6.7 4 5.1
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

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

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
• change the renaming line to
```TYPE

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

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

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
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;
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.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;

IF gotIt
THEN
str := Countries.GetKey (country);
STextIO.WriteString ("Got  ");
STextIO.WriteString (str);
ELSE
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 *)
IF CountryTable.TableStatus (table) = CountryTable.allRight
THEN
ELSE
END;
STextIO.WriteLn; STextIO.WriteLn;

(* now remove one not at the start *)
IF CountryTable.TableStatus (table) = CountryTable.allRight
THEN
ELSE
END;
STextIO.WriteLn; STextIO.WriteLn;
WriteTable;
STextIO.WriteLn; STextIO.WriteLn;

(* now see if destroy seems to work *)
CountryTable.Destroy (table);
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
---------------------------------------------
Samovia                             13000000

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

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

Got  Pompey

removed  Pompey

no got Pompey

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

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.

Contents