#lang racket
(require gigls/unsafe)
(provide (all-defined-out))

;;; File:
;;;   mergesort-lab.rkt
;;; Authors:
;;;   Janet Davis
;;;   Samuel A. Rebelsky
;;;   Jerod Weinman
;;;   YOUR NAME HERE
;;; Summary:
;;;   Starting code for the lab on merge sort.

; +---------------------+------------------------------------------------------
; | Procedures Provided |
; +---------------------+

;;; Procedure:
;;;   merge
;;; Parameters:
;;;   sorted1, a sorted list.
;;;   sorted2, a sorted list.
;;;   may-precede?, a binary predicate that compares values.
;;; Purpose:
;;;   Merge the two lists.
;;; Produces:
;;;   sorted, a sorted list.
;;; Preconditions:
;;;   may-precede? can be applied to any two values from
;;;     sorted1 and/or sorted2.
;;;   may-precede? represents a transitive operation.
;;;   sorted1 is sorted by may-precede? That is, for each i such that
;;;     0 <= i < (length sorted1)
;;;       (may-precede? (list-ref sorted1 i) (list-ref sorted1 (+ i 1)))
;;;   sorted2 is sorted by may-precede? That is, for each i such that
;;;     0 <= j < (length sorted2)
;;;       (may-precede? (list-ref sorted2 j) (list-ref sorted2 (+ j 1)))
;;; Postconditions:
;;;   sorted is sorted by may-precede?.
;;;     For each k, 0 <= k < (length sorted)
;;;       (may-precede? (list-ref sorted k) (list-ref sorted (+ k 1)))
;;;   sorted is a permutation of (append sorted1 sorted2)
;;;   Does not affect sorted1 or sorted2.
;;;   sorted may share cons cells with sorted1 or sorted2.
(define merge
  (lambda (sorted1 sorted2 may-precede?)
    (cond
      ; If the first list is empty, return the second
      ((null? sorted1) sorted2)
      ; If the second list is empty, return the first
      ((null? sorted2) sorted1)
      ; If the first element of the first list is smaller or equal,
      ; make it the first element of the result and recurse.
      ((may-precede? (car sorted1) (car sorted2))
       (cons (car sorted1) 
             (merge (cdr sorted1) sorted2 may-precede?)))
      ; Otherwise, do something similar using the first element
      ; of the second list
      (else
       (cons (car sorted2) 
             (merge sorted1 (cdr sorted2) may-precede?))))))

;;; Procedure:
;;;   split
;;; Parameters:
;;;   lst, a list
;;; Purpose:
;;;   Split a list into two nearly-equal halves.
;;; Produces:
;;;   halves, a list of two lists
;;; Preconditions:
;;;   lst is a list.
;;; Postconditions:
;;;   halves is a list of length two.
;;;   Each element of halves is a list (which we'll refer to as
;;;     firsthalf and secondhalf).
;;;   lst is a permutation of (append firsthalf secondhalf).
;;;   The lengths of firsthalf and secondhalf differ by at most 1.
;;;   Does not modify lst.
;;;   Either firsthalf or secondhalf may share cons cells with lst.
(define split
  (lambda (lst)
    ;;; kernel
    ;;;   Remove the first count elements of a list.  Return the
    ;;;   pair consisting of the removed elements (in order) and
    ;;;   the remaining elements.
    (let kernel ((remaining lst) ; Elements remaining to be used
                 (removed null)  ; Accumulated initial elements 
                 (count          ; How many elements left to use
                  (quotient (length lst) 2)))
      ; If no elements remain to be used,
      (if (= count 0)
          ; The first half is in removed and the second half
          ; consists of any remaining elements.
          (list (reverse removed) remaining)
          ; Otherwise, use up one more element.
          (kernel (cdr remaining)
                  (cons (car remaining) removed)
                  (- count 1))))))

;;; Procedures:
;;;   merge-sort
;;;   new-merge-sort
;;; Parameters:
;;;   lst, a list to be sorted
;;;   may-precede?, a binary predicate
;;; Purpose:
;;;   Sort lst.
;;; Produces:
;;;   sorted, a list.
;;; Preconditions:
;;;   may-precede? can be used with the elements of lst. That is for
;;;     all values a and b in lst, (may-precede? a b) successfully
;;;     returns a truth value.
;;;   may-precede? is transitive.  That is, for all values a, b, and 
;;;     c in lst, if (may-precede? a b) and (may-precede? b c), then
;;;     (may-precede? a c).
;;;   may-precede? is sensible.  That is, for all values a and b,
;;;     either (may-precede? a b), (may-precede? b a), or both.
;;; Preconditions:
;;;   may-precede? can be used with the elements of lst. That is for
;;;     all values a and b in lst, (may-precede? a b) successfully
;;;     returns a truth value.
;;;   may-precede? is transitive.  That is, for all values a, b, and 
;;;     c in lst, if (may-precede? a b) and (may-precede? b c), then
;;;     (may-precede? a c).
;;;   may-precede? is sensible.  That is, for all values a and b,
;;;     either (may-precede? a b), (may-precede? b a), or both.

(define merge-sort
  (lambda (lst may-precede?)
    ; If there are only zero or one elements in the list,
    ; the list is already sorted.
    (if (or (null? lst) (null? (cdr lst)))
        lst
        ; Otherwise, 
        ;   split the list in half,
        ;   sort each half,
        ;   and then merge the sorted halves.
        (let* ([halves (split lst)]
               [some (car halves)]
               [rest (cadr halves)])
          (merge (merge-sort some may-precede?)
                 (merge-sort rest may-precede?)
                 may-precede?)))))

(define new-merge-sort
  (lambda (lst may-precede?)
    (letrec (; Merge neighboring pairs in a list of lists
             [merge-pairs
              (lambda (list-of-lists)
                (cond
                  ; Base case: Empty list.
                  ((null? list-of-lists) null)
                  ; Base case: Single-element list (nothing to merge)
                  ((null? (cdr list-of-lists)) list-of-lists)
                  ; Recursive case: Merge first two and continue
                  (else (cons (merge (car list-of-lists) (cadr list-of-lists)
                                     may-precede?)
                              (merge-pairs (cddr list-of-lists))))))]
             ; Repeatedly merge pairs
             [repeat-merge
              (lambda (list-of-lists)
                ; Show what's happening
                ; (write list-of-lists) (newline)
                ; If there's only one list in the list of lists
                (if (null? (cdr list-of-lists))
                    ; Use that list
                    (car list-of-lists)
                    ; Otherwise, merge neighboring pairs and start again.
                    (repeat-merge (merge-pairs list-of-lists))))])
      (repeat-merge (map list lst)))))

;;; Procedure:
;;;   random-numbers
;;; Parameters:
;;;   n, a non-negative integer
;;; Purpose:
;;;   Create a list of n "random" integers, each in the range
;;;   [0..999].
;;; Produces:
;;;   numbers, a list.
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (length numbers) = n
;;;   For each reasonable i,
;;;     0 <= (list-ref numbers i) < 1000
(define random-numbers
  (lambda (n)
    (if (zero? n)
        null
        (cons (random 1000) (random-numbers (- n 1))))))

; +--------------------------------+----------------------------------
; | Generalized Counter Procedures |
; +--------------------------------+

;;; Procedure:
;;;   counter-new
;;; Parameters:
;;;   name, a string
;;; Purpose:
;;;   Create a counter associated with the given name.
;;; Produces:
;;;   counter, a counter
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   counter can be used as a parameter to the various counter
;;;   procedures.
;;; Process:
;;;   Counters are two element vectors.  Element 0 is the name, and
;;;   should not change.  Element 1 is the count, and should change.
(define counter-new
  (lambda (name)
    (vector name 0)))

;;; Procedure:
;;;   counter-count!
;;; Parameters:
;;;   counter, a counter 
;;; Purpose:
;;;   count the counter
;;; Produces:
;;;   counter, the same counter, now mutated
;;; Preconditions:
;;;   counter was created by counter-new (or something similar) and
;;;   has only been modified by the counter procedures.
;;; Postconditions:
;;;   (counter-get counter) gives a number one higher than it 
;;;   did before.
(define counter-count!
  (lambda (counter)
    (vector-set! counter 1 (+ 1 (vector-ref counter 1)))
    counter))

;;; Procedure:
;;;   counter-get
;;; Parameters:
;;;   counter, a counter
;;; Purpose:
;;;   Get the number of times that counter-count! has been called
;;;   on this counter.
;;; Produces:
;;;   count, a non-negative integer
;;; Preconditions:
;;;   counter was created by counter-new and has only been modified
;;;   by the counter procedures.
;;; Postconditions:
;;;   count is the number of calls to counter-new on this counter since
;;;   the last call to counter-reset! on this counter, or since the
;;;   counter was created, if there have been no calls to counter-reset!
(define counter-get
  (lambda (counter)
    (vector-ref counter 1)))

;;; Procedure:
;;;   counter-reset!
;;; Parameters:
;;;   counter, a counter 
;;; Purpose:
;;;   reset the counter
;;; Produces:
;;;   counter, the same counter, now set to 0
;;; Preconditions:
;;;   counter was created by counter-new (or something similar) and
;;;   has only been modified by the other counter procedures.
;;; Postconditions:
;;;   (counter-get counter) gives 0.
(define counter-reset!
  (lambda (counter)
    (vector-set! counter 1 0)
    counter))

;;; Procedure:
;;;   counter-print!
;;; Parameters:
;;;   counter, a counter
;;; Purpose:
;;;   Print out the information associated with the counter.
;;; Produces:
;;;   counter, the same counter
;;; Preconditions:
;;;   counter was created by counter-new and has only been modified
;;;   by the various counter procedures.
;;; Postconditions:
;;;   counter is unchanged.
;;;   The output port now contains information on counter.
;;; Ponderings:
;;;   Why does counter-print! have a bang, given that it doesn't mutate
;;;   it's parameter?  Because it mutates the broader environment - we
;;;   call counter-print! not to compute a value, but to print something.
(define counter-print!
  (lambda (counter)
    (display (vector-ref counter 0))
    (display ": ")
    (display (vector-ref counter 1))
    (newline)))

; +-------+--------------------------------------------------------------------
; | Added |
; +-------+