#lang racket

(require csc151)
(require csc151/binary-trees-from-lists)
(require racket/match)
(require racket/undefined)
(require rackunit)

;; CSC-151-01 (Spring 2021, Term 1)
;; Lab: Tree Recursion (Side B)
;;   https://rebelsky.cs.grinnell.edu/Courses/CSC151/2021SpT1/labs/tree-recursion
;; Authors: YOUR NAMES HERE
;; Date: THE DATE HERE
;; Acknowledgements:
;;   ACKNOWLEDGEMENTS HERE

; +-------------------------------------+----------------------------
; | Provided code: Additional utilities |
; +-------------------------------------+

;;; (vector->tree vec) -> binary-tree?
;;;    vec : vector
;;; Converts a vector into a relatively balanced binary tree.
(define vector->tree
  ; The kernel builds a tree from the elements at positions lb (inclusive)
  ; to ub (exclusive)
  (letrec ([helper (lambda (vec lb ub)
                     (if (<= ub lb)
                         empty-tree
                         (let [(mid (quotient (+ lb ub) 2))]
                           (btn (vector-ref vec mid)
                                (helper vec lb mid)
                                (helper vec (+ 1 mid) ub)))))])
    (lambda (vec)
      (helper vec 0 (vector-length vec)))))

;;; (random-vector-element vec) -> any?
;;;   vec : vector
;;; Randomly select an element from a non-empty vector
(define random-vector-element
  (lambda (vec)
    (vector-ref vec (random (vector-length vec)))))

;;; (random-list n rproc) -> list?
;;;   n : non-negative integer
;;;   rproc : procedure? (0 parameters)
;;; Create a random list of length n.
(define random-list
  (lambda (n rproc)
    (letrec ([helper
              (lambda (n so-far)
                (if (zero? n)
                    so-far
                    (helper (- n 1) (cons (rproc) so-far))))])
      (helper n null))))

;;; (random-tree n rproc) -> binary-tree?
;;;   n : non-negative integer
;;;   rproc : procedure? (0 parameters)
;;; Create a random tree of size n.
(define random-tree
  (lambda (n rproc)
    (if (zero? n)
        empty-tree
        (let ([left-size (random n)])
          (binary-tree (rproc)
                       (random-tree left-size rproc)
                       (random-tree (- n left-size 1) rproc))))))

;;; (random-id) -> string
;;; Create a "random" user id
(define random-id
  (let* ([consonants (list->vector (string->list "BCDFGHJKLMNPQRSTVWXYZ"))]
         [vowels (list->vector (string->list "AEIOU"))]
         [c (lambda () (random-vector-element consonants))]
         [v (lambda () (random-vector-element vowels))])
    (lambda ()
      (string (c) (v) (c) (v) (c) (v)))))

;;; (random-digit) -> integer
;;; Create a random one-digit integer (0 through 9)
(define random-digit
  (lambda ()
    (random 10)))

;;; (random-bst n) -> binary-search-tree?
;;;   n : integer? non-negative?
;;; Construct an unpredictable bst of size n
(define random-bst
  (o vector->tree 
     list->vector 
     (section sort <> string-ci<=?)
     (section random-list <> random-id)))

;;; (binary-tree-contains? tree val) -> boolean?
;;;   tree : binary-tree?
;;;   val : any?
;;; Determine if val appears somewhere in tree.
(define binary-tree-contains?
  (lambda (tree val)
    (and (not (empty-tree? tree))
         (let ([root (btt tree)])
           ; (display root) (newline)
           (or (equal? root val)
               (binary-tree-contains? (btl tree) val)
               (binary-tree-contains? (btr tree) val))))))

;;; (binary-tree-depth tree) -> integer?
;;;   tree : binary-tree?
;;; Determine the number of levels in the tree
(define binary-tree-depth
  (lambda (tree)
    (if (empty-tree? tree)
        0
        (+ 1 (max (binary-tree-depth (btl tree))
                  (binary-tree-depth (btr tree)))))))

;;; (binary-tree-size tree) -> integer?
;;;   tree : binary-tree?
;;; Determine the number of elements in a tree
(define binary-tree-size
  (lambda (tree)
    (if (empty-tree? tree)
        0
        (+ 1
           (binary-tree-size (btl tree))
           (binary-tree-size (btr tree))))))

;;; (bst-find bst str) -> string
;;;   bst : binary-search-tree?
;;;   str : string
;;; Find str (case insensitive) in bst.  If str is not in bst, returns #f.
(define bst-find
  (lambda (bst str)
    (if (empty-tree? bst)
        #f
        (let ([root (btt bst)])
          ; (display root) (newline)
          (cond
            [(string-ci=? str root)
             root]
            [(string-ci<? str root)
             (bst-find (btl bst) str)]
            [else
             (bst-find (btr bst) str)])))))
             
; +-----------------------------+------------------------------------
; | Provided code: Sample trees |
; +-----------------------------+

;;; management-tree : binary-tree?
;;; The management tree from the reading.
(define management-tree
  (btn "Board"
       empty-tree
       (btn "CEO"
            (btn "Head of Engineering"
                 (leaf "Software Developer")
                 (leaf "Tester"))
            (btn "Head of Legal"
                 empty-tree
                 (leaf "Lawyer")))))

;;; digits-tree : binary-tree?
;;; The following tree, taken from an earlier lab
;;;        5
;;;       / \
;;;      2   7
;;;     / \   \
;;;    1   4   9
;;;           /
;;;          8
(define digits-tree
  (btn 5
       (btn 2
            (leaf 1)
            (leaf 4))
       (btn 7
            empty-tree
            (btn 9
                 (leaf 8)
                 empty-tree))))

; ignore the following
(define *COMBINE* undefined)
(define *PROCESS* undefined)
(define *BASE-CASE* undefined)

; +-----------+------------------------------------------------------
; | Exercises |
; +-----------+

#| AB |#

; +-------------------------+----------------------------------------
; | Exercise 0: Preparation |
; +-------------------------+

#|
a. Have your traditional start-of-lab discussion.
|#
#|

b. Update your CSC151 library.
|#

#|
c. In a separate window, open the source code for the list-based
tree library, available at

https://raw.githubusercontent.com/grinnell-cs/csc151/main/binary-trees-from-lists.rkt
|#

#|
d. Review the provided code.
|#

#| A |#

; +----------------------------+-------------------------------------
; | Exercise 1: Building trees |
; +----------------------------+

#| B |#

; +-------------------------------+----------------------------------
; | Exercise 2: Searching vectors |
; +-------------------------------+

#|
The reading contains two procedures for searching trees.  Before we
start searching trees, let's remind ourselves of how we might search
vectors.

Consider the following procedure.
|#

;;; (vector-find vec str) -> string? (or boolean?)
;;;   vec : vectorof string?
;;;   str : string?
;;; Finds a word equal to string in vec, ignoring case.
;;; Returns false if it can't find it.
(define vector-find
  (lambda (vec str)
    (letrec ([helper 
              (lambda (pos)
                (if (< pos 0)
                    #f
                    (let ([current (vector-ref vec pos)])
                      ; (display current) (newline)
                      (if (string-ci=? str current)
                          current
                          (helper (- pos 1))))))])
      (helper (- (vector-length vec) 1)))))

#|
a. Explain, in your own words, how this procedure works.

<TODO: Enter your explanation>
|#

#|
Consider the following vector.
|#

(define names (vector "Aaardvark" "Chinchilla" "Dingo" "Emu" "Fennec Fox"
                      "Gnu" "Hippo" "Iguana" "Jackalope" "Llama" "Skink"))

#|
b. What names do you expect the `vector-find` to look at when searching
for `"SamR"`?

<TODO: Enter your answer here.>

Check your answer experimentally (e.g., by printing out the current
value after the `let` with `(display current) (newline)`).

|#

#|
c. If the vector contains 1000 elements, how many values do you
expect to look at when searching for an element not in the vector?

<TODO: Enter your answer here.>
|#

; +-----------------------------+------------------------------------
; | Exercise 3: Searching trees |
; +-----------------------------+

#|
a. The reading and lab provide two different procedures for searching
trees.  What are they?  How are they similar?  How are they different?

<TODO: Enter your answer here.>
|#


#|
b. The following code converts the vector from the prior exercise
to a tree.  Sketch the tree here.


|#

; A tree of names
(define ton (vector->tree names))

#|
c. What names do you expect `(binary-tree-contains? ton "sam")` to look at?

<TODO: Enter your answer here>

Check your answer experimentally (e.g., by uncommenting the `(display root) (newline)`
after the let that defines `root` in `binary-tree-contains?`).

<TODO: Enter your answer here> (you can copy and paste)
|#

#|
d. What names do you expect the `(binary-tree-contains? ton "SamR")` to look at?

<TODO: Enter your answer here>

Check your answer experimentally.
|#

#|
e. If the vector from which we built the tree contained 1000 elements, how many 
values do you expect `binary-tree-contains?` to look at when searching for an element 
not in the tree?

<TODO: Enter your answer here>
|#

; +-------------------------------------------+----------------------
; | Exercise 4: Searching binary search trees |
; +-------------------------------------------+

#|
a. What names do you expect the `bst-find` to look at in a call to
`(bst-find? ton "sam")`?

<TODO: Enter your answer here>

Check your answer experimentally (e.g., by uncommenting the `(display root) (newline)`
after the `let` that defines `root` in `bst-find` and then running it again).

<TODO: Enter the results of your check.
|#

#|
b. What names do you expect `bst-find` to look at when searching
for `"SamR"`?

<TODO: Enter your answer here>

Check your answer experimentally.
|#

#|
c. If the vector contains 1000 elements, how many values do you
expect to look at when searching for an element not in the vector?

<TODO: Enter your answer here>

Check your answer experimentally with `(bst-find (random-bst 1000) "SamR")`.
|#

#| A |#

; +----------------------------------+-------------------------------
; | Exercise 5: Searching, revisited |
; +----------------------------------+

; +------------------------------+-----------------------------------
; | Exercise 6: Flattening trees |
; +------------------------------+

#| B |#

; +-------------------------------------------------+----------------
; | Exercise 7: Finding the largest value in a tree |
; +-------------------------------------------------+

#|
Consider the following procedure to find the largest value in a tree that
contains only numbers our `largest-in-list` procedure from much earlier
in the semester, it requires that we have a base case of one-element
rather than no elements..
|#

(define binary-tree-largest
  (lambda (t)
    (if (leaf? t)
        (btt t)
        (max (btt t)
             (binary-tree-largest (btl t))
             (binary-tree-largest (btr t))))))

#|
Here's are a few sample trees to use with `binary-tree-largest`.
|#

;       5
(define numbers-i (leaf 5))

;       5
;     /   \
;   -2     6
(define numbers-ii (btn 5 (leaf -2) (leaf 6)))

;       5
;     /   \
;   -2     3
;   / \   / \
;  4   7 0   6
(define numbers-iii (btn 5 (btn -2 (leaf 4) (leaf 7)) (btn 3 (leaf 0) (leaf 6))))

;       5
;     /   \
;   -2     3
;   / \   / \
;  4   7 8   6
(define numbers-iv (btn 5 (btn -2 (leaf 4) (leaf 7)) (btn 3 (leaf 8) (leaf 6))))

#|
a. What do you expect `binary-tree-largest` to give for each tree?

<TODO: Enter numbers for the question marks>

(binary-tree-largest numbers-i): ????

(binary-tree-largest numbers-ii): ????

(binary-tree-largest numbers-iii): ????

(binary-tree-largest numbers-iv): ????

Check your answers experimentally
|#

#|
b. There's a subtle error in `binary-tree-largest`.  Write some tests
or do some experiments to see if you can determine the error.

<TODO: Describe the error, or at least input that gives the error>
|#

#|
c. How might you resolve the error?

<TODO: Enter your explanation>
|#