#lang racket
(require compatibility/mlist)
;; queue methods
(define (front-ptr q) (mcar q))
(define (rear-ptr q) (mcdr q))
(define (set-front-ptr! q v) (set-mcar! q v))
(define (set-rear-ptr! q v) (set-mcdr! q v))
(define (empty-queue? q) (null? (front-ptr q)))
(define (make-queue) (mcons '() '()))
(define (front-queue q)
  (if (empty-queue? q)
    (error "FRONT called on empty queue" q)
    (mcar (front-ptr q))))
(define (insert-queue! q item)
  (let ((new-item (mlist item)))
    (cond ((empty-queue? q)
           (set-front-ptr! q new-item)
           (set-rear-ptr! q new-item)
           q)
          (else
            (set-mcdr! (rear-ptr q) new-item)
            (set-rear-ptr! q new-item)
            q))))
(define (delete-queue! q)
  (cond ((empty-queue? q)
         (error "DELETE! called with an empty queue" q))
        (else
          (set-front-ptr! q (mcdr (front-ptr q)))
          q)))
;; 21
(define (print-queue q)
  (front-ptr q))
(define q1 (make-queue))
(print-queue (insert-queue! q1 'a))
(print-queue (insert-queue! q1 'b))
(print-queue (delete-queue! q1))
(print-queue (delete-queue! q1))
;; 22
(define (make-queue-obj)
  (let ((front-ptr '())
        (rear-ptr '()))
    (define (set-front-ptr! v)
      (set! front-ptr v))
    (define (set-rear-ptr! v)
      (set! rear-ptr v))
    (define (empty-queue?)
      (null? front-ptr))
    (define (front-queue)
      (mcar front-ptr))
    (define (insert-queue! item)
      (let ((new-pair (mlist item)))
        (cond ((empty-queue?)
               (set-front-ptr! new-pair)
               (set-rear-ptr! new-pair))
              (else (set-mcdr! rear-ptr new-pair)
                    (set-rear-ptr! new-pair)))))
    (define (delete-queue!)
      (cond ((empty-queue?)
             (error "DELETE! called with an empty queue" front-ptr))
            (else
              (set-front-ptr! (mcdr front-ptr)))))
    (define (dispatch m)
      (cond ((eq? m 'front-ptr) front-ptr)
            ((eq? m 'rear-ptr) rear-ptr)
            ((eq? m 'set-front-ptr!) set-front-ptr!)
            ((eq? m 'set-rear-ptr!) set-rear-ptr!)
            ((eq? m 'empty-queue?) empty-queue?)
            ((eq? m 'front-queue) front-queue)
            ((eq? m 'insert-queue!) insert-queue!)
            ((eq? m 'delete-queue!) delete-queue!)
            ((eq? m 'print-queue) front-ptr)
            (else (error "Message note defined on queue" m))))
    dispatch))
(define qobj (make-queue-obj))
((qobj 'insert-queue!) 'a)
(qobj 'print-queue)
((qobj 'insert-queue!) 'b)
(qobj 'print-queue)
((qobj 'insert-queue!) 'c)
(qobj 'print-queue)
((qobj 'delete-queue!))
(qobj 'print-queue)
;; 23
(define (make-deque) (mcons '() '()))
;; internal
(define (front-ptr-deque q) (mcar q))
(define (rear-ptr-deque q) (mcdr q))
(define (empty-deque? q) (and (null? (front-ptr-deque q)) (null? (rear-ptr-deque q))))
;; selectors
(define (front-deque q) (mcar (mcar (front-ptr-deque q))))
(define (rear-deque q) (mcar (mcar (rear-ptr-deque q))))
;; mutators
(define (front-insert-deque! q data)
  (let ((item (mlist (mlist data))))
    (cond ((empty-deque? q) (set-mcar! q item) (set-mcdr! q item) q)
          (else (set-mcdr! (mcar (front-ptr-deque q)) item)
                (set-mcdr! item (front-ptr-deque q))
                (set-mcar! q item)
                q))))
(define (rear-insert-deque! q data)
  (let ((item (mlist (mlist data))))
    (cond ((empty-deque? q) (set-mcar! q item) (set-mcdr! q item) q)
          (else (set-mcdr! (mcar item) (rear-ptr-deque q))
                (set-mcdr! (rear-ptr-deque q) item)
                (set-mcdr! q item)
                q))))
(define (rear-delete-deque! q)
    (cond ((empty-deque? q) (error "DELETE-REAR deque, tried calling delete on empty deque."))
          (else (let ((prev-ptr (mcdr (mcar (rear-ptr-deque q))))
                      (item (mcar (mcar (rear-ptr-deque q)))))
                  (set-mcdr! q prev-ptr)
                  (if (null? prev-ptr)
                    (set-mcar! q prev-ptr)
                    (set-mcdr! (rear-ptr-deque q) '()))
                  item))))
(define (front-delete-deque! q)
    (cond ((empty-deque? q) (error "DELETE-FRONT deque, tried calling delete on empty deque."))
          (else (let ((next-ptr (mcdr (front-ptr-deque q)))
                      (item (mcar (mcar (front-ptr-deque q)))))
                  (set-mcar! q next-ptr)
                  (if (null? next-ptr)
                    (set-mcdr! q next-ptr)
                    (set-mcdr! (mcar (front-ptr-deque q)) '()))
                  item))))
(define (print-deque q)
  (define (rec fn items)
    (cond ((null? items) '())
          (else (cons (fn (mcar items)) (rec fn (mcdr items))))))
  (display (rec (lambda (item)
                  (mcar item))
                (front-ptr-deque q))))
(define dq1 (make-deque))
(rear-insert-deque! dq1 'a)
(rear-insert-deque! dq1 'b)
(rear-insert-deque! dq1 'c)
(print-deque dq1)
(rear-delete-deque! dq1)
(front-delete-deque! dq1)
(rear-delete-deque! dq1)
(print-deque dq1)