IPT - A Virtual Approach IPT A Virtual Approach by Peter Whitehouse
Quick Links:
 
 
Information and Intelligent Systems Social and Ethical Implications Human Computer Interaction Software and Systems Engineering eXercise Files Course Outline and Assessment A-Z of Geeky Acronyms Terrace Work Program 2004 Sillybus FAQ = Frequently Asked Questions Help
 
 

Sets

Compound Data Structures

COMPOUND DATA STRUCTURES IN PASCAL

data is either i) scalar
                       ordinal
                            (byte or char or boolean or integer)
                       real
               ii) compound
                        set or array or string or record or
                         file or object

In Pascal...

Compound data types are used to individually store related pieces of information, such that each piece of information is readily accessible.

More specifically...

A SET is a collection of values, used when order and repetition is unimportant (ie. only one of each value needs to be stored) - in Pascal, each element of the set is the same type

An ARRAY is an ordered collection of memory cells of the same type (the order and repetition are important as every value is stored). A one dimensional array (has length) is termed a vector, a two dimensional array (length and width) is termed a matrix, 3 and above dimensions are a headache (but is often used)

A STRING is a special case of an ARRAY - fixed or variable length one dimensional arrays (vectors) of CHARACTERS.

A RECORD is (usually) a multi-part memory cell where values of varying types may be stored in a specific order. (if it will help, visualise it as a ROW of a TABLE, where the columns are different type information).

A TABLE (an invented type) is usually an ARRAY of RECORDS

A FILE is an ordered collection of RECORDS or CHARACTERS (in the case of a TEXT file) - accessible randomly or sequentially

Typically, programmers use combinations of the above eg: records of arrays of strings; arrays of arrays of sets....


THE PASCAL SET

A set is an un-ordered collection of distinct well defined items usually of the same type. Each item in the set is called an element or member. The cardinality of the set is the number of elements in the set.

The order of elements in a set, and the repetition of elements in a set is strictly irrelevant

eg.   setA = [2,3,5]        setB = [5,2,3,3]


      setA and B are EQUAL sets
      2 is an element of setA and setB


      setC = [2,5]
      setC is a SUBSET of set A      setA is the SUPERSET of setC


      setD = [1,4,5,6,7]
      the UNION of setA and setD = [1,2,3,4,5,6,7]
      the INTERSECTION of setD with setC = [5]
      the difference of setD-setC = [1,2,4,6,7]
      the symmetric difference (XOR) of setD and setC = [1,2,3,6,7]

A LITTLE SETS EDUCATION

In memory, a SET is allocated to a single 32 byte memory cell = 256 bits total --> LOGICAL limit to the number of different values that can be stored in a set

the set [2,3,4]  =    0011100000000...................
                      012345678901234567890123  (ordinal value)

the set[1,3,5,3] =    0101010000000...................

the set []  =         0000000000000.................  (ie. a NULL set)

a set of char ['A','B','C']
            = ............000111000000000......
                             ^
                             65

User Enumerated types  [eg.  type Days = (sun, mon, tue...)   ]
the set [sun,tue] = 10100000...................

Although this seems a grossly inefficient storage organ for small sets, most Pascals re-use unallocated memory cell space.

Set Operations

Testing for inclusion of an element in a set makes use of the IN operator:

   1 in [2,1,3]          results in TRUE
   1 in [5,2,6]          results in FALSE
   7 in [3..25]          results in TRUE
   x in [3..25]          depends on x's value for truth

To ADD elements to an existing set, we UNION the existing set with a set containing the new element (this is equivalent to a bit-wise OR)

      eg:   ['A','B','C'] + ['C','D'] results in  ['A','B','C','D']

      eg:   Var barbie,ken : set of byte;
            Begin

               barbie := [];
               barbie := barbie + [36,25,34];  {adding elements}

To find out COMMON elements, we INTERSECT (this is a bit-wise AND)

      eg:   newset := ken * barbie  {the intersection of them}

      eg:   newset := ken * barbie  {the intersection of them}

To REMOVE elements, we calculate as the DIFFERENCE of the original set with a set containing the elements to be exterminated (this is a bit-wise AND NOT)

      eg:   newset := ken - [36]  {removes 36 from ken}

You will notice Pascal has recycled the +, - and * operators which mean different things in other contexts.

To compare sets, we use = for EQUALITY, <>for INEQUALITY, <= for SUBSET, >= for SUPERSET

      eg:   rupert := [42];
            ken = barbie    is FALSE as they are not equal sets
            ken >= rupert   is TRUE, rupert is a subset, ken is a sssuperset

CASE STUDY - a little bit more raw sets

      Const    max = 10
      Type     days = (1..max);
               thing = set of days;
      Var      good, bad, fair    : thing;
               answer             : thing;
      Begin
         good :=  [4,6,8,10];
         fair :=  [1,4,5,7,3,10];
         bad :=   [2,3,9];
         answer := good + fair;   {good OR fair days}
         answer := good * fair;   {good AND fair days}
         answer := good - fair;   {good AND NOT fair days}
         if 1 in fair then        {day 1 is a fair day}
         if 2 in (good+fair) then {day 2 is either good or fair}
         if fair * bad <> [] then {some days are both fair and bad}
         
      Procedure WriteOutSet(barbie : thing);
         {prints out set of days to screen}
         var   loop : days;
         begin
            for loop := 1 to 10 do
               if loop in barbie
                  then write(loop:3);
            writeln
         end; {WriteOutSet}

Notes on Sets

  • maximum cardinality (ie # in set) = 256*
  • ordinal types only (boolean, char, byte, enumerated* and subrange*)
  • NO MIXED TYPES in sets
  • only way to output them is to test for elements presence, and print conditionally (ie. loop process or the like)
Compound Data Structures - Sets
 

wonko@wonko.info
©Copyright t 1992..2017+. Edition 25.150117
wonkosite
Creative Commons License
This work is licensed under a
Creative Commons Attribution-NonCommercial-ShareAlike 2.1 Australia License
.