Common Lisp Package: COM.INFORMATIMAGO.COMMON-LISP.CESARUM.QUEUE

This module exports a queue type. This is a structure optimized for FIFO operations, keeping a pointer to the head and the tail of a list. The structure of a queue is as follow: queue | V +------+------+ | head | tail |--------------------------+ +------+------+ | | | V V +------+------+ +------+------+ +------+------+ | car | cdr |--->| car | cdr |--->| car | cdr |--->nil +------+------+ +------+------+ +------+------+ | | | V V V +------+ +------+ +------+ | elem | | elem | | elem | +------+ +------+ +------+ License: AGPL3 Copyright Pascal J. Bourguignon 2001 - 2012 This program is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details. You should have received a copy of the GNU Affero General Public License along with this program. If not, see <http://www.gnu.org/licenses/>

README:

FUNCTION

Public

MAKE-QUEUE

RETURN: A new empty queue.

QUEUE-APPEND (QUEUE ELEMENTS)

DO: appends the elements to the queue. PRE: (queue-p queue) ql=(queue-length queue) el=(length elements) POST: (< 0 el) ⇒ (eq (queue-last-element queue) (first (last elements))) (queue-p queue), ql+el=(queue-length queue) RETURN: queue

QUEUE-DELETE (QUEUE ELEMENT &KEY (TEST #'EQL))

POST: (not (member element queue :test test)) RETURN: queue

QUEUE-DEQUEUE (QUEUE)

PRE: (queue-p queue) l=(queue-length queue) f=(queue-first-element queue) POST: l>0 ==> l-1=(queue-length queue) l=0 ==> 0=(queue-length queue) RETURN: f

QUEUE-ELEMENTS (QUEUE)

RETURN: The list of elements in the queue.

QUEUE-EMPTY-P (QUEUE)

RETURN: (= 0 (queue-length queue))

QUEUE-ENQUEUE (QUEUE ELEMENT)

PRE: (queue-p queue) l=(queue-length queue) POST: (eq (queue-last-element queue) element), (queue-p queue), l+1=(queue-length queue) RETURN: queue

QUEUE-FIRST-ELEMENT (QUEUE)

PRE: (queue-p queue) RETURN: The first element of the queue.

QUEUE-INVARIANT (QUEUE)

DO: Check the invariant of the QUEUE structure.

QUEUE-LAST-ELEMENT (QUEUE)

PRE: (queue-p queue) RETURN: The last element of the queue.

QUEUE-LENGTH (QUEUE)

PRE: (queue-p queue) RETURN: The number of elements in the queue.

QUEUE-REQUEUE (QUEUE ELEMENT)

DO: Insert the element at the beginning of the queue. PRE: (queue-p queue) l=(queue-length queue) POST: (eq (queue-first-element queue) element) (queue-p queue), l+1=(queue-length queue) RETURN: queue

QUEUE-TEST

DO: Test the queue data type. Insert test log at the point.

Private

QUEUE-HEAD (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

QUEUE-TAIL (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

Undocumented

%MAKE-QUEUE (&KEY ((HEAD DUM0) NIL) ((TAIL DUM1) NIL))

COPY-QUEUE (INSTANCE)

SETFQUEUE-HEAD (NEW-VALUE INSTANCE)

QUEUE-P (OBJECT)

SETFQUEUE-TAIL (NEW-VALUE INSTANCE)

MACRO

Private

WHILE (CONDITION &BODY BODY)

While loop.

CLASS

Public

QUEUE

The queue structure.