SYCAMORE ======== A fast, purely functional data structure library in Common Lisp. API Documentation: http://ndantam.github.io/sycamore Features ======== * Fast, purely functional weight-balanced binary trees. - http://en.wikipedia.org/wiki/Weight-balanced_tree - Leaf nodes are simple-vectors, greatly reducing tree height. * Interfaces for tree Sets and Maps (dictionaries). * Ropes - http://en.wikipedia.org/wiki/Rope_(data_structure) * Purely functional pairing heaps - http://en.wikipedia.org/wiki/Pairing_heap * Purely functional amortized queue Installation ============ * Sycamore uses ASDF (https://common-lisp.net/project/asdf/) * See `INSTALL` file for details Examples ======== See also `./example.lisp` Sets ---- Define an ordering function: CL-USER> (defun compare (a b) (cond ((< a b) -1) ((> a b) 1) (t 0))) COMPARE Create a set for integers: CL-USER> (sycamore:tree-set #'compare 1 2 -10 40) #<TREE-SET (-10 1 2 40)> Insertion: CL-USER> (sycamore:tree-set-insert (sycamore:tree-set #'compare 1 2) 0) #<TREE-SET (0 1 2)> Removal: CL-USER> (sycamore:tree-set-remove (sycamore:tree-set #'compare 1 2 0) 0) #<TREE-SET (1 2)> Union operation: CL-USER> (sycamore:tree-set-union (sycamore:tree-set #'compare 1 2) (sycamore:tree-set #'compare 1 0 3)) #<TREE-SET (0 1 2 3)> Intersection operation: CL-USER> (sycamore:tree-set-intersection (sycamore:tree-set #'compare 1 2) (sycamore:tree-set #'compare 1 0 3)) #<TREE-SET (1)> Difference operation: CL-USER> (sycamore:tree-set-difference (sycamore:tree-set #'compare 1 2) (sycamore:tree-set #'compare 1 0 3)) #<TREE-SET (2)> Map set: CL-USER> (sycamore:map-tree-set 'list #'1+ (sycamore:tree-set #'compare 1 0 10 2)) (1 2 3 11) Fold set: CL-USER> (sycamore:fold-tree-set (lambda (list item) (cons item list)) nil (sycamore:tree-set #'compare 1 0 10 2)) (10 2 1 0) Ropes ----- Create a Rope: CL-USER> (sycamore:rope "Hello" #\Space 'World!) #<ROPE "Hello WORLD!"> Also works on lists: CL-USER> (sycamore:rope (list "Hello" #\Space 'World!)) #<ROPE "Hello WORLD!"> And arrays: CL-USER> (sycamore:rope (vector "Hello" #\Space 'World!)) #<ROPE "Hello WORLD!"> Rope to string: CL-USER> (sycamore:rope-string (sycamore:rope "Hello" #\Space 'World!)) "Hello WORLD!" Print a rope: CL-USER> (sycamore:rope-write (sycamore:rope "Hello" #\Space 'World!) :escape nil :stream *standard-output*) Hello WORLD! Alternatives ============ There are many other Common Lisp data structure libraries. Here are a few alternatives and their trade-offs relative to Sycamore. FSet ---- https://common-lisp.net/project/fset/Site/FSet-CL.html FSet implements finite sets with a CLOS-based set interface, while Sycamore's finite sets take a parameter for a comparison function. Both used weight-balanced trees with minor algorithmic differences. Generic vs. explicit comparison functions is both an aesthetic and performance issue. FSet's generic comparison functions do not need to be passed explicitly, while Sycamore's explicit comparison function parameter makes it easier to compare the same type differently if needed, e.g., lexicographic vs. fast string comparison. Included benchmarks show that Sycamore is 30-50% faster than FSet. CL-Containers ------------- https://github.com/gwkkwg/cl-containers CL-Containers is stateful/mutable/imperative, while Sycamore is purely-functional/persistent. Lisp Interface Library (LIL) ---------------------------- https://github.com/fare/lisp-interface-library Lisp Interface Library (LIL) provides abstracted data structures using Interface Passing Style, while Sycamore provides a few concrete data structures. LIL's Interface Passing Style presumably improves flexibility at the cost of runtime overhead and API complexity. Sycamore's explicit data structures have low-overhead, optimized implementations and a simple, documented API. References ========== * Okasaki, Chris. "Purely Functional Data Structures." Cambridge University Press. June 1999. ISBN: 978-0521663502. * Boehm, H.J., Atkinson, R. and Plass, M., 1995. Ropes: an alternative to strings. Software: Practice and Experience, 25(12), pp.1315-1330. * Adams, Stephen., 1992. Implementing sets efficiently in a functional language. University of Southampton. Tech Report CSTR 92-10. Name ==== http://en.wikipedia.org/wiki/Platanus_occidentalis