The Set Structure

The third fundamental data structure—in addition to the array and the record—is the set structure. It is defined by the following declaration pattern:

type T = set of T₀

(1.26)

The possible values of a variable $x$ of type $T$ are sets of elements of $T_0$ . The set of all subsets of elements of a set $T_0$ is called the powerset of $T_0$ . The type $T$ thus comprises the powerset of its base type $T_0$ .

Examples

type intset = set of 0 .. 30
type charset = set of char
type tapestatus = set of exception

The second example is based on the standard set of characters denoted by the type char; the third example is based on a set of exception conditions which might be defined as a scalar type

type exception = (unloaded, manual, parity, skew)

describing the various exceptional states that a magnetic tape unit may assume. Given the variables

is : intset
cs : charset
t  : array[1 .. 6] of tapestatus

particular values of set types may be constructed and assigned, for example,24 as follows:¹

is := [1, 4, 9, 16, 25]
cs := [‘+’, ‘-’, ‘*’, ‘/’]
t[3] := [manual]
t[5] := [ ]
t[6] := [unloaded .. skew]

Here, the value assigned to t[3] is the singleton set consisting of the single element manual; to t[5] is assigned the empty set, meaning that the fifth tape unit is returned to operational (non-exceptional) status, whereas t[6] is assigned the set of all four exceptions.

The cardinality of a set type $T$ is

\text{cardinality}(T) = 2^{\text{cardinality}(T_0)} \tag{1.27}

This can easily be derived from the fact that each of the cardinality $(T_0)$ elements of $T_0$ must be represented by one of the two values “present” or “absent” and that all elements are independent of each other. It is evidently essential for an efficient and economical implementation that the base type be not only finite, but that its cardinality is reasonably small.

The following elementary operators are defined on all set types:

*    set intersection
+    set union
-    set difference
in   set membership

Constructing the intersection or union of two sets is often called set multiplication or set addition, respectively; the priorities of the set operators are defined accordingly, with the intersection operator having priority over the union and difference operators, which in turn have priority over the membership operator, which is classified as a relational operator. Following are examples of set expressions and their fully parenthesized equivalents:

r * s + t  = (r*s)+t
r - s * t  = r-(s*t)
r - s + t  = (r-s)+t
x in s + t = x in (s+t)

Our first example of an application of the set structure is the program of a simple scanner of a compiler. We assume that the purpose of the scanner is25 to translate a sequence of characters into a sequence of textual units of the language to be compiled, of so-called tokens or symbols. The scanner is to be represented as a procedure which each time it is called reads a sufficient number of input characters in order to generate the single next output symbol. The particular rules of translation will be the following:

The set of output symbols consists of the elements identifier, number, lessequal, greaterequal, becomes, and others which correspond to various single characters such as +, -, *, etc.
The symbol identifier is generated upon reading a sequence of letters and digits starting with a letter.
The symbol number is generated upon reading a sequence of digits.
The symbols lessequal, greaterequal, and becomes are generated upon reading the respective character pairs <= , >= , := .
Blanks and ends of lines are skipped.

We have at our disposal a primitive procedure read(x) which picks the next character off the input sequence and assigns it to the variable $x$ . The resulting output symbol is to be assigned to a global variable called sym. Moreover, there are the global variables id and num, whose purpose will be evident from Program 1.2, and ch representing the currently scanned character in the input sequence. $S$ denotes a mapping of characters to symbols, i.e., an array of symbols with an index domain over those characters which are neither digits nor letters. The use of sets of characters demonstrates how a scanner can be programmed independently of the order of the characters in the underlying character set.

A second example is drawn from constructing a school timetable. Suppose that $M$ students have made their choices among $N$ subjects. Now a timetable is to be constructed such that certain subjects are scheduled to be given at the same time in such a way that no conflicts arise [1.1].

In general, the construction of a timetable is a most difficult combinatorial problem, and a choice must be made under many constraints and with many factors to be considered. In this example we will simplify the problem drastically, without making the claim of a solution for a realistic timetable situation.

First of all, we realize that in order to find suitable choices for “parallel” sessions, we may base the decisions upon a set of data derived from the individual student’s course registrations, namely, from the enumeration of courses that cannot be given simultaneously. Therefore, we first program a data reduction process, based on the following declarations and on the convention that students are numbered from 1 to $M$ and courses from 1 to $N$ .

var ch: char;
    sym: symbol;
    num: integer;
    id: record
           k: 0 .. maxk;
           a: array [1 .. maxk] of char
        end ;
procedure scanner;
   var ch1: char;
begin {skip blanks}
   while ch = ‘␣’ do read(ch);
   if ch in [‘A’ .. ‘Z’] then
      with id do
      begin sym := identifier; k := 0;
         repeat if k < maxk then
                begin k := k+1; a[k] := ch
                end ;
            read(ch)
         until ¬(ch in [‘A’ .. ‘Z’ , ‘0’ .. ‘9’])
      end else
   if ch in [‘0’ .. ‘9’] then
      begin sym := number; num := 0;
         repeat num := 10*num+ord(ch)-ord(‘0’);
            read(ch)
         until ¬(ch in [‘0’ .. ‘9’])
      end else
   if ch in [‘<’, ‘:’, ‘>’] then
      begin ch1 := ch; read(ch);
         if ch = ‘=’ then
         begin
            if ch1 = ‘<’ then sym := leq else
            if ch1 = ‘>’ then sym := geq else sym := becomes;
            read(ch)
         end
         else sym := S[ch1]
      end else
   begin {other symbols}
      sym := S[ch]; read(ch)
   end
end {scanner}

Program 1.2 A scanner.

type course = 1 .. N;
     student = 1 .. M;
     selection = set of course;
var s: course;
    i: student;
    registration: array[student] of selection;
    conflict: array[course] of selection;
{Determine the sets of conflicting courses from the individual
 student's course registrations}
for s := 1 to N do  conflict[s] := [ ];
for i := 1 to M do
   for s := 1 to N do
   if s in registration[i] then
      conflict[s] := conflict[s] + registration[i]

(1.28)

(Note that s in conflict[s] is a consequence of this algorithm.)

The main task now consists of constructing a timetable, i.e., a list of sessions, each session being a selection of courses that do not conflict. From the whole set of courses we pick suitable, non-conflicting subsets of courses, subtracting them from a variable called remaining, until that set of remaining courses is empty.

var k: integer;
    remaining, session: selection;
    timetable: array[1 .. N] of selection;
k := 0; remaining := [1 .. N];
while remaining ≠ [ ] do
   begin session := next suitable selection;
         remaining := remaining - session;
         k := k+1; timetable[k] := session
   end

(1.29)

How do we make a “next suitable selection”? At the outset, we may select any single course from the set of remaining courses. Subsequently, the choice of further candidates may be restricted to the set of courses from the set of remaining courses which do not conflict with the ones initially selected. We call this set the trialset. When investigating a candidate from the trialset, we see that its choice depends upon whether or not the intersection of the already selected courses with the conflict-set of the candidate is empty. This leads to the following elaboration of the statement “session := next suitable selection”:

Table 1.3 Fundamental data structures. — **Table 1.3** Fundamental data structures.

var s,t: course;
    trialset: selection;
begin s := 1;
      while ¬(s in remaining) do s := s+1;
      session := [s]; trialset := remaining - conflict[s];
      for t := 1 to N do
         if t in trialset then
         begin if conflict[t] * session = [ ] then
                 session := session + [t]
         end
end

(1.30)

Evidently, this solution for selecting “suitable” sessions will not generate a timetable which is necessarily optimal in any specific sense. In unfortunate cases the number of sessions may be as large as that of courses, even if simultaneous scheduling were feasible.