#lang racket

(require csc151)
(require racket/match)
(require racket/undefined)
(require rackunit)

;; CSC-151-01 (Spring 2021, Term 1)
;; Lab: Binary Trees (Side A)
;;   https://rebelsky.cs.grinnell.edu/Courses/CSC151/2021SpT2/labs/binary-trees
;; Authors: YOUR NAMES HERE
;; Date: THE DATE HERE
;; Acknowledgements:
;;   ACKNOWLEDGEMENTS HERE

; +---------------+--------------------------------------------------
; | Provided code |
; +---------------+

;;; (binary-tree? t) -> boolean?
;;;   t : any
;;; Returns true iff t is a binary tree.
(define binary-tree?
  (let ([list-of-three-elements?
         (lambda (t)
           (and (pair? t)
                (pair? (cdr t))
                (pair? (cddr t))
                (null? (cdddr t))))])
    (lambda (t)
      (or (empty-tree? t)                    ; the empty tree is a tree
          (and (list-of-three-elements? t)   ; A list of three elements ...
               (binary-tree? (cadr t))       ; Where element 1 is a tree
               (binary-tree? (caddr t))))))) ; And element 2 is a tree

;;; empty-tree : tree?
;;; An alias for the empty binary tree.
(define empty-tree (string->symbol "\u25EC")) ; empty triangle with dot
; (define empty-tree (string->symbol "\u2022")) ; bullet
; (define empty-tree (string->symbol "\u25B5")) ; empty triangle
; (define empty-tree '_) ; Just an underscore, nothing fancy.

;;; (empty-tree? t) -> boolean?
;;;   t : value
;;; Returns true iff is t is an empty binary tree.
(define empty-tree? 
  (lambda (t)
    (eq? t empty-tree)))

;;; (binary-tree value left right) -> tree?
;;;   value : any
;;;   left : tree?
;;;   right : tree?
;;; Returns a non-empty tree with value at the root
;;; and the given left and right subtrees.
(define binary-tree list)

;;; (leaf value) -> tree?
;;;   value : any
;;; Returns a non-empty tree with no children (i.e., a leaf)
;;; with value at the root.
(define leaf
  (section binary-tree <> empty-tree empty-tree))

;;; (binary-tree-top t) -> any
;;;   t : tree?, (not (empty-tree? t))
;;; Returns the value at the root of this tree.
(define binary-tree-top car)

;;; (binary-tree-left t) -> any
;;;   t : tree?, (not (empty-tree? t))
;;; Returns the left child of this tree.
(define binary-tree-left cadr)

;;; (binary-tree-right t) -> any
;;;   t : tree?, (not (empty-tree? t))
;;; Returns the right child of this tree.
(define binary-tree-right caddr)

;;; Shorthands
(define btn binary-tree) ; n for "new" or "node"
(define btt binary-tree-top)
(define btl binary-tree-left)
(define btr binary-tree-right)

;;; (display-binary-tree t) -> void?
;;;   t : tree?
;;; Prints tree t to the console in a well-formatted manner.
(define display-binary-tree
  (lambda (t)
    (let* (; The different levels of bullets
           [bullets (vector "* " "+ " "- " ". ")]
           ; The index of the last bullet
           [last-bullet (- (vector-length bullets) 1)]
           ; Choose the appropriate bullet for a level.
           [bullet
            (lambda (level)
              (vector-ref bullets (min level last-bullet)))])
      (letrec (; Display a binary tree at the appropriate indentation
               [helper
                (lambda (t indent)
                  (when (not (empty-tree? t))
                    (display (make-string (* indent 2) #\space))
                    (display (bullet indent))
                    (display (btt t))
                    (newline)
                    (helper (btl t) (+ indent 1))
                    (helper (btr t) (+ indent 1))))])
        (helper t 0)))))

; +---------------------------------------+--------------------------
; | Provided code: The hideous shorthands |
; +---------------------------------------+

(define bttl (o btt btl))
(define btll (o btl btl))
(define btrl (o btr btl))

(define bttr (o btt btr))
(define btlr (o btl btr))
(define btrr (o btr btr))

(define bttll (o bttl btl)) ; or (o btt btl btl)
(define btlll (o btll btl))
(define btrll (o btrl btl))

(define bttrl (o bttr btl))
(define btlrl (o btlr btl))
(define btrrl (o btrr btl))

(define bttlr (o bttl btr))
(define btllr (o btll btr))
(define btrlr (o btrl btr))

(define bttrr (o bttr btr))
(define btlrr (o btlr btr))
(define btrrr (o btrr btr))

; +----------------------------------------------+-------------------
; | Provided code: The legendary management tree |
; +----------------------------------------------+

(define management-tree
  (binary-tree
    "Board"
    empty-tree
    (binary-tree
      "CEO"
      (binary-tree
        "Head of Engineering"
        (leaf "Software Developer")
        (leaf "Tester"))
      (binary-tree
        "Head of Legal"
        empty-tree
        (leaf "Lawyer")))))

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

#| AB |#

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

#|
a. Conduct the normal start-of-lab discussion.

b. Review the procedures above, taking notes as to the important
ones.  (Note: You will normally want to have the navigator keep
the list of procedures at hand so that they can check them.)

c. In the space below, describe the normal "start of lab" steps
and summarize what you answered for each.

<TODO: ENTER YOUR ANSWER HERE>
|#

#| A |#

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

; +------------------------------+-----------------------------------
; | Exercise 2: Traversing trees |
; +------------------------------+

#| B |#

; +--------------------------------------+---------------------------
; | Exercise 3: Changing representations |
; +--------------------------------------+

#|
Because we're using the tree procedures directly, we can change our underlying
representation of trees.  In this exercise, we attempt to do so.

Since Side A wrote `bt`, we're including a version here.  Remove it when
you combine the labs.
|#


;;; (BT path tree) -> binary-tree?
;;;   path : string? (contains only r's and l's)
;;;   bree : binary-tree?
;;; Follow the path given by the path and return the described
;;; value.
(define BT
  (lambda (path tree)
    (cond
      [(equal? path "")
       tree]
      [(empty-tree? tree)
       (error "You've run off the end of the tree")]
      [(char=? #\l (string-ref path 0))
       (BT (substring path 1)
           (binary-tree-left tree))]
      [(char=? #\r (string-ref path 0))
       (BT (substring path 1)
           (binary-tree-right tree))]
      [else
       (error "Invalid subpath" path)])))

#|
a. Make sure that you understand what each of the following should procedure.
(Those are our starting point.)

    > management-tree
    ?
    > (display-binary-tree management-tree)
    ?
    > (binary-tree? management-tree)
    ?
    > (BT "rlr" management-tree)
    ?
|#

#|
b. Suppose we are switching from lists to vectors.  Check off the
procedures or values you would expect to have to update if we decided
to change our representation of non-empty binary trees from
three-element lists to three-element vectors.

Tree constructors

[ ] `empty-tree`
[ ] `binary-tree`
[ ] `leaf`

Tree checkers

[ ] `empty-tree?`
[ ] `binary-tree?`

Tree traversers

[ ] `binary-tree-top`
[ ] `binary-tree-left`
[ ] `binary-tree-right`
[ ] `bt`

Other

[ ] `display-binary-tree`
[ ] `management-tree (and tree-i through tree-iv)`
[ ] <anything else you want to fill in>
|#

#|
b. Presumably, one of the procedures you would have changed is `binary-tree`.
Rename the old version of `binary-tree` to `binary-tree-old` and then write
a new version of `binary-tree` that uses `vector` instead of `list`.

<TODO: Change the code above>

<TODO: Enter the new version here, too (in the comment)>
|#

#|
c. Determine how well we're doing by exploring `management-tree`.

    > management-tree
    ?
    > (display-binary-tree management-tree)
    ?
    > (binary-tree? management-tree)
    ?
    > (BT "rlr" management-tree)
    ?
|#


#|
d. You'll also need to change `binary-tree-top`, `binary-tree-left`, and
`binary-tree-right`.

<TODO: Change the code above>

<TODO: Enter the new versions here, too (in the comment>
|#

#|
e. Determine if we're doing any better now.

    > management-tree
    ?
    > (display-binary-tree management-tree)
    ?
    > (binary-tree? management-tree)
    ?
|#

#|
f. Believe it or not, but you should only have one procedure left to rewrite,
`binary-tree?`.  Do so now.

<TODO: Change the code above>

<TODO: Enter the new versions here, too (in the comment>
|#

#|
g. See if everything now works correctly.  (It should.)

    > management-tree
    ?
    > (display-binary-tree management-tree)
    ?
    > (binary-tree? management-tree)
    ?
    > (BT "rlr" management-tree)
    ?
|#

; +------------------------------+-----------------------------------
; | Exercise 4: Changing bullets |
; +------------------------------+

#|
You may have noticed that the `display-binary-tree` procedure has a
helper procedure, `bullet`, that selects an appropriate bullet.  

Here's a tree with more than four levels.

|#

```
(define taller-tree
  (binary-tree "a"
               (binary-tree "b"
                            (binary-tree "c"
                                         (binary-tree "d"
                                                      (binary-tree "e"
                                                                   (leaf "f")
                                                                   (leaf "g"))
                                                      (leaf "h"))
                                         (leaf "i"))
                            (leaf "j"))
               (leaf "k")))
```

#|
a. What bullet do you expect to get if your tree has more than four levels,
as in the case of `taller-tree`?

<TODO: Enter your answer here>

Check your answer experimentally.

<TODO: Enter your code from the interactions pane.>

|#

#|
b. In your own words, explain how `bullet` works.

<TDOO: Enter your answer here>
|#

#|
c. As you might guess, you can change the bullets by changing the
value of `bullets`.  Create a new version of `bullets` with at least
five bullets, using the Unicode bullets, which you can find on
Wikipedia.

  https://en.wikipedia.org/wiki/Bullet_(typography)

For example, you can get the triangular bullet with "\u2023 ".

<TODO: Enter your new definition here and above.>
|#

#|
d. In your own words, explain how `display-binary-tree` seems to work.
|#

#| A |#

; +--------------------------------------+---------------------------
; | Exercise 5: Exploring tree recursion |
; +--------------------------------------+

#| B |#

; +----------------------------------------+-------------------------
; | Exercise 6: Patterns of tree recursion |
; +----------------------------------------+

#|
Note: We will return to this issue in the next class.  If you are
unable to complete this portion of the lab in the required time,
do not feel compelled to do so immediately.  Nonetheless, you may
find it useful as you go on to the next reading.
|#

#|
You've now seen or written three procedures that recurse over binary trees:

* `binary-tree?`, which checks if something is a binary tree.
* `display-binary-tree`, which prints out a binary tree
* `bt`, which traverses a binary tree
* `binary-tree-size`, which finds the number of values in the tree

Each uses a slightly different form of recursion.

As you've likely figured out, it's helpful to generalize the patterns of
recursion we see.  For example, we've realized that most list recursion
stops with null lists or one element lists (that's our base-case test)
and that most list recursion requires us to take the cdr of the list.
|#

#|
a. Let's do the same here.  `binary-tree-size` uses one of the more
common forms of tree recursion, so we'll focus on that.  Using
`binary-tree-size` as a starting point, sketch a form of recursion
over trees.  Make sure to make it clear what the base case test is
and what the recursive case looks like.>

<TODO: Enter your sketch here.>
|#

#|
b. How is binary tree recursion similar to and dissimilar from
list recursion?

<TODO: Enter your answer here.>
|#