;; -*- Mode: Irken -*-

(include "lib/basis.scm")

(datatype btree
  (:node (btree 'a) (btree 'a))
  (:leaf 'a))

(defmacro btree/make
  (btree/make (l r)) -> (btree:node (btree/make l) (btree/make r))
  (btree/make x)     -> (btree:leaf x))

(define t0 (btree/make ((0 ((1 (2 (3 4))) 5)) (((6 7) ((8 (9 10)) 11)) ((12 (((13 14) 15) (16 17))) (18 19))))))
(define t1 (btree/make (((0 ((1 2) 3)) (((4 5) (((6 7) 8) (9 10))) ((11 ((12 13) 14)) ((15 (16 17)) 18)))) 19)))
(define t2 (btree/make (((0 ((1 2) 3)) (((4 5) (((6 7) 8) (9 10))) ((88 ((12 13) 14)) ((15 (16 17)) 18)))) 19)))

(define btree/inorder
  p (btree:leaf x)   -> (p x)
  p (btree:node l r) -> (begin (btree/inorder p l) (btree/inorder p r)))

(define (btree/make-generator t)
  (make-generator
   (lambda (consumer)
     (btree/inorder consumer t)
     (let loop ()
       (consumer -1)
       (loop)))))

(define (same-fringe t0 t1)
  (let ((g0 (btree/make-generator t0))
	(g1 (btree/make-generator t1)))
    (let loop ((v0 (g0))
	       (v1 (g1)))
      (cond ((and (= v0 -1) (= v1 -1)) ;; end of the tree
	     (print-string "equal\n"))
	    ((not (= v0 v1))
	     (print-string "NOT equal\n"))
	    (else
	     (loop (g0) (g1)))))))

(same-fringe t0 t1)
(same-fringe t0 t2)