Funds provides portable, purely functional data structures in Common Lisp. The vector, hash, Queue, and Heap are implemented using trees, so “modifying” them is O(log(n)) time and space. https://common-lisp.net/project/funds/ https://common-lisp.net/project/funds/funds.pdf
Below are the exported functions; they should be self explanatory:
- MAKE-VECTOR
- VECTOR-REF
- VECTOR-SET
- VECTOR-SIZE
- VECTOR-COUNT
- MAP-VECTOR
- VECTOR-COPY (can also be used for subvector)
- VECTOR-COUNT-IF
- VECTOR-AS-LIST
- MAKE-HASH
- HASH-SET
- HASH-REMOVE
- HASH-REF
- HASH-SIZE
- MAP-HASH
- HASH-KEYS
- HASH-FROM-ALIST
- HASH-AS-ALIST
- MAKE-HASH
- HASH-SET
- HASH-REMOVE
- HASH-REF
- HASH-SIZE
- HASH-FROM-LIST
- HASH-AS-LIST
- HASH-UNION
- HASH-DIFFERENCE
- HASH-INTERSECTION
- MAKE-QUEUE
- DEQUEUE
- ENQUEUE
- QUEUE-FIRST
- QUEUE-COUNT
- QUEUE-COUNT-IF
- QUEUE-EMPTY-P
- QUEUE-SIZE
- MAP-QUEUE
- QUEUE-AS-LIST
- MAKE-HEAP
- HEAP-INSERT
- HEAP-REMOVE
- HEAP-FIRST
- HEAP-EMPTY-P
- MAKE-STACK
- STACK-PUSH
- STACK-POP
- STACK-TOP
- STACK-COUNT
- STACK-COUNT-IF
- MAP-STACK
- STACK-EMPTY-P
- STACK-SIZE
- STACK-FROM-LIST
- STACK-AS-LIST