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.