The priority-queue Reference Manual

This is the priority-queue Reference Manual, version 0.1, generated automatically by Declt version 4.0 beta 2 "William Riker" on Mon Aug 15 05:37:48 2022 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.

priority-queue

2.1 `priority-queue`

A priority queue for Common Lisp.

Author

David Sorokin

License

MIT

Version

0.1

Source

priority-queue.asd.

Child Components

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

3 Files

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

Lisp
Static

3.1.1 `priority-queue/priority-queue.asd`

Source: priority-queue.asd.
Parent Component: priority-queue (system).
ASDF Systems: priority-queue.

3.1.2 `priority-queue/priority-queue.lisp`

Source

priority-queue.asd.

Parent Component

priority-queue (system).

Packages

priority-queue.

Public Interface

make-pqueue (function).
pqueue-clear (function).
pqueue-empty-p (function).
pqueue-front (function).
pqueue-front-key (function).
pqueue-front-value (function).
pqueue-length (reader).
(setf pqueue-length) (writer).
pqueue-p (function).
pqueue-pop (function).
pqueue-push (function).
print-object (method).

Internals

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

3.2 Static

priority-queue/README

3.2.1 `priority-queue/README`

Source: priority-queue.asd.
Parent Component: priority-queue (system).

4 Packages

Packages are listed by definition order.

priority-queue

4.1 `priority-queue`

Source

priority-queue.lisp.

Nickname

pqueue

Use List

common-lisp.

Public Interface

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

Internals

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

5 Definitions

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

Public Interface
Internals

5.1 Public Interface

Ordinary functions
Standalone methods

5.1.1 Ordinary 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.

Function: pqueue-clear (pqueue) ¶

Clear the piority queue.

Package: priority-queue.
Source: priority-queue.lisp.

Function: pqueue-empty-p (pqueue) ¶

Test whether the priority queue is empty.

Package: priority-queue.
Source: priority-queue.lisp.

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.

Function: pqueue-front-key (pqueue) ¶

Return the minimal priority key.

Package: priority-queue.
Source: priority-queue.lisp.

Function: pqueue-front-value (pqueue) ¶

Return the value with the minimal priority key.

Package: priority-queue.
Source: priority-queue.lisp.

Reader: pqueue-length (instance) ¶

Writer: (setf pqueue-length) (instance) ¶

Package: priority-queue.
Source: priority-queue.lisp.
Target Slot: length.

Function: pqueue-p (object) ¶

Package: priority-queue.
Source: priority-queue.lisp.

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.

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.

5.1.2 Standalone methods

Method: print-object ((object pqueue) stream) ¶

Source: priority-queue.lisp.

5.2 Internals

Ordinary functions
Structures

5.2.1 Ordinary functions

Function: %make-pqueue (&key length predicate keys values key-type value-type) ¶

Package: priority-queue.
Source: priority-queue.lisp.

Function: copy-pqueue (instance) ¶

Package: priority-queue.
Source: priority-queue.lisp.

Function: increase (pqueue capacity) ¶

Increase the capacity of the priority queue.

Package: priority-queue.
Source: priority-queue.lisp.

Reader: pqueue-key-type (instance) ¶

Writer: (setf pqueue-key-type) (instance) ¶

Package: priority-queue.
Source: priority-queue.lisp.
Target Slot: key-type.

Reader: pqueue-keys (instance) ¶

Writer: (setf pqueue-keys) (instance) ¶

Package: priority-queue.
Source: priority-queue.lisp.
Target Slot: keys.

Reader: pqueue-predicate (instance) ¶

Writer: (setf pqueue-predicate) (instance) ¶

Package: priority-queue.
Source: priority-queue.lisp.
Target Slot: predicate.

Reader: pqueue-value-type (instance) ¶

Writer: (setf pqueue-value-type) (instance) ¶

Package: priority-queue.
Source: priority-queue.lisp.
Target Slot: value-type.

Reader: pqueue-values (instance) ¶

Writer: (setf pqueue-values) (instance) ¶

Package: priority-queue.
Source: priority-queue.lisp.
Target Slot: values.

Function: print-pqueue (pqueue stream depth) ¶

Print the priority queue.

Package: priority-queue.
Source: priority-queue.lisp.

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.

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.

5.2.2 Structures

Structure: pqueue ¶

Package

priority-queue.

Source

priority-queue.lisp.

Direct superclasses

structure-object.

Direct methods

print-object.

Direct slots

Slot: length ¶

Package: common-lisp.
Readers: pqueue-length.
Writers: (setf pqueue-length).

Slot: predicate ¶

Readers: pqueue-predicate.
Writers: (setf pqueue-predicate).

Slot: keys ¶

Readers: pqueue-keys.
Writers: (setf pqueue-keys).

Slot: values ¶

Package: common-lisp.
Readers: pqueue-values.
Writers: (setf pqueue-values).

Slot: key-type ¶

Readers: pqueue-key-type.
Writers: (setf pqueue-key-type).

Slot: value-type ¶

Readers: pqueue-value-type.
Writers: (setf pqueue-value-type).

Appendix A Indexes

Concepts
Functions
Variables
Data types

A.1 Concepts

A.2 Functions

Jump to:	% ( C F I M P S

	Index Entry	Section

%
	`%make-pqueue`:	Private ordinary functions

(
	`(setf pqueue-key-type)`:	Private ordinary functions
	`(setf pqueue-keys)`:	Private ordinary functions
	`(setf pqueue-length)`:	Public ordinary functions
	`(setf pqueue-predicate)`:	Private ordinary functions
	`(setf pqueue-value-type)`:	Private ordinary functions
	`(setf pqueue-values)`:	Private ordinary functions

C
	`copy-pqueue`:	Private ordinary functions

F
	`Function, %make-pqueue`:	Private ordinary functions
	`Function, (setf pqueue-key-type)`:	Private ordinary functions
	`Function, (setf pqueue-keys)`:	Private ordinary functions
	`Function, (setf pqueue-length)`:	Public ordinary functions
	`Function, (setf pqueue-predicate)`:	Private ordinary functions
	`Function, (setf pqueue-value-type)`:	Private ordinary functions
	`Function, (setf pqueue-values)`:	Private ordinary functions
	`Function, copy-pqueue`:	Private ordinary functions
	`Function, increase`:	Private ordinary functions
	`Function, make-pqueue`:	Public ordinary functions
	`Function, pqueue-clear`:	Public ordinary functions
	`Function, pqueue-empty-p`:	Public ordinary functions
	`Function, pqueue-front`:	Public ordinary functions
	`Function, pqueue-front-key`:	Public ordinary functions
	`Function, pqueue-front-value`:	Public ordinary functions
	`Function, pqueue-key-type`:	Private ordinary functions
	`Function, pqueue-keys`:	Private ordinary functions
	`Function, pqueue-length`:	Public ordinary functions
	`Function, pqueue-p`:	Public ordinary functions
	`Function, pqueue-pop`:	Public ordinary functions
	`Function, pqueue-predicate`:	Private ordinary functions
	`Function, pqueue-push`:	Public ordinary functions
	`Function, pqueue-value-type`:	Private ordinary functions
	`Function, pqueue-values`:	Private ordinary functions
	`Function, print-pqueue`:	Private ordinary functions
	`Function, sift-down`:	Private ordinary functions
	`Function, sift-up`:	Private ordinary functions

I
	`increase`:	Private ordinary functions

M
	`make-pqueue`:	Public ordinary functions
	`Method, print-object`:	Public standalone methods

P
	`pqueue-clear`:	Public ordinary functions
	`pqueue-empty-p`:	Public ordinary functions
	`pqueue-front`:	Public ordinary functions
	`pqueue-front-key`:	Public ordinary functions
	`pqueue-front-value`:	Public ordinary functions
	`pqueue-key-type`:	Private ordinary functions
	`pqueue-keys`:	Private ordinary functions
	`pqueue-length`:	Public ordinary functions
	`pqueue-p`:	Public ordinary functions
	`pqueue-pop`:	Public ordinary functions
	`pqueue-predicate`:	Private ordinary functions
	`pqueue-push`:	Public ordinary functions
	`pqueue-value-type`:	Private ordinary functions
	`pqueue-values`:	Private ordinary functions
	`print-object`:	Public standalone methods
	`print-pqueue`:	Private ordinary functions

S
	`sift-down`:	Private ordinary functions
	`sift-up`:	Private ordinary functions

Jump to:	% ( C F I M P S

A.3 Variables

Jump to:	K L P S V

	Index Entry	Section

K
	`key-type`:	Private structures
	`keys`:	Private structures

L
	`length`:	Private structures

P
	`predicate`:	Private structures

S
	`Slot, key-type`:	Private structures
	`Slot, keys`:	Private structures
	`Slot, length`:	Private structures
	`Slot, predicate`:	Private structures
	`Slot, value-type`:	Private structures
	`Slot, values`:	Private structures

V
	`value-type`:	Private structures
	`values`:	Private structures

Jump to:	K L P S V

A.4 Data types

Jump to:	F P R S

	Index Entry	Section

F
	`File, priority-queue.asd`:	The priority-queue/priority-queue․asd file
	`File, priority-queue.lisp`:	The priority-queue/priority-queue․lisp file
	`File, readme`:	The priority-queue/readme file

P
	`Package, priority-queue`:	The priority-queue package
	`pqueue`:	Private structures
	`priority-queue`:	The priority-queue system
	`priority-queue`:	The priority-queue package
	`priority-queue.asd`:	The priority-queue/priority-queue․asd file
	`priority-queue.lisp`:	The priority-queue/priority-queue․lisp file

R
	`readme`:	The priority-queue/readme file

S
	`Structure, pqueue`:	Private structures
	`System, priority-queue`:	The priority-queue system

Jump to:	F P R S

The priority-queue Reference Manual

The priority-queue Reference Manual

Table of Contents

1 Introduction

2 Systems

2.1 priority-queue

3 Files

3.1 Lisp

3.1.1 priority-queue/priority-queue.asd

3.1.2 priority-queue/priority-queue.lisp

3.2 Static

3.2.1 priority-queue/README

4 Packages

4.1 priority-queue

5 Definitions

5.1 Public Interface

5.1.1 Ordinary functions

5.1.2 Standalone methods

5.2 Internals

5.2.1 Ordinary functions

5.2.2 Structures

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types

2.1 `priority-queue`

3.1.1 `priority-queue/priority-queue.asd`

3.1.2 `priority-queue/priority-queue.lisp`

3.2.1 `priority-queue/README`

4.1 `priority-queue`