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

;;; File:
;;;   insertion-sort-lab.rkt
;;; Authors:
;;;   Janet Davis
;;;   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]
;;;   new-element is a number. [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.
;;; 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 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
        (cond
          [(< boundary len) ; If we have elements left to sort
           (vector-insert! vec 
                           (vector-ref vec boundary) 
                           boundary
                           may-precede?)
           (kernel (+ boundary 1))]
          [else
           vec])))))

; +--------------------------------+----------------------------------
; | 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)))

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

(define drawing
  (list (list "circ1" "ellipse" "red" 10 10 80 80)
        (list "thin" "ellipse" "blue" 10 80 300 10)
        (list "tall" "rectangle" "green" 80 5 100 2)
        (list "ys1" "rectangle" "yellow" 0 50 10 10)
        (list "ys2" "rectangle" "yellow" 0 50 20 20)
        (list "ys3" "rectangle" "yellow" 0 55 30 30)
        (list "ys4" "rectangle" "yellow" 0 60 40 40)
        (list "ys5" "rectangle" "yellow" 0 65 50 50)
        (list "ys6" "rectangle" "yellow" 0 70 60 60)
        (list "rc" "ellipse" "red" 100 100 30 30)
        (list "oc" "ellipse" "orange" 90 110 30 30)
        (list "yc" "ellipse" "yellow" 80 120 30 30)
        (list "gc" "ellipse" "green" 80 130 30 30)
        (list "bc" "ellipse" "blue" 90 140 30 30)
        (list "ic" "ellipse" "indigo" 100 150 30 30)
        (list "vc" "ellipse" "violet" 110 160 30 30)
        (list "last" "rectangle" "white" 0 0 1 1)))

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