#lang scheme

;;
;; This is a running dialogue to get the same-fringe? function working.
;; I take slight detours to get a better idea of the problem and a solution.
;;


;;
;; A tree is either a:
;;
;;     number, or a
;;     (list tree tree)


;; tree?: any -> boolean
;; Returns true if we're looking at a tree.
(define (tree? datum)
  (or (number? datum)
      (and (list? datum)
           (= (length datum) 2)
           (tree? (first datum))
           (tree? (second datum)))))


;; left: tree -> tree
(define (left a-tree)
  (first a-tree))


;; right: tree -> tree
(define (right a-tree)
  (second a-tree))


;; I have no idea how to do this yet.  An idea is to do a coroutine-linkage between a consumer and
;; a producer.


;; consumer: X producer -> ???
;; producer: consumer -> ???

;; We set aside 'exhaused as a special value that means the producer's out of gas.


;; As a simple example of a producer/consumer calling each other, let's try to make
;; a consumer that displays items, and a producer of constant values.


;; display-consumer: consumer
;; Consumes elements from the producer and displays them on screen.
(define (display-consumer n producer)
  (display n)
  (read-line) ;; wait for input
  (when (not (eq? n 'exhausted))
    (producer display-consumer)))


;; constant-producer: X -> (producer-of X)
;; Produces a-constant, over and over again.
(define ((constant-producer a-constant) a-consumer)
  (a-consumer a-constant (constant-producer a-constant)))


;; exercise-display-consumer: producer -> ???
;; Runs the display consumer over the producer
(define (exercise-display-consumer a-producer)
  (a-producer display-consumer))



;; As another example of a producer:


;; numbers: number -> producer
;; This producer will pass in increasing numbers to a consumer.
(define ((numbers n) a-consumer)
  (a-consumer n (numbers (add1 n))))


;; list-producer: list -> producer
;; Here is one that will produce until it's exhausted.
(define ((list-producer a-list) a-consumer)
  (cond [(empty? a-list)
         (a-consumer 'exhausted (constant-producer 'exhausted))]
        [else
         (a-consumer (first a-list)
                     (list-producer (rest a-list)))]))



;; Now we want a consumer that talks to two producers in lockstep.
;;
;; comparison-consumer: producer producer -> bool
;; Returns true if the producer-1 and producer-2 produce the same elements in
;; the same order till exhaustion.
(define (comparison-consumer producer-1 producer-2)
  (producer-1 (lambda (v1 producer-1-rest)
                (producer-2 (lambda (v2 producer-2-rest)
                              (cond
                                [(and (eq? v1 'exhausted) (eq? v2 'exhausted))
                                 #t]
                                [(eq? v1 'exhausted)
                                 #f]
                                [(eq? v2 'exhausted)
                                 #f]
                                [(equal? v1 v2)
                                 (comparison-consumer producer-1-rest producer-2-rest)]
                                [else
                                 #f]))))))

;; (comparison-consumer (list-producer '(1 2 3)) (list-producer '(1 2 3))) ==> #t
;; (comparison-consumer (list-producer '(1 2 3)) (list-producer '(1 2 4))) ==> #f



;; serial-producer: producer producer -> producer
;; I'd also like a way to join two producers in serial.
(define ((serial-producer producer-1 producer-2) a-consumer)
  (producer-1 (lambda (v producer-1-rest)
                (cond
                  [(eq? v 'exhausted)
                   (producer-2 a-consumer)]
                  [else
                   (a-consumer v (serial-producer producer-1-rest producer-2))]))))
  


;; Now with that out of the way, let's create a producer for an in-order traveral
(define ((tree-producer a-tree) a-consumer)
  (cond
    [(number? a-tree)
     (a-consumer a-tree (constant-producer 'exhausted))]
    [else
     ((serial-producer (tree-producer (left a-tree)) (tree-producer (right a-tree)))
      a-consumer)]))


;; With this, we can finally define same-fringe?:
;; same-fringe: tree tree -> boolean
;; Returns true if the two trees have the same fringe leaves.
(define (same-fringe? tree-1 tree-2)
  (comparison-consumer (tree-producer tree-1)
                       (tree-producer tree-2)))

;; Test
(and
 (same-fringe? '((1 2) (3 4)) '(1 (2 (3 4))))
 (not (same-fringe? '((1 2) (2 3)) '((1 2) 3))))