;;; File:
;;;   insertion-sort-lab.scm
;;; 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 numbers
;;; 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))))))

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