This is the pettomato-indexed-priority-queue Reference Manual, version 0.1.3, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sun Dec 15 07:16:22 2024 GMT+0.
The main system appears first, followed by any subsystem dependency.
pettomato-indexed-priority-queueA binary heap based priority queue implementation with efficient support for find, update, replace, and delete operations.
Austin Haas <austin@pettomato.com>
MIT
0.1.3
src (module).
Modules are listed depth-first from the system components tree.
pettomato-indexed-priority-queue/srcpettomato-indexed-priority-queue (system).
package.lisp (file).
priority-queue.lisp (file).
Files are sorted by type and then listed depth-first from the systems components trees.
pettomato-indexed-priority-queue/pettomato-indexed-priority-queue.asdpettomato-indexed-priority-queue/src/package.lisppettomato-indexed-priority-queue/src/priority-queue.lisppettomato-indexed-priority-queue/pettomato-indexed-priority-queue.asdpettomato-indexed-priority-queue (system).
pettomato-indexed-priority-queue/src/package.lispsrc (module).
pettomato-indexed-priority-queue/src/priority-queue.lisppackage.lisp (file).
src (module).
empty-queue-error (condition).
item-not-found-error (condition).
make-empty-queue (function).
queue-delete (function).
queue-empty-p (function).
queue-find (function).
queue-insert (function).
queue-peek (function).
queue-pop (function).
queue-replace (function).
queue-size (function).
queue-update (function).
+not-in-queue+ (constant).
copy-q (function).
heapify (function).
improve-key (function).
left (function).
make-q (function).
parent (function).
q (structure).
q-compare-fn (reader).
(setf q-compare-fn) (writer).
q-get-index-fn (reader).
(setf q-get-index-fn) (writer).
q-items (reader).
(setf q-items) (writer).
q-p (function).
q-set-index-fn (reader).
(setf q-set-index-fn) (writer).
right (function).
Packages are listed by definition order.
pettomato-indexed-priority-queuept-ipq
common-lisp.
empty-queue-error (condition).
item-not-found-error (condition).
make-empty-queue (function).
queue-delete (function).
queue-empty-p (function).
queue-find (function).
queue-insert (function).
queue-peek (function).
queue-pop (function).
queue-replace (function).
queue-size (function).
queue-update (function).
+not-in-queue+ (constant).
copy-q (function).
heapify (function).
improve-key (function).
left (function).
make-q (function).
parent (function).
q (structure).
q-compare-fn (reader).
(setf q-compare-fn) (writer).
q-get-index-fn (reader).
(setf q-get-index-fn) (writer).
q-items (reader).
(setf q-items) (writer).
q-p (function).
q-set-index-fn (reader).
(setf q-set-index-fn) (writer).
right (function).
Definitions are sorted by export status, category, package, and then by lexicographic order.
Return a new empty queue.
compare-fn is a function that takes two arguments and returns a true
value iff the first argument should be prioritized higher in the
queue. If the two items have equal priority, then compare-fn should
return nil.
set-index-fn and get-index-fn are a pair. Some queue operations (e.g.,
queue-delete) require that the index for an item can be
retrieved. These functions allow the user to control how that mapping
is maintained.
set-index-fn is a function that takes two arguments: the first is an
item in the queue and the second is the current index position of that
item in the heap. This function should do something to record the
association between the item and the index. Each item’s index may
change many times while it is stored in the queue; this function will
be called each time.
get-index-fn is a function that takes an item and returns the heap
index that was associated with it via set-index-fn. get-index-fn must
return -1 if the item is not in the queue. The priority queue will
call set-index-fn with -1 when an item is being removed from the
queue, but that obviously only works for items it has seen before. If
there is a chance client code will try to call one of the operations
that relies on get-index-fn with items that have never been in the
queue, you must make sure that get-index-fn returns -1. See example
below.
A trivial way to implement set-index-fn / get-index-fn would be like
this:
(let* ((hash (make-hash-table))
(set-index-fn (lambda (item index))
(setf (gethash item hash) index))
(get-index-fn (lamda (item)
(gethash item hash -1))))
(make-empty-queue #’< set-index-fn get-index-fn))
Notice that get-index-fn returns -1 for items that aren’t in the
hash. It might also be a good idea to change set-index-fn to something
like this:
(lambda (item index)
(if (= index -1)
(remhash item hash)
(setf (gethash item hash) index)))
Of course, this code all depends on each item being distinguishable
via ’eql, since that is the default test for a hash-table.
The motivation for handling the index maintenance this way is that it is straightforward and flexible. Any item can be stored in the queue and the user has control over how they are identified and where this storage takes place. In many cases, it may make sense to store the index directly as a property of the item being stored. In other cases, we may want a looser mapping that only uses some attributes of the item being stored, so that we can lookup similar items (e.g., if we were using the priority queue in a search algorithm we could check to see if the queue already contains a node with the same state as a newly discovered node).
Delete item from the queue. Returns the queue. Signals empty-queue-error if the queue is empty. Signals item-not-found-error if the item wasn’t found.
Are there no items in the queue?
Checks if item is in the queue (using the supplied
get-index-fn). If it is, returns two values: the actual item from the
queue (which could be different than the supplied item, since the
client can setup the mapping however they like) and the index. If it
isn’t, returns nil and -1.
Insert the item by priority according to the compare function. Returns the queue. [Page 140 CL&R 2nd ed.].
Return the element at the front of the queue. Signals empty-queue-error if the queue is empty.
Remove the element from the front of the queue and return
it. Signals empty-queue-error if the queue is empty. [Page 139 CL&R
2nd ed.].
Replace old with new in the queue. This is analogous to deleting the old item and inserting the new one, but it is almost always more efficient (and never less efficient) because we can just fix up the heap from the position of the swapped item. Obviously, this only makes sense if you expect the two items to be located very close to each other in the queue (perhaps even in the same location, such as if the priority is the same, but you need to swap the item being stored because of other data it contains). Returns the queue. Signals item-not-found-error if the old item wasn’t found.
queue-update makes sure that item is sorted correctly in q. Call queue-update after changing item in such a way that would affect its priority. Returns the queue. Signals item-not-found-error if the item wasn’t found.
Signaled when an operation depends on a non-empty queue.
error.
Signaled when an operation depends on an item that was not found in the queue.
error.
A sentinel value associated with an item that is not in the queue.
Assume that the children of i are heaps, but that heap[i] may be worse than its children. If it is, move heap[i] down where it belongs. [Page 130 CL&R 2nd ed.].
The item at i may be better than its parent. Promote the item until it is in the correct position.
| Jump to: | (
C F H I L M P Q R |
|---|
| Jump to: | (
C F H I L M P Q R |
|---|
| Jump to: | +
C G I S |
|---|
| Jump to: | +
C G I S |
|---|
| Jump to: | C E F I M P Q S |
|---|
| Jump to: | C E F I M P Q S |
|---|