#lang racket
(require csc151)
(require csc151/trees)
(require csc151/counters)
(require rackunit)
(require rackunit/text-ui)

;;; File:
;;;   000000.rkt
;;; Authors:
;;;   The student currently referred to as 000000
;;;   Titus Klinge
;;;   Samuel A. Rebelsky
;;; Contents:
;;;   Code and solutions for Exam 4 2017F
;;; Citations:
;;;

;; +---------+--------------------------------------------------------
;; | Grading |
;; +---------+

;; This section is for the grader's use.

;; Problem 1: 
;; Problem 2:
;; Problem 3:
;; Problem 4:
;; Problem 5:
;; Problem 6:
;;           ----
;;     Total:

;;    Scaled:
;;    Errors:
;;     Times:
;;          :
;;          :
;;          :
;;           ----
;;     Total:

;; +----------+-------------------------------------------------------
;; | Prologue |
;; +----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

;; +-----------+------------------------------------------------------
;; | Problem 1 |
;; +-----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

; Citations:

; Solution:

;;; Procedures:
;;;   list-set-one
;;;   list-set-two
;;; Parameters:
;;;   lst, a list
;;;   pos, a non-negative integer
;;;   val, a Scheme value
;;; Purpose:
;;;   Create a new version of lst with val at the specified position.
;;; Produces:
;;;   newlst, a list
;;; Preconditions:
;;;   0 <= pos < (length lst)
;;; Postconditions:
;;;   * (length newlst) = (length lst)
;;;   * (list-ref newlst pos) = val
;;;   * For all i, 0 <= i < (length lst) and i != pos,
;;;     (list-ref newlst pos) = (list-ref lst pos)
(define list-set-one
  (lambda (lst pos val)
    (letrec ([kernel
               (lambda (index lst1 pos1 val1)
                 (cond
                   [(= index (length lst))
                    null]
                   [(= index pos)
                    (cons val (kernel (increment index) lst pos val))]
                   [else
                    (cons (list-ref lst index)
                          (kernel (increment index) lst pos val))]))])
      (kernel 0 lst pos val))))

(define list-set-two
  (lambda (lst pos val)
    (let kernel ([so-far null]
                 [remaining lst])
      (cond
        [(null? remaining)
         so-far]
        [(equal? (length so-far) pos)
         (kernel (append so-far (list val))
                 (cdr remaining))]
        [else
         (kernel (append so-far (list (car remaining)))
                 (cdr remaining))]))))
 
; Examples/Tests:

;; +-----------+------------------------------------------------------
;; | Problem 2 |
;; +-----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

; Citations:

; Solution:

(define nested-list-tally
  (lambda (lst pred?)
    0)) ; STUB

; Examples/Tests:


;; +-----------+------------------------------------------------------
;; | Problem 3 |
;; +-----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

; Citations:

; Solution:

;;; Procedure:
;;;   vector-filter
;;; Parameters:
;;;   vec, 
;;;   pred?, 
;;; Purpose:
;;;   
;;; Produces:
;;;   
;;; Preconditions:
;;;   
;;; Postconditions:
;;;   

(define vector-filter
  (lambda (vec pred?)
    (vector))) ; STUB

; Examples/Tests:

;; +-----------+------------------------------------------------------
;; | Problem 4 |
;; +-----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

; Citations:

; Solution:
;;; Procedure:
;;;   next-larger
;;; Parameters:
;;;   val, a real number
;;;   vec, a vector of real numbers
;;; Purpose:
;;;   Find the smallest value in vec that is greater than val
;;; Produces:
;;;   result, a real number or #f.
;;; Preconditions:
;;;   vec is a vector of real numbers sorted from smallest to largest
;;; Postconditions:
;;;   If vec contains a number greater than val, then result is the
;;;     smallest such number.
;;;   If vec does not contain a number greater than val, then result is #f.
(define next-larger
  (lambda (val vec)
    #f)) ; STUB

; Examples/Tests:

;; +-----------+------------------------------------------------------
;; | Problem 5 |
;; +-----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

; Citations:

; Supplied code:

;;; Counter
;;;   cons-counter
(define cons-counter (counter-new "cons"))

;;; Procedure:
;;;   $cons
;;; Parameters:
;;;   left, a Scheme value
;;;   right, a Scheme value
;;; Purpose:
;;;   Make a pair from left and right and log the operation.
;;; Produces:
;;;   pair, a pair
;;; Preconditions:
;;;   cons-counter is defined.
;;; Postconditions:
;;;    (car pair) = left
;;;    (cdr pair) = right
;;;    cons-counter has been incremented.
(define $cons
  (lambda (val lst)
    (counter-increment! cons-counter)
    (cons val lst)))

;;; Procedure:
;;;   list-append
;;; Parameters:
;;;   front, a list of size n
;;;   back, a list of size m
;;; Purpose:
;;;   Put front and back together into a single list.
;;; Produces:
;;;   appended, a list of size n+m.
;;; Preconditions:
;;;   front is a list [Unverified]
;;;   back is a list [Unverified]
;;; Postconditions:
;;;   For all i, 0 <= i < n,
;;;    (list-ref appended i) is (list-ref front i)
;;;   For all i, n <= i < n+m
;;;;   (list-ref appended i) is (list-ref back (- i n))
(define list-append
  (lambda (front back)
    (if (null? front)
        back
        (cons (car front) 
              (list-append (cdr front) back)))))

;;; Procedures:
;;;   tree-flatten
;;;   tree-flatten-new
;;; Parameters:
;;;   tree, a tree
;;; Purpose:
;;;   "Flatten" the tree into the corresponding list.
;;; Produces:
;;;   lst, a list
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   Every value in the tree appears in the list.
;;;   No additional values appear in the list.
;;;   The values are in the same order in the list as they are
;;;     in the tree.  (Things in the left subtree appear before
;;;     the value in a node, which appears before things in the
;;;     right subtree.
(define tree-flatten
  (lambda (tree)
    (if (empty? tree)
        null
        (list-append (tree-flatten (left tree))
                     (cons (contents tree)
                           (tree-flatten (right tree)))))))

; Solution:

; b.
;    t1 requires ___ calls to cons
;    t2 requires ___ calls to cons
;    t3 requires ___ calls to cons
;    t4 requires ___ calls to cons
;    t5 requires ___ calls to cons
;    t6 requires ___ calls to cons
;    t7 requires ___ calls to cons

; c.
;    t# requires the most calls to cons because 

; d.
;    t# requires the fewest calls to cons because

; e.
(define tree-flatten-new
  (lambda (tree)
    null)) ; STUB

; Examples/Tests:

;; +-----------+------------------------------------------------------
;; | Problem 6 |
;; +-----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

; Citations:

; Supplied code

; Solution:

;;; Procedure:
;;;   
;;; Parameters:
;;;   
;;; Purpose:
;;;   
;;; Produces:
;;;   
;;; Preconditions:
;;;   
;;; Postconditions:
;;;   
(define ioe
  (lambda (a / b)
    (let * ([c (decrement b)]
            [d b])
      (if (and (< c (increment c))
               (<= c (square c))
               (or (negative? c)
                   (negative? (increment c))
                   (negative? (square c))))
          d
          (let ([new-c (vector-ref a d)]
                [new-d (vector-ref a c)]
                [new-a (vector-ref a (quotient (+ d c) 2))]
                [new-b (+ c (- c (increment c)))])        
            (if (and (<= c d)
                     (/ new-d new-c))
                (* new-b c)
                (* new-b d)))))))

;;; Procedure:
;;;   
;;; Parameters:
;;;   
;;; Purpose:
;;;   
;;; Produces:
;;;   
;;; Preconditions:
;;;   
;;; Postconditions:
;;;   
(define vss! 
  (lambda (? +)
    (let kernel [(/ (- (vector-length ?) 1))]
      (when (>= / 0)
        (let* ([a (ioe ? + /)]
               [b (vector-ref ? a)])
          (vector-set! ? a (vector-ref ? /))
          (vector-set! ? / b)
          (kernel (- / 1)))))))