The pettomato-indexed-priority-queue Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

The pettomato-indexed-priority-queue Reference Manual

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 Mon Aug 15 05:34:23 2022 GMT+0.

Table of Contents


1 Introduction

This is a binary heap based priority queue implementation. In addition
to the properties and operations common to all binary heaps (see
http://en.wikipedia.org/wiki/Binary_heap), this implementation also
supports efficient find, update, replace, and delete operations.

Please see the docstrings of the exported symbols for more
information, especially make-empty-queue for an explanation of how
item lookups are achieved.

--------------------------------
Acknowledgments

This code was originally based off of Peter Norvig's implementation
found here:

http://aima.cs.berkeley.edu/lisp/utilities/queue.lisp

Norvig's code was built on top of the heap algorthms in "Introduction
to Algorithms" by Corman, Leiserson, and Rivest. I trivially updated
some of that code to match the 2nd edition of the book by Corman,
Leiserson, Rivest, and Stein. Specifically, I updated the referenced
page numbers in the docstrings and implemented the Heap-Increase-Key
algorithm (called improve-key in my code), which was not in the first
edition (and is very useful for the new operations I added).


2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 pettomato-indexed-priority-queue

A binary heap based priority queue implementation with efficient support for find, update, replace, and delete operations.

Author

Austin Haas <austin@pettomato.com>

License

MIT

Version

0.1.3

Source

pettomato-indexed-priority-queue.asd.

Child Component

src (module).


3 Modules

Modules are listed depth-first from the system components tree.


Previous: , Up: Modules   [Contents][Index]

3.1 pettomato-indexed-priority-queue/src

Source

pettomato-indexed-priority-queue.asd.

Parent Component

pettomato-indexed-priority-queue (system).

Child Components

4 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

4.1 Lisp


4.1.1 pettomato-indexed-priority-queue/pettomato-indexed-priority-queue.asd

Source

pettomato-indexed-priority-queue.asd.

Parent Component

pettomato-indexed-priority-queue (system).

ASDF Systems

pettomato-indexed-priority-queue.


4.1.3 pettomato-indexed-priority-queue/src/priority-queue.lisp

Dependency

package.lisp (file).

Source

pettomato-indexed-priority-queue.asd.

Parent Component

src (module).

Public Interface
Internals

5 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

5.1 pettomato-indexed-priority-queue

Source

package.lisp.

Nickname

pt-ipq

Use List

common-lisp.

Public Interface
Internals

6 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

6.1 Public Interface


6.1.1 Ordinary functions

Function: make-empty-queue (compare-fn set-index-fn get-index-fn &key size)

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).

Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Function: queue-delete (q item)

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.

Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Function: queue-empty-p (q)

Are there no items in the queue?

Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Function: queue-find (q item)

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.

Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Function: queue-insert (q item)

Insert the item by priority according to the compare function. Returns the queue. [Page 140 CL&R 2nd ed.].

Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Function: queue-peek (q)

Return the element at the front of the queue. Signals empty-queue-error if the queue is empty.

Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Function: queue-pop (q)

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.].

Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Function: queue-replace (q old new)

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.

Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Function: queue-size (q)
Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Function: queue-update (q item)

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.

Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.


6.1.2 Conditions

Condition: empty-queue-error

Signaled when an operation depends on a non-empty queue.

Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Direct superclasses

error.

Condition: item-not-found-error

Signaled when an operation depends on an item that was not found in the queue.

Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Direct superclasses

error.


6.2 Internals


Next: , Previous: , Up: Internals   [Contents][Index]

6.2.1 Constants

Constant: +not-in-queue+

A sentinel value associated with an item that is not in the queue.

Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.


Next: , Previous: , Up: Internals   [Contents][Index]

6.2.2 Ordinary functions

Function: copy-q (instance)
Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Function: heapify (heap i compare-fn set-index-fn)

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.].

Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Function: improve-key (heap i compare-fn set-index-fn)

The item at i may be better than its parent. Promote the item until it is in the correct position.

Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Function: left (i)
Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Function: make-q (&key compare-fn set-index-fn get-index-fn items)
Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Function: parent (i)
Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Reader: q-compare-fn (instance)
Writer: (setf q-compare-fn) (instance)
Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Target Slot

compare-fn.

Reader: q-get-index-fn (instance)
Writer: (setf q-get-index-fn) (instance)
Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Target Slot

get-index-fn.

Reader: q-items (instance)
Writer: (setf q-items) (instance)
Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Target Slot

items.

Function: q-p (object)
Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Reader: q-set-index-fn (instance)
Writer: (setf q-set-index-fn) (instance)
Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Target Slot

set-index-fn.

Function: right (i)
Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.


6.2.3 Structures

Structure: q
Package

pettomato-indexed-priority-queue.

Source

priority-queue.lisp.

Direct superclasses

structure-object.

Direct slots
Slot: compare-fn
Type

function

Readers

q-compare-fn.

Writers

(setf q-compare-fn).

Slot: set-index-fn
Type

function

Readers

q-set-index-fn.

Writers

(setf q-set-index-fn).

Slot: get-index-fn
Type

function

Readers

q-get-index-fn.

Writers

(setf q-get-index-fn).

Slot: items
Type

array

Readers

q-items.

Writers

(setf q-items).


Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts


Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   (  
C   F   H   I   L   M   P   Q   R  
Index Entry  Section

(
(setf q-compare-fn): Private ordinary functions
(setf q-get-index-fn): Private ordinary functions
(setf q-items): Private ordinary functions
(setf q-set-index-fn): Private ordinary functions

C
copy-q: Private ordinary functions

F
Function, (setf q-compare-fn): Private ordinary functions
Function, (setf q-get-index-fn): Private ordinary functions
Function, (setf q-items): Private ordinary functions
Function, (setf q-set-index-fn): Private ordinary functions
Function, copy-q: Private ordinary functions
Function, heapify: Private ordinary functions
Function, improve-key: Private ordinary functions
Function, left: Private ordinary functions
Function, make-empty-queue: Public ordinary functions
Function, make-q: Private ordinary functions
Function, parent: Private ordinary functions
Function, q-compare-fn: Private ordinary functions
Function, q-get-index-fn: Private ordinary functions
Function, q-items: Private ordinary functions
Function, q-p: Private ordinary functions
Function, q-set-index-fn: Private ordinary functions
Function, queue-delete: Public ordinary functions
Function, queue-empty-p: Public ordinary functions
Function, queue-find: Public ordinary functions
Function, queue-insert: Public ordinary functions
Function, queue-peek: Public ordinary functions
Function, queue-pop: Public ordinary functions
Function, queue-replace: Public ordinary functions
Function, queue-size: Public ordinary functions
Function, queue-update: Public ordinary functions
Function, right: Private ordinary functions

H
heapify: Private ordinary functions

I
improve-key: Private ordinary functions

L
left: Private ordinary functions

M
make-empty-queue: Public ordinary functions
make-q: Private ordinary functions

P
parent: Private ordinary functions

Q
q-compare-fn: Private ordinary functions
q-get-index-fn: Private ordinary functions
q-items: Private ordinary functions
q-p: Private ordinary functions
q-set-index-fn: Private ordinary functions
queue-delete: Public ordinary functions
queue-empty-p: Public ordinary functions
queue-find: Public ordinary functions
queue-insert: Public ordinary functions
queue-peek: Public ordinary functions
queue-pop: Public ordinary functions
queue-replace: Public ordinary functions
queue-size: Public ordinary functions
queue-update: Public ordinary functions

R
right: Private ordinary functions

Jump to:   (  
C   F   H   I   L   M   P   Q   R