Inverse mappings/ interval intersections?

[yuhan0]

Thanks for releasing this library :)

Given an interval map

(def x (dean/interval-map
         {[1 3] :x1
          [4 7] :x2}))

Is there any way of querying it for the inverse mapping - ie. what interval does :x1 correspond to?

My use case is finding the intersection between an interval-map and some other interval, ie. something like

(intersect-interval x [5 9]) 
;; => {:x2 [4 7]}

Is this possible to do with the data structure, or will I have to maintain a parallel inverse mapping?

[yuhan0]

Sorry, I didn't think this through well enough - the first part about the inverse mapping is not possible because you can have multiple intervals mapped to the same value.

(dean/interval-map
  {[1 2] :a
   [4 5] :a})

But could there still be a way of getting from the list of overlapping intervals to the intervals themselves?

(def x (dean/interval-map
         {[1 3] :x1
          [4 7] :x2
          [8 9] :x3
          [0 5] :x4}))

(get x 2)       ; => (:x4 :x1)
(get-intvs x 2) ; => ([0 5] [1 3])

[dco-lentz]

Hey there thanks! Yes, let me look into this. In theory clojure.core/find should return the keyvals (you'd be interested in the keys, here). In practice it appears to error in the case of interval-map, so likely will need to be fixed and a new release. There are actually also a number of other functionalities that aren't yet exposed via any clojure interface at all, such as node-find-nearest-interval

[dco-lentz]

Ok, thanks again for finding this issue! I've put together a fix that will be included in the next release #12

The issue is that Java expects entryAt to return a map-entry. Since in the case of an Interval map we need to return a sequence of keyvals, that broke the contract. Although its a little bulky, i've conceded and I'm now returning a single MapEntry of the query-value (key) to the matching interval/val pairs. It may be helpful to look at the output from a regular (ordered) map first:

  (def x (ordered-map {:x 1 :y 2}))   
  (find x :x) 

      ;; => [:x 1]

So, in other words it is a lookup that returns both the matching key and its corresponding value. Now, for your interval-map example:

  (def x (interval-map
           {[1 3] :x1
            [4 7] :x2
            [8 9] :x3
            [0 5] :x4}))

  (find x 2)     
      ;; => [2 ([[0 5] :x4] [[1 3] :x1])]

  (find x [1 4]) 
      ;;  => [[1 4] ([[0 5] :x4] [[1 3] :x1] [[4 7] :x2])]