Common Lisp Package: DLIST

README:

dlist - A Common Lisp library that implements doubly-linked lists ================================================================= dlist is a Common Lisp library that implements the doubly-linked list data structure. dlist provides many operations on doubly-linked lists, or dlists, which are documented in the file documentation.html , which is available with the source. If your lisp implementation supports [user-extensible sequences][1] (which only SBCL and ABCL do currently), you will be able to use the standard Common Lisp sequence functions (map, reduce, etc.) with dlists. dlist does not have any dependencies other than a common lisp implementation. Obtaining and installing dlist ------------------------------ dlist is available from [http://github.com/krzysz00/dlist](GitHub) and can be installed via Quicklisp (not yet). To use dlist, simply load the ASDF system. Use: (asdf:oos 'asdf:test-op :dlist) to run the test suite. dlist is licensed under the 3-Clause BSD Licence, see the file COPYING for details. Contact Information ------------------- You can reach the author (Krzysztof Drewniak) at <krzysdrewniak@gmail.com>. If you find any bugs, please report them at dlist's GitHub issue tracker. [1]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.65.1604&rep=rep1&type=pdf

FUNCTION

Public

COPY-DLIST (DLIST &KEY DEEP-COPY)

Copies `dlist', returning a new dlist with the same elements as `dlist'. If `deep-copy' is true, `copy-dlist' deep-copies dlists and sequences.

DATA (DCONS)

Accesses the `data' slot of a dcons. The `data' of nil is nil.

SETFDATA (VAL PLACE)

Sets the `data' slot of `place' (which must be a `dcons') to `val'

DCONS (PREV DATA NEXT)

Constructs a `dcons' with the given `prev', `data', and `next'

DCONSP (OBJECT)

Returns T if `object' is a dcons

DLIST (&REST ELEMENTS)

Returns a doubly-linked list (dlist) with the elements in `elements'

DLIST->LIST (DLIST)

Converts a dlist to a list

DLIST-APPEND (&REST DLISTS)

Appends `dlists' non-derstructively by calling `dlist-nconc' with shallow copies of each dlist.

DLIST-FIRST (DLIST)

Gets the first `dcons' in a `dlist'

DLIST-LAST (DLIST)

Gets the last `dcons' in a `dlist'

DLIST-LENGTH (DLIST)

Returns the length of `dlist'

DLIST-NCONC (&REST DLISTS)

Appends `dlists'. This works like `nconc' for singly-linked lists, except it is destructive and the resuld will share structure with the input dlists. This function should have running time proportional to the number of lists being appended.

DLIST-NTH (N DLIST &KEY FROM-END)

Returns the nth element of `dlist', as the primary value. If n is >= the length of the list, NIL will be returned. The secondary value will be T if the value was actually found in the list, and NIL otherwise. If `from-end' is true, `dlist-nth' returns the @code{n}th element from the end, subject to the rules above.

SETFDLIST-NTH (VAL N DLIST &KEY FROM-END)

Sets the data of the nth dcons in `dlist' to `val'. If `from-end' is true, sets the @code{n}th element from the end.

DLIST-REVERSE (DLIST)

Reverses dlist non-destructively.

DLIST= (DLIST &REST MORE-DLISTS)

Tests dlists for equality by element, recursively descending into sub-dlists.

DLISTP (OBJECT)

Tests if `object' is a dlist.

MAKE-DLIST (SIZE &KEY INITIAL-ELEMENT)

Creates a dlist that contains `initial-element' `size' times.

MAPDCON (FUNCTION DLIST &REST MORE-DLISTS-AND-FROM-END)

Maps `function' over `dlist' the dconses in `dlist', then returns `dlist'

MAPDCONS (FUNCTION DLIST &REST MORE-DLISTS-AND-FROM-END)

Maps over the dconses in `dlist' and `more-dlists'. If `more-dlists' contains the keyword :from-end, the value after it in the argumnt list will be taken as the value of :from-end, and both will be removed from `more-dlists'. The order of elements in the result is the same as the oder in which the elements are returned from the function.

MAPDLIST (FUNCTION DLIST &REST MORE-DLISTS-AND-FROM-END)

Behaves like `mapdcons', except the function will be passed the `data' of each dcons.

NEXT (DCONS)

Accesses the `next' slot of a dcons. The `next' of nil is nil.

SETFNEXT (VAL PLACE)

Sets the `next' slot of `place' (which must be a `dcons') to `val'

NTHDCONS (N DLIST &KEY FROM-END)

Returns the @code{n}th dcons in `dlist' (zero-based). If n is >= the length of the list, returns NIL. If `from-end' is true, returns the @code{n}th dcons from the end.

PREV (DCONS)

Accesses the `prev' slot of a dcons. The `prev' of nil is nil.

SETFPREV (VAL PLACE)

Sets the `prev' slot of `place' (which must be a `dcons') to `val'

Undocumented

SETFDLIST-FIRST (VAL PLACE)

SETFDLIST-LAST (VAL PLACE)

Private

DCONS-APPEND (OBJECT DCONS)

Creates a dcons whose `data' is `object' and appends it to `dcons', returning `dcons' with a pointer to the new dcons in `dcons''s next.

DCONS-DATA (INSTANCE)

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

DCONS-NEXT (INSTANCE)

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

DCONS-PREV (INSTANCE)

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

DLIST-CONS-ON (OBJECT DLIST)

Returns a dlist whose elements are `object' and the elements of `dlist'. `dlist' is destructively mosified. This is intended to have the same use as @code{(cons object list)} for regular lists.

Undocumented

COPY-DCONS (INSTANCE)

SETFDCONS-DATA (NEW-VALUE INSTANCE)

SETFDCONS-NEXT (NEW-VALUE INSTANCE)

DCONS-P (OBJECT)

SETFDCONS-PREV (NEW-VALUE INSTANCE)

MAKE-DCONS (&KEY ((PREV DUM0) NIL) ((DATA DUM1) NIL) ((NEXT DUM2) NIL))

MACRO

Public

DLIST-POP (DLIST &KEY FROM-END)

Pops an element from dlist and returns it. If `from-end' is non-`nil', the element will be popped from the end of the dlist. Otherwise, it will be popped from the begining.

DLIST-PUSH (OBJ DLIST &KEY AT-END)

Pushes `obj' onto `dlist'. If `at-end' is not-nil, the element is added to the end of dlist, otherwise it is added to the begining.

DODCONS ((VAR DLIST &OPTIONAL RESULT-FORM FROM-END) &BODY BODY)

Loops over the dconses in `dlist', binding `var' to each in turn. If `from-end' is non-nil, the loop proceeds from the last element of ther list to the first. This is basically `dolist' for dlists.

DODLIST ((VAR DLIST &OPTIONAL RESULT-FORM FROM-END) &BODY BODY)

Loops over the elements in `dlist', binding each to `var' in turn, then executing `body'. If `from-end' is non-nil, the loop proceeds from the end of the list to the begining.

SLOT-ACCESSOR

Private

Undocumented

%DLIST-FIRST (OBJECT)

SETF%DLIST-FIRST (NEW-VALUE OBJECT)

%DLIST-LAST (OBJECT)

SETF%DLIST-LAST (NEW-VALUE OBJECT)

CLASS

Public

DCONS (PREV DATA NEXT)

A three-member cons cell for doubly-linked lists, which has `prev', `data' and `next' slots

DLIST (&REST ELEMENTS)

A class that represents a doubly-linked list