For Gauche 0.9.5


Next: , Previous: , Up: Library modules - SRFIs   [Contents][Index]

11.23 srfi-117 - Queues based on lists

Module: srfi-117

A library of simple queue based on lists. Gauche has a queue support in data.queue module, which also includes MT-safe queue (see Queue). This library is implemented on top of data.queue’s <queue> object and mainly provided for portable code.

The list-queue is just an instance of <queue>, so you can pass a queue created by make-queue to srfi-117 API and a list-queue created by make-list-queue to Gauche’s queue API.

Note: Some APIs of this srfi require to return internal pairs the queue uses, for the efficiency. The pair’s car/cdr will be mutated by subsequent queue operation, and also any mutation done on the pair would cause inconsistency in the original queue.

Function: make-list-queue lis :optional last

[SRFI-117] Creates and returns a list-queue whose initial content is lis. In Gauche, a list queue is just an instance of <queue> (see Queue).

The cells in lis are owned by the queue; the caller shouldn’t mutate it afterwords, nor assume its structure remains the same.

The optional last argument must be the last pair of lis. If it is passed, make-list-queue will skip scanning lis and just hold a reference to last as the tail of the queue.

Function: list-queue elt …

[SRFI-117] Creates and returns a list-queue whose initial content is elt …. In Gauche, a list queue is just an instance of <queue> (see Queue).

Function: list-queue-copy queue

[SRFI-117] Returns a copy of a list-queue queue.

Function: list-queue-unfold p f g seed :optional queue

[SRFI-117] Prepend queue with the items generated by (unfold p f g seed) and returns the updated queue. See SRFI-1 List utilities, for unfold. If queue is omitted, a fresh queue is created.

(list-queue-unfold (pa$ = 5) ; p
                   (pa$ * 2) ; f
                   (pa$ + 1) ; g
                   0         ; seed
                   (list-queue 'x 'y 'z))
 ⇒ a queue containing (0 2 4 6 8 x y z)
Function: list-queue-unfold-right p f g seed :optional queue

[SRFI-117] Append queue with the items generated by (unfold-right p f g seed) and returns the updated queue. See SRFI-1 List utilities, for unfold-right. If queue is omitted, a fresh queue is created.

(list-queue-unfold-right (pa$ = 5) ; p
                         (pa$ * 2) ; f
                         (pa$ + 1) ; g
                         0         ; seed
                         (list-queue 'x 'y 'z))
 ⇒ a queue containing (x y z 8 6 4 2 0)
Function: list-queue? obj

[SRFI-117] Returns true iff queue is a list-queue. In Gauche, it is the same as queue? in the data.queue module.

Function: list-queue-empty? queue

[SRFI-117] Returns true iff queue is empty. Same as queue-empty? of data.queue.

Function: list-queue-front queue

[SRFI-117] Returns the front element of the queue. An error is thrown if queue is empty. Same as queue-front of data.queue.

Function: list-queue-back queue

[SRFI-117] Returns the rear element of the queue. An error is thrown if queue is empty. Same as queue-rear of data.queue.

Function: list-queue-list queue

[SRFI-117] Returns the internal list of queue. Note that the list would be modified by subsequent operations of queue, and any modification on the list would make queue inconsistent. The primary purpose of this procedure is to implement other queue-related operations with small overhead.

If you merely need a cheap access the content of the queue, consider list-queue-remove-all!. That returns the list of elements of the queue without copying, and simultaneoulsy reset the queue to empty, so it’s safe.

Function: list-queue-fist-last queue

Returns two values, the first and last pair of queue. If the queue is empty, two empty lists are returned.

This also returns the internal pair of the queue, so any subsequent operations of queue would change the contents of the pairs, and any modification on the pairs would make queue inconsistent. The purpose of this procedure is to implement other queue-related operations with small overhead. This procedure should not be used in general.

Function: list-queue-add-front! queue elt

[SRFI-117] Add elt to the front of queue. Same as (queue-push! queue elt) of data.queue.

Function: list-queue-add-back! queue elt

[SRFI-117] Add elt to the back of queue. Same as (enqueue! queue elt) of data.queue.

Function: list-queue-remove-front! queue

[SRFI-117] Remove an element from the front of queue and returns the removed element. Throws an error if queue is empty. Same as dequeue! of data.queue.

Function: list-queue-remove-back! queue

[SRFI-117] Remove an element from the back of queue and returns the removed element. Throws an error if queue is empty. This isn’t guaranteed to be efficient; it is O(n) operation where n is the number of elements. In general, if you need this operation frequently, you should consider double-ended queue. (See Immutable deques, and also see Ring buffer.)

Function: list-queue-remove-all! queue

[SRFI-117] Remove all the elements from queue and returns them as a list. The list isn’t copied—this is O(1) operation. This should be preferred over list-queue-list, for it’s safer. In Gauhce, this is the same as dequeue-all! in data.queue.

Function: list-queue-set-list! queue lis :optional last

[SRFI-117] Modify queue to have the elements in lis as its element. The original content of queue is discarded. If the optional last argument is provided, it must be the last pair of lis, and the procedure uses that instead of scanning lis, to achieve O(1) operation.

After calling this, lis is owned by queue and it may be mutated. The caller shouldn’t change, or rely on lis afterwards.

Function: list-queue-append queue …

[SRFI-117] Returns a fresh list-queue whose contents are concatenation of queues. The contents of arguments are intact. This is O(n) operation where n is the total number of elements.

Function: list-queue-append! queue …

[SRFI-117] Returns a list-queue whose contents are concatenation of queues. During the operation, the contents of queues may be mutated, and they shouldn’t be used any longer. (In Gauche, to avoid accident, we actually empty all the queues.) It is also noted that the result doesn’t need to be eq? to any of the arguments. This is O(m) operation where m is the total number of queues (as opposed to the number of elements).

Function: list-queue-concatenate queues

[SRFI-117] (apply list-queue-append queues).

Function: list-queue-map proc queue

[SRFI-117] Returns a fresh list-queue whose elements are obtained by applying proc on every elements in queue.

Function: list-queue-map! proc queue

[SRFI-117] Replaces every element in queue by the result of application of proc on the element.

Function: list-queue-for-each proc queue

[SRFI-117] Applies proc on every element of queue. The results are discarded.


Next: , Previous: , Up: Library modules - SRFIs   [Contents][Index]