#!/usr/bin/guile \
-e main -s
!#
;;; Copyright 2005 Daniel Cer (daniel.cer@cs.colorado.edu)
;;;
;;; This work is licensed under the Creative Commons Attribution-NonCommercial-
;;; ShareAlike License. To view a copy of this license, visit 
;;; http://creativecommons.org/licenses/by-nc-sa/2.5/ or send a letter to 
;;; Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 
;;; 94105, USA.

; read-entries - read in a list of new-line seperated numbers from an
; input-port.
(define (read-entries port) (let ((in-line (read-line port)))
  (if (eof-object? in-line) '()
      (append (list (string->number in-line)) (read-entries port)))))

; insertion-sort - returns a list with all of the items in the list 'entries'
; but with the items in ascending order
(define (insertion-sort entries)
  (let ((entries-vec (list->vector entries)) (entries-len (length entries)))
  (let sort-loop ((i 1) (j 0) (value (car (cdr entries))))

  ; first check to see if we're done yet, if so return the sorted list
  (if (equal? entries-len i) (vector->list entries-vec) 

  ; otherwise - there are still items left to be inserted. so, we must search 
  ; for the approprate place to do the insertion
  (if (<= (vector-ref entries-vec j) value)
     ; value should be inserted at position j+1
     (begin (vector-set! entries-vec (+ j 1) value) (sort-loop (+ i 1) i 
        (vector-ref entries-vec (min (+ i 1) (- entries-len 1)))))
     ; else - keep looking for where to insert 'value'
     (begin (vector-set! entries-vec (+ j 1) (vector-ref entries-vec j))
        (if (equal? j 0) 
           ; we've reached the start of the array, so insert 'value' here
           (begin  (vector-set! entries-vec 0 value) (sort-loop (+ i 1) i 
              (vector-ref entries-vec (min (+ i 1) (- entries-len 1)))))
           ; else - continue in inner loop
           (sort-loop i (- j 1) value))))))))

(define (main args) (if (not (equal? (length args) 2)) 
  (display
     (string-append "Usage:\n\t" (car args) " (file with numbers to sort)\n"))
  (map (lambda (entry) (display entry) (newline)) ; display the sorted list
    (insertion-sort                               ; sort everything
    (call-with-input-file (car (cdr args)) read-entries)) ; read in the items
)))