#lang racket
(require csc151)

;;; File:
;;;   binary-tree-lab.rkt
;;; Authors:
;;;   Charlie Curtsinger
;;;   Titus Klinge
;;;   Samuel A. Rebelsky
;;;   YOUR NAME(S) HERE
;;; Contents:
;;;   A variety of procedures for working with binary trees.

; +--------------+---------------------------------------------------
; | Constructors |
; +--------------+

;;; Name:
;;;   empty
;;; Type:
;;;   tree
;;; Value:
;;;   The empty tree
(define empty 'empty)

;;; Procedure:
;;;   leaf
;;; Parameters:
;;;   val, a value
;;; Purpose:
;;;   Make a leaf node.
;;; Produces:
;;;   tree, a tree
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (contents tree) = val
;;;   (left tree) = empty
;;;   (right tree) = empty
(define leaf
  (lambda (val)
    (node val empty empty)))

;;; Procedure:
;;;   node
;;; Parameters:
;;;   val, a value
;;;   left-subtree, a tree
;;;   right-subtree, a tree
;;; Purpose:
;;;   Create a node in a binary tree.
;;; Produces:
;;;   tree, a tree
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (node? tree) holds.
;;;   (left tree) = left-subtree.
;;;   (right tree) = right-subtree.
;;;   (contents tree) = val.
(define node
  (lambda (val left right)
    (vector 'node val left right)))

;;; Procedure:
;;;   vector->tree
;;; Parameters:
;;;   vec, a vector
;;; Purpose:
;;;   Convert a vector into a relatively balanced binary tree.
;;; Produces:
;;;   tree, a binary tree
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   * All values in vec appear in tree.
;;;   * No other values in vec appear in tree.
;;;   * If val1 appears before val2 in vec, val1 appears to the
;;;     left of val2 in tree.
(define vector->tree
  ; The kernel builds a tree from the elements at positions lb..ub, inclusive.
  (letrec ([kernel (lambda (vec lb ub)
                      (if (< ub lb)
                          empty
                          (let [(mid (quotient (+ lb ub) 2))]
                            (node (vector-ref vec mid)
                                  (kernel vec lb (decrement mid))
                                  (kernel vec (increment mid) ub)))))])
    (lambda (vec)
      (kernel vec 0 (decrement (vector-length vec))))))

; +-----------+------------------------------------------------------
; | Observers |
; +-----------+

;;; Procedure:
;;;   contents
;;; Parameters:
;;;   nod, a binary tree node
;;; Purpose:
;;;   Extract the contents of node.
;;; Produces:
;;;   val, a value
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (contents (node val l r)) = val
(define contents
  (lambda (nod)
    (cond
      [(not (node? nod))
       (error "contents requires a node, received" nod)]
      [else
       (vector-ref nod 1)])))

;;; Procedure:
;;;   left
;;; Parameters:
;;;   nod, a binary tree node
;;; Purpose:
;;;   Extract the left subtree of nod.
;;; Produces:
;;;   l, a tree
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (left (node val l r)) = l
(define left
  (lambda (nod)
    (cond
      [(not (node? nod))
       (error "left requires a node, received" nod)]
      [else
       (vector-ref nod 2)])))

;;; Procedure:
;;;   right
;;; Parameters:
;;;   nod, a binary tree node
;;; Purpose:
;;;   Extract the right subtree of nod.
;;; Produces:
;;;   r, a tree
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (right (node val l r)) = r
(define right
  (lambda (nod)
    (cond
      [(not (node? nod))
       (error "right requires a node, received" nod)]
      [else
       (vector-ref nod 3)])))

; +------------+-----------------------------------------------------
; | Predicates |
; +------------+

;;; Procedure:
;;;   empty?
;;; Parameters:
;;;   val, a Scheme value
;;; Purpose:
;;;   Determine if val represents an empty tree.
;;; Produces:
;;;   is-empty?, a Boolean 
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   is-empty? is true (#t) if and only if val can be interpreted as
;;;   the empty tree.
(define empty? 
  (section eq? <> empty))

;;; Procedure:
;;;   leaf?
;;; Parameters:
;;;   val, a Scheme value
;;; Purpose:
;;;   Determine if val is a tree leaf
;;; Produces:
;;;   is-leaf?, a Boolean
(define leaf?
  (lambda (val)
    (and (node? val)
         (empty? (left val))
         (empty? (right val)))))

;;; Procedure:
;;;   node?
;;; Parameters:
;;;   val, a Scheme value
;;; Purpose:
;;;   Determine if val can be used as a tree node.
;;; Produces:
;;;   is-node?, a Boolean
(define node?
  (lambda (val)
    (and (vector? val)
         (= (vector-length val) 4)
         (eq? (vector-ref val 0) 'node))))

; +----------+-------------------------------------------------------
; | Examples |
; +----------+

;;; Procedure:
;;;   tree-contains?
;;; Parameters:
;;;   tree, a binary tree
;;;   val, a Scheme value
;;; Purpose:
;;;   Determine if val appears in tree
;;; Produces:
;;;   contains?, a Boolean value
(define tree-contains?
  (lambda (tree val)
    (and (not (empty? tree))
         (or (equal? (contents tree) val)
             (tree-contains? (left tree) val)
             (tree-contains? (right tree) val)))))

;;; Procedure:
;;;   tree-depth
;;; Parameters:
;;;   tree, a tree
;;; Purpose:
;;;   Determine the depth of tree
;;; Produces:
;;;   depth, an integer
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   depth represents the number of nodes on the path from the root to 
;;;   the furthest leaf.
(define tree-depth
  (lambda (tree)
    (if (empty? tree)
        0
        (+ 1 (max (tree-depth (left tree))
                  (tree-depth (right tree)))))))

;;; Procedure:
;;;   tree-size
;;; Parameters:
;;;   tree, a binary tree
;;; Purpose:
;;;   Determines the nmber of values in the tree
;;; Produces:
;;;   size, a non-negative integer
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   size represents the number of nodes in tree
(define tree-size
  (lambda (tree)
    (if (empty? tree)
        0
        (+ 1 
           (tree-size (left tree))
           (tree-size (right tree))))))

; +---------------------+--------------------------------------------
; | Binary Search Trees |
; +---------------------+

;;; Procedure:
;;;   bst-find
;;; Parameters:
;;;   bst, a binary search tree of strings
;;;   str, a string
;;; Purpose:
;;;   Determine if str appears in the tree
;;; Produces:
;;;   result, a Scheme value
;;; Preconditions:
;;;   bst is a binary search tree.  That is, it is a binary tree
;;;     with the property that each left subtree contains the smaller
;;;     values and each right subtree contains the larger values.
;;; Postconditions:
;;;   * If something equal to str (same letters, potentially different
;;;     capitalization) appears in the tree, result is that value.
;;;   * Otherwise, result is #f.
(define bst-find
  (lambda (bst str)
    (if (empty? bst)
        #f
        (let ([root (contents bst)])
          (cond
            [(string-ci=? str root)
             root]
            [(string-ci<? str root)
             (bst-find (left bst) str)]
            [else
             (bst-find (right bst) str)])))))