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

  1. Double-ended queue
  2. 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.

  3. Playing Cards
  4. 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.

 

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