(require 2htdp/image)
(require 2htdp/universe)

;;Exercise 1
; A [Comparator X] is a [X X -> Number] function such that
; - (f a b) < 0 if a < b
; - (f a b) = 0 if a = b
; - (f a b) > 0 if a > b

(define COMPARATOR -)

(define-struct branch [val left right])
; A [Tree X] is one of:
; - "leaf"
; - (make-branch X [Tree X] [Tree X])
; and represents a tree that contains data of type X

(define TREE-0 "leaf")
(define TREE-1 (make-branch 5 TREE-0 TREE-0))
(define TREE-2 (make-branch 7 TREE-1 TREE-0))
(define TREE-3 (make-branch 3 TREE-0 TREE-2))
(define TREE-4 (make-branch 10 TREE-3 TREE-0))
(define TREE-5 (make-branch 2 TREE-0 TREE-4))

;;tree-template: [X] [Tree X] -> ???
#;(define (tree-template t)
    (cond
      [(string? t)...]
      [(branch? t)...(branch-val t)...
                  ...(tree-template (branch-left t))...
                  ...(tree-template (branch-right t))...]))

(define-struct bst [comparator tree])
; A [BST X] is a (make-bst [Comparator X] [Tree X])
; and represents a binary search tree that contains data of type X with no repeats
; For some (make-bst f (make-branch x y z))
; - x is greater than every element in the tree y according to the comparator f
; - x is less than every element in the tree z according to the comparator f
; - y and z are are also ordered according to the comparator
; Note: (make-branch x "leaf" "leaf") is ordered by any comparator

(define BST-0 (make-bst COMPARATOR TREE-0))
(define BST-1 (make-bst COMPARATOR TREE-1))
(define BST-2 (make-bst COMPARATOR TREE-2))
(define BST-3 (make-bst COMPARATOR TREE-3))
(define BST-4 (make-bst COMPARATOR TREE-4))
(define BST-5 (make-bst COMPARATOR TREE-5))

;;Exercise 2
;;in-bst?: [X] X [BST X] -> Boolean
;;is the value X in the given binary search tree?
(check-expect (in-bst? 10 BST-5) #true)
(check-expect (in-bst? 3 BST-1) #false)
(check-expect (in-bst? 5 BST-1) #true)
(check-expect (in-bst? 7 BST-0) #false)

(define (in-bst? x bst)
  (in-tree? (bst-tree bst) (bst-comparator bst) x))

; in-tree? : [X] [Tree X]  [X X -> Number] X -> Boolean
; checks if x is in the tree
(check-expect (in-tree? TREE-0 COMPARATOR 0) #false)
(check-expect (in-tree? TREE-4 COMPARATOR 7) #true)
(check-expect (in-tree? TREE-3 COMPARATOR 2) #false)

(define (in-tree? tree f x)
  (cond
    [(string? tree) #f]
    [else (or (equal? (f (branch-val tree) x) 0)
              (in-tree? (branch-left tree) f x)
              (in-tree? (branch-right tree) f x))]))

;;Exercise 3
;;swap-bst: [X] [BST X] -> [BST X]
;;produces the opposite BST
(check-expect (swap-bst BST-0) (make-bst (swap-comparator (bst-comparator BST-0)) TREE-0))
(check-expect (swap-bst BST-2) (make-bst (swap-comparator (bst-comparator BST-2))
                                         (make-branch 7 TREE-0 TREE-1)))
(check-expect (swap-bst BST-3) (make-bst (swap-comparator (bst-comparator BST-3))
                                         make-branch 3 TREE-2 TREE-0))

(define (swap-bst bst)
  (make-bst (swap-comparator (bst-comparator bst)) (swap-tree (bst-tree bst))))

;;swap-tree: [X] [Tree X] -> [Tree X]
;;swaps the branches of a tree
(check-expect (swap-tree TREE-0) TREE-0)
(check-expect (swap-tree TREE-5) (make-branch 2 TREE-4 TREE-0))

(define (swap-tree tree)
  (cond
    [(string? tree) tree]
    [(branch? tree) (make-branch (branch-val tree)
                                 (branch-right tree)
                                 (branch-left tree))]))

;;swap-comparator: [X] [X X -> Number] -> [X X -> Number]
;;produces the opposite comparator
(check-expect ((swap-comparator -) 4 5) 1)
(check-expect ((swap-comparator -) 10 3) -7)
(check-expect (number? ((swap-comparator -) 3 5)) #true)

(define (swap-comparator c)
  (λ (x y) (c y x)))

;;Exercise 4
;;place-in-bst: [X] [BST X] X -> [BST X]
;;places the value x in the appropriate branch of the tree if it is not already in the tree

#;;(define (place-in-bst bst x)
;  (cond
 ;   [(in-bst? x bst) bst]
  ;  [else (if ()
   ;           ()
    ;          ())


;;Exercise 5
; An Ending is a (make-ending String Boolean)
(define-struct ending [text good?])
; and represents an ending to the story with some text and whether it was a happy ever after

;ending-temp: Ending -> ???
#;(define (ending-temp e)
    (...(ending-text e)...(ending-good? e)...))

; An [NEList-of X] (Non-Empty List) is one of:
; - (cons X '())
; - (cons X [NEList-of X])

;nelist-temp: [X] [NEList-of X] -> ???
#;(define (nelist-temp nel)
    (cond
      [(empty? (rest nel))...]
      [(cons? (rest nel))...(first nel)...
                         ...(nelist-tempp (rest nel))...]))

; A Choice is a a (make-choice String Section)
(define-struct choice [text result])
; and represents the blurb shown to the reader and the resulting section if that is the
; choice they make

;choice-temp: Choice -> ???
#;(define (choice-temp c)
    (...(choice-text c)...(choice-result c)...))

; A Chapter is a (make-chapter String [NEList-of Choice])
(define-struct chapter [text choices])
; and represents a chapter in a choose-your-own adventure book with a body
; and a list of choices at the end

#;(define (chapter-temp ch)
    (...(chapter-text ch)...(nelist-temp (chapter-choices ch))...))

; A Section is one of:
; - Ending
; - Chapter
; and represents a section in a choose your own adventure book

;section-temp: Section -> ???
#;(define (section-temp s)
    (cond
      [(ending? s)...(ending-temp s)...]
      [(chapter? s)...(chapter-temp s)...]))

(define MY-STORY
  (make-chapter
   "You are alone in a room. There is a door before you."
   (list
    (make-choice
     "Stay in the room."
     (make-ending "You stay in the room. Nothing happens. Nothing ever will again." #f))
    (make-choice
     "Open the door."
     (make-chapter
      "You open the door. On the other side lays an eternity of nothingness."
      (list
       (make-choice
        "Scream."
        (make-ending
         "You scream into the void. There is no response. There never will be." #f))
       (make-choice
        "Accept your fate."
        (make-ending
         "You accept the simple beauty of the void. You achieve nirvana." #t))))))))

;;Exercise 6
;;possible-endings: Section -> Natural
;;produces the total number of possible endings to the story
(check-expect (possible-endings MY-STORY) 3)

(define (possible-endings s)
  (cond
    [(ending? s) 1]
    [(chapter? s) (count-endings (chapter-choices ch))]))

;count-endings: [X] [NEList-of Choice] -> Natural

(define (count-endings-loc nel)
    (cond
      [(empty? (rest nel)) (if (choice-ending? (first nel)) 1 0)]
      [(cons? (rest nel)) (if (choice-ending? (first nel))
                              (add1 (count-endings (rest nel)))
                              (count-endings (rest nel)))]))

;;choice-ending?: Choice -> Boolean
;;does the choice result in an ending?

(define (choice-ending? ch)
  (ending? (choice-result ch)))