#lang racket
(require csc151)
(require csc151/counters)
(provide (all-defined-out))

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

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

;;; Procedure:
;;;   insert-number
;;; Parameters:
;;;   sorted, a list of real numbers
;;;   new-element, a real number
;;; Purpose:
;;;   Insert new-element into sorted.
;;; Produces:
;;;   new-ls, a new list of real numbers
;;; Preconditions:
;;;   sorted is a list of numbers arranged in increasing order.   That is,
;;;   (<= (list-ref sorted i) (list-ref sorted (+ i 1)))
;;;   for all reasonable values of i.  [Unverified]
;;; Postconditions:
;;;   * new-ls is a list of numbers arranged in increasing order.
;;;   * new-ls is a permutation of (cons new-element sorted).
(define insert-number
  (lambda (sorted new-element)
    (cond 
      [(null? sorted) 
       (list new-element)]
      [(<= new-element (car sorted)) 
       (cons new-element sorted)]
      [else 
       (cons (car sorted) 
             (insert-number (cdr sorted) new-element))])))

;;; Procedure:
;;;   numbers-insertion-sort
;;; Parameters:
;;;   numbers, a list of real numbers
;;; Purpose:
;;;   Sorts numbers
;;; Produces:
;;;   sorted, a list of real numbers
;;; Preconditions:
;;;   [none]
;;; Postconditions:
;;;   * sorted is a list of real numbers.
;;;   * sorted is organized in increasing order.  That is, 
;;;     (<= (list-ref sorted i) (list-ref sorted (+ i 1)))
;;;     for all reasonable values of i.
;;;   * sorted is a permutation of numbers.
(define numbers-insertion-sort
  (lambda (numbers)
    (let kernel ([unsorted numbers]  ; The remaining unsorted values
                 [sorted null])      ; The sorted values
      (if (null? unsorted) 
          sorted
          (kernel (cdr unsorted) (insert-number sorted (car unsorted)))))))

;;; Procedure:
;;;   list-insertion-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.
;;; Postconditions:
;;;   * sorted is sorted.  That is, for all reasonable i,
;;;     (may-precede? (list-ref lst i) (list-ref lst (increment i)))
;;;   * sorted is a permutation of lst.
(define list-insertion-sort
  (lambda (lst may-precede?)
    (letrec ([insert
              (lambda (lst val)
                (cond
                  [(null? lst)
                   (list val)]
                  [(may-precede? val (car lst))
                   (cons val lst)]
                  [else
                   (cons (car lst) (insert (cdr lst) val))]))]
             [kernel
              (lambda (unsorted sorted)
                (if (null? unsorted) 
                    sorted
                    (kernel (cdr unsorted) (insert sorted (car unsorted)))))])
      (kernel lst null))))

;;; Procedure:
;;;   list-keyed-insertion-sort
;;; Parameters:
;;;   lst, a list
;;;   get-key, a procedure
;;;   may-precede?, a binary predicate
;;; Purpose:
;;;   Sort lst.
;;; Produces:
;;;   sorted, a list
;;; Preconditions:
;;;   * get-key? can be applied to each element of lst.
;;;   * may-precede? can be used with the values returned by get-key. That is 
;;;     for all values a and b in lst, (may-precede? (get-key a) (get-key b)) 
;;;     successfully returns a truth value.
;;;   * may-precede? is transitive.  That is, for all keys a, b, and 
;;;     c, if (may-precede? a b) and (may-precede? b c), then
;;;     (may-precede? a c).
;;;   * may-precede? is sensible.  That is, for all keys a and b,
;;;     (may-precede? a b) holds, (may-precede? b a) holds, or both
;;;     hold.
;;; Postconditions:
;;;   * sorted is sorted by key using may-precede?.  That is, for all i 
;;;     such that 0 <= i < (- (length lst) 1),
;;;     (may-precede? (get-key (list-ref sorted i))
;;;                   (get-key (list-ref sorted (+ i 1))))
;;;   * sorted is a permutation of lst.
(define list-keyed-insertion-sort
  (lambda (lst get-key may-precede?)
    (list-insertion-sort lst
                         (lambda (v1 v2)
                           (may-precede? (get-key v1) (get-key v2))))))

;;; Procedure:
;;;   vector-insert!
;;; Parameters:
;;;   vec, a vector of values
;;;   new-element, a value
;;;   boundary, an index into the vector
;;;   may-precede?, a binary predicate
;;; Purpose:
;;;   Insert new-element into the portion of vec between 0 and
;;;   boundary, inclusive.
;;; Produces:
;;;   [Nothing; called for side effects.]
;;; Preconditions:
;;;   * 0 <= boundary < (vector-length vec)
;;;   * The elements in positions 0..boundary-1 of vec are sorted.
;;;     That is, (may-precede? (vector-ref vec i) (vector-ref vec (+ i 1)))
;;;     for all 0 <= i < boundary-2.
;;;   * may-precede? is transitive and sensible.
;;; Postconditions:
;;;   * The elements in positions 0..boundary of vec are sorted.
;;;     That is, (may-precede? (vector-ref vec i) (vector-ref vec (+ i 1)))
;;;     for all 0 <= i < boundary.
;;;   * The elements in positions 0..boundary of vec after insert! finishes
;;;     are a permutation of new-element and the elements that were in 
;;;     positions 0..(boundary-1) before the procedure started.
(define vector-insert!
  (lambda (vec new-element boundary may-precede?)
    (let kernel ((pos boundary))
      (cond 
        ; If we've reached the left end of the vector, we've run out of
        ; elements to shift.  Insert the new element.
        [(zero? pos)  
         (vector-set! vec pos new-element)]
        ; If we've reached a point at which the element to the left
        ; is smaller, we insert the new element here.
        [(may-precede? (vector-ref vec (- pos 1)) new-element)
         (vector-set! vec pos new-element)]
        ; Otherwise, we shift the current element to the right and
        ; continue.
        [else
         (vector-set! vec pos (vector-ref vec (- pos 1)))
         (kernel (- pos 1))]))))

;;; Procedure:
;;;   vector-insertion-sort!
;;; Parameters:
;;;   vec, a vector 
;;;   may-precede?, a binary predicate
;;; Purpose:
;;;   Sorts the vector.
;;; Produces:
;;;   [Nothing; sorts in place]
;;; Preconditions:
;;;   vec is a vector.
;;;   may-precede? can be applied to any two elements of vec.
;;;   may-precede? is transitive.
;;; Postconditions:
;;;   The final state of vec is a permutation of the original state.
;;;   vec is sorted.  That is, 
;;;     (may-precede? (vector-ref vec i) (vector-ref vec (+ i 1)))
;;;     for all reasonable values of i.
(define vector-insertion-sort!
  (lambda (vec may-precede?)
    (let ([len (vector-length vec)])
      (let kernel ([boundary 1]) ; The index of the first unsorted value
        (when (< boundary len) ; If we have elements left to sort
          (vector-insert! vec 
                          (vector-ref vec boundary) 
                          boundary
                          may-precede?)
          (kernel (+ boundary 1)))))))

; +------+---------------------------------------------------------------------
; | Data |
; +------+

;;; Values:
;;;   grinnell-directory
;;;   grinnell-directory-annotated
;;; Type:
;;;   List of lists.
;;; Note:
;;;   * Each sublist is of length at least four and contains a last
;;;     name, a first name, a username, a phone number, and an
;;;     optional sequence of annotations.
;;;   * The
;;; Contents:
;;;   A list of people at Grinnell with contact information and some
;;;   useful attributes.
(define grinnell-directory
  (list
   (list "Rebelsky"        "Samuel"  "messy-office" "4410")
   (list "Klinge"          "Titus"   "cauldron"     "3271")
   (list "Osera"           "Michael" "peter"        "4010")
   (list "Weinman"         "Jerod"   "map-reader"   "9812")
   (list "Osera"           "PM"      "type-snob"    "4010")
   (list "Curtsinger"      "Charlie" "systems-guy"  "3127")
   (list "Vostinar"        "Anya"    "cache"        "4306")
   (list "Rebelsky"        "Spam"    "emailer"      "4410")
   (list "Osera"           "MP"      "fast-typist"  "4010")
   (list "Dahlby-Albright" "Sarah"   "cheery-coach" "4362")
   (list "Osera"           "Peter"   "michael"      "4010")
   (list "Rodrigues"       "Liz"     "vivero"       "3362")
   (list "Rebelsky"        "Essay"   "muser"        "4410")
   (list "Barks"           "Sarah"   "stem-careers" "4940")
   (list "Kington"         "Raynard" "the-prez"     "3000")))

(define grinnell-directory-annotated
  (list
   (list "Rebelsky"        "Samuel"  "messy-office" "4410"
         "CSC" "151prof" "DigHum" "Professor")
   (list "Osera"           "Michael" "peter"        "4010"
         "CSC" "fictitious")
   (list "Klinge"          "Titus"   "cauldron"     "3271"
         "CSC" "Assistant" "151prof")
   (list "Weinman"         "Jerod"   "map-reader"   "9812"
         "CSC" "Chair" "Associate" "NSF Grant")
   (list "Osera"           "PM"      "type-snob"    "4010"
         "Assistant" "NSF Grant" "Tutorial" "CSC")
   (list "Curtsinger"      "Charlie" "systems-guy"  "3127"
         "CSC" "Assistant" "Tutorial" "ASFAC")
   (list "Vostinar"        "Anya"    "cache"        "4306"
         "CSC" "Assistant" "Interdisciplinary")
   (list "Rebelsky"        "Spam"    "emailer"      "4410"
         "CSC" "fictitious")
   (list "Osera"           "MP"      "fast-typist"  "4010"
         "CSC" "fictitious")
   (list "Dahlby-Albright" "Sarah"   "cheery-coach" "4362"
         "Statistics" "CSC" "Outreach")
   (list "Osera"           "Peter"   "michael"      "4010"
         "CSC" "fictitious")
   (list "Rodrigues"       "Liz"     "vivero"       "3362"
         "LIB" "DigHum" "Assistant" )
   (list "Rebelsky"        "Essay"   "muser"        "4410"
         "CSC" "fictitious")
   (list "Barks"           "Sarah"   "stem-careers" "4940"
         "CLS" "STEM" "Neuroscience")
   (list "Kington"         "Raynard" "the-prez"     "3000"
         "Bigwig")))

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