toy immutable sorted set

xset.clj

; toy immutable sorted set

(defn xseq [t]
  (when t
    (concat
      (xseq (:l t))
      [(:root t)]
      (xseq (:r t)))))
 
(defn xconj [t v]
  (cond
    (nil? t)        {:root v, :l nil, :r nil}
    (< v (:root t)) {:root (:root t),
                     :l (xconj (:l t) v),
                     :r (:r t)}
    :else           {:root (:root t),
                     :l (:l t),
                     :r (xconj (:r t) v)}))

(let [t1 (-> nil (xconj 5) (xconj 8) (xconj 3)),
      t2 (xconj t1 4)]
  (println "t1:" (xseq t1))
  (println "t2:" (xseq t2))
  (println "Do they share?" (identical? (:r t1) (:r t2))))

; Warnings:
; Only stores numbers
; Will blow the heap for large collections
; The tree will get out of balance
; xseq is not lazy and will copy the whole tree into a seq before returning

; Shows:
; Values are never copied, only references to them.
; Unchanged branches are simply reused, not copied.
; Every change creates a new root node, plus new nodes as needed in the path
; through tree to where the new value is being inserted.
; Completely threadsafe -- no object that existed before the fn call is changed
; in any way, newly created objects are in their final state before being
; returned.