# 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.