Abstract
Sycamore is a fast, purely functional data structure library in Common Lisp. It include hash array mapped tries, weight-balanced binary trees, set and map (dictionary) interfaces, pairing heaps, and amortized queues.
SYCAMORE is available under the 3-Clause BSD license.Download Source:
git clone https://github.com/ndantam/sycamore
%rope
*rope-print*
alist-hash-map
alist-tree-map
amortized-dequeue
amortized-enqueue
amortized-queue
amortized-queue
amortized-queue-empty-p
amortized-queue-list
amortized-queue-push
do-hash-map
do-tree-map
do-tree-set
empty-hash-map
empty-tree-map
empty-tree-set
fold-hash-map
fold-hash-map-keys
fold-hash-map-values
fold-hash-set
fold-right-hash-set
fold-tree-map
fold-tree-set
hash-map
hash-map-alist
hash-map-contains
hash-map-find
hash-map-hash-table
hash-map-insert
hash-map-keys
hash-map-remove
hash-map-values
hash-set
hash-set-difference
hash-set-empty-p
hash-set-find
hash-set-insert
hash-set-intersection
hash-set-intersection-p
hash-set-list
hash-set-remove
hash-set-subset-p
hash-set-union
hash-table-hash-map
hash-table-tree-map
list-hash-set
make-amortized-queue
make-hash-map
make-hash-set
make-tree-map
make-tree-set
map-hash-map
map-hash-set
map-tree-map
map-tree-set
object-rope
or-compare
output-rope
rope
rope-compare-fast
rope-compare-lexographic
rope-length
rope-map
rope-parenthesize
rope-pathname
rope-ref
rope-split
rope-string
rope-write
rope/=
rope<
rope<=
rope=
rope>
rope>=
ropep
sexp-rope
subrope
tree-map
tree-map-alist
tree-map-contains
tree-map-count
tree-map-find
tree-map-hash-table
tree-map-insert
tree-map-insert-alist
tree-map-insert-hash-table
tree-map-insert-map
tree-map-insertf
tree-map-keys
tree-map-remove
tree-map-values
tree-set
tree-set
tree-set-compare
tree-set-count
tree-set-difference
tree-set-equal-p
tree-set-find
tree-set-insert
tree-set-insertf
tree-set-intern
tree-set-intersection
tree-set-intersection-difference
tree-set-intersection-p
tree-set-list
tree-set-max
tree-set-member-p
tree-set-min
tree-set-p
tree-set-position
tree-set-ref
tree-set-remove
tree-set-remove-max
tree-set-remove-min
tree-set-remove-position
tree-set-replace
tree-set-subset-p
tree-set-union
[Function]
%rope first second => result
Construct a rope from FIRST and SECOND. FIRST: an object of rope or sequence type SECOND: an object of rope or sequence type RETURNS: a rope concatenating FIRST and SECOND
[Special variable]
*rope-print*
How to print ropes, one of (or :rope :string :structure)
[Function]
alist-hash-map alist &key test hash-function => result
Returns a hash-map from keys and values of association list `ALIST'
[Function]
alist-tree-map alist compare => result
Returns a tree-map containing the keys and values of the association list ALIST.
[Function]
amortized-dequeue queue => result
Remove first element of QUEUE. RETURNS: (VALUES new-queue element)
[Function]
amortized-enqueue queue element => result
Add ELEMENT to QUEUE. RETURNS: new-queue
[Standard class]
amortized-queue
[Function]
amortized-queue &rest args => result
Create an amortized queue of ARGS.
[Function]
amortized-queue-empty-p queue => result
Is the queue empty?
[Function]
amortized-queue-list queue => result
Return an inorder list of elements in QUEUE.
[Function]
amortized-queue-push queue element => result
Add ELEMENT to the front of QUEUE.
[Macro]
do-hash-map ((key value) hash-map &optional result) declaration* statement* => result
[Macro]
do-tree-map ((key value) map &optional result) declaration* statement* => result
[Macro]
do-tree-set (var set &optional result) declaration* statement* => result
[Function]
empty-hash-map hash-map => result
Create a new empty hash-map.
[Function]
empty-tree-map tree-map => result
Create a new empty tree-map.
[Function]
empty-tree-set tree-set => result
Create a new empty tree-set.
[Function]
fold-hash-map function initial-value hash-map => result
Fold `FUNCTION' over members of the `HASH-MAP' FUNCTION: (FUNCTION (initial-value key value)) -> initial-value
[Function]
fold-hash-map-keys function initial-value hash-map => result
Fold `FUNCTION' over members of the `HASH-MAP' FUNCTION: (FUNCTION (initial-value key)) -> initial-value
[Function]
fold-hash-map-values function initial-value hash-map => result
Fold `FUNCTION' over members of the `HASH-MAP' FUNCTION: (FUNCTION (initial-value value)) -> initial-value
[Function]
fold-hash-set function initial-value set => result
Fold `FUNCTION' over every element of `SET'. FUNCTION: (lambda (initial-value element)) -> next-initial-value. INITIAL-VALUE: value passed as first argument to initial call to `FUNCTION'. SET: a hash-set whose elements are past as the second argument in each call to `FUNCTION'.
[Function]
fold-right-hash-set function set initial-value => result
Fold `FUNCTION' over every element of `SET'. FUNCTION: (lambda (element initial-value)) -> next-initial-value. SET: a hash-set whose elements are past as the first argument in each call to `FUNCTION'. INITIAL-VALUE: value passed as second argument to initial call to `FUNCTION'.
[Function]
fold-tree-map function initial-value tree-map => result
Fold FUNCTION over members of the map FUNCTION: (FUNCTION initial-value key value) -> initial-value
[Function]
fold-tree-set function initial-value set => result
Fold FUNCTION over every element of SET.
[Standard class]
hash-map
[Function]
hash-map-alist hash-map => result
Return an association list of all elements in the hash-map.
[Function]
hash-map-contains hash-map key => result
Test if a `KEY' is present in `HASH-MAP'
[Function]
hash-map-find hash-map key &optional default => result
Find value indexed by `KEY' in `HASH-MAP' RETURNS: (values VALUE T) if `KEY' is in `HASH-MAP', or (values DEFAULT NIL) if `KEY' is not in `HASH-MAP'.
[Function]
hash-map-hash-table hash-map &rest hash-table-initargs => result
Returns a hash table containing the keys and values of `HASH-MAP'. Hash table is initialized using the HASH-TABLE-INITARGS.
[Function]
hash-map-insert hash-map key value => result
Insert `KEY'=>`VALUE' into `HASH-MAP', returning the new hash-map.
[Function]
hash-map-keys hash-map => result
[Function]
hash-map-remove hash-map key => result
Remove `KEY' from `HASH-MAP', returning the new hash-map.
[Function]
hash-map-values hash-map => result
[Standard class]
hash-set
[Function]
hash-set-difference set-1 set-2 => result
Difference of `SET-1' and `SET-2'.
[Function]
hash-set-empty-p set => result
Test if `SET' is empty. RETURNS: T if `SET' contains zero items, or NIL `SET' contains some items.
[Function]
hash-set-find set item &optional default => result
Search `SET' for `ITEM'. RETURNS: (values ITEM T) if `ITEM' is in `SET', or (values DEFAULT NIL) if `ITEM' is not in `SET'.
[Function]
hash-set-insert set item => result
Insert `ITEM' into `SET'.
[Function]
hash-set-intersection set-1 set-2 => result
Intersection of `SET-1' and `SET-2'.
[Function]
hash-set-intersection-p set-1 set-2 => result
Do `SET-1' and `SET-2' intersect?
[Function]
hash-set-list set => result
Return a list of elements in `SET'.
[Function]
hash-set-remove set item => result
Remove `ITEM' from `SET'.
[Function]
hash-set-subset-p set-1 set-2 => result
Is `SET-1' a subset of `SET-2'? RETURNS: T or NIL
[Function]
hash-set-union set-1 set-2 => result
Union of `SET-1' and `SET-2'.
[Function]
hash-table-hash-map hash-table &key test hash-function => result
Returns a hash-map containing the keys and values of the hash-table `HASH-TABLE'.
[Function]
hash-table-tree-map hash-table compare => result
Returns a tree-map containing the keys and values of the hash-table HASH-TABLE.
[Function]
list-hash-set list &key test hash-function key => result
Construct a hash-set from a list of elements.
[Function]
make-amortized-queue => result
Make a new queue.
[Function]
make-hash-map &key test hash-function => result
Create and return new HASH-mAP. The keywords are as follows: :TEST Function to compare items: (TEST key-1 key-2) -> BOOLEAN. :HASH-FUNCTION Function to compute hash codes: (HASH-FUNCTION key) -> non-negative-fixnum. If not provided, MAKE-HASH-SET will try to find a valid hash function for TEST.
[Function]
make-hash-set &key test hash-function key => result
Create and return new HASH-SET. The keywords are as follows: :TEST Function to compare items: (TEST item-1 item-2) -> BOOLEAN. :HASH-FUNCTION Function to compute hash codes: (HASH-FUNCTION item) -> non-negative-fixnum. If not provided, MAKE-HASH-SET will try to find a valid hash function for TEST. :KEY If provided, apply `TEST' and `HASH-FUNCTION' to `(FUNCALL KEY ITEM)'. Note 1: It is required that when (TEST ITEM-1 ITEM-2) is true, HASH-FUNCTION will return the same value for both ITEM-1 and ITEM-2. Note 2: ANSI Common Lisp DOES NOT require #'SXHASH to return the same value for two numbers that are #'= but of different types, or for two objects that are #'EQUALP, but not #'EQUAL. MAKE-HASH-SET will attempt to use implementation-specific hashing functions for those tests. However, if either the implementation specific function is not known to MAKE-HASH-SET or the caller is using some other TEST, then the caller must provide a valid HASH-FUNCTION.
[Function]
make-tree-map compare => result
Create a new tree-map.
[Function]
make-tree-set compare => result
Create a new tree-set.
[Function]
map-hash-map result-type function hash-map => result
Apply `FUNCTION' to all elements in `HASH-MAP'. RESULT-TYPE: (or nil 'list 'vector). FUNCTION: (FUNCTION key value) -> result
[Function]
map-hash-set result-type function set => result
Apply `FUNCTION' to all elements in `SET'. RESULT-TYPE: (or nil 'list 'vector) FUNCTION: (lambda (element)).
[Function]
map-tree-map order result-type function tree-map => result
Apply FUNCTION to all elements in TREE-MAP. ORDER: (or :inorder :preorder :postorder). RESULT-TYPE: (or nil 'list). FUNCTION: (FUNCTION key value) -> result
[Function]
map-tree-set result-type function set => result
Apply FUNCTION to every element of SET.
[Generic function]
object-rope object => result
[Method]
object-rope (object cgen-subscript) => result
[Method]
object-rope (object cgen-binop) => result
[Method]
object-rope (object cgen-unop-post) => result
[Method]
object-rope (object cgen-unop-pre) => result
[Method]
object-rope (object cgen-block) => result
[Method]
object-rope object => result
[Method]
object-rope (object pathname) => result
[Method]
object-rope (object double-float) => result
[Method]
object-rope (object float) => result
[Method]
object-rope (object array) => result
[Method]
object-rope (object list) => result
[Method]
object-rope (object symbol) => result
[Method]
object-rope (object character) => result
[Method]
object-rope (object rope-node) => result
[Method]
object-rope (object string) => result
[Macro]
or-compare &rest comparisons => result
Short-circuit evaluatation of arguments, returning the first one that is nonzero.
[Function]
output-rope object place &key if-exists => result
[Function]
rope &rest args => result
Concatenate all ropes in ARGS. Arguments of sequence type will be flattened and concatanted into the rope. Other non-rope arguments will be coerced to a rope type by calling the OBJECT-ROPE generic function. RETURNS: a rope
[Function]
rope-compare-fast rope-1 rope-2 => result
Compare ropes quickly. The resulting order is not necessarily lexographic.
[Function]
rope-compare-lexographic rope-1 rope-2 => result
Compare ropes lexographically.
[Function]
rope-length rope => result
Return the number of characters in rope
[Function]
rope-map function sequence &key start end separator => result
Apply FUNCTION to each element of SEQUENCE and collect results into a rope. FUNCTION: (lambda (x)) => ROPE SEQUENCE: a sequence START: initial position in SEQUENCE END: final position in SEQUENCE SEPARATOR: a rope to splice between the items of SEQUENCE RETURNS: a rope
[Function]
rope-parenthesize rope => result
Return the parenthesized ROPE.
[Function]
rope-pathname rope => result
Convert the rope to a pathname.
[Function]
rope-ref rope i => result
Return the character at position I.
[Function]
rope-split separator sequence &key start end => result
[Function]
rope-string rope &key element-type => result
Convert the rope to a string.
[Function]
rope-write rope &key escape stream => result
Write ROPE to STREAM.
[Function]
rope/= rope-1 rope-2 => result
[Function]
rope< rope-1 rope-2 => result
[Function]
rope<= rope-1 rope-2 => result
[Function]
rope= rope-1 rope-2 => result
[Function]
rope> rope-1 rope-2 => result
[Function]
rope>= rope-1 rope-2 => result
[Function]
ropep object => result
[Function]
sexp-rope sexp &key symbol-function => result
Construct a rope representing S-Expression SEXP. SYMBOL-FUNCTION: A function to transform symbols in the rope. (lambda (symbol)) => rope RETURNS: a rope
[Function]
subrope rope &key start end copy => result
Return the subrope of ROPE, beginning with element number START and continuing up to element number END. START: initial element number of the subrope END: one past the final element number of the subrope COPY: if true, copy leaf strings
[Standard class]
tree-map
[Function]
tree-map-alist tree-map => result
Returns an association list containging the keys and values of tree-map TREE-MAP.
[Function]
tree-map-contains tree-map key => result
Test if a key is present in tree-map
[Function]
tree-map-count map => result
Number of elements in MAP.
[Accessor]
tree-map-find tree-map key &optional default => result
(setf (tree-map-find map key) value)
Find value indexed by KEY in TREE-MAP.
[Function]
tree-map-hash-table tree-map &rest hash-table-initargs => result
Returns a hash table containing the keys and values of the tree-map TREE-MAP. Hash table is initialized using the HASH-TABLE-INITARGS.
[Function]
tree-map-insert tree-map key value => result
Insert KEY=>VALUE into TREE-MAP, returning the new tree-map.
[Function]
tree-map-insert-alist tree-map alist => result
Insert all elements of ALIST into TREE-MAP
[Function]
tree-map-insert-hash-table tree-map hash-table => result
Insert all elements of HASH-TABLE into TREE-MAP
[Function]
tree-map-insert-map tree-map other-map => result
Insert all elements of OTHER-MAP into TREE-MAP
[Macro]
tree-map-insertf place key value => result
Insert KEY=>VALUE into the tree map at PLACE, store at place.
[Function]
tree-map-keys tree-map => result
[Function]
tree-map-remove tree-map key => result
Remove KEY from TREE-MAP, returning the new tree-map.
[Function]
tree-map-values tree-map => result
[Standard class]
tree-set
[Function]
tree-set compare &rest args => result
Create a new tree-set containing all items in ARGS.
[Function]
tree-set-compare tree-1 tree-2 => result
Order relation on sets.
[Function]
tree-set-count set => result
Number of elements in SET.
[Function]
tree-set-difference set-1 set-2 => result
Difference of SET-1 and SET-2.
[Function]
tree-set-equal-p set-1 set-2 => result
Do SET-1 and SET-2 contain the same elements?
[Accessor]
tree-set-find set item => result
(setf (tree-set-find set) item)
Find ITEM in SET
[Function]
tree-set-insert set item => result
Insert ITEM into SET.
[Macro]
tree-set-insertf place item => result
Insert INTER into the tree set at PLACE, store at PLACE.
[Function]
tree-set-intern set item => result
Add item to set, unless it already exists. RETURNS: (values NEW-SET NEW-ITEM)
[Function]
tree-set-intersection set-1 set-2 => result
Intersection of SET-1 and SET-2.
[Function]
tree-set-intersection-difference tree-1 tree-2 => result
Simultanously compute intersection and difference.
[Function]
tree-set-intersection-p set-1 set-2 => result
Do SET-1 and SET-2 intersect? RETURNS: T or NIL
[Function]
tree-set-list set => result
Return list of elements in `SET' in comparison order.
[Function]
tree-set-max set => result
Return the greatest item in SET.
[Function]
tree-set-member-p set item => result
Is ITEM a member of SET?
[Function]
tree-set-min set => result
Return the lest item in SET.
[Function]
tree-set-p object => result
[Function]
tree-set-position set value => result
Return the position of `VALUE' in `SET' or NIL.
[Function]
tree-set-ref set subscript => result
Return the element of `SET' at position `SUBSCRIPT'.
[Function]
tree-set-remove set item => result
Remove ITEM from SET.
[Function]
tree-set-remove-max set => result
Remove maximum element of SET.
[Function]
tree-set-remove-min set => result
Remove minimum element of SET.
[Function]
tree-set-remove-position set i => result
Remove element of SET and position I.
[Function]
tree-set-replace set item => result
Replace ITEM into SET.
[Function]
tree-set-subset-p set-1 set-2 => result
Is SET-1 a subset of SET-2? RETURNS: T or NIL
[Function]
tree-set-union set-1 set-2 => result
Union of SET-1 and SET-2.
This documentation was prepared with DOCUMENTATION-TEMPLATE.