#lang plait

(define-type (Treeof 'a) 
  (leaf [val : 'a])
  (node [val : 'a]
        [left : (Treeof 'a)]
        [right : (Treeof 'a)]))

(define (contains? [t : (Treeof 'a)] [n : 'a]) : Boolean
  (type-case (Treeof 'a) t
    [(leaf v) (equal? v n)]
    [(node v l r)
     (or (equal? v n)
         (contains? l n)
         (contains? r n))]))

(print-only-errors #t)
(test (contains? (leaf 10) 10) #t)
(test (contains? (leaf 10) 11) #f)
(test (contains? (node 5 (leaf 6) (leaf 7)) 6) #t)
(test (contains? (node 5 (leaf 6) (leaf 7)) 16) #f)
(test (contains? (node "5" (leaf "6") (leaf "7")) "16") #f)

;; Determines whether every value in `t' is
;; greater than `n' and sorted, returning the
;; maximum value in `t'.
;; This implementation checks for an in-order
;; sort, but in a way that could be easily
;; adapted to a pre-order sort.
(define (sorted-with [t : (Treeof 'a)]
                     [n : 'a]
                     [comparator : ('a 'a -> Boolean)]) : (Optionof 'a)
  (type-case (Treeof 'a) t
    [(leaf v) (if (comparator v n) 
                  (some v)
                  (none))]
    [(node v l r)
     (local [(define n2 (sorted-with l n comparator))]
       (type-case (Optionof 'a) n2
         [(none) (none)]
         [(some n2) ; l is sorted
          (if (comparator v n2) ; v is as big as max of `l'
              (sorted-with r v comparator)
              (none))]))]))

(test (sorted-with (leaf 10) 0 >=) (some 10))
(test (sorted-with (leaf 10) 10 >=) (some 10))
(test (sorted-with (leaf 10) 11 >=) (none)) 
(test (sorted-with (node 11 (leaf 10) (leaf 12)) 0 >=) (some 12))
(test (sorted-with (node 10 (leaf 11) (leaf 12)) 0 >=) (none))
(test (sorted-with (node 11 (leaf 10) (leaf 9)) 0 >=) (none))
(test (sorted-with (node 11 (leaf 10) (leaf 12)) 14 >=) (none))

(define-type-alias (T 'a) (Treeof 'a))

(define (sorted? [t : (T 'a)]
                 [comparator : ('a 'a -> Boolean)]
                 [beginning : 'a]) : Boolean
  (type-case (Optionof 'a) (sorted-with t beginning comparator)
    [(none) #f]
    [(some n) #t]))

(test (sorted? (leaf 0) >= -inf.0) #t)
(test (sorted? (leaf -1) >= -inf.0) #t)
(test (sorted? (node 0 (leaf -2) (leaf 2)) >= -inf.0) #t)
(test (sorted? (node 0 (leaf 1) (leaf 2)) >= -inf.0) #f)
(test (sorted? (node 0 (leaf -2) (leaf -1)) >= -inf.0) #f)

(test (sorted? (node "apple" (leaf "aardvark") (leaf "bug")) (lambda (x y) #t) "") #t)