# FUNCTION

# Public

# DEQUEUE (Q)

The queue that results when the first item is removed from the given queue.

# DICTIONARY-ADD (D K V)

A dictionary similar to the given dictionary except that k maps to
v in the returned dictionary.

# DICTIONARY-AS-ALIST (D)

An alist containing the same key-value pairs as the given dictionary.

# DICTIONARY-LOOKUP (D K)

The value associated with the given key in the given dictionary. A second
value is returned to indicate whether the key is associated with any value or
is not found.

# DICTIONARY-REMOVE (D K)

A dictionary similar to the given dictionary, except that k does
not map to any value in the returned dictionary.

# ENQUEUE (Q ITEM)

The queue that results when the given item is equeued on the given queue.

# F-ARRAY-COUNT (ITEM F-ARRAY &KEY (KEY #'IDENTITY) (TEST #'EQL))

The number of elements in the given f-array that satisfy the test.

# F-ARRAY-COUNT-IF (PRED F-ARRAY &KEY (KEY #'IDENTITY))

The number of elements in the given f-array that satisfy the test.

# F-ARRAY-ELT (ARRAY INDEX)

The element at the given index of the given array.

# F-ARRAY-REPLACE (ARRAY INDEX ELEMENT)

An array similar to the given array except that index and element are
associated in the returned array.

# F-ARRAY-SIZE (ARRAY)

The number of elements in the given array.

# HEAP-EMPTY-P (HEAP)

Whether the given heap has any elements.

# HEAP-FIRST (HEAP)

The first value on the given heap.

# MAKE-AVL-TREE

An empty AVL tree.

# MAKE-BINARY-TREE

An empty binary tree.

# MAKE-DICTIONARY (&KEY (HASH #'SXHASH) (TEST #'EQL))

An empty dictionary that hashes occording to the given hash function,
which defaults to #'sxhash and and tests according to the given test
function, which defaults to #'eql.

# MAKE-F-ARRAY (SIZE &KEY (INITIAL-CONTENTS NIL) (INITIAL-ELEMENT NIL))

A functional array of the given size with the given initial contents.

# MAKE-HEAP (&KEY (PRIORITY 0 P-P) VALUE (LEFT (MAKE-HEAP-LEAF)) (RIGHT (MAKE-HEAP-LEAF)))

An empty binary heap.

# MAKE-STACK

An empty stack.

# MAP-F-ARRAY (FUNCTION F-ARRAY)

A new f-array whose elements are the results of the application
of the given function to the elements of the given f-array.

# MAP-QUEUE (FUNCTION Q)

A queue containing items that are the result of applying function to
the items in the given queue.

# MAP-STACK (FUNCTION STACK)

A stack whose elements are those of the given stack when function is applied
to them.

# MAP-TREE (FUNCTION TREE)

A tree each node of which corresponds to the application of
function to one node of the given tree.

# QUEUE-AS-LIST (Q)

The elements in the given queue, returned as a list, in the order they
would be dequeued from the given queue.

# QUEUE-COUNT (ITEM Q &KEY (KEY #'IDENTITY) (TEST #'EQL))

The number of elements in the given queue that satisfy the test.

# QUEUE-COUNT-IF (PREDICATE Q &KEY (KEY #'IDENTITY))

The number of elements in the given queue that satisfy the test.

# QUEUE-EMPTY-P (Q)

Whether the given queue does not contain any items.

# QUEUE-FIRST (Q)

The value at the head of the given queue.

# QUEUE-SIZE (Q)

The number of items in the given queue.

# STACK-AS-LIST (STACK)

This function is here in case the implementation of stack changes from what
it is now, a list.

# STACK-EMPTY-P (STACK)

Whether the given stack is empty.

# STACK-FROM-LIST (LIST)

This function is here in case the implementation of stack changes from what
it is now, a list.

# STACK-PUSH (STACK ITEM)

The stack that results when the given item is pushed onto the given stack.

# STACK-SIZE (STACK)

The number of items on this stack; note that this is an O(n) operation.

# STACK-TOP (STACK)

The top item on the given stack.

# TREE-COUNT (ITEM TREE &KEY (KEY #'IDENTITY) (TEST #'EQL))

The number of sub-trees in the tree that satisfy the test.

# TREE-COUNT-IF (PREDICATE TREE &KEY (KEY #'IDENTITY))

The number of sub-trees in the given tree that satisfy the test.

# Undocumented

# DICTIONARY-FROM-ALIST (ALIST &KEY (TEST #'EQL) (HASH #'SXHASH))

# F-ARRAY-AS-LIST (F-ARRAY)

# MAKE-QUEUE (&KEY (INITIAL-CONTENTS NIL))

# STACK-COUNT (ITEM STACK &KEY (KEY #'IDENTITY) (TEST #'EQL))

# STACK-COUNT-IF (PREDICATE STACK &KEY (KEY #'IDENTITY))

# Private

# CLIP-LAST (HEAP)

The heap that results when the last node is removed.

# DICT-HASH (INSTANCE)

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

# DICT-TEST (INSTANCE)

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

# DICT-TREE (INSTANCE)

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

# STACK-POP (STACK)

The stack that results when the top item is popped off the given stack.

# Undocumented

# ATTACH-HEAP (ROOT &KEY LEFT RIGHT)

# BALANCE (KEY VALUE LEFT RIGHT)

# BALANCED-P (T1 T2)

# BUBBLE-DOWN (ROOT &KEY LEFT RIGHT ORDER)

# COPY-DICT (INSTANCE)

# SETFDICT-HASH (NEW-VALUE INSTANCE)

# DICT-P (OBJECT)

# SETFDICT-TEST (NEW-VALUE INSTANCE)

# SETFDICT-TREE (NEW-VALUE INSTANCE)

# HEAVIER-P (TREE &KEY SIDE)

# HEIGHT-DIFFERENCE (T1 T2)

# IN-ORDER-P (H1 H2 &KEY ORDER)

# LAST-DIRECTION (HEAP)

# LAST-NODE (HEAP)

# LEFT-P (SIDE)

# MAKE-AVL-LEAF

# MAKE-BT-LEAF

# MAKE-DICT (&KEY ((HASH DUM0) NIL) ((TEST DUM1) NIL) ((TREE DUM2) NIL))

# MAKE-HEAP-LEAF

# NEXT-DIRECTION (HEAP)

# NEXT-IN-ORDER (TREE)

# NO-CHILDREN-P (HEAP)

# OTHER-SIDE (SIDE)

# PARENT-HEIGHT (T1 T2)

# PATH-DIRECTION (N)

# REMOVE-ROOT (TREE &KEY TEST ORDER)

# REMOVE-ROOT-WITH-CHILDREN (TREE &KEY TEST ORDER)

# ROTATE (INSIDE ROOT-KEY ROOT-VALUE OUTSIDE &KEY SIDE)

# SIDE-TO-INSERT (TREE KEY &KEY ORDER)

# STITCH-AVL-TREE (&KEY ROOT (KEY (BT-KEY ROOT)) (VALUE (BT-VALUE ROOT)) (LEFT (MAKE-AVL-LEAF)) (RIGHT (MAKE-AVL-LEAF)))

# STITCH-BINARY-TREE (&KEY ROOT (KEY (BT-KEY ROOT)) (VALUE (BT-VALUE ROOT)) (LEFT (MAKE-BINARY-TREE)) (RIGHT (MAKE-BINARY-TREE)))

# TREE-CHILD (TREE &KEY SIDE)

# GENERIC-FUNCTION

# Public

# HEAP-REMOVE (HEAP &KEY ORDER)

The heap that results when first value is removed
from the given heap.

# TREE-AS-ALIST (TREE)

An association list containing the key-value pairs in the given tree.

# TREE-EMPTY-P (TREE)

Whether the given tree does not contain key-value pairs.

# TREE-FIND (TREE KEY &KEY TEST ORDER)

The value to which the given key is mapped, or nil if this tree contains no
such key. The second value returned indicates whether the tree contained the
key. So
(find t k) -> nil t
if k maps to nil. But
(find t k) -> nil nil
if there is no mapping for k in the tree.

# TREE-HEIGHT (TREE)

The height of the given tree.

# TREE-INSERT (TREE KEY VALUE &KEY TEST ORDER)

A new tree similar to the given tree except that the given key and
value are now associated with one another. If the given key is already
contained in the tree, according to the test function, then the old value
is replaced by the specified value in the returned tree. The order function
specifies whether the given key-value pair should be inserted to the left or
right of the given tree. The given tree is not modified.

# TREE-REMOVE (TREE KEY &KEY TEST ORDER)

A new tree with the given key removed. The test function is used to compare
the tree's key to the given key. The order function is used to determine
whether the key can be found to the left or right if it is not found at the
root.

# TREE-WEIGHT (TREE)

The number of nodes in the given tree.

# Undocumented

# HEAP-INSERT (HEAP VALUE PRIORITY &KEY ORDER)

# Private

# Undocumented

# STITCH-TREE (TREE &KEY RIGHT LEFT (VALUE (BT-VALUE TREE)) (KEY (BT-KEY TREE)))

# TREE-AS-PRE-ORDER-ALIST (TREE)

# SLOT-ACCESSOR

# Public

# Undocumented

# BT-KEY (OBJECT)

# BT-VALUE (OBJECT)

# Private

# Undocumented

# AVL-HEIGHT (OBJECT)

# BT-LEFT (OBJECT)

# BT-RIGHT (OBJECT)

# HEAP-PRIORITY (OBJECT)

# HEAP-WEIGHT (OBJECT)

# QUEUE-HEAP (OBJECT)

# QUEUE-NEXT-PRIORITY (OBJECT)

# VARIABLE

# Private

# Undocumented

# +HEAP-LEAF+

# CLASS

# Private

# AVL-LEAF

A leaf node of an AVL tree.

# AVL-TREE

A height-balanced binary tree.

# BINARY-TREE

A binary tree that holds a key-value pair in its root.

# BT-LEAF

A leaf node of an AVL tree.

# HEAP-LEAF

A leaf node of a heap.

# LEAF

A leaf with no data or children.

# TREE

The foundation of all trees.