;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; PROBLEM 1: Lists
;;


;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;
;;
;; PROBLEM 1a: Function Template for lists-of-numbers
;;

;(define (fun-for-a-lons a-lons)
;  (cond
;    [(empty? a-lons) ...]
;    [else
;     (first a-lons) ...
;     (fun-for-a-lons (rest a-lons)) ...]))

;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;
;;
;; PROBLEM 1b: Cross
;;
;; loss is a list-of-symbols
;; lons is a list-of-numbers
;; lops is a list-of-pairs-of-symbol-number
;;  (list symbol number)

;; cross:  loss lons -> lops
;; create list of all possible pairs consisting of a symbol in loss and a
;;    number in lons

;; Examples
;; "(cross empty '(1 2)))"
;; "expected value:  empty"
;; (cross '(a b c) '(1 2))
;; "expected value:  (list (list 'a 1) (list 'a 2) (list 'b 1) (list 'b 2)
;;                          (list 'c 1) (list 'c 2))"

(define (cross-one s lons)
  (cond
    [(empty? lons) empty]
    [else
     (cons (list s (first lons))
           (cross-one s (rest lons)))]))

(define (cross loss lons)
  (local [
     (define (cross-one s lons)
       (cond
         [(empty? lons) empty]
         [else
          (cons (list s (first lons))
           (cross-one s (rest lons)))])) ]     
  (cond
    [(empty? loss) empty]
    [else 
     (append (cross-one (first loss) lons)
             (cross (rest loss) lons))])))

"(cross empty '(1 2)))"
"expected value:  empty"
(cross empty '(1 2))
(cross '(a b c) '(1 2))
"expected value:  (list (list 'a 1) (list 'a 2) (list 'b 1) (list 'b 2)
                         (list 'c 1) (list 'c 2))"
(cross '(a b c) '(1 2))



;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;
;;
;; PROBLEM 1c: Dot Product
;;

 ;; Examples:
;;(dot-product empty) = 0
;; (dot-prouct (list 3 6) (list (5 10) = (3*5) + (6*10) = 75
;; (dot-product (list 1 2 3) (list 4 5 6)) = (1*4) + (2*5) + (3*6) = 32

;; dot-product: list-of-numbers list-of-numbers -> list-of-numbers
;; Compute the dot product of a-lons1 and a-lons2, where these
;; are lists of the same length. Return 0, if lists are empty.
(define (dot-product a-lons1 a-lons2) 
  (cond
    [(empty? a-lons1) 0]
    [else
     (+ (* (first a-lons1) (first a-lons2)) 
        (dot-product (rest a-lons1) (rest a-lons2)))]))

;; Tests
"(dot-product empty)"
"expected-value:  0"
(dot-product empty empty)

"(dot-product (list 3 6) (list 5 10))"
"expected value: 75"
(dot-product (list 3 6) (list 5 10))
            
"(dot-product (list 1 2 3) (list 4 5 6)) = (1*4) + (2*5) + (3*6)"
"expected value:  32" 
(dot-product (list 1 2 3) (list 4 5 6))

;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;
;;
;; PROBLEM 1d: Equality for lists of symbols
;;
;;  No need to change template since symbols are basic data

;; Examples:
;; (sym-list=? '(a b c) '(c a b)) = false
;; (sym-list=? '(a b c) '(a b c)) = true

;; sym-list=? : list-of-symbols list-of-symbols -> boolean
;; to determine whether a-list1 and a-list2
;; contain the same symbols in the same order
(define (sym-list=? a-list1 a-list2) 
  (cond
    [(and (empty? a-list1) (empty? a-list2)) true]
    [(or (empty? a-list1) (empty? a-list2)) false] ;; exactly one is empty
    [else ;; neither empty
     (and 
      (symbol=? (first a-list1) (first a-list2))
      (sym-list=? (rest a-list1) (rest a-list2)))]))

;; Tests
"(sym-list=? empty empty)"
"expected value:  true"
(sym-list=? empty empty)

"(sym-list=? empty '(a b c))"
"expected value:  false"
(sym-list=? empty '(a b c))

"(sym-list=? '(a b c) empty)"
"expected value:  false"
(sym-list=? '(a b c) empty)

"(sym-list=? '(a b c) '(a b c))"
"expected value:  true"
(sym-list=? '(a b c) '(a b c))

"(sym-list=? '(a b c) '(c a b))"
"expected value:  false"
(sym-list=? '(a b c) '(c a b))

;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;
;;
;; PROBLEM 1d: list-of-posns
;;

;;  a posn is complex data, so we must modify the template:

;(define (fun-for-a-lopsns a-lopsns)
;  (cond
;    [(empty? a-lopsns) ...]
;    [else
;     (fun-for-posn (first a-lopsns)) ...
;     (fun-for-a-lopsns (rest a-lopsns)) ...]))

;(define (fun-for-posn a-posn)
;  (posn-x a-posn) ...
;  (posn-y a-posn) ... )

;; posn=? posn posn -> boolean
;;   test whether two posns are the same
(define (posn=? a-posn1 a-posn2)
  (and 
   (= (posn-x a-posn1) (posn-x a-posn2))
   (= (posn-y a-posn1) (posn-y a-posn2))))

;; Tests
"(posn=? (make-posn 1 2) (make-posn 1 2))"
"expected value:  true"
(posn=? (make-posn 1 2) (make-posn 1 2))

"(posn=? (make-posn 1 2) (make-posn 2 2))"
"expected value:  false"
(posn=? (make-posn 1 2) (make-posn 2 2))

"(posn=? (make-posn 1 2) (make-posn 1 3))"
"expected value:  false"
(posn=? (make-posn 1 2) (make-posn 1 3))

;; posn-list=? : list-of-posns list-of-posns -> boolean
;; to determine whether a-list1 and a-list2
;; contain the same posns in the same order
(define (posn-list=? a-list1 a-list2) 
  (cond
    [(and (empty? a-list1) (empty? a-list2)) true]
    [(or (empty? a-list1) (empty? a-list2)) false]
    [else
     (and
      (posn=? (first a-list1) (first a-list2))
      (posn-list=? (rest a-list1) (rest a-list2)))]))

;; Tests:
"(posn-list=? empty empty)"
"expected value:  true"
(posn-list=? empty empty)

"(posn-list=? (list (make-posn 1 2) empty)"
"expected value:  false"
(posn-list=? (list (make-posn 1 2)) empty)

"(posn-list=? empty (list (make-posn 1 2)))"
"expected value:  false"
(posn-list=? empty (list (make-posn 1 2)))

"(posn-list=? (list (make-posn 1 2)) (list (make-posn 1 2)))"
"expected value:  true"
(posn-list=? (list (make-posn 1 2)) (list (make-posn 1 2)))

"(posn-list=? (list (make-posn 1 2)) (list (make-posn 1 1)))"
"expected value:  false"
(posn-list=? (list (make-posn 1 2)) (list (make-posn 1 1)))



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; PROBLEM 2:  Binary-Symbol-Trees
;;

;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;
;;
;; PROBLEM 2a: Template for a binary-symbol-tree
;;

;; A binary-symbol-tree is a
;; --empty
;; (make-bst symbol binary-symbol-tree binary-symbol-tree)
(define-struct bst (node left right))
;; Template for binary-symbol-trees
;(define (fun-for-bst a-bst)
;  (cond
;    [(empty? a-bst)   ]
;    [else
;     (bst-node a-bst)
;     (fun-for-bst (bst-left a-bst))
;     (fun-for-bst (bst-right a-bst)) ...]))

;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;
;;
;; PROBLEM 2b: Counting Nodes
;;


;; Examples:
;; (count-nodes empty) = 0
;; (count-nodes (make-bst 'a (make-bst 'b empty empty) empty)) = 2

;; count-nodes: binary-symbol-tree -> number
;; Return the number of nodes in a-bst
(define (count-nodes a-bst) 
  (cond
    [(empty? a-bst) 0]
    [else
     (+ 1 (count-nodes (bst-left a-bst))
        (count-nodes (bst-right a-bst)))]))

;; Tests
"(count-nodes empty)"
"expected value:  0"
(count-nodes empty)

"(count-nodes (make-bst 'a (make-bst 'b empty empty) empty))"
"expected value:  2"
(count-nodes (make-bst 'a (make-bst 'b empty empty) empty))


;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;
;;
;; PROBLEM 2c: Equality between Binary-Symbol-Trees
;;

;; Examples:
;; (bst=? empty empty) = true
;; (bst=? (make-bst 'a empty empty) (make-bst 'b empty empty)) = false
;; (bst=? (make-bst 'a empty empty) empty) = false

;; bst=? : binary-symbol-tree binary-symbol-tree -> boolean
;; to determine whether a-bst1 and a-bst2
;; are the same binary-symbol-trees
(define (bst=? a-bst1 a-bst2) 
  (cond
    [(and (empty? a-bst1) (empty? a-bst2)) true]
    [(or (empty? a-bst1) (empty? a-bst2)) false] ;; only one empty
    [else
     (and (symbol=? (bst-node a-bst1) (bst-node a-bst2))
          (bst=? (bst-left a-bst1) (bst-left a-bst2))
          (bst=? (bst-right a-bst1) (bst-right a-bst2)))]))

;; Tests
"(bst=? empty empty)"
"expected value : true"
(bst=? empty empty)

"(bst=? (make-bst 'a empty empty) (make-bst 'b empty empty))"
"expected value: false"
(bst=? (make-bst 'a empty empty) (make-bst 'b empty empty))

"(bst=? (make-bst 'a empty empty) empty)"
"expected value: false"
(bst=? (make-bst 'a empty empty) empty)

"(bst=? (make-bst 'a empty empty) (make-bst 'a empty empty))"
"expected value: true"
(bst=? (make-bst 'a empty empty) (make-bst 'a empty empty))

"(bst=? (make-bst 'a empty empty) (make-bst 'b empty empty))"
"expected value: false"
(bst=? (make-bst 'a empty empty) (make-bst 'b empty empty))




;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; PROBLEM 3: Symbol-Trees
;;

;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;
;;
;; PROBLEM 3a: Template for Symbol-Trees
;;


;; A symbol-tree is a
;; --empty
;; (make-st symbol list-of-symbol-trees)
(define-struct st (node branches))
;; A list-of-symbol-trees is one of
;; --empty
;; --(cons symbol-tree list-of-symbol-trees)

;; Template for symbol-trees


;(define (fun-for-st an-st) 
;  (cond
;    [(empty? an-st)  ...]
;    [else
;     (st-node an-st) ...
;     (fun-for-list-st (st-branches an-st)) ...]))
;
;(define (fun-for-list-st an-lst) 
;  (cond
;    [(empty? an-lst) ... ]
;    [else
;     (fun-for-st (first an-lst)) ...
;     (fun-for-list-st (rest an-lst))]))




;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;
;;
;; PROBLEM 3b: Counting nodes for Symbol-Trees
;;

;; Examples:
;; (count-nodes-st empty) = 0
;; (count-nodes-st (make-st 'a (list (make-st 'b empty)))) = 2

;; count-node-st: symbol-tree -> number
;; returns number of nodes on an-st


 (define (count-nodes-st an-st)
  (cond
    [(empty? an-st)  0]
    [else
     (+ 1(count-nodes-lst (st-branches an-st)))]))

(define (count-nodes-lst an-lst) 
  (cond
    [(empty? an-lst) 0 ]
    [else
     (+ (count-nodes-st (first an-lst))
        (count-nodes-lst (rest an-lst)))]))
;; Test:
"(count-nodes-st empty)"
"expected value: 0"
(count-nodes-st empty)

"(count-nodes-st (make-st 'a (list (make-st 'b empty))))"
"expected value:  2"
(count-nodes-st (make-st 'a (list (make-st 'b empty))))

"(count-nodes-st (make-st 'a (list (make-st 'b 
                                           (list (make-st 'c empty)))
                                  (make-st 'd (list (make-st 'e empty))))))"
"expected value:  5"
(count-nodes-st (make-st 'a (list (make-st 'b 
                                           (list (make-st 'c empty)))
                                  (make-st 'd (list (make-st 'e empty))))))



;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;
;;
;; PROBLEM 3c: Finding nodes on Symbol-Trees
;;
;;

;; find-node-st?: symbol symbol-tree -> boolean
;; Return true if node in an-st and false otherwise.


(define (find-node-st? node an-st) 
  (cond
    [(empty? an-st) false]
    [else
     (or (symbol=? (st-node an-st) node)
     (find-node-lst? node (st-branches an-st)))]))

(define (find-node-lst? node an-lst) 
  (cond
    [(empty? an-lst) false]
    [else
     (or (find-node-st? node (first an-lst))
     (find-node-lst? node (rest an-lst)))]))

;; Tests
"(find-node-st? 'a empty)"
"expected value:  false"
(find-node-st? 'a empty)

"(find-node-st? 'e (make-st 'a (list (make-st 'b 
                                           (list (make-st 'c empty)))
                                  (make-st 'd (list (make-st 'e empty))))))"
"expected value:  true"
(find-node-st? 'e (make-st 'a (list (make-st 'b 
                                           (list (make-st 'c empty)))
                                  (make-st 'd (list (make-st 'e empty))))))

"(find-node-st? 'f (make-st 'a (list (make-st 'b 
                                           (list (make-st 'c empty)))
                                  (make-st 'd (list (make-st 'e empty))))))"
"expected value:  false"
(find-node-st? 'f (make-st 'a (list (make-st 'b 
                                           (list (make-st 'c empty)))
                                  (make-st 'd (list (make-st 'e empty))))))


;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;
;;
;; PROBLEM 3c: Equality Symbol-Trees
;;
;;

;; st=? : symbol-tree symbol-tree -> boolean
;; to determine whether an-st1 and an-st2
;; are the same symbol-trees

(define (st=? an-st1 an-st2) 
  (cond
    [(and (empty? an-st1)(empty? an-st2)) true ]
    [(or (empty? an-st1) (empty? an-st2)) false]  ;; only one empty
    [else
     (and (symbol=? (st-node an-st1) (st-node an-st2))
          (st-list=? (st-branches an-st1) (st-branches an-st2)))]))

(define (st-list=? an-lst1 an-lst2) 
  (cond
    [(and (empty? an-lst1) (empty? an-lst2)) true ]
    [(or (empty? an-lst1) (empty? an-lst2)) false ] ;; only one empty
    [else
     (and (st=? (first an-lst1) (first an-lst2))
     (st-list=? (rest an-lst1) (rest an-lst2)))]))

;; Tests
"(st=? empty empty)"
"expected value:  true"
(st=? empty empty)

"(st=? (make-st 'a empty) empty)"
"expected value:  false"
(st=? (make-st 'a empty) empty)

"(st=? empty (make-st 'a empty))"
"expected value:  false"
(st=?  empty (make-st 'a empty))

(define st1
  (make-st 'a (list (make-st 'b 
                                           (list (make-st 'c empty)))
                                  (make-st 'd (list (make-st 'e empty))))))

(define st2
  (make-st 'a (list (make-st 'b 
                                           (list (make-st 'c empty)))
                                  (make-st 'd (list (make-st 'f empty))))))

"(st=? st1 st1)"
"expected value: true"
(st=? st1 st1)

"(st=? st1 st2)"
"expected value:  false"
(st=? st1 st2)