CP502: The type set.

3.7. The type set.

In mathematics, a set is a collection of elements. Java allows sets of bits which could be used as the basis for an arbitrary set. The BitSet class is limited to integers but can be arbitrarily large. We will see later that we can set, clear and query bits in the set and also perform bitwise ands and ors. This gives us most of the functionality of a mathematical set.

Our pseudo-code design will assume we have sets:


      enumerated type or subrange 0 -> N

      type musictype=(classical,folk,rock)

            musicset = set of musictype

      var  musicp,musicpref:musicset

Therefore variable musicpref can have these possible values.


 [classical],[folk],[rock],[classical,folk],[classical,rock]

 [rock,folk],[classical,rock,folk],[].

Note that the order of elements in set is irrelevant - sets are unordered. Variable musicpref can have 8 possible values including the empty or null set [].


      type    letters = 'A'..'Z';

             SetOfLetters = set of letters;

      var  vowels,consonants:set of letters;

                  :

            vowels  ['A','E','I','O','U'];

            consonants  ['A'..'Z']-vowels;

We can construct a set in a shorthand manner.


      [1,2,3,4,5]=[1..5]  specify subrange

      [1,2,3,4,5,10]=[1..5,10]    [classical..rock]

      [5..1]=[]            since 5>1

3.7.1. Set Operators.

What operators can be used on/with sets?
Arithmetic operators:
+ = set union = adding elements to a set.


       [3..5] + [1,2] = [1..5]

Note:   musicpref  musicp + [classical];   /* Correct */

        musicpref  musicp + classical;     /* Incorrect */

Also  [classical,folk,rock] + [folk] = [classical,folk,rock]

- set difference = removing elements from set.


        [classical,folk]-[folk] = [classical]

        [classical,folk]-[rock] = [classical,folk]

* set intersection = which elements are in both sets.


      [classical,folk]*[folk,rock] -> [folk]

      [folk]*[rock] -> []

Note:


   if element is not in set then deleting it, '-', changes nothing;

   if it is already in Set, then adding it to set, '+', changes nothing.

3.7.2. Relational operators and membership.

These produce a boolean result: = true or false
= equality : do sets contain same elements?


      [classical,jazz]=[jazz,classical] is true

      [5..1]=[]  is true since 5>1

      [1]=[1,2] is false

!= inequality as above but not same elements in set.
<= inclusion X<=Y: is x a subset of Y?
>= inclusion X>=Y: is Y a subset of X?


      [2..5] <= [1,2..5]  is true

      [1..3] <= [1,3]     is false

      [classical] >= [classical,folk,rock] is false

in set membership is a particular value in set?


                7 in [1..6]  is false

                7 in [1..7]  is true

        Note: not [7] in [1..7]

Rather than write


        if (ch>='a') and (ch<='z')  we could use

        if  ch in ['a'..'z']

BUT


 Rutgers Pascal manual page A-2 item f says:

        sets of char are restricted and in fact

          ['a'..'z'] is same as ['A'..'Z'].  BE CAREFUL.

This is because the maximum size of a set in some languages is implementation defined. Therefore sets can only contain a certain number of elements.
On the DEC-10 it was 72 (for 128 ASCII characters) with lower case and control characters mapped into upper case and blank respectively.
On Cyber we had a maximum set size of 60 and their character set size was 64 long!!

Therefore check implementation defined limits before you write a large "elegant" set program.

NOTE:

(1) A typical error is

                                 Wrong

        repeat

               ...........

        until ch not in ['0'..'9'];

            Correct form is

        repeat

              .........

        until not ch in ['0'..'9'];

not must precede a boolean expression, not a set range.

(2) Assume that we can only have sets of ordinal types. (It would be nice to have a set of some-type: set of pointers?)

(3) ch in ['A'..'Z'] will only work only if 'A' -> 'Z' is ordered and contiguous.