;; -*- 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)