The persistent-tree-map is an immutable red-black tree with O(log(n)) reads and writes. Credit goes to the implementation of Persistent Tree Map in Clojure upon which this implementation is based.
A tree map is a Tree of key-value pairs.
Given that persistent-tree-map collides with several important function definitions in the :common-lisp namespace it is recommended that this library is used with a local nickname. For example, like this:
(defpackage my-package
(:use #:cl)
(:local-nicknames (#:ptm #:persistent-tree-map)))Items in the tree-map are sorted by a comparer function taking two keys, returning less than zero when the first key comes before the second, 0 when they are equal and greater than zero when the first key is ordered after the second.
(lambda (key1 key2) ...) ;; Expected return type of fixnumFor example, this is the implementation for the eq-comparer provided with this library:
(defun eq-comparer (left right)
(cond ((eq left right) 0)
((null left) -1)
((null right) 1)
((< left right) -1)
(:else 1)))Constructor:
(ptm:make-tree-map #'ptm:eq-comparer nil 1 "a" 'foo)
;; #<treemap nil 1,"a" FOO>Adding:
(ptm:add (ptm:make-tree-map #'ptm:eq-comparer 1 "foo") 1 "bar")
;; #<treemap 1 "bar">
Removing:
(ptm:remove (ptm:make-tree-map #'ptm:eq-comparer 1 1 2 2) 1)
;; #<treemap 2 2>Finding values:
(ptm:value (ptm:make-tree-map #'ptm:eq-comparer "foo" 2 "bar") 1)
;; "foo"Testing keys:
(ptm:has-key (ptm:make-tree-map #'ptm:eq-comparer 1 1 2 2) 1)
;; T
(ptm:has-key (ptm:make-tree-map #'ptm:eq-comparer 1 1 2 2) 100)
;; nilLength/Count:
(ptm:length (ptm:make-tree-map #'ptm:eq-comparer 1 "foo" 2 "bar"))
;; 2Mapping:
(ptm:map (ptm:make-tree-map #'ptm:eq-comparer 1 100 2 200 3 300)
(lambda (key val) (+ key val))
;; (101 202 303)Reduce:
(ptm:reduce (ptm:make-tree-map #'ptm:eq-comparer 1 0 2 0 3 0)
(lambda (start key val) (+ start key val))
0)
;; 6