SYCAMORE - Purely Functional Trees, Etc.



Sycamore is a purely functional data structure library in Common Lisp. It include fast, 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



  1. The SYCAMORE dictionary
    1. amortized-dequeue
    2. amortized-enqueue
    3. amortized-queue
    4. amortized-queue
    5. amortized-queue-empty-p
    6. amortized-queue-list
    7. amortized-queue-push
    8. do-tree-set
    9. fold-tree-set
    10. make-amortized-queue
    11. make-tree-map
    12. make-tree-set
    13. map-tree-map
    14. map-tree-set
    15. or-compare
    16. tree-map-count
    17. tree-map-find
    18. tree-map-insert
    19. tree-map-remove
    20. tree-set
    21. tree-set
    22. tree-set-compare
    23. tree-set-count
    24. tree-set-difference
    25. tree-set-equal-p
    26. tree-set-find
    27. tree-set-insert
    28. tree-set-intersection
    29. tree-set-intersection-difference
    30. tree-set-list
    31. tree-set-member-p
    32. tree-set-p
    33. tree-set-position
    34. tree-set-ref
    35. tree-set-remove
    36. tree-set-remove-max
    37. tree-set-remove-min
    38. tree-set-remove-position
    39. tree-set-subset-p
    40. tree-set-union
  2. Author
  3. Acknowledgements


The SYCAMORE dictionary

amortized-dequeue queue => result

Remove first element of QUEUE. RETURNS: (VALUES new-queue element)

amortized-enqueue queue element => result

Add ELEMENT to QUEUE. RETURNS: new-queue

[Standard class]

amortized-queue &rest args => result

Create an amortized queue of ARGS.

amortized-queue-empty-p queue => result

Is the queue empty?

amortized-queue-list queue => result

Return an inorder list of elements in QUEUE.

amortized-queue-push queue element => result

Add ELEMENT to the front of QUEUE.

do-tree-set (var set &optional result) declaration* statement* => result

fold-tree-set function initial-value set => result

Fold FUNCTION over every element of SET.

make-amortized-queue => result

Make a new queue.

make-tree-map compare => result

Create a new tree-map.

make-tree-set compare => result

Create a new tree-set.

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: (lambda (key value)).

map-tree-set result-type function set => result

Apply FUNCTION to every element of SET.

or-compare &rest comparisons => result

Short-circuit evaluatation of arguments, returning the first one that is nonzero.

tree-map-count map => result

Number of elements in MAP.

tree-map-find tree-map key &optional default => result

Find value indexed by KEY in TREE-MAP.

tree-map-insert tree-map key value => result

Insert KEY=>VALUE into TREE-MAP, returning the new tree-map.

tree-map-remove tree-map key => result

Insert KEY from TREE-MAP, returning the new tree-map.

[Standard class]

tree-set compare &rest args => result

Create a new tree-set containing all items in ARGS.

tree-set-compare tree-1 tree-2 => result

Order relation on sets.

tree-set-count set => result

Number of elements in SET.

tree-set-difference set-1 set-2 => result

Difference of SET-1 and SET-2.

tree-set-equal-p set-1 set-2 => result

Do SET-1 and SET-2 contain the same elements?

tree-set-find set item => result

Find ITEM in SET

tree-set-insert set item => result

Insert ITEM into SET.

tree-set-intersection set-1 set-2 => result

Intersection of SET-1 and SET-2.

tree-set-intersection-difference tree-1 tree-2 => result

Simultanously compute intersection and difference.

tree-set-list set => result

Return list of elements in `SET' in comparison order.

tree-set-member-p set item => result

Is ITEM a member of SET?

tree-set-p object => result

tree-set-position set value => result

Return the position of `VALUE' in `SET' or NIL.

tree-set-ref set subscript => result

Return the element of `SET' at position `SUBSCRIPT'.

tree-set-remove set item => result

Remove ITEM from SET.

tree-set-remove-max set => result

Remove maximum element of SET.

tree-set-remove-min set => result

Remove minimum element of SET.

tree-set-remove-position set i => result

Remove element of SET and position I.

tree-set-subset-p set-1 set-2 => result

Is SET-1 as subset of SET-2?

tree-set-union set-1 set-2 => result

Union of SET-1 and SET-2.




This documentation was prepared with DOCUMENTATION-TEMPLATE.