This module exports a double-linked list type. This is a structure
optimized for insertions and deletions in any place, each node keeping
a pointer to both the previous and the next node. The stub keeps a
pointer to the head of the list, and the list is circularly closed
(the tail points to the head).
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/>
|
dll |
structure |
A Doubly-Linked List. A DLL keeps a reference to the first node and to the last node.
|
(dll &rest list) |
function |
RETURN: A new DLL containing the elements passed as arguments.
|
(dll-append &rest dlls) |
function |
DO: Appends the elements in all the DLLS into a single dll.
The DLLs are not modified.
RETURN: A new dll with all the elements in DLLS.
|
(dll-contents dlist) |
function |
RETURN: A new list containing the items of the dll.
|
(dll-copy dlist) |
function |
RETURN: A copy of the DLL DLIST.
|
(dll-delete node dlist) |
function |
DO: Delete the NODE from the DLL DLIST. RETURN: DLIST
|
(dll-empty-p dlist) |
function |
RETURN: Whether the DLL DLIST is empty. ie. (zerop (dll-length dlist))
|
(dll-equal &rest dlls) |
function |
RETURN: Whether all the DLLS contain the same elements in the same order.
|
(dll-first dlist) |
function |
RETURN: The first element in the DLL DLIST, or NIL if it's empty.
|
(dll-first-node dlist) |
function |
RETURN: The first node of the DLIST.
|
(dll-insert dlist node item) |
function |
DO: Insert a new node after NODE, or before first position when (NULL NODE). RETURN: The new node.
|
(dll-last dlist) |
function |
RETURN: The last element in the DLL DLIST, or NIL if it's empty.
|
(dll-last-node dlist) |
function |
RETURN: The last node of the DLIST.
|
(dll-length dlist) |
function |
RETURN: The number of elements in the DLL DLIST.
|
(dll-nconc first-dll &rest dlls) |
function |
PRE: No dll appears twice in (CONS FIRST-DLL DLLS).
DO: Extract the nodes from all but the FIRST-DLL,
and append them all to that FIRST-DLL.
POST: ∀l∈dlls, (dll-empty-p l)
(dll-length first-dll) = Σ (dll-length old l)
l∈dlls
|
dll-node |
structure |
A node in a Doubly-Linked List. Each node is linked to the previous and to the next node in the list, and keeps a reference to its item.
|
(dll-node-item dll-node) |
function |
The item of the node.
|
(dll-node-next dll-node) |
function |
The next node.
|
(dll-node-nth index dlist) |
function |
RETURN: The INDEXth node of the DLL DLIST, or NIL if it's empty.
|
(dll-node-position node dlist &key test) |
function |
RETURN: The INDEX of the first node in the DLL DLIST that satisfies
the test (TEST element NODE).
|
(dll-node-previous dll-node) |
function |
The previous node.
|
(dll-nth index dlist) |
function |
RETURN: The INDEXth element in the DLL DLIST.
|
(dll-position item dlist &key test) |
function |
RETURN: The INDEX of the first element in the DLL DLIST that satisfies
the test (TEST element ITEM).