iterator.lisp

   1 (in-package :trees)
   2
   3 (defun extreme-node-with-path (root leftp &optional path)
   4   (do ((node root (if leftp (left node) (right 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 (current stack)
  16         (if (and currentp stackp)
  17             (values current stack)
  18             (extreme-node-with-path (root tree) forwardp))
  19       (lambda ()
  20         (cond
  21           ((/= modcount (modcount tree))
  22            (error "~A modified during iteration" tree))
  23           ((null current)
  24            (values nil nil))
  25           (t
  26            (let* ((next current)
  27                   (top (pop stack))
  28                   (node (if forwardp (right top) (left top))))
  29              (cond
  30                ((null node)
  31                 (setf current (first stack)))
  32                (t
  33                 (setf (values current stack)
  34                       (extreme-node-with-path node forwardp stack))))
  35              (values next t))))))))