srfi-117 | chickadee

SRFI-117: Queues based on lists

List queues are mutable ordered collections that can contain any Scheme object. Each list queue is based on an ordinary Scheme list containing the elements of the list 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. List queues are disjoint from other types of Scheme objects.

Installation

$ chicken-install srfi-117

$ chicken-install srfi-117 -test

if you want to run the tests for the egg in addition.

SRFI Description

For a full description of this SRFI, see the full SRFI document. This documentation covers the API only.

List Queues

Constructors

make-list-queue list #!optional lastprocedure

Returns a newly allocated list queue containing the elements of list in order. The result shares storage with list. If the last argument is not provided, this operation is O(n) where n is the length of list.

However, if last is provided, make-list-queue returns a newly allocated list queue containing the elements of the list whose first pair is first and whose last pair is last. It is an error if the pairs do not belong to the same list. Alternatively, both first and last can be the empty list. In either case, the operation is O(1).

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

list-queue element ...procedure: Returns a newly allocated list queue containing the elements. This operation is O(n) where n is the number of elements.

list-queue-copy list-queueprocedure: Returns a newly allocated list queue containing the elements of list-queue. This operation is O(n) where n is the length of list-queue.

list-queue-unfold stop? mapper successor seed #!optional queueprocedure

Performs the following algorithm:

If the result of applying the predicate stop? to seed is true, return queue. Otherwise, apply the procedure mapper to seed, returning a value which is added to the front of queue. Then get a new seed by applying the procedure successor to seed, and repeat this algorithm.

If queue is omitted, a newly allocated list queue is used.

list-queue-unfold-right stop? mapper successor seed #!optional queueprocedure

Performs the following algorithm:

If the result of applying the predicate stop? to seed is true, return the list queue. Otherwise, apply the procedure mapper to seed, returning a value which is added to the back of the list queue. Then get a new seed by applying the procedure successor to seed, and repeat this algorithm.

If queue is omitted, a newly allocated list queue is used.

Predicates

list-queue? objprocedure: Returns #t if obj is a list queue, and #f otherwise. This operation is O(1).

list-queue-empty? list-queueprocedure: Returns #t if list-queue has no elements, and #f otherwise. This operation is O(1).

Accessors

list-queue-front list-queueprocedure: Returns the first element of list-queue. If the list queue is empty, it is an error. This operation is O(1).

list-queue-back list-queueprocedure: Returns the last element of list-queue. If the list queue is empty, it is an error. This operation is O(1).

list-queue-list list-queueprocedure: Returns the list that contains the members of list-queue in order. The result shares storage with list-queue. This operation is O(1).

list-queue-first-last list-queueprocedure: Returns two values, the first and last pairs of the list that contains the members of list-queue in order. If list-queue is empty, returns two empty lists. The results share storage with list-queue. This operation is O(1).

Mutators

list-queue-add-front! list-queue elementprocedure: Adds element to the beginning of list-queue. Returns an unspecified value. This operation is O(1).

list-queue-add-back! list-queue elementprocedure: Adds element to the end of list-queue. Returns an unspecified value. This operation is O(1).

list-queue-remove-front! list-queueprocedure: Removes the first element of list-queue and returns it. If the list queue is empty, it is an error. This operation is O(1).

list-queue-remove-back! list-queueprocedure: Removes the last element of list-queue and returns it. If the list queue is empty, it is an error. This operation is O(n) where n is the length of list-queue, because queues do not not have backward links.

list-queue-remove-all! list-queueprocedure: Removes all the elements of list-queue and returns them in order as a list. This operation is O(1).

list-queue-set-list! list-queue list #!optional lastprocedure

Replaces the list associated with list-queue with list, effectively discarding all the elements of list-queue in favor of those in list. Returns an unspecified value. This operation is O(n) where n is the length of list. If last is provided, it is treated in the same way as in make-list-queue, and the operation is O(1).

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

list-queue-append list-queue ...procedure: Returns a list queue which contains all the elements in front-to-back order from all the list-queues in front-to-back order. The result does not share storage with any of the arguments. This operation is O(n) in the total number of elements in all queues.

list-queue-append! list-queue ...procedure: Returns a list queue which contains all the elements in front-to-back order from all the list-queues in front-to-back order. It is an error to assume anything about the contents of the list-queues after the procedure returns. This operation is O(n) in the total number of queues, not elements. It is not part of the R7RS-small list API, but is included here for efficiency when pure functional append is not required.

list-queue-concatenate list-of-list-queuesprocedure: Returns a list queue which contains all the elements in front-to-back order from all the list queues which are members of list-of-list-queues in front-to-back order. The result does not share storage with any of the arguments. This operation is O(n) in the total number of elements in all queues. It is not part of the R7RS-small list API, but is included here to make appending a large number of queues possible in Schemes that limit the number of arguments to apply.

Mapping

list-queue-map proc list-queueprocedure: Applies proc to each element of list-queue in unspecified order and returns a newly allocated list queue containing the results. This operation is O(n) where n is the length of list-queue.

list-queue-map! proc list-queueprocedure: Applies proc to each element of list-queue in front-to-back order and modifies list-queue to contain the results. This operation is O(n) in the length of list-queue. It is not part of the R7RS-small list API, but is included here to make transformation of a list queue by mutation more efficient.

list-queue-for-each proc list-queueprocedure: Applies proc to each element of list-queue in front-to-back order, discarding the returned values. Returns an unspecified value. This operation is O(n) where n is the length of list-queue.

Repository

Github

Version History

1.4: Fixes egg synopsis for C5
1.3: Adds CHICKEN 5 support
1.2: Adds standard README.org to SRFI and fixes hardcoded .so in setup
1.1: Packages egg without extraneous files
1.0: Initial release

License

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 above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

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.

chickadee » srfi-117

Identifier search