exercise 3.23

やっと解けた・・・。もっと精進せねば。

(define (front-ptr queue) (car queue))
(define (rear-ptr queue) (cdr queue))
(define (set-front-ptr! queue item) (set-car! queue item))
(define (set-rear-ptr! queue item) (set-cdr! queue item))

(define (empty-queue? queue) (or (null? (front-ptr queue))
                                 (null? (rear-ptr queue))))

(define (make-queue) (cons '() '()))

(define (make-item x)
  (cons x (cons '() '())))
(define (previous-item item)
  (car (cdr item)))
(define (next-item item)
  (cdr (cdr item)))
(define (ptrs item)
  (cdr item))
(define (content item)
  (car item))

(define (front-queue queue)
  (if (empty-queue? queue)
      (error "FRONT called with an empty queue" queue)
      (content (front-ptr queue))))

(define (rear-queue queue)
  (if (empty-queue? queue)
      (error "FRONT called with an empty queue" queue)
      (content (rear-ptr queue))))

(define (rear-insert-queue! queue item)
  (let ((new-item (make-item item)))
    (cond ((empty-queue? queue)
           (set-front-ptr! queue new-item)
           (set-rear-ptr! queue new-item)
           (print-queue queue))
          (else
           (set-cdr! (ptrs (rear-ptr queue)) new-item)
           (set-car! (ptrs new-item) (rear-ptr queue))
           (set-rear-ptr! queue new-item)
           (print-queue queue)))))

(define (front-insert-queue! queue item)
  (let ((new-item (make-item item)))
    (cond ((empty-queue? queue)
           (set-front-ptr! queue new-item)
           (set-rear-ptr! queue new-item)
           (print-queue queue))
          (else
           (set-car! (ptrs (front-ptr queue)) new-item)
           (set-cdr! (ptrs new-item) (front-ptr queue))
           (set-front-ptr! queue new-item)
           (print-queue queue)))))


(define (front-delete-queue! queue)
  (cond ((empty-queue? queue)
         (error "DELETE! called with an empty queue" queue))
        ((eq? (front-ptr queue) (rear-ptr queue))
         (set-front-ptr! queue '())
         (set-rear-ptr! queue '())
         (print-queue queue))
        (else
         (set-front-ptr! queue (next-item (front-ptr queue)))
         (set-car! (ptrs (front-ptr queue)) '())
         (print-queue queue))))

(define (rear-delete-queue! queue)
  (cond ((empty-queue? queue)
         (error "DELETE! called with an empty queue" queue))
        ((eq? (front-ptr queue) (rear-ptr queue))
         (set-front-ptr! queue '())
         (set-rear-ptr! queue '())
         (print-queue queue))
        (else
         (set-rear-ptr! queue (previous-item (rear-ptr queue)))
         (set-cdr! (ptrs (rear-ptr queue)) '())
         (print-queue queue))))

(define (print-queue queue)
  (let ((rear (rear-ptr queue)))
    (define (iter items)
      (cond ((eq? items '()) '())
            ((eq? items rear) (cons (content items) '()))
            ((null? (next-item queue)) (content items))
            (else (cons (content items)
                        (iter (next-item items))))))
    (if (empty-queue? queue)
        '()
     (iter (front-ptr queue)))))

とりあえずO(1)を達成するにはどっちの方向にも進めるリストが欲しいので（何て表現するんだろう・・・）適当に作成

・・・見直してみると、一応セレクターとかコンストラクターはつくるようになったが、itemのポインタの変更とかはまだまだ冗長・・・。
適当にset-next-item!だの作ればよかったかなぁ<追記＞
あと、print-queueの使い方が何か変・・・
名前と一致してない使い方な気がする。というかリストに整形してるだけだしprintではないよなぁ