SICP 読み (106) 3.3.2 キューの表現

とりあえず、例示されている make-queue 関連のソレ達を試験。
先に試験から作る。試験するインターフェースとしては

• make-queue
• empty-queue?
• front-queue
• insert-queue!
• delete-queue!
• front-ptr
• rear-ptr
• set-front-ptr!
• set-rear-ptr!

で良いのかな??

で、無理矢理でっち上げた試験を以下に。なんと言えば良いか微妙だ。

#!/usr/bin/env gosh

(use test.unit)
(require "3.3.2")

(define-test-suite "3.3.2"

 ("make-queue test"
  ("(make-queue) returns '(())"
   (assert-equal '(()) (make-queue))
   )

  ("(front-ptr (make-queue)) returns '()"
   (let ((q (make-queue)))
     (assert-equal '() (front-ptr q)))
   )

  ("(rear-ptr (make-queue)) returns '()"
   (let ((q (make-queue)))
     (assert-equal '() (rear-ptr q)))
   )

  ("empty-queue? returns true"
   (let ((q (make-queue)))
     (assert-true (empty-queue? q)))
   )

  ("front-queue error"
   (let ((q (make-queue)))
     (assert-error (lambda () (front-queue q))))
   )
  )

 ("front-ptr test"
  ("return (car queue)"
   (assert-equal 'car (front-ptr (cons 'car 'cdr)))
   )
  )

 ("rear-ptr test"
  ("return (cdr queue)"
   (assert-equal 'cdr (rear-ptr (cons 'car 'cdr)))
   )
  )

 ("set-front-ptr! test"
  ("set-car!"
   (let ((q (cons 'car 'cdr)))
     (set-front-ptr! q 'change)
     (assert-equal 'change (front-ptr q)))
   )
  )

 ("set-rear-ptr! test"
  ("set-cdr!"
   (let ((q (cons 'car 'cdr)))
     (set-rear-ptr! q 'change)
     (assert-equal 'change (rear-ptr q)))
   )
  )

 ("empty-queue? test"
  ("empty"
   (assert-true (empty-queue? '(())))
   )

  ("not empty"
   (assert-false (empty-queue? (cons 'a '())))
   )
  )

 ("front-queue test"
  ("empty queue"
   (assert-error (lambda () (front-queue '(()))))
   )

  ("normal"
   (let ((q (cons (cons 1 '()) '())))
     (assert-equal 1 (front-queue q)))
   )
  )

 ("insert-queue! test"
  ("insert"
   (let ((q (make-queue)))
     (insert-queue! q 1)
     (insert-queue! q 2)
     (insert-queue! q 3)
     (assert-equal 1 (front-queue q))
     (assert-equal 2 (car (cdr (front-ptr q))))
     (assert-equal 3 (car (cdr (cdr (front-ptr q)))))
     (assert-equal 3 (car (rear-ptr q)))
     (insert-queue! q 4)
     (assert-equal 4 (car (rear-ptr q)))
     )
   )
  )

 ("delete-queue! test"
  ("delete"
   (let ((q (make-queue)))
     (insert-queue! q 1)
     (insert-queue! q 2)
     (assert-equal 1 (front-queue q))
     (delete-queue! q)
     (assert-equal 2 (front-queue q))
     (insert-queue! q 3)
     (assert-equal 2 (front-queue q))
     (delete-queue! q)
     (assert-equal 3 (front-queue q))
     (delete-queue! q)
     (assert-true (empty-queue? q)))
   )
  )
 )

実装は略します。

問題 3.21

これは front-ptr を戻せば良い、という話ではないのかなぁ。

gosh> (define q (make-queue))
q
gosh> q
(())
gosh> (front-ptr q)
()
gosh> (insert-queue! q 1)
(#0=(1) . #0#)
gosh> (front-ptr q)
(1)
gosh> (insert-queue! q 2)
((1 . #0=(2)) . #0#)
gosh> (front-ptr q)
(1 2)
gosh> (insert-queue! q 'a)
((1 2 . #0=(a)) . #0#)
gosh> (front-ptr q)
(1 2 a)
gosh> 

上記を元に以下の試験を追加。

 ("3.21"
  ("print-queue test"
   (let ((q (make-queue)))
     (insert-queue! q 1)
     (assert-equal '(1) (print-queue q))
     (insert-queue! q 2)
     (assert-equal '(1 2) (print-queue q))
     (insert-queue! q 'a)
     (assert-equal '(1 2 a) (print-queue q)))
   )
  )

print-queue は以下の定義

(define (print-queue q) (front-ptr q))

一応パスはしてるんですが、なんとなく微妙なカンジ。

3.22 とか 3.23 とかさくっと出来そうなんですが、へろへろなのでこれで止め。