;; hw 07 solution

;; 1a.
;; merge:  list-of num list-of-num --> list-of-num
;; Takes two list-of-nums already sorted in descending order
;; and creates a new list with all the values of both lists combined
;; in descending order.
(define (merge lon1 lon2)
  (local
      [;; merge_help:  cons list-of-num --> list-of-num
       ;; Takes two list-of-nums already sorted in descending order
       ;; and creates a new list with all the values of both lists combined
       ;; in descending order.  lon1 is assumed to be cons.
       ;; Merge_help only checks lon2 for empty/cons and thus uses merge to check both
       ;; lon1 and lon2 when needed.
       (define (merge_help lon1 lon2)
         (cond 
           [(empty? lon2) lon1]
           [(cons? lon2) (cond
                           [(> (first lon1) (first lon2)) (cons (first lon1) (merge (rest lon1) lon2))]
                           [else (cons (first lon2) (merge lon1 (rest lon2)))])]))]
    (cond 
      [(empty? lon1) lon2]
      [(cons? lon1) (merge_help lon1 lon2)])))


(define myList1 (list 5 4 1))
(define myList2 (list 6 3))

"merge test cases:"
(equal? empty (merge empty empty))
(equal? myList1 (merge myList1 empty))
(equal? myList2 (merge empty myList2))
(equal? (list 6 5 4 3 1) (merge myList1 myList2))
(equal? (list 6 5 4 3 1) (merge myList2 myList1))

;;a loa is:
;;- empty
;;- (cons <anything> <los>)

;;a tuple is:
;;(list <loa> <loa>)

;;unzip: loa --> tuple
;;unzip returns a list of two lists, with each having half of the members of the given list
(define (unzip a-list)
  (cond [(empty? a-list) (list empty empty)]
        [(cons? a-list)   
         (local
             [(define unzipped (unzip (rest a-list)))]
           (list (cons (first a-list) (second unzipped))
                 (first unzipped)))]))

"unzip test cases:"
(equal? (list empty empty) (unzip empty))
(equal? (list (list 42) empty) (unzip (list 42)))
(equal? (list (list 1 3 5 ) (list 2 4 6)) (unzip (list 1 2 3 4 5 6)))


;; mergesort: list-of-num --> list-of-num
;; sorts the list of num in descending order.
(define (mergesort lon)
  (cond
    [(empty? lon) empty]
    [(cons? lon) 
     (local
         [(define (mergesort_help lon rest_lon dat)
            (cond
              [(empty? rest_lon) (list dat)]
              [(cons? rest_lon) 
               (local
                   [(define unzipped (unzip lon))]
                 (merge (mergesort (first unzipped)) (mergesort (second unzipped))))]))]
       (mergesort_help lon (rest lon) (first lon)))]))


"mergesort test cases:"
(equal? empty (mergesort empty))
(equal? (list 42) (mergesort (list 42)))
(equal? (list 7 6 5 4 3 2 1 ) (mergesort (list 3 5 2 1 6 4 7)))



;; 1b.
;; mergesort2: list-of-num --> list-of-num
;; sorts the list of num in descending order.
(define (mergesort2 lon)
  (local
      [(define (merge lon1 lon2)
         (local
             [(define (help lon1 lon2)
                (cond 
                  [(empty? lon2) lon1]
                  [(cons? lon2) (cond
                                  [(> (first lon1) (first lon2)) (cons (first lon1) (merge (rest lon1) lon2))]
                                  [else (cons (first lon2) (merge lon1 (rest lon2)))])]))
              ]
           (cond 
             [(empty? lon1) lon2]
             [(cons? lon1) (help lon1 lon2)])))
       
       (define (unzip a-list)
         (cond [(empty? a-list) (list empty empty)]
               [(cons? a-list)   
                (local
                    [(define unzipped (unzip (rest a-list)))]
                  (list (cons (first a-list) (second unzipped))
                        (first unzipped)))]))]
    (cond
      [(empty? lon) empty]
      [(cons? lon) 
       (local
           [(define (mergesort_help lon rest_lon dat)
              (cond
                [(empty? rest_lon) (list dat)]
                [(cons? rest_lon)                
                 (local
                     [(define unzipped (unzip lon))]
                   (merge (mergesort (first unzipped)) (mergesort (second unzipped))))]))]
         (mergesort_help lon (rest lon) (first lon)))])))


"mergesort2 test cases:"
(equal? empty (mergesort2 empty))
(equal? (list 42) (mergesort2 (list 42)))
(equal? (list 7 6 5 4 3 2 1 ) (mergesort2 (list 3 5 2 1 6 4 7)))



;; 2a. 
(define-struct Sorter (split join))

(define merger (make-Sorter unzip merge))

;; sort: list-of-num, Sorter --> list-of-num
;; sorts the list of num in descending order using 
;; a specified sortor.
(define (sort lon sorter)
  (cond
    [(empty? lon) empty]
    [(cons? lon) 
     (local
         [(define (sort_help lon rest_lon dat)
            (cond
              [(empty? rest_lon) (list dat)]
              [(cons? rest_lon) (local
                                    [(define splitter ((Sorter-split sorter) lon))]
                                  ((Sorter-join sorter) 
                                   (sort (first splitter) sorter) 
                                   (sort (second splitter) sorter)))]))]
       (sort_help lon (rest lon) (first lon)))]))

"sort test cases, merge:"
(equal? empty (sort empty merger))
(equal? (list 42) (sort (list 42) merger))
(equal? (list 7 6 5 4 3 2 1 ) (sort (list 3 5 2 1 6 4 7) merger))



;;2b. 

;; insert-split: lon -> lon, lon
;; splits one list into two lists with the first list containing the first number in the 
;; original list and the second list contains the rest of the numbers in the orginal
;; list

(define (insert-split lon)  
  (cond [(empty? lon) (list empty empty)]
        [else (list (list (first lon)) (rest lon))]))
 
;; insert-join: lon, lon -> lon
;; creates a list of numbers in descending order
(define (insert-join lon1 lon2)
  (cond
       [(empty? lon2) lon1]
       [(cons? lon2) 
        (cond  [(> (first lon2) (first lon1)) (cons (first lon1) lon2)]
               [else 
                (cons (first lon2) ((Sorter-join insertioner) lon1 (rest lon2)))])]))

;; insertion sort

(define insertioner (make-Sorter insert-split insert-join))

"sort test cases, insertioner:"
(equal? empty (sort empty insertioner))
(equal? (list 42) (sort (list 42) insertioner))
(equal? (list 1 2 3 4 5 6 7 ) (sort (list 3 5 2 1 6 4 7) insertioner))




;; 2c
;; lambda version of insertion
(define insertioner2 
  (make-Sorter
   (lambda (lon)
     (list (list (first lon)) (rest lon)))
   (lambda (lon1 lon2)
     (cond
       [(empty? lon2) lon1]
       [(cons? lon2) 
        (cond  [(> (first lon2) (first lon1)) (cons (first lon1) lon2)]
               [else 
                (cons (first lon2) ((Sorter-join insertioner2) lon1 (rest lon2)))])]))))

"sort test cases, insertioner2:"
(equal? empty (sort empty insertioner2))
(equal? (list 42) (sort (list 42) insertioner2))
(equal? (list 1 2 3 4 5 6 7 ) (sort (list 3 5 2 1 6 4 7) insertioner2))


;; 2d
;; lambda version of merge
(define merger2 
  (make-Sorter 
   (lambda (lon)
     (cond 
       [(empty? lon) (list empty empty)]
       [(cons? lon)   
        (local
            [(define unzipped ((Sorter-split merger2) (rest lon)))]
          (list (cons (first lon) (second unzipped))
                (first unzipped)))]))
   
   (lambda (lon1 lon2)
     (local
         [(define (merge_help lon1 lon2)
            (cond 
              [(empty? lon2) lon1]
              [(cons? lon2) 
               (cond
                 [(> (first lon1) (first lon2)) (cons (first lon1) ((Sorter-join merger2) (rest lon1) lon2))]
                 [else (cons (first lon2) ((Sorter-join merger2) lon1 (rest lon2)))])]))]
       (cond 
         [(empty? lon1) lon2]
         [(cons? lon1) (merge_help lon1 lon2)])))
   ))

"sort test cases, merge:"
(equal? empty (sort empty merger2))
(equal? (list 42) (sort (list 42) merger2))
(equal? (list 10 7 6 5 4 3 2 1 ) (sort (list 3 5 2 1 6 4 7 10) merger2))



;; 2e. 

;; sort: list-of-num, Sorter, comparison-function --> list-of-num
;; sorts the list of num in the order specified by the comparison
;; function.
(define (sort3 lon sorter comp)
  (cond
    [(empty? lon) empty]
    [(cons? lon) 
     (local
         [(define (sort_help lon rest_lon dat)
            (cond
              [(empty? rest_lon) (list dat)]
              [(cons? rest_lon) (local
                                    [(define splitter ((Sorter-split sorter) lon comp))]
                                  ((Sorter-join sorter) 
                                   (sort3 (first splitter) sorter comp) 
                                   (sort3 (second splitter) sorter comp)
                                   comp))]))]
       (sort_help lon (rest lon) (first lon)))]))


(define merger3 
  (make-Sorter 
   (lambda (lon comp)
     (cond 
       [(empty? lon) (list empty empty)]
       [(cons? lon)   
        (local
            [(define unzipped ((Sorter-split merger3) (rest lon) comp))]
          (list (cons (first lon) (second unzipped))
                (first unzipped)))]))
   
   (lambda (lon1 lon2 comp)
     (local
         [(define (merge_help lon1 lon2)
            (cond 
              [(empty? lon2) lon1]
              [(cons? lon2) 
               (cond
                 [(comp (first lon1) (first lon2)) (cons (first lon1) ((Sorter-join merger3) (rest lon1) lon2 comp))]
                 [else (cons (first lon2) ((Sorter-join merger3) lon1 (rest lon2) comp))])]))]
       (cond 
         [(empty? lon1) lon2]
         [(cons? lon1) (merge_help lon1 lon2)])))
   ))

"sort test cases, merge:"
(equal? empty (sort3 empty merger3 >))
(equal? (list 42) (sort3 (list 42) merger3 >))
(equal? (list 1 2 3 4 5 6 7 ) (sort3 (list 3 5 2 1 6 4 7) merger3 <))
(equal? empty (sort3 empty merger3 <))
(equal? (list 42) (sort3 (list 42) merger3 <))
(equal? (list 7 6 5 4 3 2 1 ) (sort3 (list 3 5 2 1 6 4 7) merger3 >))


(define insertioner3 
  (make-Sorter
   (lambda (lon comp)
     (list (list (first lon)) (rest lon)))
   (lambda (lon1 lon2 comp)
     (cond
       [(empty? lon2) lon1]
       [(cons? lon2) 
        (cond  [(comp (first lon2) (first lon1)) (cons (first lon1) lon2)]
               [else 
                (cons (first lon2) ((Sorter-join insertioner3) lon1 (rest lon2) comp))])]))))

"sort test cases, insertion:"
(equal? empty (sort3 empty insertioner3 <))
(equal? (list 42) (sort3 (list 42) insertioner3 <))
(equal? (list 7 6 5 4 3 2 1 ) (sort3 (list 3 5 2 1 6 4 7) insertioner3 <))
(equal? empty (sort3 empty insertioner3 >))
(equal? (list 42) (sort3 (list 42) insertioner3 >))
(equal? (list 1 2 3 4 5 6 7) (sort3 (list 3 5 2 1 6 4 7) insertioner3 >))



;; 2f

"string test cases, insertion:"
(equal?(list "Albert" "David" "Donald" "Ken" "Kyle" "Martha" "Stephen") 
       (sort3 (list "David" "Donald" "Albert" "Ken" "Kyle" "Stephen" "Martha") insertioner3 string>?))

(equal?(list "Stephen" "Martha" "Kyle" "Ken" "Donald" "David" "Albert")
       (sort3 (list "David" "Donald" "Albert" "Ken" "Kyle" "Stephen" "Martha") insertioner3 string<?))

"string test cases, merger:"
(equal?(list "Albert" "David" "Donald" "Ken" "Kyle" "Martha" "Stephen") 
       (sort3 (list "David" "Donald" "Albert" "Ken" "Kyle" "Stephen" "Martha") merger3 string<?))

(equal?(list "Stephen" "Martha" "Kyle" "Ken" "Donald" "David" "Albert")
       (sort3 (list "David" "Donald" "Albert" "Ken" "Kyle" "Stephen" "Martha") merger3 string>?))



;;2g - Extra Credit

;; tail-recursive implemenation
(define bubbler 
  (make-Sorter
   (lambda (lon comp)
     (local
         [(define (helper lon min l)
            (cond
              [(empty? lon) (list (cons min empty) l)]
              [(cons? lon) (cond
                             [(comp (first lon) min) (helper (rest lon) min (append (list (first lon)) l))]
                             [else (helper (rest lon) (first lon) (append (list min) l))])]))]
       (helper (rest lon) (first lon) empty)))
   (lambda (lon1 lon2 comp)
     (append lon1 lon2))))

"sort test cases, bubbler:"
(equal? empty (sort3 empty bubbler <))
(equal? (list 42) (sort3 (list 42) bubbler <))
(equal? (list 7 6 5 4 3 2 1 ) (sort3 (list 3 5 2 1 6 4 7) bubbler <))
(equal? empty (sort3 empty bubbler >))
(equal? (list 42) (sort3 (list 42) bubbler >))
(equal? (list 1 2 3 4 5 6 7) (sort3 (list 3 5 2 1 6 4 7) bubbler >))

;; non-tail recursive implementation
(define bubbler2 
  (make-Sorter
   (lambda (lon comp)
     (local
         [(define (helper lon min)
            (cond
              [(empty? lon) (list (cons min empty) empty)]
              [(cons? lon) (cond
                             [(comp (first lon) min) (local [(define result (helper (rest lon) min))]
                                                       (list (first result) (cons (first lon) (second result))))]
                             [else (local [(define result (helper (rest lon) (first lon)))]
                                     (list (first result) (cons min (second result)))) ])]))]
       (helper (rest lon) (first lon))))
   (lambda (lon1 lon2 comp)
     (append lon1 lon2))))

"sort test cases, bubbler2:"
(equal? empty (sort3 empty bubbler2 <))
(equal? (list 42) (sort3 (list 42) bubbler2 <))
(equal? (list 7 6 5 4 3 2 1 ) (sort3 (list 3 5 2 1 6 4 7) bubbler2 <))
(equal? empty (sort3 empty bubbler2 >))
(equal? (list 42) (sort3 (list 42) bubbler2 >))
(equal? (list 1 2 3 4 5 6 7) (sort3 (list 3 5 2 1 6 4 7) bubbler2 >))

"String sorting tests:"
(equal?(list "Albert" "David" "Donald" "Ken" "Kyle" "Martha" "Stephen") 
       (sort3 (list "David" "Donald" "Albert" "Ken" "Kyle" "Stephen" "Martha") bubbler string>?))

(equal?(list "Stephen" "Martha" "Kyle" "Ken" "Donald" "David" "Albert")
       (sort3 (list "David" "Donald" "Albert" "Ken" "Kyle" "Stephen" "Martha") bubbler string<?))