C.I.CLを眺める(5) CIRCULAR-LENGTH — #:g1

Posted 2011-01-19 11:30:00 GMT

今回は、C.I.CLのlist.lispから CIRCULAR-LENGTH です。
名前のとおり循環リストの長さ(というか要素数)を数えるものです.
定義は、

(defun circular-length (list)
  "LIST must be either a proper-list or a circular-list, not a dotted-list.
RETURN: the total length ; the length of the stem ; the length of the circle.
"
  (let ((indexes (make-hash-table)))
    (loop
       :for i :from 0
       :for current :on list
       :do (let ((index (gethash current indexes)))
             (if index
                 ;; found loop
                 (return (values i index (- i index)))
                 (setf (gethash current indexes) i)))
       :finally (return (values i)))))
となっていて、コンスセルを先頭から一つずつ位置と一緒に記録しておいて、同じものが現われたら結果を返す、というようになっています。
結果は多値で返して、1値目は、全体の長さ、2値目は、循環が始まるところまでの長さ、3値目は、循環しているリストの長さです。
動作は、
(import 'com.informatimago.common-lisp.list:circular-length)

(circular-length '(1 2 3 4)) ;=> 4

(circular-length '#0=(1 2 3 . #0#)) ;=> 3 ; 0 ; 3

(circular-length '(1 . #0=(2 3 . #0#))) ;=> 3 ; 1 ; 2

というところ

comments powered by Disqus