The priority-queue Reference Manual

Table of Contents

The priority-queue Reference Manual

This is the priority-queue Reference Manual, version 0.1, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 12:25:29 2018 GMT+0.

1 Introduction

PRIORITY-QUEUE -- a priority queue for Common Lisp

The implementation uses an array-based heap.

Licence:

 Copyright (c) 2012 David Sorokin 

 Permission is hereby granted, free of charge, to any person
 obtaining a copy of this software and associated documentation files
 (the "Software"), to deal in the Software without restriction,
 including without limitation the rights to use, copy, modify, merge,
 publish, distribute, sublicense, and/or sell copies of the Software,
 and to permit persons to whom the Software is furnished to do so,
 subject to the following conditions:

 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

2 Systems

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

2.1 priority-queue

Author

David Sorokin

License

MIT

Description

A priority queue for Common Lisp.

Version

0.1

Source

priority-queue.asd (file)

Components

• priority-queue.lisp (file)
• readme (file)

3 Files

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

3.1 Lisp

3.1.1 priority-queue.asd

Location

priority-queue.asd

Systems

priority-queue (system)

3.1.2 priority-queue/priority-queue.lisp

Parent

priority-queue (system)

Location

priority-queue.lisp

Packages

priority-queue

Exported Definitions

• make-pqueue (function)
• pqueue-clear (function)
• pqueue-empty-p (function)
• pqueue-front (function)
• pqueue-front-key (function)
• pqueue-front-value (function)
• pqueue-length (function)
• (setf pqueue-length) (function)
• pqueue-p (function)
• pqueue-pop (function)
• pqueue-push (function)

Internal Definitions

• %make-pqueue (function)
• copy-pqueue (function)
• increase (function)
• pqueue (structure)
• pqueue-key-type (function)
• (setf pqueue-key-type) (function)
• pqueue-keys (function)
• (setf pqueue-keys) (function)
• pqueue-predicate (function)
• (setf pqueue-predicate) (function)
• pqueue-value-type (function)
• (setf pqueue-value-type) (function)
• pqueue-values (function)
• (setf pqueue-values) (function)
• print-pqueue (function)
• sift-down (function)
• sift-up (function)

3.2 Other

3.2.1 priority-queue/README

Parent

priority-queue (system)

Location

README

4 Packages

Packages are listed by definition order.

4.1 priority-queue

Source

priority-queue.lisp (file)

Nickname

pqueue

Use List

common-lisp

Exported Definitions

• make-pqueue (function)
• pqueue-clear (function)
• pqueue-empty-p (function)
• pqueue-front (function)
• pqueue-front-key (function)
• pqueue-front-value (function)
• pqueue-length (function)
• (setf pqueue-length) (function)
• pqueue-p (function)
• pqueue-pop (function)
• pqueue-push (function)

Internal Definitions

• %make-pqueue (function)
• copy-pqueue (function)
• increase (function)
• pqueue (structure)
• pqueue-key-type (function)
• (setf pqueue-key-type) (function)
• pqueue-keys (function)
• (setf pqueue-keys) (function)
• pqueue-predicate (function)
• (setf pqueue-predicate) (function)
• pqueue-value-type (function)
• (setf pqueue-value-type) (function)
• pqueue-values (function)
• (setf pqueue-values) (function)
• print-pqueue (function)
• sift-down (function)
• sift-up (function)

5 Definitions

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

5.1 Exported definitions

5.1.1 Functions

Function: make-pqueue PREDICATE &key KEY-TYPE VALUE-TYPE

Make a priority queue with the specfied types for keys and values.

Package

priority-queue

Source

priority-queue.lisp (file)

Function: pqueue-clear PQUEUE

Clear the piority queue.

Package

priority-queue

Source

priority-queue.lisp (file)

Function: pqueue-empty-p PQUEUE

Test whether the priority queue is empty.

Package

priority-queue

Source

priority-queue.lisp (file)

Function: pqueue-front PQUEUE

Take an element with the minimal priority key and return a multiple value: the element value, its key.

Package

priority-queue

Source

priority-queue.lisp (file)

Function: pqueue-front-key PQUEUE

Return the minimal priority key.

Package

priority-queue

Source

priority-queue.lisp (file)

Function: pqueue-front-value PQUEUE

Return the value with the minimal priority key.

Package

priority-queue

Source

priority-queue.lisp (file)

Function: pqueue-length INSTANCE

Function: (setf pqueue-length) VALUE INSTANCE

Package

priority-queue

Source

priority-queue.lisp (file)

Function: pqueue-p OBJECT

Package

priority-queue

Source

priority-queue.lisp (file)

Function: pqueue-pop PQUEUE

Dequeue the element with the minimal priority key and return a multiple value: the element value, its key.

Package

priority-queue

Source

priority-queue.lisp (file)

Function: pqueue-push VALUE KEY PQUEUE

Enqueue a new value with the specified priority key and return the queue.

Package

priority-queue

Source

priority-queue.lisp (file)

5.2 Internal definitions

5.2.1 Functions

Function: %make-pqueue &key (LENGTH LENGTH) (PREDICATE PREDICATE) (KEYS KEYS) (VALUES VALUES) (KEY-TYPE KEY-TYPE) (VALUE-TYPE VALUE-TYPE)

Package

priority-queue

Source

priority-queue.lisp (file)

Function: copy-pqueue INSTANCE

Package

priority-queue

Source

priority-queue.lisp (file)

Function: increase PQUEUE CAPACITY

Increase the capacity of the priority queue.

Package

priority-queue

Source

priority-queue.lisp (file)

Function: pqueue-key-type INSTANCE

Function: (setf pqueue-key-type) VALUE INSTANCE

Package

priority-queue

Source

priority-queue.lisp (file)

Function: pqueue-keys INSTANCE

Function: (setf pqueue-keys) VALUE INSTANCE

Package

priority-queue

Source

priority-queue.lisp (file)

Function: pqueue-predicate INSTANCE

Function: (setf pqueue-predicate) VALUE INSTANCE

Package

priority-queue

Source

priority-queue.lisp (file)

Function: pqueue-value-type INSTANCE

Function: (setf pqueue-value-type) VALUE INSTANCE

Package

priority-queue

Source

priority-queue.lisp (file)

Function: pqueue-values INSTANCE

Function: (setf pqueue-values) VALUE INSTANCE

Package

priority-queue

Source

priority-queue.lisp (file)

Function: print-pqueue PQUEUE STREAM DEPTH

Print the priority queue.

Package

priority-queue

Source

priority-queue.lisp (file)

Function: sift-down INDEX LENGTH PREDICATE KEYS VALUES KEY VALUE

Sift down the key and value starting at the specified index.

Package

priority-queue

Source

priority-queue.lisp (file)

Function: sift-up INDEX PREDICATE KEYS VALUES KEY VALUE

Sift up the key and value starting at the specified index.

Package

priority-queue

Source

priority-queue.lisp (file)

5.2.2 Structures

Structure: pqueue ()

Package

priority-queue

Source

priority-queue.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

print-object (method)

Direct slots

Slot: length

Readers

pqueue-length (function)

Writers

(setf pqueue-length) (function)

Slot: predicate

Readers

pqueue-predicate (function)

Writers

(setf pqueue-predicate) (function)

Slot: keys

Readers

pqueue-keys (function)

Writers

(setf pqueue-keys) (function)

Slot: values

Readers

pqueue-values (function)

Writers

(setf pqueue-values) (function)

Slot: key-type

Readers

pqueue-key-type (function)

Writers

(setf pqueue-key-type) (function)

Slot: value-type

Readers

pqueue-value-type (function)

Writers

(setf pqueue-value-type) (function)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types