;; qsort-library.ss
;;
;; export:
;;
;; fori= : (num num num (num -> void) -> void)
;; (* perform some action for some range of numbers *)
;;
;; partition : ((vector num) num num num -> (list num num))
;; (* Description of partition:
;;  (partition v left right pivot)
;;  Input:
;;    v is a vector of numbers,
;;    pivot is a number,
;;    left, right are indices such that
;;       left..right-1 are valid for v
;;      (NOTE that right should be one more than the
;;       last index you want partitioned!  This
;;       convention for index ranges is often convenient;
;;       consider the meanings of the return value, below.)
;;
;;  Effect: The elements of v from left...right-1
;;    may be re-arranged, subject to the below.
;;
;;  Return: (list s1 s2), where s1, s2  are
;;    indices such that the following holds:
;;    Locations left..s1-1    of v are < pivot,
;;    locations   s1..s2-1    of v are = pivot,
;;    locations   s2..right-1 of v are > pivot.
;;    Warning:  In general,
;;    s1-1 might be left-1 (if all elements of v > pivot), and
;;    s2 might be right    (if all elements of v < pivot);
;;    these might not be legal indices.
;;  End description of partition *)
;;
;; hidden:
;;   sweep-left : ((vector X) num num (X -> boolean) -> num)
;;   (* shuffle the vector 

(unit/sig (partition fori=)
  (import plt:userspace^)

;; (partition v left right pivot)
;; See above for description.
;;
;; Algorithm: First sweep all values < pivot
;; to the left of location s1.
;; Then sweep all values from s1..right-1
;; which are =pivot to the left.
;; Watch out for s1=right.
;;
(define  (partition v left right pivot)
  (let* ((s1 (sweep-left v left right 
			 (lambda (n) (< n pivot))))
         (s2 (if (< s1 right)
		 (sweep-left v s1 right
			     (lambda (n) (= n pivot)))
		 s1)))
    (list s1 s2)))

  
;; (sweep-left v l r p?)
;; v is a vector
;; l,r are indices such that l..r-1 are legal indices of v,
;; and r > l.
;; p? is a function from elements of v to boolean.
;;
;; Side effect: shuffle elements of v in range l..r-1
;;
;; Return an index s, such that:
;; elements l..s-1 of v meet p?
;; elements s..r-1 of v fail p?
;;
;; Caution: s might be l or r.
;;
(define (sweep-left v l r p?)
  (let* ((r-1 (- r 1))
	 (leftVal (vector-ref v l)))
    (cond ((= l r-1) (if (p? leftVal) r l))
	  ((p? leftVal)
	   (sweep-left v (+ l 1) r p?))
	  (else  ;; not (p? leftVal)
	   (begin (vector-set! v l (vector-ref v r-1))
		  (vector-set! v r-1 leftVal)
		  (sweep-left v l r-1 p?))))))
  
(define (fori= start end step p)
  (if (>= start end) (void) 
      (begin (p start) (fori= (+ start step) end step p))))


;; End unit/sig
)