[elpa] externals/heap e2c16be 06/31: Version 0.10.3 of the predictive completion package.

[Stefan Monnier]

branch: externals/heap
commit e2c16bec4b231e5caa990449381e4d5d63f90c5a
Author: Toby Cubitt <toby-predictive@dr-qubit.org>
Commit: tsc25 <tsc25@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-predictive@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