CS 136 Tutorials - Spring 2007

Tutorials »

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 d₁, d₂, ..., d_n. There are five operations on DEQs, as follows:

• The enqueue-front operation has two arguments: an item e and a DEQ D = d₁, d₂, ..., d_n, with precondition "true". The postcondition is that D = e, d₁, d₂, ..., d_n, and no value is produced.
• The enqueue-rear operation has two arguments: an item e and a DEQ D = d₁, d₂, ..., d_n, with precondition "true". The postcondition is that D = d₁, d₂, ..., d_n, e, and no value is produced.
• The dequeue-front operation has one argument, a DEQ D = d₁, d₂, ..., d_n, with precondition n > 0. The postcondition is that D = d₂, d₃, ..., d_n, and the value d₁ is produced.
• The dequeue-rear operation has one argument, a DEQ D = d₁, d₂, ..., d_n-1, d_n, with precondition n > 0. The postcondition is that D = d₁, d₂, ..., d_n-1, and the value d_n is produced.
• The DEQ-empty operation has one argument, a DEQ D = d₁, d₂, ..., d_n, 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, C₁ = (r₁,s₁) and C₂ = (r₂,s₂), and returns "true" if and only if they have the same rank, i.e. r₁=r₂.
• The rank-lessthan operation takes two cards, C₁ = (r₁,s₁) and C₂ = (r₂,s₂), and returns "true" if and only if the rank of C₁ is less than the rank of C₂, i.e. r₁<r₂.
• The suit-equals operation takes two cards, C₁ = (r₁,s₁) and C₂ = (r₂,s₂), and returns "true" if and only if they have the same suit, i.e. s₁=s₂.
• The card-equals operation takes two cards, C₁ = (r₁,s₁) and C₂ = (r₂,s₂), and returns "true" if and only if they have the same rank and suit, i.e. r₁=r₂ and s₁=s₂.

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

Last modified on Friday, 19 August 2011, at 18:05 hours.