branch: externals/heap
commit e2c16bec4b231e5caa990449381e4d5d63f90c5a
Author: Toby Cubitt <toby-predict...@dr-qubit.org>
Commit: tsc25 <ts...@cantab.net>
Version 0.10.3 of the predictive completion package.
(Versions 0.10.1-2 were very minor, and were skipped.)
---
heap.el | 93 ++++++++++++++++++++++++++++++++++++++---------------------------
1 file changed, 54 insertions(+), 39 deletions(-)
diff --git a/heap.el b/heap.el
index bbc048a..17e5893 100644
--- a/heap.el
+++ b/heap.el
@@ -2,15 +2,15 @@
;;; heap.el --- heap (a.k.a. priority queue) data structure package
-;; Copyright (C) 2004 2005 Toby Cubitt
+;; Copyright (C) 2004-2006 Toby Cubitt
;; Author: Toby Cubitt <toby-predict...@dr-qubit.org>
-;; Version: 0.1.2
+;; Version: 0.1.4
;; Keywords: heap, priority queue
;; URL: http://www.dr-qubit.org/emacs.php
-;; This file is part of the Emacs Predictive Completion package.
+;; This file is NOT part of Emacs.
;;
;; This program is free software; you can redistribute it and/or
;; modify it under the terms of the GNU General Public License
@@ -30,13 +30,22 @@
;;; Commentary:
;;
-;; A heap consists of two cons cells, the first one holding the tag 'HEAP in
-;; the car cell and the second one having the heap in the car and the compare
-;; function in the cdr cell. The compare function must take two arguments of
-;; the type which is to be stored in the heap and must return non-nil or
-;; nil. To implement a max-heap, it should return non-nil if the first
-;; argument is "greater" than the second. To implement a min-heap, it should
-;; return non-nil if the first argument is "less than" the second.
+;; A heap is a form of efficient self-sorting tree (sometimes called a
+;; priority queue). In particular, the root node is guaranteed to be
+;; the highest-ranked entry in the tree. (The comparison function used
+;; for ranking the data can, of course, be freely defined). Therefore
+;; repeatedly removing the root node will return the data in order of
+;; increasing rank. They are often used as priority queues, for
+;; scheduling tasks in order of importance.
+;;
+;; A heap consists of two cons cells, the first one holding the tag
+;; 'HEAP in the car cell and the second one having the heap in the car
+;; and the compare function in the cdr cell. The compare function must
+;; take two arguments of the type which is to be stored in the heap
+;; and must return non-nil or nil. To implement a max-heap, it should
+;; return non-nil if the first argument is "greater" than the
+;; second. To implement a min-heap, it should return non-nil if the
+;; first argument is "less than" the second.
;;
;; Note that this package implements a ternary heap, since ternary
;; heaps are about 12% more efficient than binary heaps for heaps
@@ -46,6 +55,12 @@
;;; Change log:
;;
+;; Version 0.1.4
+;; * fixed internal function and macro names
+;;
+;; Version 0.1.3
+;; * added more commentary
+;;
;; Version 0.1.2
;; * moved defmacros before their first use so byte-compilation works
;;
@@ -72,33 +87,33 @@
;;; Internal functions for use in the heap package
-(defmacro hp-vect (heap)
+(defmacro heap--vect (heap)
;; Return the heap vector. ;; INTERNAL USE ONLY
`(car (cdr ,heap))
)
-(defmacro hp-cmpfun (heap)
+(defmacro heap--cmpfun (heap)
;; Return the comparison function of a heap. ;; INTERNAL USE ONLY
`(cdr (cdr ,heap))
)
-(defmacro hp-set-vect (heap vect)
+(defmacro heap--set-vect (heap vect)
;; Set the vector containing the heap itself to VECT.
`(setcar (cdr ,heap) ,vect)
)
-(defmacro hp-child (heap i)
+(defmacro heap--child (heap i)
;; Compare the 3 children of element I, and return element reference of the
;; smallest/largest (depending on whethen it's a min- or max-heap).
;; INTERNAL USE ONLY
- `(let* ((vect (hp-vect ,heap))
- (cmpfun (hp-cmpfun ,heap))
+ `(let* ((vect (heap--vect ,heap))
+ (cmpfun (heap--cmpfun ,heap))
(len (length vect)) (j nil) (k (* 3 ,i)))
;; Lots of if's in case I has less than three children.
(if (>= (1+ k) len) nil
@@ -121,14 +136,14 @@
-(defun hp-sift-up (heap n)
+(defun heap--sift-up (heap n)
;; Sift-up starting from element N of the heap vector belonging to
;; heap HEAP. ;; INTERNAL USE ONLY
- (let* ((i n) (j nil) (vect (hp-vect heap)) (v (aref vect n)))
+ (let* ((i n) (j nil) (vect (heap--vect heap)) (v (aref vect n)))
;; Keep moving element up until it reaches top or is smaller/bigger
;; than its parent.
(while (and (> i 0)
- (funcall (hp-cmpfun heap) v
+ (funcall (heap--cmpfun heap) v
(aref vect (setq j (/ (1- i) 3)))))
(vswap vect i j)
(setq i j)))
@@ -136,19 +151,19 @@
-(defun hp-sift-down (heap n)
+(defun heap--sift-down (heap n)
;; Sift-down from element N of the heap vector belonging to
;; heap HEAP. ;; INTERNAL USE ONLY
- (let* ((vect (hp-vect heap))
- (cmpfun (hp-cmpfun heap))
- (i n) (j (hp-child heap i)) (len (length vect)) (v (aref vect n)))
+ (let* ((vect (heap--vect heap))
+ (cmpfun (heap--cmpfun heap))
+ (i n) (j (heap--child heap i)) (len (length vect)) (v (aref vect n)))
;; Keep moving the element down until it reaches the bottom of the tree or
;; reaches a position where it is bigger/smaller than all its children.
(while (and j (funcall cmpfun (aref vect j) v))
(vswap vect i j)
(setq i j)
- (setq j (hp-child heap i)))
+ (setq j (heap--child heap i)))
)
)
@@ -171,8 +186,8 @@ B. To implemenet a min-heap, it should return non-nil if A
is less than B."
(defun heap-copy (heap)
"Return a copy of heap HEAP."
- (let ((newheap (heap-create (hp-cmpfun heap))))
- (hp-set-vect newheap (hp-vect heap))
+ (let ((newheap (heap-create (heap--cmpfun heap))))
+ (heap--set-vect newheap (heap--vect heap))
newheap)
)
@@ -186,21 +201,21 @@ B. To implemenet a min-heap, it should return non-nil if
A is less than B."
(defun heap-empty (heap)
"Return t if the heap is empty, nil otherwise."
- (= 0 (length (hp-vect heap)))
+ (= 0 (length (heap--vect heap)))
)
(defun heap-size (heap)
"Return the number of entries in the heap."
- (length (hp-vect heap))
+ (length (heap--vect heap))
)
(defun heap-compare-function (heap)
"Return the comparison function for the heap HEAP."
- (hp-cmpfun heap)
+ (heap--cmpfun heap)
)
@@ -208,26 +223,26 @@ B. To implemenet a min-heap, it should return non-nil if
A is less than B."
(defun heap-add (heap data)
"Add DATA to the heap."
;; Add data to bottom of heap and sift-up from bottom.
- (hp-set-vect heap (vconcat (hp-vect heap) (vector data)))
- (hp-sift-up heap (1- (length (hp-vect heap))))
+ (heap--set-vect heap (vconcat (heap--vect heap) (vector data)))
+ (heap--sift-up heap (1- (length (heap--vect heap))))
)
(defun heap-delete-root (heap)
"Return the root of the heap and delete it from the heap."
- (let ((vect (hp-vect heap))
+ (let ((vect (heap--vect heap))
(root nil) (len nil))
;; Deal with special cases of empty heap and heap with just one element.
(if (heap-empty heap) nil
(setq len (length vect))
(setq root (aref vect 0))
- (if (= 1 len) (hp-set-vect heap [])
+ (if (= 1 len) (heap--set-vect heap [])
;; Delete root, swap last element to top, and sift-down from top.
- (hp-set-vect heap (vconcat (vector (aref vect (1- len)))
+ (heap--set-vect heap (vconcat (vector (aref vect (1- len)))
(subseq vect 1 (1- len))))
- (hp-sift-down heap 0))
+ (heap--sift-down heap 0))
root)
)
)
@@ -243,7 +258,7 @@ heap, and return non-nil if it should be modified, nil
otherwise.
Note that only the match highest up the heap is modified."
- (let ((vect (hp-vect heap)) (i 0))
+ (let ((vect (heap--vect heap)) (i 0))
;; search vector for the first match
(while (and (< i (length vect))
(not (funcall match-function (aref vect i))))
@@ -254,9 +269,9 @@ Note that only the match highest up the heap is modified."
(aset vect i data)
;; if the new data is greater than old data, sift-up, otherwise
;; sift-down
- (if (funcall (hp-cmpfun heap) data olddata)
- (hp-sift-up heap i)
- (hp-sift-down heap i))
+ (if (funcall (heap--cmpfun heap) data olddata)
+ (heap--sift-up heap i)
+ (heap--sift-down heap i))
t ; return t if the match was successfully modified
)
nil ; return nil if no match was found
