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