;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname review) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ())))
;; Good luck everybody!! Remember, use the design recipe!
;; Deep breaths! Bring a snack/water! You're almost there!

;; You probably don't have to do this on the test for
;; complex functions, especially if it helps you follow
;; a template, but I convered the boolean functions
;; to use only and, or, and not. If a boolean function 
;; is simple you should definitely write it with and or
;; and not.

;; Problem 1
(define-struct node (left right))

;; A [BT X] is one of:
;; - an X
;; - (make-node [BT X] [BT X])
(define bt1 (make-node (make-node "Olin" "Shivers")
                       (make-node "David"
                                  (make-node "Van" "Horn"))))

;; fold-tree : [Y Y -> Y] [X -> Y] [BT X] -> Y
;; Fold all of the elements of the tree together with node-op
;; and map them with value-op
(define (fold-tree node-op leaf-op abt)
  (cond [(node? abt) (node-op (fold-tree node-op leaf-op (node-left abt))
                              (fold-tree node-op leaf-op(node-right abt)))]
        [else (leaf-op abt)]))

(check-expect (fold-tree + string-length "Hello") 5)
(check-expect (fold-tree + string-length bt1) 23)

;; [BT X] -> ?
#;(define (bt-temp bt)
    (cond [(node? bt) (bt-temp (node-left bt))
                      (bt-temp (node-right bt))]
          [else ...]))

;; height : [BT X] -> Natural
;; Calculates the height of the binary tree
;; fold-tree : [Number Number -> Number] [X -> Number] [BT X] -> Number
(define (height bt)
  (fold-tree (λ (left-height right-height)
               (add1 (max left-height right-height)))
             (λ (x) 0)
             bt))

(check-expect (height "Hello") 0)
(check-expect (height bt1) 3)




;; a Monthly-Report is a
;; (make-monthly-report string number number number)
;; where month is the current month
;; year is the current year
;; expenditures is the total expenditures for the month
;; revenues is the total revenues
(define-struct monthly-report
  (month year expenditures revenues))

;; A [Listof Monthly-Report] is one of
;; -- empty
;; -- (cons Monthly-Report [Listof Monthly-Report])

;; Profit = Revenue – Expenditures

;; total-profits: Number [Listof Monthly-Report]-> Number
;; consumes a list of monthly budget reports and a year and
;; computes the total profits for that year
(define (total-profits year lomr)
  (local (;; profit : Monthly-Report -> Number
          ;; calculates profit
          (define (profit mr)
            (- (monthly-report-revenues mr)
               (monthly-report-expenditures mr))))
    ;; foldl : [X Y -> Y] Y [List-of X] -> Y
    ;; foldl : [MR Number -> Number] Number [List-of MR] -> Number
    ;; foldl uses an accumulator
    ;; foldr would be wrong
    (foldl (λ (mr profit-acc)
             (if (= year (monthly-report-year mr))
                 (+ profit-acc (profit mr))
                 profit-acc))
           0 lomr)))


#;(define (total-profits year lomr)
     (local (;; profit : Monthly-Report -> Number
          ;; calculates profit
          (define (profit mr)
            (- (monthly-report-revenues mr)
                          (monthly-report-expenditures mr)))
          ;; helper : Number  [Listof Monthly-Report] -> Number
          ;; accumulates the profits of monthly reports
          ;; that match the year
          (define (helper profit-acc lomr)
            (cond [(empty? lomr) profit-acc]
                  [(cons? lomr) 
                   (if (= year (monthly-report-year (first lomr)))
                       (helper 
                        (+ profit-acc (profit (first lomr)))
                        (rest lomr))
                       (helper profit-acc (rest lomr)))])))
    (helper 0 lomr)))

(define sample-lomr (list
                     (make-monthly-report
                      "May"
                      2014
                      10
                      20)
                     (make-monthly-report 
                      "June"
                      2014
                      25
                      50)
                     (make-monthly-report 
                      "June"
                      2013
                      25
                      50)))
(check-expect (total-profits 2014 sample-lomr)
              35)
(check-expect (total-profits 2013 sample-lomr)
              25)
(check-expect (total-profits -2 sample-lomr)
              0)



(define target 2)
;; guess-number : Integer Integer -> Integer
;; Finds target between lo and hi effeciently
;; lo < hi
(define (guess-number lo hi)
  (local ((define middle (quotient (+ lo hi) 2)))
    (cond [(= middle target) target]
          ;; lo------target---------middle---------------hi
          ;;                     ^highest it could be
          [(> middle target) (guess-number lo (sub1 middle))]
          ;; lo------------------middle-------target----hi
          ;;                         ^lowest it could be
          [(< middle target) (guess-number (add1 middle) hi)])))
(check-expect (guess-number -10000 10000) 2)
;; do not have to do on test,
;; good idea for when you have a computer
(check-expect (build-list 
               100000
               (λ (n)
                 (local ((define target2 n)
                         (define (guess-number lo hi)
                           (local ((define middle (quotient (+ lo hi) 2)))
                             (cond [(= middle target2) target2]
                                   ;; lo------target---------middle---------------hi
                                   ;;                     ^highest it could be
                                   [(> middle target2) (guess-number lo (sub1 middle))]
                                   ;; lo------------------middle-------target----hi
                                   ;;                         ^lowest it could be
                                   [(< middle target2) (guess-number (add1 middle) hi)]))))
                   (guess-number 0 100000))))
              (build-list 100000 identity))

;; 2list-temp : [List X] [List Y] -> ??
(define (2list-temp a b)
  (cond [(and (empty? a) (empty? b))...]
        [(and (cons? a) (empty? b)) (... (first a) ... (rest a)...)]
        [(and (empty? a) (cons? b)) (... (first b) ... (rest b)...)]
        [(and (cons? a) (cons? b))
         (... (first a) ... (first b) ...
              (2list-temp (rest a) (rest b)))]))

;; lex< : [List Number] [List Number] -> Boolean
;; Is a lexographically less than b?
#;(define (lex< a b)
    (cond [(and (empty? a) (empty? b)) false]
          [(and (cons? a) (empty? b)) false]
          [(and (empty? a) (cons? b)) true]
          [(and (cons? a) (cons? b))
           (or (proper-prefix a b)
               (match-until-greater a b))]))
(define (lex< a b)
  (or (and (empty? a) (cons? b))
      (and (cons? a) (cons? b)
           (or (proper-prefix a b)
               (match-until-greater a b)))))
;; proper-prefix : [List Number] [List Number] -> Boolean
;; Is a a proper prefix of b?
#;(define (proper-prefix a b)
    (cond [(and (empty? a) (empty? b)) false]
          [(and (cons? a) (empty? b)) false] ;; '(1 2 3) is not prefix of empty
          [(and (empty? a) (cons? b)) true] ;; the opposite is
          [(and (cons? a) (cons? b))
           (and (= (first a)  (first b))
                (proper-prefix (rest a) (rest b)))]))
(define (proper-prefix a b)
  (or (and (empty? a) (cons? b))
      (and (cons? a) (cons? b)
           (and (= (first a)  (first b))
                (proper-prefix (rest a) (rest b))))))
;; match-until-greater : [List Number] [List Number] -> Boolean
;; some element of a is less than the corresponding
;; element of b, and the two lists match
;; identically on the preceding elements
#;(define (match-until-greater a b)
    (cond [(and (empty? a) (empty? b)) false]
          [(and (cons? a) (empty? b)) false]
          [(and (empty? a) (cons? b)) false]
          [(and (cons? a) (cons? b))
           (or (< (first a)  (first b))
               (and (= (first a)  (first b))
                    (match-until-greater (rest a) (rest b))))]))
(define (match-until-greater a b)
  (and (cons? a) (cons? b)
       (or (< (first a)  (first b))
           (and (= (first a)  (first b))
                (match-until-greater (rest a) (rest b))))))
(check-expect (lex< empty empty) false)
(check-expect (lex< '() '(1)) true)
(check-expect (lex< '(1) '()) false)
(check-expect (lex< '(1) '(1)) false)
(check-expect (lex< '(1) '(1 2)) true)
(check-expect (lex< '(1 2 3 4 5 6 7 8 9) '(1 2)) false)
(check-expect (lex< '(1 2 3 4 5 6 7 8 9) '(1 2 4)) true)

;; for kicks:
(define (lex> a b)
  (lex< b a))
(define (lex=< a b)
  (not (lex> a b)))
(define (lex=> a b)
  (not (lex< a b)))
#;(define (lex= a b)
    (and (not (lex< a b)) (not (lex< b a)))) ;; slow :(
(define (lex= a b)
  (or (and (empty? a) (empty? b))
      (and (cons? a) (cons? b) 
           (= (first a) (first b))
           (lex= (rest a) (rest b)))))

(define-struct gnode (left val right))
;;; A GradeTree is one of:
;;; - a Grade
;;; - (make-gnode GradeTree Grade GradeTree)
;;;
;;; A Grade is a number in the range [0,100].

;; tree-ordered? : GradeTree -> Boolean
;; Is this GradeTree ordered?
(define (tree-ordered? gt)
  (local (;; helper : Number Number GradeTree -> Boolean
          ;; Keeps track of what the min and max can be
          ;; at all times, outputs if gt adheres to it
          #;(define (helper min max gt)
              (cond [(number? gt) (< min gt max)]
                    [(gnode? gt) 
                     (and
                      (< min (gnode-val gt) max)
                      (helper min (gnode-val gt) (gnode-left gt))
                      (helper (gnode-val gt) max (gnode-right gt)))]))
          (define (helper min max gt)
            (or (and (number? gt) (< min gt max))
                (and (gnode? gt) 
                     (< min (gnode-val gt) max)
                     (helper min (gnode-val gt) (gnode-left gt))
                     (helper (gnode-val gt) max (gnode-right gt))))))
    (helper -1 101 gt)))
(check-expect (tree-ordered? 0) true)
(define ordered-example (make-gnode 10 50 80))
(check-expect (tree-ordered? ordered-example) true)
(define unordered-example (make-gnode (make-gnode 12 30 51) 50 80))
(check-expect (tree-ordered? unordered-example) false)