(in-package :trees)

(defun extreme-node-with-path (root leftp &optional path)
  (do ((node root (if leftp (left node) (right node)))
       (parent nil node))
      ((null node) (values parent path))
    (push node path)))

(defun make-iterator (tree &key
                       forwardp
                       (current nil currentp)
                       (stack nil stackp))
  (declare (type binary-tree tree))
  (let ((modcount (modcount tree)))
    (multiple-value-bind (current stack)
        (if (and currentp stackp)
            (values current stack)
            (extreme-node-with-path (root tree) forwardp))
      (lambda ()
        (cond
          ((/= modcount (modcount tree))
           (error "~A modified during iteration" tree))
          ((null current)
           (values nil nil))
          (t
           (let* ((next current)
                  (top (pop stack))
                  (node (if forwardp (right top) (left top))))
             (cond
               ((null node)
                (setf current (first stack)))
               (t
                (setf (values current stack)
                      (extreme-node-with-path node forwardp stack))))
             (values next t))))))))