(import scheme iterators simple-tests)

(define-iterator (states n)
  ; yields all combinations of #t and #f for n bits
  (if (= n 1)
    (begin (yield '(#f)) (yield '(#t)))
    (iterate (states (- n 1))
      (yield (cons #f it))
      (yield (cons #t it)))))

(define-test (recursive-yields?)
  (equal?
    (let ((result '()))
      (iterate (states 3) (set! result (cons it result)))
      (reverse result))
    '((#f #f #f)
      (#t #f #f)
      (#f #t #f)
      (#t #t #f)
      (#f #f #t)
      (#t #f #t)
      (#f #t #t)
      (#t #t #t)))
    )


(define-iterator (walk-tree tree)
  (cond
    ((pair? tree)
      (yield-all (walk-tree (car tree)))
      (yield-all (walk-tree (cdr tree))))
    ((null? tree) '())
    (else (yield tree))))

(define (same-fringe? t1 t2)
  (let loop ((c1 (coroutine (walk-tree t1)))
             (c2 (coroutine (walk-tree t2))))
    ;(print "XXX " (co-value c1) " " (co-value c2))
    (if (and (co-finished? c1) (co-finished? c2))
        #t
        (if (or (co-finished? c1) (co-finished? c2))
            #f
            (if (eq? (co-value c1) (co-value c2))
                (loop (co-move c1) (co-move c2))
                #f)))))

(define (Same-fringe? t1 t2)
  (let loop ((cs (coroutines (walk-tree t1) (walk-tree t2))))
      ;(print "YYY " (co-values cs))
      (cond
        ((co-all-finished? cs) #t)
        ((co-any-finished? cs) #f)
        ((eq? (co-value (car cs)) (co-value (cadr cs)))
         (loop (co-move-all cs)))
        (else #f))));)

(define-test (tree-walking?)

  (same-fringe? '(a (b (c))) '(a b c))
  (same-fringe? '(a (b (c))) '((a b) c))
  (not (same-fringe? '(x (b (c))) '((a b) c)))
  (not (same-fringe? '(a (b (c))) '(a b)))

  (Same-fringe? '(a (b (c))) '(a b c))
  (Same-fringe? '(a (b (c))) '((a b) c))
  (not (Same-fringe? '(a (x (c))) '((a b) c)))
  (not (Same-fringe? '(a (b (c))) '(a b)))
  )

(define-iterator (repmin tr)
  (cond
    ((pair? tr)
      (let* (
        (co-trs (apply coroutines (map repmin tr)))
        (co-vals (co-values co-trs))
        )
        (co-values
          (co-move-all
            (co-return-all
              (yield (apply min co-vals))
              co-trs)))))
    ((null? tr) '())
    (else (yield tr))))

(define-test (repmin?)
  (equal? (iterate (repmin '(3 ((2)) (3 4) 1)) it)
          '(1 ((1)) (1 1) 1))
  )

(compound-test (ITERATORS)
  (recursive-yields?)
  (tree-walking?)
  (repmin?))