11.5 System Structures: a Generic Sets Package

Up to this point we have seen only generic functions and procedures. In this section, we develop a generic package, namely, one for representing discrete sets, or sets of integers or enumeration values.

Sets are very important both in mathematics and in computer applications. Given a universe of objects or values, a set S is just a collection of objects belonging to that universe. Some common universes are the integers, the positive integers, alphabet letters, and so on. Sets are so important in programming that some languages, especially Pascal, provide sets as a predefined type. Ada does not have a predefined set type; in this section we will show an ADT that will emulate Pascal's predefined type, using a generic package.

Often sets are described just by listing their members between braces, as in the set {a,b} taken from the universe of English alphabet letters. In general, there is no ordering associated with a set, so {a,b} and {b,a} usually describe the same set. Two sets are said to be equal if they have the same members. A set is said to be empty if it has no members. In cases where there is no ordering, it also makes no difference if we name a member twice, so {a,b,a} = {b,a,b} = {a,b}.

Operations on Sets

What are the important operations associated with sets? Certainly inserting a member in a set and deleting a member from a set are essential; so are testing a set to see if a given element is a member and testing a set to see if it is empty. The last two operations are predicate or inquiry selector operations; they return Boolean values. The most important dyadic constructor operations are:

The union of two sets S and T (written usually as S U T), which returns the set containing all of S's members and all of T's members
The intersection of S and T (S ^ T), which returns the set containing all elements which are members of both S and T
The difference S-T, which returns the set containing all elements which are members of S but not of T

An often-used monadic constructor is the complement -S, which returns the set containing all elements in the universe which are not members of S.

We will use + and * to represent the union and intersection, respectively, because the union and intersection symbols are not part of the ASCII character set. For example, if the universe is the letters a..k, inclusive, and S = {a,d,e,g} and T = {b,c,d,e,k}, then

S+T = {a,b,c,d,e,g,k}

S*T = {d,e}

S-T = {a,g} and T-S = {b,c,k}

-S = {b,c,f,h,i,j,k}

Finally, two more inquiry operations are commonly used:

the improper subset operation (S C= T), which returns True if and only if all members of S are also members of T
the proper subset operation (S C T), which returns True if and only if S C= T and S /= T, that is, at least one member of T is not a member of S

Because the subset symbols are also missing from ASCII, we use < and < for improper and proper subset, respectively. For example, {b,c} < {a,b,c,d,e} and {b,c} < {a,b,c,d,e} but is not a subset of {c,e}. Also, {a,b} < {a,b}.

Specifying the Generic Set ADT

Mathematically, sets can be infinite (all the integers, for example). In programming applications, however, it is finite sets that are most interesting. Therefore we confine ourselves to representing finite sets, and specifically to sets taken from finite universes of integers or enumeration values. As we shall see, it is easy to use Ada's generic facility to build a package providing a good but more flexible approximation of the predefined set facility of Pascal.

A universe is either an integer subtype or an enumeration type, which means that a universe also happens to be a valid index range for arrays. Choosing a universe, we implement a set as a one-dimensional array of Boolean values, with index range corresponding to that universe. Given a set S represented in this fashion, if a given member of the universe is a member of S, we let the corresponding element of S be True; otherwise we let that element be False. This representation is often called the characteristic function or bit map of a set, and is an especially compact way to represent a large set. For example, suppose we choose the universe a..g. Every set over this universe is represented as a Boolean array indexed a..g, and specifically the set S = {a,d,e,g} is represented as

Array Representation

Now let us devise a generic Ada package for this ADT. A framework for the generic part of the specification is

    GENERIC

      TYPE Universe IS (<>);

    PACKAGE Sets_Generic IS
      . . .
    END Sets_Generic;

The second line specifies a generic parameter which can match any discrete type, that is, any enumeration type or integer subtype. This is exactly what we need for our finite, discrete, universes.

Program 11.14 gives the desired specification, complete with a private part defining the type Set. Making sets a PRIVATE type allows client programs to copy sets and check them for inequality using the predefined :=, =, and /= operations but prohibits clients from direct access to the implementation of sets. This leaves us, the package writer, the flexibility to change the implementation of sets without requiring any code changes in client programs.

Program 11.14
Specification for Generic Set Package

GENERIC

  TYPE Universe IS (<>);  -- any integer or enumeration type

PACKAGE Sets_Generic IS

------------------------------------------------------------------------
--| Generic specification for sets over discrete universes
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: September 1995                                     
------------------------------------------------------------------------

  TYPE Set IS PRIVATE;
  Phi: CONSTANT Set; -- empty set

  -- constructors

  FUNCTION "+" (S: Set; E: Universe) RETURN Set;
  FUNCTION "-" (S: Set; E: Universe) RETURN Set;
  -- Pre:  S and E are defined
  -- Post: returns S with E inserted or deleted respectively;
  --   "+" has no effect if IsIn(S,E); "-" has none if NOT IsIn(S,E)

  FUNCTION Singleton(E: Universe) RETURN Set;
  FUNCTION "+" (E1, E2: Universe) RETURN Set;
  -- Pre:  E, E1, and E2 are defined
  -- Post: returns a set made from one or two elements

  FUNCTION "+" (S, T : Set) RETURN Set;
  FUNCTION "*" (S, T : Set) RETURN Set;
  FUNCTION "-" (S, T : Set) RETURN Set;
  -- Pre:  S and T are defined
  -- Post: returns the union, intersection, and difference of
  --   S and T, respectively

  FUNCTION "-"  (S : Set) RETURN Set;
  -- Pre:  S is defined
  -- Post: returns the complement of S

  -- selectors
  FUNCTION IsIn (S : Set; E : Universe) RETURN Boolean;
  -- Pre:  S and E are defined
  -- Post: returns True if and only if E is a member of S

  FUNCTION IsEmpty (S : Set) RETURN Boolean;
  -- Pre:  S is defined
  -- Post: returns True if and only if S is empty

  FUNCTION SizeOf (S : Set) RETURN Natural;
  -- Pre:  S is defined
  -- Post: returns the number of members in S

  FUNCTION "<=" (S, T : Set) RETURN Boolean;
  FUNCTION "<"  (S, T : Set) RETURN Boolean;
  -- Pre:  S and T are defined
  -- Post: returns True if and only if S is 
  --   an improper or proper subset of T, respectively

PRIVATE
  TYPE SetArray IS ARRAY (Universe) OF Boolean;
  TYPE Set IS RECORD
    Store: SetArray := (OTHERS => False);
  END RECORD;
  Phi: CONSTANT Set := (Store => (OTHERS => False));
END Sets_Generic;

Note in the type definition that the Boolean array is stored in a record. This is to allow us to initialize all sets by default to the empty set: Recall that Ada allows us to default-initialize only objects of a record type. Note also the constant Phi, which we use to represent the empty set. The constant is partially declared at the top of the specification, then completed in the private part, after the full type definition for the PRIVATE type is given.

The operations to insert and delete a member are shown as operators "+" and "-", respectively, so that given a set S and an element E, the expressions S + E and S - E are meaningful. We include two additional constructor operators: Singleton, which creates a singleton set--a set with a single member--from its element parameter, and another "+" operator to create a set from two elements. Specifying all these operations as functions makes it easy to create a set with the desired membership. For example, a client program could instantiate GenericSets as follows:

    SUBTYPE SmallNatural is NATURAL RANGE 0..15);
    PACKAGE NaturalSets IS NEW Sets_Generic(Universe => SmallNatural);

and then, having declared a variable,

    S: NaturalSets.Set;

can include the odd small naturals in S with

    S := 7 + 3 + 13 + 5 + 1 + 9 + 11 + 15;

Implementing the Generic Set ADT

Program 11.15 shows the body of the package Sets_Generic. Note that the union, intersection, and difference operators construct their results by looping through the sets, finding elementwise AND, OR, and NOT values.

Program 11.15
Body of Generic Set Package

PACKAGE BODY Sets_Generic IS
------------------------------------------------------------------
--| Body of generic sets package
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: September 1995                                     
------------------------------------------------------------------

  -- constructors

  FUNCTION "+" (S: Set; E: Universe) RETURN Set IS
    Result: Set := S;
  BEGIN -- "+"
    Result.Store (E) := True;
    RETURN Result;
  END "+";

  FUNCTION "-" (S: Set; E: Universe) RETURN Set IS
    Result: Set := S;
  BEGIN -- "-"
    Result.Store (E) := False;
    RETURN Result;
  END "-";

  FUNCTION Singleton(E: Universe) RETURN Set IS
  BEGIN -- Singleton
    RETURN Phi + E;
  END Singleton;

  FUNCTION "+" (E1, E2: Universe) RETURN Set IS
  BEGIN -- "+"
    RETURN Phi + E1 + E2;
  END "+";

  FUNCTION "+" (S, T : Set) RETURN Set IS
    Result: Set;
  BEGIN -- "+"
    FOR E IN Universe LOOP
      Result.Store(E) := S.Store(E) OR T.Store(E);
    END LOOP;
    RETURN Result;
  END "+";

  FUNCTION "*" (S, T : Set) RETURN Set IS
    Result: Set;
  BEGIN -- "*"
    FOR E IN Universe LOOP
      Result.Store(E) := S.Store(E) AND T.Store(E);
    END LOOP;
    RETURN Result;
  END "*";

  FUNCTION "-" (S, T : Set) RETURN Set IS
    Result: Set;
  BEGIN -- "-"
    FOR E IN Universe LOOP
      Result.Store(E) := S.Store(E) AND NOT T.Store(E);
    END LOOP;
    RETURN Result;
  END "-";

  FUNCTION "-" (S : Set) RETURN Set IS
    Result: Set;
  BEGIN -- "-"
    FOR E IN Universe LOOP
      Result.Store(E) := NOT S.Store(E);
    END LOOP;
    RETURN Result;
  END "-";

  -- selectors

  FUNCTION IsIn (S : Set; E : Universe) RETURN Boolean IS
  BEGIN -- IsIn
    RETURN S.Store (E);
  END IsIn;

  FUNCTION IsEmpty (S : Set) RETURN Boolean IS
  BEGIN -- IsEmpty
    RETURN S = Phi;
  END IsEmpty;

  FUNCTION SizeOf (S : Set) RETURN Natural IS
    Result: Natural := 0;
  BEGIN -- SizeOf
    FOR E IN Universe LOOP
      IF S.Store(E) THEN
        Result := Result + 1;
      END IF;
    END LOOP;
    RETURN Result;
  END SizeOf;

  FUNCTION "<=" (S, T : Set) RETURN Boolean IS
  BEGIN -- "<="
    RETURN (S + T) = T;
  END "<=";

  FUNCTION "<" (S, T : Set) RETURN Boolean IS
  BEGIN -- "<"
    RETURN S /= T AND THEN S <= T;
  END "<";

END Sets_Generic;

An Application: Music Makers

Program 11.16 shows an example of how Sets_Generic might be used. An enumeration type Instruments is declared, representing common musical instruments. The generic package is instantiated for these, and variables are created representing different kinds of musical ensembles, depending on the instruments usually found in them. The program shows one local procedure DisplayEnsemble which operates by using an instance of Text_IO.Enumeration_IO and iterating through an ensemble to display only those instruments present in that ensemble.

Program 11.16
A Music Makers Program

WITH Ada.Text_IO;
WITH Sets_Generic;
PROCEDURE Music_Makers IS
------------------------------------------------------------------------
--| Example of the use of Sets_Generic, to create musical ensembles
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: September 1995                                     
------------------------------------------------------------------------

  TYPE Instruments IS
    (Violin, Viola, Cello, BassViol,      -- classical strings
     Piano, Harpsichord, Organ,           -- classical keyboards
     Clarinet, Saxophone,                 -- single-reed woodwinds
     Oboe, Bassoon,                       -- double-reed woodwinds
     Flute, Piccolo,                      -- flutes
     Trumpet, Trombone, FrenchHorn, Tuba, -- brass
     Tympani, Snare, TomTom, BassDrum,    -- drums
     Cymbals, Triangle, Bells, Marimba,   -- percussion
     Guitar, Banjo, Ukelele,              -- folk strings
     Accordion, Keyboard);                -- miscellaneous

  PACKAGE Music_IO IS NEW Ada.Text_IO.Enumeration_IO(Enum => Instruments);
  PACKAGE Ensembles IS NEW Sets_Generic (Universe => Instruments);
  USE Ensembles;

  SUBTYPE Ensemble IS Ensembles.Set; -- nickname for this program

  Strings: CONSTANT Ensemble := Violin + Viola + Cello + BassViol;
  Brasses: CONSTANT Ensemble := Trumpet + Trombone + FrenchHorn + Tuba;
  JazzDrums: CONSTANT Ensemble := Snare + TomTom + BassDrum + Cymbals;
  
  JazzCombo:        Ensemble;
  StringQuartet:    Ensemble;
  PhillyStringBand: Ensemble;
  RockBand:         Ensemble;

  PROCEDURE DisplayEnsemble(Band: Ensemble) IS
  BEGIN
    FOR Instrument IN Instruments LOOP
      IF IsIn(Band, Instrument) THEN
        Music_IO.Put(Instrument);
        Ada.Text_IO.New_Line;
      END IF;
    END LOOP;
    Ada.Text_IO.New_Line;
  END DisplayEnsemble;

BEGIN -- Music_Makers

  JazzCombo := JazzDrums + Guitar + BassViol + Trumpet;
  Ada.Text_IO.Put(Item => "Jazz Combo:");
  Ada.Text_IO.New_Line;
  DisplayEnsemble(Band => JazzCombo);

  PhillyStringBand := Guitar + Ukelele + Banjo + Accordion
    + Saxophone + Snare + BassDrum;
  Ada.Text_IO.Put(Item => "Philly String Band:");
  Ada.Text_IO.New_Line;
  DisplayEnsemble(Band => PhillyStringBand);

  StringQuartet := Strings - BassViol;
  Ada.Text_IO.Put(Item => "String Quartet:");
  Ada.Text_IO.New_Line;
  DisplayEnsemble(Band => StringQuartet);

  RockBand := Guitar + Keyboard + JazzDrums;
  Ada.Text_IO.Put(Item => "Rock Band:");
  Ada.Text_IO.New_Line;
  DisplayEnsemble(Band => RockBand);

END Music_Makers;

Sample Run

Jazz Combo:
BASSVIOL
TRUMPET
SNARE
TOMTOM
BASSDRUM
CYMBALS
GUITAR

Philly String Band:
SAXOPHONE
SNARE
BASSDRUM
GUITAR
BANJO
UKELELE
ACCORDION

String Quartet:
VIOLIN
VIOLA
CELLO

Rock Band:
SNARE
TOMTOM
BASSDRUM
CYMBALS
GUITAR
KEYBOARD

One of the ensembles in the program, PhillyStringBand, reveals the author's Philadelphia upbringing: this city is the home of the String Band, which--as can be seen from the instruments--contains more than strings, and no violins. A large number of String Bands march in Philadelphia's New Year's Day parade; prizes are awarded to the groups having the most imaginative costumes as well as the best music.

As an exercise, you can create some of your favorite musical ensembles. Try creating a brass band and a symphony orchestra. This example highlights one of the difficulties in using sets in the pure mathematical sense: Because duplicate elements do not change the set, we cannot, using this representation, keep track of just how many of each instrument are in a particular ensemble--only the instrument types are represented.