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/>

(make-queue)

function

RETURN: A new empty queue.

queue

structure

The queue structure.

(queue-append queue elements)

function

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)

function

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

(queue-dequeue queue)

function

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)

function

RETURN: The list of elements in the queue.

(queue-empty-p queue)

function

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

(queue-enqueue queue element)

function

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)

function

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

(queue-invariant queue)

function

DO: Check the invariant of the QUEUE structure.

(queue-last-element queue)

function

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

(queue-length queue)

function

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

(queue-requeue queue element)

function

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)

function

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