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

This package exports list processing functions. License: AGPL3 Copyright Pascal J. Bourguignon 2003 - 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

AGET (PLACE INDICATOR &OPTIONAL DEFAULT)

RETURN: The value of the entry INDICATOR of the a-list PLACE, or DEFAULT.

CIRCULAR-LENGTH (LIST)

LIST must be either a proper-list or a circular-list, not a dotted-list. RETURN: the total length ; the length of the stem ; the length of the circle.

COMBINE (&REST ARGS)

RETURN: (elt args 0) x (elt args 1) x ... x (elt args (1- (length args))) = the set of tuples built taking one item in order from each list in args. EXAMPLE: (COMBINE '(WWW FTP) '(EXA) '(COM ORG))) --> ((WWW EXA COM) (WWW EXA ORG) (FTP EXA COM) (FTP EXA ORG))

DEEPEST (TREE)

RETURN: The deepest list in the tree. NOTE: Iterative algorithm. SEE-ALSO: deepest-rec

DEEPEST-REC (TREE)

RETURN: The deepest list in the tree. NOTE: Recursive algorithm. SEE-ALSO: deepest-iti

DEPTH (TREE)

RETURN: The depth of the tree.

DLL-NEXT (DLL-CONS)

RETURN: The next dll-cons in the `dll-cons' double-linked-list node.

DLL-NODE (DLL-CONS)

RETURN: The node in the `dll-cons' double-linked-list node.

DLL-PREVIOUS (DLL-CONS)

RETURN: The previous dll-cons in the `dll-cons' double-linked-list node.

ENSURE-CIRCULAR (LIST)

If list is not a circular list, then modify it to make it circular. RETURN: LIST

ENSURE-LIST (ITEM)

RETURN: item if it's a list or (list item) otherwise.

EQUIVALENCE-CLASSES (SET &KEY (TEST #'EQL) (KEY #'IDENTITY))

RETURN: The equivalence classes of SET, via KEY, modulo TEST.

FLATTEN (TREE)

RETURN: A list containing all the elements of the `tree'.

HASHED-INTERSECTION

AUTHORS: Paul F. Dietz <dietz@dls.net> Thomas A. Russ <tar@sevak.isi.edu>

IOTA (COUNT &OPTIONAL (START 0) (STEP 1))

RETURN: A list containing the elements (start start+step ... start+(count-1)*step) The start and step parameters default to 0 and 1, respectively. This procedure takes its name from the APL primitive. EXAMPLE: (iota 5) => (0 1 2 3 4) (iota 5 0 -0.1) => (0 -0.1 -0.2 -0.3 -0.4)

LIST-ELEMENTS (CLIST)

CLIST is any kind of list: proper-list, circular-list or dotted-list. RETURN: for a proper list: a copy of clist, the length of the list and 0; for a circular list: a list of elements in the clist, the length of the stem, and the length of the circle; for a dotted list: a list of the elements in the clist, the number of cons cells, and nil; for an atom: a list of the atom, 0, and nil.

LIST-INSERT-SEPARATOR (LIST SEPARATOR)

RETURN: A list composed of all the elements in `list' with `separator' in-between. EXAMPLE: (list-insert-separator '(a b (d e f) c) 'x) ==> (a x b x (d e f) x c)

LIST-LENGTHS (LIST)

LIST is any kind of list: proper-list, circular-list or dotted-list. RETURN: for a proper list, the length of the list and 0; for a circular list, the length of the stem, and the length of the circle; for a dotted list, the number of cons cells, and nil; for an atom, 0, and nil.

LIST-TO-DOUBLE-LINKED-LIST (SINGLE)

RETURN: A double-linked-list. NOTE: Use dll-node, dll-next and dll-previous to walk the double-linked-list. EXAMPLE: (setq d (list-to-double-linked-list '( a b c))) ==> (a nil b #0 c (b #0 c #1)) (dll-node d) ==> a (dll-next d) ==> (b (a nil b #1 c #0) c #0) (dll-previous (dll-next d)) ==> (a nil b #0 c (b #0 c #1))

LIST-TRIM (BAG LIST &KEY (TEST #'EQL) (KEY #'IDENTITY))

RETURN: A sublist of LIST with the elements in the BAG removed from both ends.

MAKE-CIRCULAR-LIST (SIZE &KEY INITIAL-ELEMENT)

RETURN: a new circular list of length SIZE. POST: (circular-length (make-circular-list size)) == (values size 0 size)

MAKE-LIST-OF-RANDOM-NUMBERS (LENGTH &KEY (MODULO MOST-POSITIVE-FIXNUM))

RETURN: A list of length `length' filled with random numbers MODULO: The argument to RANDOM.

MAPTREE (FUN &REST TREES)

DO: Calls FUN on each non-null atom of the TREES. PRE: The trees in TREES must be congruent, or else the result is pruned like the smallest tree. RETURN: A tree congruent to the TREES, each node being the result of FUN (it may be a subtree).

MEMQ (ITEM LIST)

RETURN: (MEMBER ITEM LIST :TEST (FUNCTION EQ))

NSPLIT-LIST (LIST POSITION &KEY (FROM-END NIL))

PRE: 0<=POSITION<=(LENGTH LIST) DO: SPLIT THE LIST IN TWO AT THE GIVEN POSITION. (NSPLIT-LIST (LIST 'A 'B 'C) 0) --> NIL ; (A B C) (NSPLIT-LIST (LIST 'A 'B 'C) 1) --> (A) ; (B C) (NSPLIT-LIST (LIST 'A 'B 'C) 2) --> (A B) ; (C) (NSPLIT-LIST (LIST 'A 'B 'C) 3) --> (A B C) ; NIL POSITION: POSITION OF THE SPLIT; WHEN FROM-START AND 0<=POSITION<=(LENGTH LIST), THAT'S THE LENGTH OF THE FIRST RESULT FROM-START: THE DEFAULT, SPLIT COUNTING FROM THE START. FROM-END: WHEN SET, COUNT FROM THE END OF THE LIST. (NSPLIT-LIST L P :FROM-END T) === (NSPLIT-LIST L (- (LENGTH L) P)) RETURN: THE FIRST PART ; THE LAST PART

NSPLIT-LIST-ON-INDICATOR (LIST INDICATOR)

RETURN: a list of sublists of list (the conses from list are reused), the list is splited between items a and b for which (indicator a b).

PLIST-CLEANUP (PLIST)

Returns a plist that has the same associations than PLIST, but with a single occurence of each key and the first value found. EXAMPLE: (plist-cleanup '(:a 1 :b 2 :a 11 :c 3)) --> (:b 2 :c 3 :a 1)

PLIST-GET (PLIST PROP)

Extract a value from a property list. PLIST is a property list, which is a list of the form (PROP1 VALUE1 PROP2 VALUE2...). This function returns the value corresponding to the given PROP, or nil if PROP is not one of the properties on the list.

PLIST-KEYS (PLIST)

Returns a list of the properties in PLIST.

PLIST-PUT (PLIST PROP VALUE)

Change value in PLIST of PROP to VALUE. PLIST is a property list, which is a list of the form (PROP1 VALUE1 PROP2 VALUE2 ...). PROP is a symbol and VALUE is any object. If PROP is already a property on the list, its value is set to VALUE, otherwise the new PROP VALUE pair is added. The new plist is returned; use `(setq x (plist-put x prop val))' to be sure to use the new value. The PLIST is modified by side effects.

PLIST-REMOVE (PLIST PROP)

DO: (REMF PLIST PROP) RETURN: The modified PLIST.

PROPER-LIST-P (OBJECT)

RETURN: whether object is a proper list NOTE: terminates with any kind of list, dotted, circular, etc.

REPLACE-TREE (DST SRC)

DO: Copies the elements of the src tree into the dst tree. If dst is missing cons cells, structure sharing occurs. RETURN: dst

SUBSETS (SET)

RETURN: The set of all subsets of the strict SET.

TRANSPOSE (TREE)

RETURN: A tree where all the CAR and CDR are exchanged.

TREE-DIFFERENCE (A B &KEY (TEST #'EQL))

RETURN: A tree congruent to A and B where each node is = when the corresponding nodes are equal (as indicated by TEST), or (/= a-elem b-elem) otherwise. EXAMPLE: (tree-difference '((a b c) 1 (d e f)) '((a b c) (1) (d x f))) --> ((= = = . =) (/= 1 (1)) (= (/= e x) = . =) . =)

Private

CIRCULAR-LIST-LENGTHS (CIRCULAR-LIST)

CIRCULAR-LIST must be a circular list. RETURN: the length of the stem; the length of the circle.

DOTTED-LIST-LENGTH (DOTTED-LIST)

DOTTED-LIST must be a dotted list or a proper list. RETURN: the number of cons cells in the list.

Undocumented

LIST-TRIM-TEST

TEST

TEST/LIST-ELEMENTS

TEST/LIST-LENGTHS