initial commit
[trees.git] / 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)))))))))