#lang racket

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

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

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

;;; (count-cons-cells tree) -> integer?
;;;   tree : tree?
;;; Counts the number of cons cells that appear in tree.
;;; Does not look into vectors.
(define count-cons-cells
  (lambda (tree)
    (if (pair? tree)
        (+ 1
           (count-cons-cells (car tree))
           (count-cons-cells (cdr tree)))
        0)))

;;; (tree->code pair-struct) -> list?
;;;   tree : tree?
;;; Converts a tree into an approximation of the Scheme expression 
;;; that builds the tree.
(define tree->code
  (lambda (tree)
    (cond
      [(null? tree)
       'null]
      [(pair? tree)
       (list 'cons (tree->code (car tree)) (tree->code (cdr tree)))]
      [else
       tree])))

;;; (random-nums len max) -> listof integer?
;;;    len : non-negative-integer?
;;;    max : positive-integer?
;;; Make a list of length `len`, containing unpredictable numbers
;;; from the range [0..max).
(define random-nums
  (lambda (len max)
    (letrec ([helper
              (lambda (len so-far)
                (if (zero? len)
                    so-far
                    (helper (- len 1) (cons (random max) so-far))))])
      (helper len '()))))

;;; (ref-experiment collection rounds) -> void?
;;;   collection : (vectorof integer?) or (listof integer?)
;;;   rounds : natural?
;;;
;;; Look for integers selected randomly from the range between 
;;; 0 and the length of collection.  
;;;
;;; Returns nothing.  Used mostly for timing purposes.
(define ref-experiment
  (lambda (collection rounds)
    (let* ([ref (if (vector? collection) 
                    vector-ref 
                    list-ref)]
           [len (if (vector? collection) 
                    (vector-length collection)
                    (length collection))])
      (letrec ([kernel
                 (lambda (n)
                   (when (> n 0)
                     (ref collection (random len))
                     (kernel (- n 1))))])
        (kernel rounds)))))

#| AB |#

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

#|
a. If you have not done so, please conduct the normal "start of class
algorithm".  Introduce yourself to your partner.  Discuss work habits,
strengths, and areas to improve.  Make your 4:30 plans.

b. Review the documentation for the two supplied procedures to
ensure you understand what they are suposed to do.  If you're
not sure, feel free to experiment or to ask the staff.
|#

; +--------------------------------------+---------------------------
; | Exercise 1: Box and pointer diagrams |
; +--------------------------------------+

#|
a. Draw own box-and-pointer diagrams (on paper) for the following
expressions.  Each student should draw their own diagrams.

i. '(("x") "y" "z")
ii. '("x" ("y" "z"))
iii. '(("a") "b" ("c" ()))

b. Compare your answers to reach consensus.

c. Count the number of cons cells (pairs) in each.

d. Using `count-cons-cells`, determine how many cons cells (pairs) are
in each.  If the numbers differ, use `tree->code` to explore the code
used to build each.

There is nothing to submit for this problem, but make sure you 
understand the results.

Feel free to ask the lab staff to review your results.
|#

; +-----------------------------+------------------------------------
; | Exercise 2: Are they lists? |
; +-----------------------------+

#|
What do you think that `pair?` will return for each of the following?
How about `list?`. Attempt to confirm each answer experimentally and
explain any that you found particularly tricky.

i. (cons 'a 'b)
ii. (cons 'a (cons 'b 'c))
iii. (cons 'a null)
iv. null
v. (list 'a 'b 'c)
vi. (list 'a)
vii. (list)

There is nothing to submit for this problem, but make sure that you
can answer these questions.
|#

#| A |#

; +-------------------------------+----------------------------------
; | Exercise 3: Vector efficiency |
; +-------------------------------+

; +-----------------------------+------------------------------------
; | Exercise 4: Summing vectors |
; +-----------------------------+

#| B |#

; +-----------------------------+------------------------------------
; | Exercise 5: Filling vectors |
; +-----------------------------+

#|
Write a recursive procedure, `(my-vector-fill! vec val)`, that takes
two parameters, a mutable vector and a value, and puts that value
in every position of the vector.

> (define vec (vector 'a 'b 'c))
> vec
'#(a b c)
> (my-vector-fill! vec 0)
> vec
'#(0 0 0)
> (my-vector-fill! vec 'a)
> vec
'#(a a a)

Some implementations of Scheme come with vector-fill!. You may not
use that procedure.

Note: `my-vector-fill!` is supposed to modify an existing vector. It
is pointless to create a new vector.

Note: You may find that you want to do two things for a particular
position: fill the value at that position and recur. Remember that
when you want to sequence multiple actions if a test succeeds, you
should use a cond or when rather than an if.
|#

(define my-vector-fill!
  (lambda (vec val)
    undefined))

; +----------------------------------+-------------------------------
; | Exercise 6: Searching in vectors |
; +----------------------------------+

#|
Write a recursive procedure, `(vector-index-of vec elt)`, that looks
for `elt` in vector and returns the index of the first appearance
of `elt` if it appears in the vector and #f otherwise.

> (vector-index-of (vector 'a 'b 'c) 'b)
1
> (vector-index-of (vector 'a 'b 'c 'c 'b 'c) 'c)
2
> (vector-index-of (vector 'a 'b 'c) 'd)
#f
|#

(define vector-index-of
  (lambda (vec elt)
    undefined))

#| AB |#

; +----------------------------+-------------------------------------
; | Extra 1 : Trees to Strings |
; +----------------------------+

#|
a. Write a recursive procedure, `(intlist->string ints)`, that takes
as input a list of integers and returns a string that represents
the list.

> (intlist->string null)
"()"
> (intlist->string '(1))
"(1)"
> (intlist->string '(1 2 3))
"(1 2 3)"
> (intlist->string (cons 1 2))
BOOM!
|#

;;; (intlist->string ints) -> string
;;;   ints : a list of integers
;;; Convert a list of integers to a string.
(define intlist->string
  (lambda (ints)
    undefined))

#|
b. Write a similar procedure that accepts a pair of integers as the
last cons cell in the list.  (In a normal list, the last cons cell
has an integer and a null.)  When you reach the end of a list and
the `cdr` is not null, you should print a period and the cdr.

> (intseq->string null)
"()"
> (intseq->string (cons 1 2))
"(1 . 2)"
> (intseq->string (cons 1 (cons 2 3)))
"(1 2 . 3)"
|#

(define intseq->string
  (lambda (ints)
    undefined))

#|
c. Extend your procedure to handle nested pair structure.

> (intpairs->string null)
"()"
> (intpairs->string (list (list 1)))
"((1))"
> (intpairs->string (list 1 (list 2 3) 4))
"(1 (2 3) 4)"
> (intpairs->string (list 1 (cons 2 3) 4))
"(1 (2 . 3) 4)"
|#

(define intpairs->string
  (lambda (ints)
    undefined))