Changeset 3980

Timestamp:

2016-05-30T20:45:29-07:00 (8 years ago)

Author:

Marek Rychlik

Message:

* empty log message *

File:

• branches/f4grobner/heap.lisp (modified) (4 diffs)

branches/f4grobner/heap.lisp

@@ -34 +34 @@
 (defparameter +heap-allocation-size+ 16)
 
-(defun priority-queue-make-heap (&key (element-type 'fixnum))
+(defun make-heap (&key (element-type 'fixnum))
   (make-array *priority-queue-allocation-size* :element-type element-type :fill-pointer 1
               :adjustable t))
 
-(defstruct (priority-queue (:constructor priority-queue-construct))
-  (heap (priority-queue-make-heap))
-  test)
-
-(defun make-priority-queue (&key (element-type 'fixnum)
-                            (test #'<=)
-                            (element-key #'identity))
-  (priority-queue-construct
-   :heap (priority-queue-make-heap :element-type element-type)
-   :test #'(lambda (x y) (funcall test (funcall element-key y) (funcall element-key x)))))
-  
-(defun priority-queue-insert (pq item)
-  (priority-queue-heap-insert (priority-queue-heap pq) item (priority-queue-test pq)))
-
-(defun priority-queue-remove (pq)
-  (priority-queue-heap-remove (priority-queue-heap pq) (priority-queue-test pq)))
-
-(defun priority-queue-empty-p (pq)
-  (priority-queue-heap-empty-p (priority-queue-heap pq)))
-
-(defun priority-queue-size (pq)
+(defun heap-size (pq)
   (fill-pointer (priority-queue-heap pq)))
 
-(defun priority-queue-upheap (a k
+(defun heap-upheap (a k
                &optional
                (test #'<=)
@@ -78 +58 @@
 
     
-(defun priority-queue-heap-insert (a item &optional (test #'<=))
+(defun heap-insert (a item &optional (test #'<=))
   (vector-push-extend item a)
-  (priority-queue-upheap a (1- (fill-pointer a)) test))
+  (heap-upheap a (1- (fill-pointer a)) test))
 
-(defun priority-queue-downheap (a k
+(defun heap-downheap (a k
                  &optional
                  (test #'<=)
@@ -100 +80 @@
   a)
 
-(defun priority-queue-heap-remove (a &optional (test #'<=) &aux (v (aref a 1)))
+(defun heap-remove (a &optional (test #'<=) &aux (v (aref a 1)))
   (when (<= (fill-pointer a) 1) (error "Empty queue."))
   (setf (aref a 1) (vector-pop a))
@@ -106 +86 @@
   (values v a))
 
-(defun priority-queue-heap-empty-p (a)
+(defun heap-empty-p (a)
   (<= (fill-pointer a) 1))