Finding keys closest to a given value for clojure sorted-maps

Question

For clojure's sorted-map, how do I find the entry having the key closest to a given value?

e.g. Suppose I have

(def my-map (sorted-map 
                      1 A 
                      2 B
                      5 C))

I would like a function like

(find-closest my-map 4)

which would return (5,C), since that's the entry with the closest key. I could do a linear search, but since the map is sorted, there should be a way of finding this value in something like O(log n).

I can't find anything in the API which makes this possible. If, for instance, I could ask for the i'th entry in the map, I could cobble together a function like the one I want, but I can't find any such function.

Edit:

So apparently sorted-map is based on a PersistentTreeMap class implemented in java, which is a red and black tree. So this really seems like it should be doable, at least in principle.

Answer 1

Use the Clojure contrib library data.avl. It supports sorted-maps with a nearest function and other useful features.

https://github.com/clojure/data.avl

Answer 2

subseq and rsubseq are very fast because they exploit the tree structure:

(def m (sorted-map 1 :a, 2 :b, 5 :c)) 

(defn abs [x] (if (neg? x) (- x) x))
(defn find-closest [sm k]
  (if-let [a (key (first (rsubseq sm <= k)))]
    (if (= a k)
      a
      (if-let [b (key (first (subseq sm >= k)))]
        (if (< (abs (- k b)) (abs (- k a)))
          b
          a)))
    (key (first (subseq sm >= k)))))

user=> (find-closest m 4)
5
user=> (find-closest m 3)
2

This does slightly more work than ideal, in the ideal scenario we would just do a <= search then look at the node to the right to check if there is anything closer in that direction. You can access the tree (.tree m) but the .left and .right methods aren't public so custom traversal is not currently possible.