dco-dev / interval-tree Goto Github PK

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?

Currently the interval functionality is based on [x,y]. Would Open Intervals (x,y) be useful?

These could significantly improve creation time for large trees

Hey, thanks or the amazing lib! I'd like to use it in clojurescript, but afaict the source are all .clj instead of .cljc. So do you have any plan to port it to .cljc?

Consider this example:

;; 01234
;; aaa a
;; b b b
(let [m (interval-map {[0 2] :a
                       [3 4] :a
                       [0 1] :b
                       [2 3] :b
                       [3 4] :b})]
  (pprint m))

;; Syntax error reading source at (solver.clj:337:33).
;; Duplicate key: [3 4]

Comparing with helins.interval.map...

(let [m (-> imap/empty
            (imap/mark 0 2 :a)
            (imap/mark 3 4 :a)
            (imap/mark 0 1 :b)
            (imap/mark 2 3 :b)
            (imap/mark 3 4 :b))]
  (pprint m))

;; {[0 1] #{:b :a},
;;  [1 2] #{:a},
;;  [2 3] #{:b},
;;  [3 4] #{:b :a}}

Related to: #11

Hey @dco-lentz! Been a while since I mentioned you on GitHub :) Do you think you could release this to Clojars? One current use case I have for it is doing rate limiting. I'm sure there are other future uses I'll have for it.

Thanks so much and all the best!

Hey, I was wondering if the current implementation would permit to get extended to efficiently obtain a subtree. Something along the lines of

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

(dean/subtree x [5 5]) ; => {[4 7] :x2 [0 5] :x4 [3 9] :x7 [4 5] :x8}

by efficient I mean at the order of log(n), where n is the number of intervals in the original tree.