;;; Binary-search-tree sort
;;; John David Stone
;;; Department of Computer Science
;;; Grinnell College
;;; created March 18, 2000
;;; last revised January 6, 2017
(define-library (afp sorting binary-search-tree-sort)
(export sort)
(import (afp primitives)
(only (afp trees) make-empty-tree tree->list)
(only (afp bags) fold-bag)
(only (afp binary-search-trees) put-into-binary-search-tree))
(begin
;; ===== sort =========================================================
;; (alpha, alpha -> Boolean), bag(alpha) -> list(alpha)
;; may-precede? aro
;; The sort procedure constructs a list that has the values in aro as
;; its elements and is ordered by may-precede?.
;; Preconditions:
;; may-precede? is an ordering relation.
;; may-precede? can receive any values in aro.
(define (sort may-precede? aro)
(tree->list ((fold-bag make-empty-tree
(put-into-binary-search-tree may-precede?))
aro)))))
;;; copyright (C) 2011, 2017 John David Stone
;;; This program is free software. You may redistribute it and/or modify
;;; it under the terms of the GNU General Public License as published by
;;; the Free Software Foundation -- either version 3 of the License, or (at
;;; your option) any later version. A copy of the GNU General Public
;;; License is available on the World Wide Web at
;;;
;;; http://www.gnu.org/licenses/gpl.html
;;;
;;; This program is distributed in the hope that it will be useful, but
;;; WITHOUT ANY WARRANTY -- without even the implied warranty of
;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
;;; General Public License for more details.