
Tutorial 3:
ADTs (May 18)
Today's tutorial focuses on Abstract Data Types (ADTs) and how to implement
them in PLT Scheme's object/class system.
These concepts are introduced in Lecture Modules 3 and 4
(see Handouts).
 Doubleended queue
Here is a description of the doubleended queue (DEQ) ADT:
A DEQ is a (possibly empty) sequence of values
d_{1}, d_{2}, ...,
d_{n}.
There are five operations on DEQs, as follows:
 The enqueuefront operation has two arguments: an item e
and a DEQ
D = d_{1}, d_{2}, ...,
d_{n},
with precondition "true".
The postcondition is that
D = e,
d_{1}, d_{2}, ...,
d_{n},
and no value is produced.
 The enqueuerear operation has two arguments: an item e
and a DEQ
D = d_{1}, d_{2}, ...,
d_{n},
with precondition "true".
The postcondition is that
D =
d_{1}, d_{2}, ...,
d_{n}, e,
and no value is produced.
 The dequeuefront operation has one argument,
a DEQ
D = d_{1}, d_{2}, ...,
d_{n},
with precondition n > 0.
The postcondition is that
D =
d_{2}, d_{3}, ...,
d_{n},
and the value d_{1} is produced.
 The dequeuerear operation has one argument,
a DEQ
D = d_{1}, d_{2}, ...,
d_{n1}, d_{n},
with precondition n > 0.
The postcondition is that
D = d_{1},
d_{2}, ...,
d_{n1},
and the value d_{n} is produced.
 The DEQempty operation has one argument,
a DEQ
D = d_{1}, d_{2}, ...,
d_{n},
with precondition "true".
The postcondition is "true", and the value "true" is produced if and only if
n=0.
Implement the doubleended queue ADT as a class called DEQ%
in Scheme.
 Playing Cards
The following is a description of the Card ADT:
A Card is a pair (r,s), where r (the "rank")
is an integer in the range [1,13], and s (the "suit")
is one of the four words "spades", "hearts", "clubs", or "diamonds".
Cards are immutable, and so all preconditions and postconditions of all
operations are "true". A Card has the following operations:
 The getrank operation takes a Card (r,s)
and produces the rank r of that Card.
 The getsuit operation takes a Card (r,s)
and produces the suit s of that Card.
 The rankequals operation takes two cards,
C_{1} = (r_{1},s_{1})
and
C_{2} = (r_{2},s_{2}),
and returns "true" if and only if they have the same rank,
i.e. r_{1}=r_{2}.
 The ranklessthan operation takes two cards,
C_{1} = (r_{1},s_{1})
and
C_{2} = (r_{2},s_{2}),
and returns "true" if and only if the rank of C_{1} is
less than the rank of C_{2},
i.e. r_{1}<r_{2}.
 The suitequals operation takes two cards,
C_{1} = (r_{1},s_{1})
and
C_{2} = (r_{2},s_{2}),
and returns "true" if and only if they have the same suit,
i.e. s_{1}=s_{2}.
 The cardequals operation takes two cards,
C_{1} = (r_{1},s_{1})
and
C_{2} = (r_{2},s_{2}),
and returns "true" if and only if they have the same rank and suit,
i.e. r_{1}=r_{2}
and s_{1}=s_{2}.
Implement the Card ADT as a class called card% in Scheme.
