Common Lisp Package: JPL-QUEUES

README:

FUNCTION

Private

Undocumented

TEST-BOUNDED-FIFO-QUEUE-DEQUEUE-OBJECT-IF (LIST-LENGTH)

GENERIC-FUNCTION

Public

CAPACITY (QUEUE)

Returns the number of elements that can be stored at once in the given QUEUE, or NIL if there is no limit. Most implementations will take constant time.

DEQUEUE (QUEUE)

Removes an element from QUEUE, returning the element. After this function returns, FULL? must return false. It is the caller's responsibility to determine whether QUEUE has an element available for reading. The consequences are undefined if it doesn't. Most implementations will take constant time.

DEQUEUE-OBJECT (OBJECT QUEUE &KEY TEST KEY (KEY #'IDENTITY) (TEST #'EQL))

Prematurely dequeues OBJECT from QUEUE. TEST is a function of two arguments that is used to compare OBJECT with the result of KEY applied to each enqueued element. When TEST returns true, the element is deleted. Zero or more elements may be matched and removed. If anything was actually removed, FULL? must return false. Most implementations will have the same time complexity as DELETE-OBJECT-IF.

DEQUEUE-OBJECT-IF (PREDICATE QUEUE &KEY KEY (KEY #'IDENTITY))

Prematurely dequeues elements from QUEUE that PREDICATE returns true for. PREDICATE is called with the result of KEY applied to each enqueued element. When PREDICATE returns true, the element is deleted. Zero or more elements may be matched and removed. If anything was actually removed, FULL? must return false. Most implementations will take time in linear proportion to the number of enqueued elements.

EMPTY? (QUEUE)

Returns a boolean indicating whether the given QUEUE cannot have any more elements dequeued from it. When this function returns false, it is safe to call DEQUEUE. Most implementations will take constant time.

ENQUEUE (OBJECT QUEUE)

Writes OBJECT to QUEUE. After this function returns, EMPTY? must return false. It is the caller's responsibility to determine whether QUEUE has room for another element. The consequences are undefined if it doesn't. Most implementations will take constant time.

FULL? (QUEUE)

Returns a boolean indicating whether the given QUEUE cannot have any more elements enqueued to it. When this function returns false, it is safe to call ENQUEUE. This is subtly different than saying its SIZE is equal to its CAPACITY: a lossy queue may have a capacity, and it may be "full" in that sense, but it will still accept new elements to be enqueued. Most implementations will take constant time.

SLOT-ACCESSOR

Public

SIZE (QUEUE)

The Returns the number of elements stored in QUEUE. Most implementations will take constant time.

Private

BUFFER (OBJECT)

A list of elements, oldest first, that have yet to be read. The cells of the list do not share structure with anything outside the queue.

CLASS

Public

BOUNDED-FIFO-QUEUE

A bounded FIFO queue. The queue capacity (a positive integer less than ARRAY-DIMENSION-LIMIT) must be specified with the :CAPACITY keyword parameter. Space usage is constant after instantiation, in proportion to the capacity. Conses little, if at all, for any operation.

LOSSY-BOUNDED-FIFO-QUEUE

A bounded FIFO queue that throws away old entries when ENQUEUE is called and the queue is full. A queue capacity (a positive integer less than ARRAY-DIMENSION-LIMIT) must be specified with the :CAPACITY keyword parameter. Space usage is constant after instantiation, in proportion to the capacity. Conses little, if at all, for any operation.

QUEUE

Abstract class for queues. Unless noted otherwise, subclasses do no synchronization. It is the client's responsibility to ensure no two operations occur simultaneously. The usual time complexity for each operation is documented in the generic function for the operation. Per-method exceptions should be documented.

SYNCHRONIZED-QUEUE

Wraps another QUEUE (given by the :QUEUE keyword parameter), synchronizing operations for safe multithreaded access. After instantiating this queue, the wrapped QUEUE must not be directly used for the duration of this queue. When ENQUEUE is called on this QUEUE and the wrapped QUEUE is full, blocks until it is no longer full. When DEQUEUE is called on this QUEUE and the wrapped QUEUE is empty, blocks until it is no longer empty. This blocking also ensures that the internal state of the wrapped QUEUE won't become corrupt by calling DEQUEUE when empty or ENQUEUE when full. Operations that should return no useful value will return no values. The time and space complexity for this queue and all its operations are equal to those of the wrapped QUEUE, plus any locking overhead imposed by the system, except that ENQUEUE and DEQUEUE may block indefinitely.

UNBOUNDED-FIFO-QUEUE

An unbounded FIFO queue. Space usage is proportional to the number of queued elements at any given point in time. Conses for each enqueued element.

UNBOUNDED-RANDOM-QUEUE

A virtually unbounded, random-order queue. (Strictly speaking, the queue size is limited by ARRAY-DIMENSION-LIMIT.) Space usage is proportional to the peak number of queued elements over the lifetime of the queue. An initial queue capacity (a positive integer less than ARRAY-DIMENSION-LIMIT) may optionally be specified with the :CAPACITY keyword parameter; the capacity will be grown as required. Conses for an enqueued element only when the current queue capacity is reached and needs to be extended.