C311 Spring 1997 -- Programming Languages

Assignment 10: Simple Object Oriented Programming

Due Thursday, April 17, 11:59pm

1. Define in Scheme a queue class, such that after (define q (make-queue)):
   • (q 'num-queues) returns the number of queues created so far.
   • ((q 'enqueue) x) adds x to the tail of q.
   • (q 'dequeue) removes and returns the value at the head of q.
   Hint: represent queues internally as lists, with the head of the queue at the beginning of the list. Use two instance variables, one pointing to the head of the queue and one pointing to the tail. Add an element to the end of a non-empty queue with set-cdr! on the last element pair of the existing queue.

2. Use delegation to define a bounded-queue class that extends the queue class such that after (define bq (make-bounded-queue b)):
   • bq represents a bounded queue with bound b.
   • ((bq 'enqueue) x), and (bq 'dequeue) work as for queues, except that an error is raised on an enqueue if the number of elements in the queue is already the same as the bound.
   • (bq 'size) returns the current number of elements in bq.
   • (bq 'bound) returns the bound of bq.
   • (bq 'num-bqueues) returns the number of bounded queues created so far.

Test cases

          Chez Scheme Version 5.0b
          Copyright (c) 1994 Cadence Research Systems
          
          > (load "a10.ss")
          > (define q1 (make-queue))
          > (define q2 (make-queue))
          > (q2 'num-queues)
          2
          > (define q3 (make-queue))
          > (q1 'num-queues)
          3
          > ((q1 'enqueue) 3)
          > ((q2 'enqueue) 1)
          > ((q2 'enqueue) 4)
          > ((q2 'enqueue) 1)
          > ((q2 'enqueue) 5)
          > (q3 'dequeue)
          
          Error in dequeue: Underflow.
          Type (debug) to enter the debugger.
          > (q1 'dequeue)
          3
          > (q2 'dequeue)
          1
          > (q2 'dequeue)
          4
          > (q2 'dequeue)
          1
          > (q2 'dequeue)
          5
          > (q2 'dequeue)
          
          Error in dequeue: Underflow.
          Type (debug) to enter the debugger.
          > (define bq1 (make-bounded-queue 3))
          > (define bq2 (make-bounded-queue 5))
          > (bq1 'size)
          0
          > (bq2 'bound)
          5
          > (bq1 'num-bqueues)
          2
          > (bq1 'num-queues)
          5
          > ((bq1 'enqueue) 2)
          > ((bq1 'enqueue) 7)
          > ((bq1 'enqueue) 1)
          > ((bq1 'enqueue) 8)
          
          Error in enqueue: Bound 3 exceeded.
          Type (debug) to enter the debugger.
          > (bq2 'size)
          0
          > (bq1 'size)
          3
          > (bq1 'dequeue)
          2
          > (bq1 'dequeue)
          7
          > (bq1 'dequeue)
          1
          > (bq1 'dequeue)
          
          Error in dequeue: Underflow.
          Type (debug) to enter the debugger.
          > (bq1 'nomessage)
          
          Error in nomessage: Unknown message.
          Type (debug) to enter the debugger.
          >
	

Submission