# CS 136 Tutorials - Spring 2007

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

### Double-ended queue

Here is a description of the double-ended queue (DEQ) ADT:

A DEQ is a (possibly empty) sequence of values d1, d2, ..., dn. There are five operations on DEQs, as follows:

• The enqueue-front operation has two arguments: an item e and a DEQ D = d1, d2, ..., dn, with precondition "true". The postcondition is that D = e, d1, d2, ..., dn, and no value is produced.
• The enqueue-rear operation has two arguments: an item e and a DEQ D = d1, d2, ..., dn, with precondition "true". The postcondition is that D = d1, d2, ..., dn, e, and no value is produced.
• The dequeue-front operation has one argument, a DEQ D = d1, d2, ..., dn, with precondition n > 0. The postcondition is that D = d2, d3, ..., dn, and the value d1 is produced.
• The dequeue-rear operation has one argument, a DEQ D = d1, d2, ..., dn-1, dn, with precondition n > 0. The postcondition is that D = d1, d2, ..., dn-1, and the value dn is produced.
• The DEQ-empty operation has one argument, a DEQ D = d1, d2, ..., dn, with precondition "true". The postcondition is "true", and the value "true" is produced if and only if n=0.

Implement the double-ended 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 get-rank operation takes a Card (r,s) and produces the rank r of that Card.
• The get-suit operation takes a Card (r,s) and produces the suit s of that Card.
• The rank-equals operation takes two cards, C1 = (r1,s1) and C2 = (r2,s2), and returns "true" if and only if they have the same rank, i.e. r1=r2.
• The rank-lessthan operation takes two cards, C1 = (r1,s1) and C2 = (r2,s2), and returns "true" if and only if the rank of C1 is less than the rank of C2, i.e. r1<r2.
• The suit-equals operation takes two cards, C1 = (r1,s1) and C2 = (r2,s2), and returns "true" if and only if they have the same suit, i.e. s1=s2.
• The card-equals operation takes two cards, C1 = (r1,s1) and C2 = (r2,s2), and returns "true" if and only if they have the same rank and suit, i.e. r1=r2 and s1=s2.

Implement the Card ADT as a class called `card%` in Scheme.