URL
https://opencores.org/ocsvn/scarts/scarts/trunk
Subversion Repositories scarts
[/] [scarts/] [trunk/] [toolchain/] [scarts-binutils/] [binutils-2.19.1/] [cgen/] [slib/] [sort.scm] - Rev 6
Compare with Previous | Blame | View Log
;;; "sort.scm" Defines: sorted?, merge, merge!, sort, sort! ;;; Author : Richard A. O'Keefe (based on Prolog code by D.H.D.Warren) ;;; Updated: 11 June 1991 ;;; Modified for scheme library: Aubrey Jaffer 19 Sept. 1991 ;;; (sorted? sequence less?) ;;; is true when sequence is a list (x0 x1 ... xm) or a vector #(x0 ... xm) ;;; such that for all 1 <= i <= m, ;;; (not (less? (list-ref list i) (list-ref list (- i 1)))). ;;; (merge a b less?) ;;; takes two lists a and b such that (sorted? a less?) and (sorted? b less?) ;;; and returns a new list in which the elements of a and b have been stably ;;; interleaved so that (sorted? (merge a b less?) less?). ;;; Note: this does _not_ accept vectors. See below. ;; The loop handles the merging of non-empty lists. It has ;; been written this way to save testing and car/cdring. ;; x <= y ;;; (merge! a b less?) ;;; takes two sorted lists a and b and smashes their cdr fields to form a ;;; single sorted list including the elements of both. ;;; Note: this does _not_ accept vectors. ;; (car a) <= (car b) ; (car a) <= (car b) ;;; (sort! sequence less?) ;;; sorts the list or vector sequence destructively. It uses a version ;;; of merge-sort invented, to the best of my knowledge, by David H. D. ;;; Warren, and first used in the DEC-10 Prolog system. R. A. O'Keefe ;;; adapted it to work destructively in Scheme. ;; otherwise, assume it is a list ;;; (sort sequence less?) ;;; sorts a vector or list non-destructively. It does this by sorting a ;;; copy of the sequence. My understanding is that the Standard says ;;; that the result of append is always "newly allocated" except for ;;; sharing structure with "the last argument", so (append x '()) ought ;;; to be a standard way of copying a list x. ;;; eof