Exercise 3.23

Read Exercise 3.23 ~ Solution

---

I decided to use a single object with a dispatch procedures instead of a set of global procedures.

(define (make-deque)
  (define front null)
  (define rear null)
  
  (define (set-front! item) (set! front item))
  (define (set-rear! item)  (set! rear item))
  (define (empty-deque?) (null? front))
  (define (insert-front! item)
    (let ((new-front (cons (cons item null) front)))
      (cond ((empty-deque?) (set-front! new-front)
                            (set-rear!  new-front)
                            dispatch)
            (else (set-cdr! (car front) new-front)
                  (set-front! new-front)
                  dispatch))))
  (define (insert-rear! item)
    (let ((new-rear (cons (cons item rear) null)))
      (cond ((empty-deque?) (set-front! new-rear)
                            (set-rear!  new-rear)
                            dispatch)
            (else (set-cdr! rear new-rear)
                  (set-rear! new-rear)
                  dispatch))))
  (define (delete-front!)
    (cond ((empty-deque?) (error "DELETE-FRONT! called on empty queue" front))
          (else (set-front! (cdr front))
                (unless (empty-deque?)
                  (set-cdr!  (car front) null))
                dispatch)))
  (define (delete-rear!)
    (cond ((empty-deque?) (error "DELETE-REAR! called on empty queue" front))
          (else (set-rear! (cdar rear))
                (if (null? rear)
                    (set-front! null)
                    (set-cdr! rear null))
                dispatch)))
  (define (print-queue)
    (define (print-end) (display ")") (newline))
    (display "(")
    (let print-next ((next front))
      (cond ((null? next) (print-end))
            ((null? (cdr next)) (display (caar next))
                                 (print-end))
            (else (display (caar next))
                  (display " ")
                  (print-next (cdr next))))))
  (define (dispatch m)
    (cond ((eq? m 'insert-front!) insert-front!)
          ((eq? m 'insert-rear!)  insert-rear!)
          ((eq? m 'delete-front!) (delete-front!))
          ((eq? m 'delete-rear!)  (delete-rear!))
          ((eq? m 'front)         front)
          ((eq? m 'rear)          rear)
          ((eq? m 'print)         (print-queue))
          (else (error "DEQUEUE -- Unknown instruction" m))))
  dispatch)

(define dq (make-deque))
(((dq 'insert-rear!) 'a) 'print)
(a)

(((dq 'insert-front!) 'z) 'print)
 (z a)

(((dq 'insert-rear!) 'b) 'print)
(z a b)

(((dq 'insert-front!) 'y) 'print)
(y z a b)

(((dq 'insert-rear!) 'c) 'print)
(y z a b c)

(((dq 'insert-front!) 'x) 'print)
(x y z a b c)

((dq 'delete-front!) 'print)
(y z a b c)

((dq 'delete-rear!) 'print)
(y z a b)

((dq 'delete-front!) 'print)
(z a b)

((dq 'delete-front!) 'print)
(a b)

((dq 'delete-rear!) 'print)
(a)

((dq 'delete-rear!) 'print)
()