A poor man’s interval tree

unsorted — cgrand, 16 March 2012 @ 22 h 49 min

Sorted collections can be put to good (ab)use, here I define interval-lt a partial order on intervals and points — where an interval is a vector [from to] (from inclusive, to exclusive; they can be nil to denote infinity) and a point is [n n].

(defn interval-lt
  [[a b] [c d]]
  (boolean (and b c 
                (if (= a b)
                  (neg? (compare b c))
                  (<= (compare b c) 0)))))

Using this partial order and a sorted-map, I can build an interval tree:

(def empty-interval-map 
  (sorted-map-by interval-lt [nil nil] #{}))

(defn- isplit-at [interval-map x]
  (if x
    (let [[[a b :as k] vs] (find interval-map [x x])]
      (if (or (= a x) (= b x))
        interval-map
        (-> interval-map (dissoc k) (assoc [a x] vs [x b] vs))))
    interval-map))

(defn- ialter [interval-map from to f & args]
  (let [interval-map (-> interval-map (isplit-at from) (isplit-at to))
        kvs (for [[r vs] 
                  (cond 
                    (and from to)
                    (subseq interval-map >= [from from] < [to to])
                    from
                    (subseq interval-map >= [from from])
                    to
                    (subseq interval-map < [to to])
                    :else
                    interval-map)]
              [r (apply f vs args)])]
    (into interval-map kvs)))

(defn iassoc [interval-map from to v]
  (ialter interval-map from to conj v))

(defn idissoc [interval-map from to v]
  (ialter interval-map from to disj v))

(defn iget [interval-map x]
  (get interval-map [x x]))

Demo, let’s state who’s present and at which time:

(-> empty-interval-map
  (iassoc 9 17 "Ethel")
  (iassoc 7 12 "Lucy")
  (iassoc 11 20 "Fred"))
; {[nil 7] #{}, [7 9] #{"Lucy"}, 
;  [9 11] #{"Ethel" "Lucy"}, 
;  [11 12] #{"Ethel" "Fred" "Lucy"}, 
;  [12 17] #{"Ethel" "Fred"}, 
;  [17 20] #{"Fred"}, 
;  [29 nil] #{}}

And now one can query by time:

(iget *1 8)
; #{"Lucy"}
(iget *2 15)
; #{"Ethel" "Fred"}
(iget *3 20)
; #{}

Sure, this is not the best interval tree implementation ever, it suffers from severe fragmentation and not ideal update complexity. However if what only matters is lookup, it works nicely in O(log n) — each iassoc adds at most two entries to the map so for n intervals you have at most 1+2n entries, lookup is O(log (2n+1)), that is O(log n).

3 Comments »

  1. [...] Clojure and me » A poor man’s interval tree http://clj-me.cgrand.net/2012/03/16/a-poor-mans-interval-tree/ [...]

  2. This turns out to be the exact API I need, and at a perfect level of richness, to detect when a beat being played overlaps any cues that have been defined in the show interface I am building for Beat Link Trigger. Thanks so much for sharing it! https://github.com/Deep-Symmetry/beat-link-trigger#beat-link-trigger

    Comment by James Elliott — 31 December 2018 @ 19 h 58 min
  3. Actually, it turns out I needed a wee bit more: your iget function only allows you to probe for intervals that intersect a point, and I needed to find intervals that intersected another interval. So I refactored ialter to pull out the function that finds the matching subsequence within the tree, and used that to add another arity for iget that let me find cues that overlapped a given cue. It’s working wonderfully! Here’s the commit with my tweaked version, if you are interested: https://github.com/Deep-Symmetry/beat-link-trigger/commit/fc60b518f19818620b6c90e6b93c1388e8441811

    Comment by James Elliott — 3 January 2019 @ 2 h 23 min

RSS feed for comments on this post. TrackBack URI

Leave a comment

(c) 2024 Clojure and me | powered by WordPress with Barecity