This site is a static rendering of the Trac instance that was used by R7RS-WG1 for its work on R7RS-small (PDF), which was ratified in 2013. For more information, see Home. For a version of this page that may be more recent, see QueuesCowan in WG2's repo for R7RS-large.

Queues­Cowan

cowan
2014-09-01 22:40:08
7history
source

Queues

Queues (more precisely, mostly-output-restricted deques) are mutable ordered collections that can contain any Scheme object. Each queue is based on an ordinary Scheme list that contains the elements of the queue by maintaining pointers to the first and last pairs of the list. It's cheap to add or remove elements from the front of the list or to add elements to the back, but not to remove elements from the back. Queues are disjoint from other types of Scheme objects.

The API provided here is closely analogous to the R7RS-small API for lists. Other list procedures can be applied to queues using queue->list, list->queue, and list-queue!. It subsumes the Chicken and SLIB APIs.

These procedures signal an error that satisfies queue-error? if there is no element to return, modify, or delete.

Procedures

Constructors

(make-queue k [ fill ])

(queue element ...)

Returns a newly allocated queue containing the elements. This operation is O(n).

(queue-copy queue)

Returns a newly allocated queue containing the elements of queue. This operation is O(n).

Predicates

(queue? obj)

Returns #t if obj is a queue, and #f otherwise. This operation is O(1).

(queue-empty? queue)

Returns #t if obj is a queue with no elements, and #f otherwise. This operation is O(1).

Accessors

(queue-first queue element)

Returns the first element of the queue. This operation is O(1).

(queue-lastqueue element)

Returns the last element of the queue. This operation is O(1).

(queue-ref ''queue k'')`

Returns the kth element of queue. This operation is O(k).

Mutators

These procedures signal an error that satisfies queue-error? if there is no element to delete or modify.

(queue-add-first! queue element)

Adds element to the beginning of queue. Returns an unspecified value. This operation is O(1).

(queue-add-last! queue element)

Adds element to the end of queue. Returns an unspecified value. This operation is O(1).

(queue-remove-first! queue)

Removes the first element of the queue and returns it. This operation is O(1).

(queue-remove-last! queue)

Removes the last element of the queue and returns it. This operation is O(n), because the list does not have backward links.

(queue-set! queue k value)

Sets the kth element of queue to value. This operation is O(k).

The whole queue

(queue-length queue)

Returns the number of elements in queue. This operation is O(n).

(queue-append queue ...)

Returns a queue which contains all the elements in all the queues in the order in which they appear in the call. The result does not share storage with any of the arguments. This operation is O(n) in the total number of elements.

(queue-reverse queue)

Returns a newly allocated queue with the same elements as in queue but in reverse order. The result does not share structure with any of the arguments. This operation is O(n).

(queue-member? queue element; [ predicate ])

Returns #t if element is a member of queue (in the sense of predicate, which defaults to equal?) and #f otherwise. This operation is O(n).

Mapping

(queue-map proc queue)

Applies proc to each element of queue in order and returns a newly allocated queue containing the results. This operation is O(n).

(queue-map! proc queue)

Applies proc to each element of queue in order and modifies queue to contain the results. This operation is O(n).

(queue-for-each proc queue)

Applies proc to each element of queue in order, discarding the returned values. Returns an unspecified value. This operation is O(n).

Conversion and list operations

(queue->list queue)

Returns the list that contains the members of queue in order. It is an error to mutate the cdrs of such a list, as it shares storage with the queue. This operation is O(1).

(list->queue list)

Returns a newly allocated queue containing the elements of list in order. It is an error to mutate the cdrs of list after calling this procedure, as it shares storage with the queue. This operation is O(n).

To apply a non-destructive list procedure to a queue and return a new queue, use (list->queue (proc (queue->list queue))).

(list->queue! queue list)

Replaces the list associated with queue with list, effectively discarding all the elements of queue in favor of those in list. It is an error to mutate the cdrs of list after calling this procedure, as it shares storage with the queue. Returns an unspecified value. This operation is O(n).

To apply a destructive list procedure to a queue, use (list->queue! (proc (queue->list queue))).

Comparator

queue-comparator

A comparator suitable for use with queues, using the procedures of list-comparator.

Exceptions

(queue-error? obj)

Returns #t if obj is a condition object thrown by a queue procedure in circumstances given above, and #f otherwise.

Implementation note

R5RS implementations do not have make-list, list-copy, list-set!, or map!, which therefore would need to be packaged with the sample implementation. All but list-set! are available in SRFI 1, but it's trivial to provide local implementations of them.