;;; -*- Mode: Lisp -*-
;;;
;;; $Header: /home/gene/library/website/docsrc/amo/RCS/utils.lisp,v 395.1 2008/04/20 17:25:45 gene Exp $
;;;
;;; Copyright (c) 2005 Gene Michael Stover.  All rights reserved.
;;;
;;; This program is free software; you can redistribute it and/or modify
;;; it under the terms of the GNU Lesser General Public License as
;;; published by the Free Software Foundation; either version 2 of the
;;; License, or (at your option) any later version.
;;;
;;; 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 Lesser General Public License for more details.
;;;
;;; You should have received a copy of the GNU Lesser General Public
;;; License along with this program; if not, write to the Free Software
;;; Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301
;;; USA
;;;

;;;
;;; Miscellaneous utilities I wrote while doing the exercises
;;;

(defpackage "UTILS"
  (:use "COMMON-LISP")
  (:import-from "CYBERTIGGYR-TEST" "DEFTEST")
  (:export "FIRST-HALF"
	   "HEAPSORT"
	   "PAIRS"
	   "SECOND-HALF"))
(in-package "UTILS")

(deftest test0000 ()
  "Null test.  Always succeeds."
  'test0000)

(defun first-half (lst)
  "Return a copy of the first half of LST.  Example: FIRST-HALF
applied to (1 2 3 4 5) returns (1 2)."
  (subseq lst 0 (floor (/ (length lst) 2))))

(defun heapsort (seq initial insert findMin deleteMin)
  "Does a brute-force heap sort on the items in sequence.
It's brute-force because it inserts each item into the heap;
there are more efficient ways to insert a ton of items into
a heap, but we don't use them here.  Non-destructive.  Returns
a new sequence."
  (declare (type sequence seq) (type function insert findMin deleteMin))
  (labels
      ((build-heap ()
         (do ((heap initial (funcall insert (first x) heap))
	      (x seq (rest x)))
	     ((endp x) heap)))
       (remove-heap (heap)
         (do ((heap heap (funcall deleteMin heap))
	      (lst nil (cons (funcall findMin heap) lst)))
	     ((null heap) (reverse lst)))))

    (coerce (remove-heap (build-heap)) (type-of seq))))

(defun pairs (lst)
  "Returna  new list of two-element lists.  The first two
elements of LST become the elements of the fist element of
the new list.  The next two elements of LST become the
elements of the second element of LST, & so on.
Example: PAIRS (1 2 3) => ((1 2) (3 nil))"
  (do ((lst2 () (cons (list (first x) (second x)) lst2))
       (x lst (rest (rest x))))
      ((endp x) lst2)))

(defun second-half (lst)
  "Return a copy of the second half of LST.
Example: SECOND-HALF (1 2 3 4 5) => (3 4 5)"
  (subseq lst (floor (/ (length lst) 2))))

;;; --- end of file ---