;;; Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
(defpackage #:heap
;;; Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
(defpackage #:heap
;;;--------------------------------------------------------------------------
;;; High-level heap things
;;;--------------------------------------------------------------------------
;;; High-level heap things
(defstruct (heap (:predicate heapp) (:constructor %make-heap))
"Data structure for a heap."
(v (make-array 16) :type vector)
(n 0 :type index)
(defstruct (heap (:predicate heapp) (:constructor %make-heap))
"Data structure for a heap."
(v (make-array 16) :type vector)
(n 0 :type index)
(defun heap-empty-p (heap)
"True if HEAP is empty."
(declare (type heap heap))
(zerop (heap-count heap)))
(defun heap-empty-p (heap)
"True if HEAP is empty."
(declare (type heap heap))
(zerop (heap-count heap)))
(defun heap-insert (heap item)
"Insert ITEM into the HEAP."
(declare (type heap heap))
(defun heap-insert (heap item)
"Insert ITEM into the HEAP."
(declare (type heap heap))
(defun heap-head (heap)
"Peep at the head item on HEAP."
(declare (type heap heap))
(assert (not (heap-empty-p heap)))
(aref (heap-v heap) 0))
(defun heap-head (heap)
"Peep at the head item on HEAP."
(declare (type heap heap))
(assert (not (heap-empty-p heap)))
(aref (heap-v heap) 0))
(defun heap-remove (heap)
"Remove the head item from HEAP and return it."
(declare (type heap heap))
(defun heap-remove (heap)
"Remove the head item from HEAP and return it."
(declare (type heap heap))
(defun heap-sort (items compare &key (key #'identity))
"Return the ITEMS, least-first, as sorted by the ordering COMPARE."
(let ((heap (make-heap :compare compare :contents items :key key)))
(defun heap-sort (items compare &key (key #'identity))
"Return the ITEMS, least-first, as sorted by the ordering COMPARE."
(let ((heap (make-heap :compare compare :contents items :key key)))