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

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

README:

FUNCTION

Public

DLL (&REST LIST)

RETURN: A new DLL containing the elements passed as arguments.

DLL-APPEND (&REST DLLS)

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)

RETURN: A new list containing the items of the dll.

DLL-COPY (DLIST)

RETURN: A copy of the DLL DLIST.

DLL-DELETE (NODE DLIST)

DO: Delete the NODE from the DLL DLIST. RETURN: DLIST

DLL-EMPTY-P (DLIST)

RETURN: Whether the DLL DLIST is empty. ie. (zerop (dll-length dlist))

DLL-EQUAL (&REST DLLS)

RETURN: Whether all the DLLS contain the same elements in the same order.

DLL-FIRST (DLIST)

RETURN: The first element in the DLL DLIST, or NIL if it's empty.

DLL-FIRST-NODE (DLIST)

RETURN: The first node of the DLIST.

DLL-INSERT (DLIST NODE ITEM)

DO: Insert a new node after NODE, or before first position when (NULL NODE). RETURN: The new node.

DLL-LAST (DLIST)

RETURN: The last element in the DLL DLIST, or NIL if it's empty.

DLL-LAST-NODE (DLIST)

RETURN: The last node of the DLIST.

DLL-LENGTH (DLIST)

RETURN: The number of elements in the DLL DLIST.

DLL-NCONC (FIRST-DLL &REST DLLS)

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-ITEM (INSTANCE)

The item of the node.

DLL-NODE-NEXT (INSTANCE)

The next node.

DLL-NODE-NTH (INDEX DLIST)

RETURN: The INDEXth node of the DLL DLIST, or NIL if it's empty.

DLL-NODE-POSITION (NODE DLIST &KEY (TEST #'EQL))

RETURN: The INDEX of the first node in the DLL DLIST that satisfies the test (TEST element NODE).

DLL-NODE-PREVIOUS (INSTANCE)

The previous node.

DLL-NTH (INDEX DLIST)

RETURN: The INDEXth element in the DLL DLIST.

DLL-POSITION (ITEM DLIST &KEY (TEST #'EQL))

RETURN: The INDEX of the first element in the DLL DLIST that satisfies the test (TEST element ITEM).

Undocumented

SETFDLL-NODE-ITEM (NEW-VALUE INSTANCE)

SETFDLL-NODE-NEXT (NEW-VALUE INSTANCE)

SETFDLL-NODE-PREVIOUS (NEW-VALUE INSTANCE)

Private

%DLL-FIRST (INSTANCE)

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

%DLL-LAST (INSTANCE)

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

DLL-DELETE-NTH (INDEX DLIST)

DO: Delete the INDEXth element of the DLL DLIST. RETURN: DLIST

Undocumented

SETF%DLL-FIRST (NEW-VALUE INSTANCE)

SETF%DLL-LAST (NEW-VALUE INSTANCE)

COPY-DLL (INSTANCE)

COPY-DLL-NODE (INSTANCE)

DLL-EXTRACT-NODE (DLIST NODE)

DLL-NODE-P (OBJECT)

DLL-P (OBJECT)

MAKE-DLL (&KEY ((FIRST DUM0) NIL) ((LAST DUM1) NIL))

MAKE-DLL-NODE (&KEY ((PREVIOUS DUM38) NIL) ((NEXT DUM39) NIL) ((ITEM DUM40) NIL))

CLASS

Public

DLL (&REST LIST)

A Doubly-Linked List. A DLL keeps a reference to the first node and to the last node.

DLL-NODE

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.