CODEWITHSUNDEEP
javadata-structuresclojurefunctional-programming
Mael
Mael

Reputation: 1322

Clojure sorted-map: find largest key that is less than or equal to x (floor key)

I have a problem where I have some keys that represent time and some values at each time. A small example:

 (sorted-map -4 "a" -1 "b" 2 "c" 3 "d")

For a given x I would like to find the largest key that is less than or equal to x.

For instance in the Julia DataStructures package there is a sorted dictionary with method such as

searchsortedlast(sc,k) Argument sc is a SortedDict, SortedMultiDict or SortedSet and k is a key. This routine returns the semitoken of the last item in the container whose key is less than or equal to k. If there is no such key, then the before-start semitoken is returned. Time: O(c log n)

I have been trying to find documentation about a similar function in clojure, but have not been able to find anything. My naive approach is as follows:

(apply max (filter #(< % x) (keys (sorted-map -4 "a" -1 "b" 2 "c" 3 "d" -10 "e"))))

but I think this is sub-optimal because it first collect all keys, then filters them, creating unnecessary computation.

My questions are 1) is if there is already a function that implements this which I cannot find. 2) If this is not the case, should I search for a Java data structure and use the java datastructure and associated methods 3) is it possible to make my approach lazy so that it is more efficient?

EDIT:

From Java's TreeMap:

K floorKey(K key) Returns the greatest key less than or equal to the given key, or null if there is no such key.

This is what I am looking for with clojure sorted-map. Should I abandon sorted-map and work with Javas treemap?

EDIT2:

I found this https://github.com/clojure/data.avl which provides an alternative sorted-map implementation with "nearest-key" functions

Upvotes: 5

Views: 593

Answers (1)

Piotrek Bzdyl
Piotrek Bzdyl

Reputation: 13175

For working with sorted collections like sorted map you can use subseq and rsubseq.

In your example to find an entry with the largest key equal or less than x you can use:

(let [m (sorted-map -4 "a" -1 "b" 2 "c" 3 "d")
      x 0]
  (first (rsubseq m <= x)))
;; => [-1 "b"]

Upvotes: 4

Related Questions