The pettomato-indexed-priority-queue Reference Manual

Table of Contents

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 2.4 "Will Decker" on Wed Jun 20 12:23:23 2018 GMT+0.


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

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


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

2 Systems

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


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

2.1 pettomato-indexed-priority-queue

Author

Austin Haas <austin@pettomato.com>

License

MIT

Description

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

Version

0.1.3

Source

pettomato-indexed-priority-queue.asd (file)

Component

src (module)


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

3 Modules

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


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

3.1 pettomato-indexed-priority-queue/src

Parent

pettomato-indexed-priority-queue (system)

Location

src/

Components

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

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


Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.1 pettomato-indexed-priority-queue.asd

Location

pettomato-indexed-priority-queue.asd

Systems

pettomato-indexed-priority-queue (system)


Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.2 pettomato-indexed-priority-queue/src/package.lisp

Parent

src (module)

Location

src/package.lisp

Packages

pettomato-indexed-priority-queue


Previous: , Up: Lisp files   [Contents][Index]

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

Dependency

package.lisp (file)

Parent

src (module)

Location

src/priority-queue.lisp

Exported Definitions
Internal Definitions

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

5 Packages

Packages are listed by definition order.


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

5.1 pettomato-indexed-priority-queue

Source

package.lisp (file)

Nickname

pt-ipq

Use List

common-lisp

Exported Definitions
Internal Definitions

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

6 Definitions

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


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

6.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

6.1.1 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 (file)

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 (file)

Function: queue-empty-p Q

Are there no items in the queue?

Package

pettomato-indexed-priority-queue

Source

priority-queue.lisp (file)

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

Function: queue-size Q
Package

pettomato-indexed-priority-queue

Source

priority-queue.lisp (file)

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 (file)


Previous: , Up: Exported definitions   [Contents][Index]

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 (file)

Direct superclasses

error (condition)

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 (file)

Direct superclasses

error (condition)


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

6.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [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 (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

6.2.2 Functions

Function: copy-q INSTANCE
Package

pettomato-indexed-priority-queue

Source

priority-queue.lisp (file)

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 (file)

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 (file)

Function: left I
Package

pettomato-indexed-priority-queue

Source

priority-queue.lisp (file)

Function: make-q &key (COMPARE-FN COMPARE-FN) (SET-INDEX-FN SET-INDEX-FN) (GET-INDEX-FN GET-INDEX-FN) (ITEMS ITEMS)
Package

pettomato-indexed-priority-queue

Source

priority-queue.lisp (file)

Function: parent I
Package

pettomato-indexed-priority-queue

Source

priority-queue.lisp (file)

Function: q-compare-fn INSTANCE
Function: (setf q-compare-fn) VALUE INSTANCE
Package

pettomato-indexed-priority-queue

Source

priority-queue.lisp (file)

Function: q-get-index-fn INSTANCE
Function: (setf q-get-index-fn) VALUE INSTANCE
Package

pettomato-indexed-priority-queue

Source

priority-queue.lisp (file)

Function: q-items INSTANCE
Function: (setf q-items) VALUE INSTANCE
Package

pettomato-indexed-priority-queue

Source

priority-queue.lisp (file)

Function: q-p OBJECT
Package

pettomato-indexed-priority-queue

Source

priority-queue.lisp (file)

Function: q-set-index-fn INSTANCE
Function: (setf q-set-index-fn) VALUE INSTANCE
Package

pettomato-indexed-priority-queue

Source

priority-queue.lisp (file)

Function: right I
Package

pettomato-indexed-priority-queue

Source

priority-queue.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

6.2.3 Structures

Structure: q ()
Package

pettomato-indexed-priority-queue

Source

priority-queue.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: compare-fn
Type

function

Readers

q-compare-fn (function)

Writers

(setf q-compare-fn) (function)

Slot: set-index-fn
Type

function

Readers

q-set-index-fn (function)

Writers

(setf q-set-index-fn) (function)

Slot: get-index-fn
Type

function

Readers

q-get-index-fn (function)

Writers

(setf q-get-index-fn) (function)

Slot: items
Type

array

Readers

q-items (function)

Writers

(setf q-items) (function)


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

Appendix A Indexes


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

A.1 Concepts

Jump to:   F   L   M   P  
Index Entry  Section

F
File, Lisp, pettomato-indexed-priority-queue.asd: The pettomato-indexed-priority-queue<dot>asd file
File, Lisp, pettomato-indexed-priority-queue/src/package.lisp: The pettomato-indexed-priority-queue/src/package<dot>lisp file
File, Lisp, pettomato-indexed-priority-queue/src/priority-queue.lisp: The pettomato-indexed-priority-queue/src/priority-queue<dot>lisp file

L
Lisp File, pettomato-indexed-priority-queue.asd: The pettomato-indexed-priority-queue<dot>asd file
Lisp File, pettomato-indexed-priority-queue/src/package.lisp: The pettomato-indexed-priority-queue/src/package<dot>lisp file
Lisp File, pettomato-indexed-priority-queue/src/priority-queue.lisp: The pettomato-indexed-priority-queue/src/priority-queue<dot>lisp file

M
Module, pettomato-indexed-priority-queue/src: The pettomato-indexed-priority-queue/src module

P
pettomato-indexed-priority-queue.asd: The pettomato-indexed-priority-queue<dot>asd file
pettomato-indexed-priority-queue/src: The pettomato-indexed-priority-queue/src module
pettomato-indexed-priority-queue/src/package.lisp: The pettomato-indexed-priority-queue/src/package<dot>lisp file
pettomato-indexed-priority-queue/src/priority-queue.lisp: The pettomato-indexed-priority-queue/src/priority-queue<dot>lisp file

Jump to:   F   L   M   P  

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): Internal functions
(setf q-get-index-fn): Internal functions
(setf q-items): Internal functions
(setf q-set-index-fn): Internal functions

C
copy-q: Internal functions

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

H
heapify: Internal functions

I
improve-key: Internal functions

L
left: Internal functions

M
make-empty-queue: Exported functions
make-q: Internal functions

P
parent: Internal functions

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

R
right: Internal functions

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

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

A.3 Variables

Jump to:   +  
C   G   I   S  
Index Entry  Section

+
+not-in-queue+: Internal constants

C
compare-fn: Internal structures
Constant, +not-in-queue+: Internal constants

G
get-index-fn: Internal structures

I
items: Internal structures

S
set-index-fn: Internal structures
Slot, compare-fn: Internal structures
Slot, get-index-fn: Internal structures
Slot, items: Internal structures
Slot, set-index-fn: Internal structures

Jump to:   +  
C   G   I   S  

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

A.4 Data types

Jump to:   C   E   I   P   Q   S  
Index Entry  Section

C
Condition, empty-queue-error: Exported conditions
Condition, item-not-found-error: Exported conditions

E
empty-queue-error: Exported conditions

I
item-not-found-error: Exported conditions

P
Package, pettomato-indexed-priority-queue: The pettomato-indexed-priority-queue package
pettomato-indexed-priority-queue: The pettomato-indexed-priority-queue system
pettomato-indexed-priority-queue: The pettomato-indexed-priority-queue package

Q
q: Internal structures

S
Structure, q: Internal structures
System, pettomato-indexed-priority-queue: The pettomato-indexed-priority-queue system

Jump to:   C   E   I   P   Q   S