;   1.  (15 pts)
;        
;   a. (5 pts) A function map-square which consumes a list of numbers,
;   and returns a list of the squares of those numbers.  (The name
;   "map" is traditional, coming from the math sense: a function
;   mapping a bunch of inputs to a bunch of outputs.)

(define lon0 (cons 4 (cons 100 (cons 2 (cons 100 (cons -3 (cons 0 empty)))))))
(define lon1 empty)
(define lon2 (cons 42 empty))

;; map-square: list of numbers --> list of numbers
;; Given a list of numbers, returns a list of the squares of those numbers.
(define (map-square a-lon)
  (cond
    [(empty? a-lon) empty]
    [(cons? a-lon) (cons (sqr (first a-lon)) (map-square (rest a-lon)))]))

"map-square test cases"
(equal? (map-square lon0)
        (cons 16 (cons 10000 (cons 4 (cons 10000 (cons 9 (cons 0 empty)))))))
(equal? (map-square lon1)
        empty)
(equal? (map-square lon2)
        (cons 1764 empty))

; b. (10 pts) A function substitute-num which takes in a
; list-of-numbers, plus a "before" number and "after" number and
; returns a list like the input, except that wherever the input list
; contains the "before" number, the output list now contains the
; "after" number.

;; substitute-num: number, number, list of numbers --> list of numbers
;; Given a "before" number, an "after" number, and a list of numbers,
;; return the list with the "after" value substituted for each "before" value.
(define (substitute-num before after a-lon)
  (cond
    [(empty? a-lon) empty]
    [(cons? a-lon)
     (cond
       [(= before (first a-lon))
        (cons after (substitute-num before after (rest a-lon)))]
       [else
        (cons (first a-lon) (substitute-num before after (rest a-lon)))])]))
; NOTE: There's a good deal of repeated code here, which should annoy you.
; In a little while we'll see a way to eliminate this redundancy.

"substitute-num test cases"
(equal? (substitute-num 100 101 lon0)
        (cons 4 (cons 101 (cons 2 (cons 101 (cons -3 (cons 0 empty)))))))
(equal? (substitute-num 20 200 lon0)
        lon0)
(equal? (substitute-num 100 100 lon0)
        lon0)
(equal? (substitute-num 1 2 lon1)
        empty)
(equal? (substitute-num 42 -42 lon2)
        (cons -42 empty))
(equal? (substitute-num -42 42 lon2)
        (cons 42 empty))
(equal? (substitute-num 1901 2001 
                        (cons 6 (cons 1901 (cons 7 (cons 2001 empty)))))
        (cons 6 (cons 2001 (cons 7 (cons 2001 empty)))))


;  2.
; First, recall our definitions of directories and entries from HW 3.
;;; An entry is: 
;; (make-entry symbol val)
;; An entry is structure consisting of
;; - key identifies the entry,
;; - val which is the interesting part -- the datum
;; associated with the key.
(define-struct entry (key val))

;Examples:
(make-entry 'malcolm 4041)
(make-entry 'operator 0000)
(make-entry 'campos 6000)


#|  Template for an entry:
;; .. : entry --> ..
;;
;;
(define (handle-entry an-entry)
  ..(entry-key an-entry)..(entry-val an-entry)..)
|#


; A telephone directory is a list of entries which is 
; - empty
; - cons(f,r)
; where f is an entry
; where r is a list of entries


;Examples
(define malc (make-entry 'malcolm  4041))
(define police (make-entry 'campos 6000))
(define help (make-entry 'operator 0000))

(define dir0 empty)
(define dir1 (cons (make-entry 'campos   6000) empty))
(define dir2 (cons (make-entry 'operator 0000) dir1))
(define dir3 (cons (make-entry 'malcolm  4041) dir2))


; Finally, let's make a variation of substitute which operates on
; directories. We'll call it update, and it takes in a directory, a
; name, and a number. It returns a new directory with all the
; original entries, plus an entry with the given name/number. If that
; name already occurred in some entry (with possibly a different
; number), then the new directory should contain the updated
; information, but you should not introduce any duplicate
; entries. (If you were given a directory that already had duplicate
; entries for the key you are updating, mention whether your code
; leaves them be, or eliminates them. (Either is fine.))

;; update: directory, name, number --> directory
;; Given a directory dir with a name and number to add, returns dir
;; with the new entry added.  If there is already an entry in dir
;; with the same name as the given one, the old entry is replaced with the new
;; one.  If there are duplicate entries with the same name as the given one,
;; update will only replace the first entry and leave the rest alone.
;; 
(define (update dir new-name new-num)
  (cond [(empty? dir) (cons (make-entry new-name new-num) empty)]
        [(cons? dir) 
         (cond
           [(entries-match? (make-entry new-name new-num)
                            (first dir))
            (cons (make-entry new-name new-num) (rest dir))]
           [else 
            (cons (first dir)
                  (update (rest dir) new-name new-num))])]))

;; entries-match?: entry, entry --> boolean
;; Returns true if the given entries match (they have the same name).
;;
(define (entries-match? entry1 entry2)
  (symbol=? (entry-key entry1) (entry-key entry2)))

"update test cases"
(define joe (make-entry 'Joe-Schmoe 1234))
(define new-police (make-entry 'campos 6001))

(equal? (update dir0 'Joe-Schmoe 1234)
        (cons joe empty))
(equal? (update dir3 'Joe-Schmoe 1234)
        (list malc help police joe))
(equal? (update dir3 'campos 6001)
        (list malc help (make-entry 'campos 6001)))
(equal? (update (list help police malc joe police)
        'campos 6001)
        (list help new-police malc joe police))

;
; 3. (10pts) Hand-evaluation
;      Hand-evaluate:
;
;;; prod: list-of-nums --> num
;;; Return the product of a list of numbers.
;;;
;(define (prod nums)
;  (cond [(empty? nums)  1]   ; 1 is the identity element for *.
;        [(cons?  nums)  (* (first nums) (prod (rest nums)))]))
;
;(prod (cons 2 (cons 7 empty)))
;

; As usual, your hand-evaluation should include one line per stepper
; step, and you should indicate (perhaps via underlining or
; italicizing) on your printout which sub-expression is about to be
; evaluated.

; NOTE: On paper, you'll use italics or underlining.  Here, I'll use double angle
; brackets <<like this>> to indicate the sub-expression that's about to be
; evaluated.
; <<(prod (cons 2 (cons 7 empty))>>
; = (cond [<<(empty? (cons 2 (cons 7 empty)))>> 1]
;         [(cons? (cons 2 (cons 7 empty))) (* (first nums) (prod (rest nums)))])
; = <<(cond [false 1]
;           [(cons? (cons 2 (cons 7 empty))) 
;            (* (first (cons 2 (cons 7 empty))) 
;               (prod (rest (cons 2 (cons 7 empty)))))])>>
; = (cond [<<(cons? (cons 2 (cons 7 empty)))>> 
;            (* (first (cons 2 (cons 7 empty))) 
;               (prod (rest (cons 2 (cons 7 empty)))))])
; = <<(cond [false (* (first (cons 2 (cons 7 empty))) 
;                     (prod (rest (cons 2 (cons 7 empty)))))])>>
; = (* <<(first (cons 2 (cons 7 empty)))>> (prod (rest (cons 2 (cons 7 empty)))))
; = (* 2 (prod <<(rest (cons 2 (cons 7 empty)))>>))
; = (* 2 <<(prod (cons 7 empty))>>)
; = (* 2 (cond [<<(empty? (cons 7 empty))>> 1]
;              [(cons?  (cons 7 empty))
;               (* (first (cons 7 empty)) (prod (rest (cons 7 empty))))]))
; = (* 2 <<(cond [false 1]
;              [(cons?  (cons 7 empty))
;               (* (first (cons 7 empty)) (prod (rest (cons 7 empty))))])>>)
; = (* 2 (cond [<<(cons?  (cons 7 empty))>>
;               (* (first (cons 7 empty)) (prod (rest (cons 7 empty))))]))
; = (* 2 <<(cond [true 
;                 (* (first (cons 7 empty)) (prod (rest (cons 7 empty))))]))>>
; = (* 2 (* <<(first (cons 7 empty))>> (prod (rest (cons 7 empty)))))
; = (* 2 (* 7 (prod <<(rest (cons 7 empty))>>)))
; = (* 2 (* 7 <<(prod empty)>>))
; = (* 2 (* 7 (cond [<<(empty? empty)>> 1]
;                   [(cons? empty) (* (first empty) (prod (rest empty)))])))
; = (* 2 (* 7 <<(cond [true 1]
;                     [(cons? empty) (* (first empty) (prod (rest empty)))])>>))
; = (* 2 <<(* 7 1)>>)
; = <<(* 2 7)>>
; = 14
 
;   4. (10 pts) Natural Numbers Write the function my-odd?, which
;takes a NatNum and tells whether or not it's an odd number. (Include
;the data definition, examples, template for NatNums, of course.)
;Your function should follow directly from the template. Your code
;will be based on the fact that a non-zero natural number is odd iff
;its predecessor isn't.  For this problem, do not use the built-in
;functions even?, odd?, remainder, modulo, nor round, ceiling, ...

; my-odd?: NatNum --> boolean
; Returns whether or not the given number is odd. The input is assumed to be a
; natural number (greater than or equal to zero).
;
(define (my-odd? a-num)
  (cond [(zero? a-num) false]
        [else (not (my-odd? (sub1 a-num)))]))

"my-odd? test cases"
(boolean=? (my-odd? 0)
           false)
(boolean=? (my-odd? 1)
           true)
(boolean=? (my-odd? 12345)
           true)
(boolean=? (my-odd? 23456)
           false)

;   5. (20 pts) NatNum in, List out
; a. (0pts) Setup for this problem: Be sure to be using the draw.ss
; teachpack as in hw02 (Unless you cleared your teachpacks, it's still
; in use.) Also include the following:


;; A constant, used for width of various bands, in part (b).
;;
(define band-width 20)
;
;;; --------- Begin data definitions.
;
;;; A posn is (make-posn num num)
;;; and is already defined inside draw.ss.
;
;
;;; A color is: one of {'red, 'yellow, 'white, 'black, 'blue, 'green}.
;
;
;;;; Note: If you want to use your own structs from hw02
;;;;       instead of these, that's okay.
;
(define-struct rectangle (location width height color))
;; A rectangle is:
;;   (make-rectangle  posn num num color)
;; where location refers to the northwest corner.

(define-struct circle (location radius color))
;; A circle is:
;;   (make-circle posn num color)
;; where location refers to the center.

;; A Shape is either:
;;   - a rectangle, or
;;   - a circle.
;;
;; (Note: Since we have already just defined "circle", "rectangle" as data,
;;  there's no need to repeat that info.)
;; --------- End data definitions.


; b. (10 pts) Do one of the following, whichever looks more fun to you:

; 	* rectangles: Write a simple function that is given a number
; i, and creates a rectangle whose northwest corner is at canvas
; location (i*band-width, 0), with width band-width and height
; (* i i).
;	* circles: Write a simple function that is given a number i,
; and creates a circle centered at (say) canvas location (150,150),
; with radius (* i band-width), and either the color red or blue,
; depending on whether i is odd or even.  Note: you don't need to recur
; on your input, so this is a simple function.

;; fun-rectangle: number --> rectangle 
;; Given a number i, creates a green rectangle whose northwest corner
;; is at canvas location (i*band-width, 0), with width band-width and
;; height (* i i).
;;
(define (fun-rectangle i)
  (make-rectangle (make-posn (* i band-width) 0)
                  band-width
                  (* i i)
                  'green))

"fun-rectangle test cases"
(equal? (fun-rectangle 10)
        (make-rectangle (make-posn (* 10 band-width) 0)
                        band-width
                        100
                        'green))
(equal? (fun-rectangle 0)
        (make-rectangle (make-posn 0 0)
                        band-width
                        0
                        'green))

;; fun-circle: number --> circle 
;; Takes in a number i and returns a circle whose center is at canvas
;; location (150, 150) and whose radius is i*band-width.  The circle
;; is red if i is odd or blue if i is even.
;;
(define (fun-circle i)
  (make-circle (make-posn 150 150) 
               (* i band-width)
               (cond [(odd? i) 'red]
                     [else 'blue])))

"fun-circle test cases"
(equal? (fun-circle 12)
        (make-circle (make-posn 150 150)
                     (* 12 band-width)
                     'blue))
(equal? (fun-circle 5)
        (make-circle (make-posn 150 150)
                     (* 5 band-width)
                     'red))

; c. (10 pts) Write a function which takes in a NatNum n, and returns
; a list of shapes: shapes created by the preceding function, called
; with n, n-1, n-2, ... 1, 0.

;; many-fun-rectangles: NatNum --> list of rectangles
;; Given a number n, returns a list of rectangles created by the fun-rectangle
;; function called on n, n-1, n-2, ..., 1, 0.  Assumes n is a natural number.
;;
(define (many-fun-rectangles n)
  (cond [(zero? n) (cons (fun-rectangle 0) empty)]
        [else (cons (fun-rectangle n) (many-fun-rectangles (sub1 n)))]))

"many-fun-rectangles test cases"
(equal? (many-fun-rectangles 3)
        (list (fun-rectangle 3) 
              (fun-rectangle 2) 
              (fun-rectangle 1) 
              (fun-rectangle 0)))
(equal? (many-fun-rectangles 0)
        (cons (fun-rectangle 0) empty))

;; many-fun-circles: NatNum --> list of circles
;; Given a number n, returns a list of circles created by the fun-circle function
;; called on n, n-1, n-2, ... 1, 0.  n is assumed to be a natural number.
;;
(define (many-fun-circles n)
    (cond [(zero? n) (cons (fun-circle 0) empty)]
        [else (cons (fun-circle n) (many-fun-circles (sub1 n)))]))


; d. (0pts) You are not required to write draw-list-of-shapes, and
; draw the output of your previous function. (It's pretty simple to
; do, though. Recall that to draw A and draw B, you can combine
; operations with and (since they all return true.)) If your structs
; representing circles and rectangles differed from those presented
; above, that's fine -- use whichever you like, but make sure your
; data definitions are correct.

; Sure, why not? :-)
; First, recall our drawing functions from HW 2.

(start 500 500) ; Opens a canvas to draw on.

;; draw-shape: Shape --> true
;; Draw a-shape on the current canvas, and return true.
;;
(define (draw-shape a-shape)
  (cond [(circle?    a-shape) 
         (draw-solid-disk (circle-location a-shape)
                          (circle-radius a-shape) 
                          (circle-color a-shape))]
        [(rectangle? a-shape) 
         (draw-solid-rect (rectangle-location a-shape)
                          (rectangle-width a-shape) 
                          (rectangle-height a-shape)
                          (rectangle-color a-shape))]))

; Examples of posns, circles and rectangles:
(define origin (make-posn 0 0))
(define p34    (make-posn 3 4))
(define circ1  (make-circle p34     1 'red))    ; A little red dot.
(define circ23 (make-circle origin 23 'blue))    
(define rect1 (make-rectangle (make-posn 10 10) 15 30 'yellow))
(define rect2 (make-rectangle (make-posn  0  0)  2  2 'red))

"draw-shape test cases"
(boolean=? (draw-shape circ1) true)
(boolean=? (draw-shape circ23) true)
(boolean=? (draw-shape rect1) true)
(boolean=? (draw-shape rect2) true)

;; draw-list-of-shapes: list of shapes --> boolean
;; Takes in a list of shapes and draws each one, returning true.
;;
;; NOTE: Some shapes, particularly rectangles with zero heights supplied by
;; the many-fun-rectangles functions, are undrawable and will throw an error
;; if you try to draw them.
;;
(define (draw-list-of-shapes a-los)
  (cond
    [(empty? a-los) true]
    [(cons? a-los) (and (draw-shape (first a-los))
                        (draw-list-of-shapes (rest a-los)))]))

;; remove-last: non-empty list --> list
;; Removes the last element of a list.  Not defined for empty lists.
;; Based on the following template:
;; 	A NonEmptyList is:
;;	  - (cons <val> empty)
;; 	  - (cons <val> <NonEmptyList>)
;;
(define (remove-last a-list)
  (cond [(empty? (rest a-list)) empty] ; Last element?
        [(cons? (rest a-list)) 
         (cons (first a-list) (remove-last (rest a-list)))]))


"draw-list-of-shapes test cases"

; NOTE: The last elements of the functions 'many-fun-circles' and
; 'many-fun-rectangles' are undrawable.  (They are either circles with
; radius 0 or rectangles with 0 height.)  We use 'remove-last' to
; remove these undrawable shapes before drawing them.

(boolean=? (draw-list-of-shapes (list circ1 rect1 circ23 rect2))
           true)
(boolean=? (draw-list-of-shapes empty)
           true)
(boolean=? (draw-list-of-shapes (remove-last (many-fun-circles 21)))
           true)
(boolean=? (draw-list-of-shapes (remove-last (many-fun-rectangles 22)))
           true)

;6.(20 pts) Write two functions that return the largest number in a list 
;  of numbers: one written using natural recursion (reverse accumulation) 
;  and another using the accumulator style (forward accumulation). 


; Let's do natural recursion first

;; largest-num: list-of-num -> num or symbol
;; takes in a list of numbers and returns the largest number or the 
;; symbol 'empty-list if given an empty list
;; we will learn later in the course that this solution is not the most 
;; efficient natural recursion solution.
(define (largest-num alon)
  (cond 
    [(empty? alon) 'empty-list]
    [(empty? (rest alon)) (first alon)]
    [(cons? alon) 
     (cond 
       [(>= (first alon) (largest-num (rest alon))) (first alon)]
       [else (largest-num (rest alon))])]))


;test cases

(largest-num empty)
(= 17 (largest-num (list -5 8 -4 17)))
(= -8 (largest-num (list -8)))
(= -3 (largest-num (list -6 -8 -3 -10)))


;; largest-num2: list-of-num -> num or symbol
;; accumulator version that initializes the accumator to
;; be 'empty-list , it calls largest-num-acc
(define (largest-num2 alon)
  (largest-num-acc 'empty-list alon))

;; largest-num-acc: num or symbol, list-of-num -> num or symbol
;; returns the largest number in the list or the symbol 'empty-list
;; if the list is empty

(define (largest-num-acc acc alon)
  (cond
    [(empty? alon) acc]
    [(and (cons? alon) (symbol? acc)) 
     (largest-num-acc (first alon) (rest alon))]
    [(and (cons? alon) (not (symbol? acc)))
     (largest-num-acc (cond 
                        [(> (first alon) acc) (first alon)]
                        [(<= (first alon) acc) acc])
                      (rest alon))]))
                       
;test cases

(largest-num2 empty)
(= 17 (largest-num2 (list -5 8 -4 17)))
(= -8 (largest-num2 (list -8)))
(= -3 (largest-num2 (list -6 -8 -3 -10)))