;1.  (15 pts) Functions Processing Family Trees
;
;Using the following data definition of FamTree
;
;        A FamTree is
;
;        -- (make-unknown symbol)       
;        -- (make-child symbol number famTree famTree), where the symbol 
;           represents a name, the first FamTree is the mother's family tree, 
;           the second FamTree is the father's side, and the number is the
;           birthyear.
;
;    And the following data definition for a Name+Generation tuple:
;
;    A NamGen is a (make-NamGen sym num) where name is the name of a person and 
;    gen is the generation number as measured from the root of some specified 
;    FamTree. That is, the child at the root of the FamTree is gen=0, their 
;    parents are gen=1, grandparents gen=2, etc.
;    (define-struct NamGen (name gen))
;
;    write a function earliest: FamTree --> NamGen, which returns the name and 
;    generation of the earliest (farthest back generation) known person in the 
;    family tree.

;; Data definitions
(define-struct Unknown (sym))
(define-struct Child (name birthyear mTree fTree))
(define-struct NamGen (name gen))

;; Data examples
(define ENaismith (make-Child 'Elizabeth 3024
                              (make-Unknown 'UNKNOWN)
                              (make-Unknown 'UNKNOWN)))
(define DearCaptain (make-Child 'Cordelia 3049
                                ENaismith
                                (make-Unknown 'UNKNOWN)))
(define theAdmiral (make-Child 'Miles 3081
                               DearCaptain
                               (make-Child 'Aral 3048
                                           (make-Unknown 'UNKNOWN)
                                           (make-Child 'Piotr 3024
                                                       (make-Unknown 'UNKNOWN)
                                                       (make-Unknown 'UNKNOWN)))))

;; earliest: FamTree --> NamGen
;; Returns the name and generation of the (known) person appearing earliest
;; (farthest generation back) in the family tree.  If more than one person
;; appears in the earliest generation, the leftmost person in the tree is
;; chosen, assuming one's mother is the left branch and one's father is the
;; right branch.  (This choice was arbitrary; any choice is acceptable.)
;;
(define (earliest aFamTree)
  (cond [(Unknown? aFamTree) (make-NamGen 'UNKNOWN -1)]
        [(Child? aFamTree)
         (cond [(and (Unknown? (Child-mTree aFamTree)) 
                     (Unknown? (Child-fTree aFamTree)))
                (make-NamGen (Child-name aFamTree) 0)]
               [(>= (NamGen-gen (earliest (Child-mTree aFamTree))) 
                    (NamGen-gen (earliest (Child-fTree aFamTree))))
                (add1gen (earliest (Child-mTree aFamTree)))]
               [else 
                (add1gen (earliest (Child-fTree aFamTree)))])]))

;; add1gen: NamGen --> NamGen
;; Adds one to the generation field of a NamGen, translating a NamGen from the
;; perspective of a parent to the perspective of their child.
(define (add1gen aNamGen)
  (make-NamGen (NamGen-name aNamGen) (add1 (NamGen-gen aNamGen))))

"earliest test cases"
(equal? (earliest (make-Unknown 'UNKNOWN)) (make-NamGen 'UNKNOWN -1))
(equal? (earliest ENaismith) (make-NamGen 'Elizabeth 0))
(equal? (earliest DearCaptain) (make-NamGen 'Elizabeth 1))
(equal? (earliest theAdmiral) (make-NamGen 'Elizabeth 2))

;2. (75 pts total) Function of Two Non-trivial Inputs and Mutual Recursion
;
;   a. (10 pts) Write a function that returns the n'th element of a list, or
;   false if it is not in the list.

;; nth: positive-num, list-of-num --> num
;; Returns the nth element of a list, or false if there is no nth element.
;; n is assumed to be positive.
(define (nth n nums)
  (cond [(and (= n 1) (empty? nums)) false]
        [(and (= n 1) (cons? nums)) (first nums)]
        [(and (> n 1) (empty? nums)) false]
        [(and (> n 1) (cons? nums)) (nth (sub1 n) (rest nums))]))

; Note: If you like, this function can be written more concisely as
; follows (but be careful about introducing bugs when condensing code!):

;; nth2: positive-num, list-of-num --> num
;; Returns the nth element of a list, or false if there is no nth element.
;; n is assumed to be positive.
(define (nth2 n nums)
  (cond [(empty? nums) false]
        [(cons? nums) (cond [(= n 1) (first nums)]
                            [(> n 1) (nth2 (sub1 n) (rest nums))])]))

"nth test cases"
(define list0 (list 10 20 30 40 50))
(define list1 empty)
(define list2 (list 55))

(equal? (nth 4 list0)
        40)
(equal? (nth 1 list0)
        10)
(equal? (nth 1 list2)
        55)
(equal? (nth 6 list0)
        false)
(equal? (nth2 4 list0)
        40)
(equal? (nth2 1 list0)
        10)
(equal? (nth2 1 list2)
        55)
(equal? (nth2 6 list0)
        false)

;   b. (15 pts) Write a function that will "zip" to 2 lists together, that is
;      (equal? (list 1 3 2 4) (zip (list 1 2 ) (list 3 4))
;      Your function must be able to take all lists, including lists of unequal 
;      length and have well defined behavior for all lists. You need not
;      specify which list's first element will appear first in the result,
;      though if you can specify this, you may.

;; zip: list-of-any, list-of-any --> list-of-any
;; "Zips" two lists together by interleaving the elements of the input lists.
;; If the lists are of unequal length, the leftover elements of the longer list
;; appear at the end of the list.
;;
(define (zip list1 list2)
  (cond [(empty? list1) list2]
        [(empty? list2) list1]
        [else (cons (first list1)
                    (cons (first list2) 
                          (zip (rest list1) (rest list2))))]))

"zip test cases"
(equal? (zip (list 'a 'b 'c) (list 1 2 3))
        (list 'a 1 'b 2 'c 3))
(equal? (zip empty empty)
        empty)
(equal? (zip (list 'apples 'bananas 'oranges) empty)
        (list 'apples 'bananas 'oranges))
(equal? (zip empty (list 'All 'Your 'Base))
        (list 'All 'Your 'Base))
(equal? (zip (list "This" "list" "is" "somewhat" 'longer)
             (list "than" 'this 1))
        (list "This" "than" "list" 'this "is" 1 "somewhat" 'longer))
(equal? (zip (list 'Curly 'Larry 'Moe)
             (list (list 1 2 3) (list 4 5) (list 6 7) (list 8) empty))
        (list 'Curly (list 1 2 3) 'Larry (list 4 5) 'Moe 
              (list 6 7) (list 8) empty))

;   c. (50 pts total) Consider the following data definition of a generalized
;   list of symbols:
;      ;; A GenList is
;      ;; -- symbol
;      ;; -- NSGenList
;
;      ;;A NSGenList (Non-Symbol GenList) is
;      ;; -- empty
;      ;; -- (cons GenList NSGenList)
;
;      GenList can be either just a symbol or a list of lists of lists of lists
;      of....of symbols.
;
;         i. (5 pts) Draw the UML diagram for GenList and NSGenList

;                    +---------+
;                    | GenList |
;                    +---------+
;                    |         |<---------+
;                    |         |          |
;                    +---------+          |
;                        /_\              |
;                         |               |
;                 +-------+--------+      |
;                 |                |      |
;          +------------+        Symbol   |
;          |  NSGenList |                 |
;          +------------+                 |
;          |            |<----------+     |
;          |            |           |     |
;          +------------+           |     |
;               /_\                 |     |
;                |                  |     |
;     +----------+----+             |     |
;     |               |             |     |
; +------+          empty           |     |
; | cons |                          |     |
; +------+ first                    |     |
; |      |--------------------------------+
; |      | rest                     |
; |      |---------------------------
; +------+

;         ii. (5 pts) Write the template for a function that processes a 
;         GenList. Note: list? can be used to detect a NSGenList.

;(define (f-GenList aGenList)
;  (cond [(symbol? aGenList) ...]
;        [(list? aGenList) ...(f-NSGenList aGenList)...]))
;
;(define (f-NSGenList aNSGenList)
;  (cond [(empty? aNSGenList) ...]
;        [(cons? aNSGenList)
;         ...(f-GenList (first aNSGenList))...
;         ...(f-NSGenList (rest aNSGenList)).. ]))

;         iii. (10 pts) Write the template(s) for a function taking two
;         GenLists, based on a Process Flow Analysis (see Lecture 15 an
;         Lecture 16).

;;; f-2GenLists: GenList, GenList --> ?
;(define (f-2GenLists genList1 genList2)
;  (cond [(symbol? genList1) (f-2GenLists_help_sym genList1 genList2)]
;        [(list? genList1) (f-2GenLists_help_NSGL genList1 genList2)]))
;
;;; f-2GenLists_help_sym: symbol, GenList --> ?
;(define (f-2GenLists_help_sym genList1 genList2)
;  (cond [(symbol? genList2) ...genList1...genList2... ]
;        [(list? genList2) (f-2GenLists_help_sym_NSGL genList1 genList2)]))
;
;;; f-2GenLists_help_sym_NSGL: symbol, NSGenList --> ?
;(define (f-2GenLists_help_sym_NSGL genList1 genList2)
;  (cond [(empty? genList2) ...genList1...]
;        [(cons? genList2) ...genList1...
;         ...(first genList2)...(rest genList2)...]))
;
;;; f-2GenLists_help_NSGL: NSGenList, GenList --> ?
;(define (f-2GenLists_help_NSGL genList1 genList2)
;  (cond [(empty? genList1) (f-2GenLists_help_empty genList2)]
;        [(cons? genList1) (f-2GenLists_help_cons genList1 genList2)])]))
;
;;; f-2GenLists_help_empty: GenList --> ?
;(define (f-2GenLists_help_empty genList2)
;  (cond [(symbol? genList2) ...genList2...]
;        [(list? genList2) (f-2GenLists_help_empty_NSGL genList2)]))
;
;;; f-2GenLists_help_empty_NSGL: NSGenList --> ?
;(define (f-2GenLists_help_empty genList2)
;  (cond [(empty? genList2) ...]
;        [(cons? genList2) ...(first genList2)...(rest genList2)... ]))
;
;;; f-2GenLists_help_cons: NSGenList, GenList --> ?
;(define (f-2GenLists_help_cons genList1 genList2)
;  (cons [(symbol? genList2) ...(first genList1)...(rest genList1)...
;                            ...genList2...]
;        [(list? genList2) (f-2GenLists_help_cons_NSGL genList1 genList2)]))
;                           
;;; f-2GenLists_help_cons_NSGL: NSGenList, NSGenList --> ?
;(define (f-2GenLists_help_cons_NSGL genList1 genList2)
;  (cond [(empty? genList2) ...(first genList1)...(rest genList1)...]
;        [(cons? genList2) ...(first genList1)...(rest genList1)...
;                          ...(first genList2)...(rest genList2)...]))

;         iv. (15 pts) Based on your templates, write a function, eqGL? that
;         compares two GenLists and returns true if the two GenLists are the
;         same. You may omit helper functions if they would consist of only one
;         line of code.

;; eqGL?: GenList, GenList --> boolean
;; Returns true if the two GenLists are equal.
;;
(define (eqGL? genList1 genList2)
  (cond [(symbol? genList1) (eqGL?_help_sym genList1 genList2)]
        [(list? genList1) (eqGL?_help_NSGL genList1 genList2)]))

;; eqGL?_help_sym: symbol, GenList --> boolean
(define (eqGL?_help_sym genList1 genList2)
  (cond [(symbol? genList2) (symbol=? genList1 genList2)]
        [(list? genList2) false]))

;; eqGL?_help_NSGL: NSGenList, GenList --> boolean
(define (eqGL?_help_NSGL genList1 genList2)
  (cond [(empty? genList1) (eqGL?_help_empty genList2)]
        [(cons? genList1) (eqGL?_help_cons genList1 genList2)]))

;; eqGL?_help_empty: GenList --> boolean
(define (eqGL?_help_empty genList2)
  (cond [(symbol? genList2) false]
        [(list? genList2) (empty? genList2)]))

;; eqGL?_help_cons: NSGenList, GenList --> boolean
(define (eqGL?_help_cons genList1 genList2)
  (cond [(symbol? genList2) false]
        [(list? genList2)
         (eqGL?_help_cons_NSGL genList1 genList2)]))

;; eqGL?_help_cons_NSGL: NSGenList, NSGenList --> boolean
(define (eqGL?_help_cons_NSGL genList1 genList2)
  (cond [(empty? genList2) false]
        [(cons? genList2) 
         (and (eqGL? (first genList1) (first genList2))
              (eqNSGL? (rest genList1) (rest genList2)))]))

;; eqNSGL?: NSGenList, NSGenList --> boolean
(define (eqNSGL? nsgl1 nsgl2)
  (cond [(empty? nsgl1) (empty? nsgl2)]
        [(cons? nsgl1) (eqNSGL_help_cons nsgl1 nsgl2)]))

;; eqNSGL_help_cons: NSGenList, NSGenList --> boolean
(define (eqNSGL_help_cons nsgl1 nsgl2)
  (cond [(empty? nsgl2) false]
        [(cons? nsgl2) (and (eqGL? (first nsgl1) (first nsgl2))
                            (eqNSGL? (rest nsgl1) (rest nsgl2)))]))

"eqGL? test cases"
(define gl0 'aSymbol)
(define gl1 empty)
(define gl2 (cons 'foo empty))
(define gl3 (list 'abc 'def (list 'ghi 'jkl) 'mno))

(boolean=? (eqGL? gl0 gl0) true)
(boolean=? (eqGL? gl0 gl1) false)
(boolean=? (eqGL? gl0 gl2) false)
(boolean=? (eqGL? gl0 gl3) false)
(boolean=? (eqGL? gl1 gl0) false)
(boolean=? (eqGL? gl1 gl1) true)
(boolean=? (eqGL? gl1 gl2) false)
(boolean=? (eqGL? gl1 gl3) false)
(boolean=? (eqGL? gl2 gl0) false)
(boolean=? (eqGL? gl2 gl1) false)
(boolean=? (eqGL? gl2 gl2) true)
(boolean=? (eqGL? gl2 gl3) false)
(boolean=? (eqGL? gl3 gl0) false)
(boolean=? (eqGL? gl3 gl1) false)
(boolean=? (eqGL? gl3 gl2) false)
(boolean=? (eqGL? gl3 gl3) true)

;         v. (10 pts) Write the same eqGL? function but with a single multi-way 
;         cond statement. Call this implementation "eqGL2?". You do not need to 
;         rewrite the contract, header and purpose, but you do need to test it
;         against the same test suite used on eqGL?.

(define (eqGL2? genList1 genList2)
  (cond [(and (symbol? genList1) (symbol? genList2))
         (symbol=? genList1 genList2)]
        [(and (symbol? genList1) (list? genList2)) false]
        [(and (list? genList1) (symbol? genList2)) false]
        [(and (list? genList1) (list? genList2)) (eqNSGL2? genList1 genList2)]))

(define (eqNSGL2? genList1 genList2)
  (cond
    [(and (empty? genList1) (empty? genList2)) true]
    [(and (empty? genList1) (cons? genList2)) false]
    [(and (cons? genList1) (empty? genList2)) false]
    [(and (cons? genList1) (cons? genList2))
     (and (eqGL2? (first genList1) (first genList2))
          (eqNSGL2? (rest genList1) (rest genList2)))]))

"eqGL2? test cases"
(boolean=? (eqGL2? gl0 gl0) true)
(boolean=? (eqGL2? gl0 gl1) false)
(boolean=? (eqGL2? gl0 gl2) false)
(boolean=? (eqGL2? gl0 gl3) false)
(boolean=? (eqGL2? gl1 gl0) false)
(boolean=? (eqGL2? gl1 gl1) true)
(boolean=? (eqGL2? gl1 gl2) false)
(boolean=? (eqGL2? gl1 gl3) false)
(boolean=? (eqGL2? gl2 gl0) false)
(boolean=? (eqGL2? gl2 gl1) false)
(boolean=? (eqGL2? gl2 gl2) true)
(boolean=? (eqGL2? gl2 gl3) false)
(boolean=? (eqGL2? gl3 gl0) false)
(boolean=? (eqGL2? gl3 gl1) false)
(boolean=? (eqGL2? gl3 gl2) false)
(boolean=? (eqGL2? gl3 gl3) true)

;         vi. (5 pts) Rewrite the above multi-way cond implementation by 
;         simplifying the cond statement. Call this implementation "eqGL3?".
;         Once again, you do not need to rewrite the contract, header and
;         purpose, but you do need to test it against the same test suite used
;         on eqGL?.

(define (eqGL3? genList1 genList2)
  (cond [(and (symbol? genList1) (symbol? genList2))
         (symbol=? genList1 genList2)]
        [(and (empty? genList1) (empty? genList2))
         true]
        [(and (list? genList1) (list? genList2))
         (eqNSGL3? genList1 genList2)]
        [else false]))

(define (eqNSGL3? genList1 genList2)
  (cond [(and (empty? genList1) (empty? genList2)) true]
        [(and (cons? genList1) (cons? genList2))
         (and (eqGL3? (first genList1) (first genList2))
              (eqNSGL3? (rest genList1) (rest genList2)))]
        [else false]))

"eqGL3? test cases"
(boolean=? (eqGL3? gl0 gl0) true)
(boolean=? (eqGL3? gl0 gl1) false)
(boolean=? (eqGL3? gl0 gl2) false)
(boolean=? (eqGL3? gl0 gl3) false)
(boolean=? (eqGL3? gl1 gl0) false)
(boolean=? (eqGL3? gl1 gl1) true)
(boolean=? (eqGL3? gl1 gl2) false)
(boolean=? (eqGL3? gl1 gl3) false)
(boolean=? (eqGL3? gl2 gl0) false)
(boolean=? (eqGL3? gl2 gl1) false)
(boolean=? (eqGL3? gl2 gl2) true)
(boolean=? (eqGL3? gl2 gl3) false)
(boolean=? (eqGL3? gl3 gl0) false)
(boolean=? (eqGL3? gl3 gl1) false)
(boolean=? (eqGL3? gl3 gl2) false)
(boolean=? (eqGL3? gl3 gl3) true)