iterator.lisp

   1 (in-package :trees)
   2
   3 (defun extreme-node-with-path (root direction &optional path)
   4   (do ((node root (funcall direction node))
   5        (parent nil node))
   6       ((null node) (values parent path))
   7     (push node path)))
   8
   9 (defun make-iterator (tree &key
  10                        forwardp
  11                        (current nil currentp)
  12                        (stack nil stackp))
  13   (declare (type binary-tree tree))
  14   (let ((modcount (modcount tree)))
  15     (multiple-value-bind (extremum examine)
  16                   (if forwardp
  17                       (values #'left #'right)
  18                       (values #'right #'left))
  19       (multiple-value-bind (current stack)
  20           (if (and currentp stackp)
  21               (values current stack)
  22               (extreme-node-with-path (root tree) extremum))
  23         #'(lambda ()
  24             (cond
  25               ((/= modcount (modcount tree))
  26                (error "~A modified during iteration" tree))
  27               ((null current)
  28                (values nil nil))
  29               (t
  30                (let* ((next current)
  31                       (top (pop stack))
  32                       (node (funcall examine top)))
  33                  (cond
  34                    ((null node)
  35                     (setf current (first stack)))
  36                    (t
  37                     (setf (values current stack)
  38                           (extreme-node-with-path node extremum stack))))
  39                  (values next t)))))))))