(load "~wolfe/www-docs/287/code/mitmacros.scm")
; (load "~wolfe/www-docs/287/code/drscheme-eopl.ss")

(define-record node (val left right))
(define-record leaf (sym))

(define path-sum ;; GOOD VERSION using continuations
  (lambda (tree key succeed fail)
    ;; Applies succeed to sum of leftmost path in tree down to key,
    ;;   or, if key not in tree, applies fail to no args.
    (variant-case tree
      (leaf (sym) (if (eq? sym key)
                      (succeed 0)
                      (fail)))
      (node
       (val left right)
       (path-sum left key
                 (lambda (left-sum)
                   (succeed (+ val left-sum)))
                 (lambda ()
                   (path-sum right key
                             (lambda (right-sum)
                               (succeed (+ val right-sum)))
                             fail))))
      (else (error "unexpected tree type" tree)))))
;-------------------------------------------------------------
(define bad-path-sum ;; NOT AS GOOD does not use continuations
  (lambda (tree key)
    (variant-case tree
      (leaf (sym) (if (eq? sym key)
                      0
                      'failed))
      (node
       (val left right)
       (let ((left-result (bad-path-sum left key)))
         (if (not (eq? left-result 'failed))
             (+ val left-result)
             (let ((right-result (bad-path-sum right key)))
               (if (eq? right-result 'failed)
                   'failed
                   (+ val right-result))))))
      (else (error "unexpected tree type" tree)))))
;-------------------------------------------------------------
(define worse-path-sum ;; Worst of both worlds
  (lambda (tree key succeed fail)
    (variant-case tree
      (leaf (sym) (if (eq? sym key)
                      (succeed 0)
                      (fail)))
      (node
       (val left right)
       (let ((left-result (worse-path-sum left key
                                          (lambda (left-sum)
                                            left-sum)
                                          (lambda ()
                                            'failed))))
         (if (not (eq? left-result 'failed))
             (succeed (+ val left-result))
             (let ((right-result (worse-path-sum right key
                                                 (lambda (right-sum)
                                                   right-sum)
                                                 (lambda ()
                                                   'failed))))
               (if (eq? right-result 'failed)
                   (fail)
                   (succeed (+ val right-result)))))))
      (else (error "unexpected tree type" tree)))))
;----------------------------------------------------------------

(path-sum sample-tree 'q
          (lambda (sum)
            (display "Found with path sum ")
            (display sum))
          (lambda ()
            (display "Didn't find")))

(define path-sum-plus
  (lambda (tree key acc succeed fail)
    ;; Applies succeed to sum of leftmost path in tree down to key plus acc,
    ;;   or, if key not in tree, applies fail to no args.
    (variant-case tree
      (leaf (sym) (if (eq? sym key)
                      (succeed acc)
                      (fail)))
      (node
       (val left right)
       (path-sum-plus left key (+ val acc)
                      succeed
                      (lambda ()
                        (path-sum-plus right key (+ val acc)
                                       succeed
                                       fail))))
      (else (error "unexpected tree type" tree)))))