interval/difference that supports non-disjoint intervals?

[rafd]

I needed a version of difference that supports non-disjoint intervals. Would you be interested in adding this to tick?

Draft code below. Requires priority-map (see comment).

Will include tests if you want this added in.

(defn pm-conj
  [pm interval]
  (conj pm [interval (:tick/beginning interval)]))

(defn difference
  "Subtracts subtract-intervals from intervals; not using t.i/difference because it requires disjoint intervals"
  [intervals & subtract-intervals]
  ;; to avoid the n^2 complexity of checking each interval against each subtract-interval
  ;;
  ;; take inspiration from classic "merge" for 2 sorted lists
  ;; compare the heads of both lists (intervals and subtract-intervals)
  ;; and based on their relation, decide what to do
  ;;
  ;; using priority-maps as priority-queues
  ;; because in several of the cases below
  ;; we re-insert a modified current-interval that starts later
  ;; but we need to keep the intervals and subtract-intervals sorted
  (loop [intervals (->> intervals
                        (map (fn [i]
                               [i (:tick/beginning i)]))
                        (into (pm/priority-map)))
         subtract-intervals (->> subtract-intervals
                                 (map (fn [i]
                                        [i (:tick/beginning i)]))
                                 (into (pm/priority-map)))
         out-intervals []]
    (if (or (empty? subtract-intervals)
            (empty? intervals))
      (into out-intervals (map key intervals))
      (let [[current-interval _] (peek intervals)
            [current-subtract _] (peek subtract-intervals)]
        (case (t.i/relation current-interval current-subtract)
          (:precedes :meets)
          (recur (pop intervals)
                 subtract-intervals
                 (conj out-intervals current-interval))

          (:preceded-by :met-by)
          (recur intervals
                 (pop subtract-intervals)
                 out-intervals)

          (:equals :starts :during :finishes)
          (recur (pop intervals)
                 subtract-intervals
                 out-intervals)

          :contains
          (recur (-> (pop intervals)
                     (pm-conj
                      (t.i/new-interval (:tick/end current-subtract)
                                        (:tick/end current-interval)))
                     (pm-conj
                      (t.i/new-interval (:tick/beginning current-interval)
                                        (:tick/beginning current-subtract))))
                 subtract-intervals
                 out-intervals)

          :started-by
          (recur (pm-conj (pop intervals)
                          (t.i/new-interval (:tick/end current-subtract)
                                            (:tick/end current-interval)))
                 subtract-intervals
                 out-intervals)

          :finished-by
          (recur (pm-conj (pop intervals)
                          (t.i/new-interval (:tick/beginning current-interval)
                                            (:tick/beginning current-subtract)))
                 subtract-intervals
                 out-intervals)

          :overlaps
          (recur (pm-conj (pop intervals)
                          (t.i/new-interval (:tick/beginning current-interval)
                                            (:tick/beginning current-subtract)))
                 subtract-intervals
                 out-intervals)

          :overlapped-by
          (recur (pm-conj (pop intervals)
                          (t.i/new-interval (:tick/end current-subtract)
                                            (:tick/end current-interval)))
                 subtract-intervals
                 out-intervals))))))

[henryw374]

So would this be a different function altogether? for my reference this is the existing one I guess it would need to be if performance is significantly different?

https://github.com/clojure/data.priority-map - clojure only, not cljc? if it can't work for cljs then a separate fn probably the way to go.

It'd be interesting to see a few example usages.

I was having a look and tbh the existing tests could have a bit more docs around them

tick/test/tick/alpha/interval_test.cljc

Line 467 in b96d4c4

(deftest difference-test

alternatively, the readme could have a links section to 'more fns' or something

[rafd]

It could replace the original (ie. it is a superset of the original; it should return the same results for disjoint sets). Or, I might take a look at modifying the original (to keep its use of lazyseq).

Good catch on priority-map being only clj. I have a cljc version in progress (based on https://github.com/shamsimam/clj-priority-queue), but when I tried swapping data.prority-map with clj-priority-queue in my project, it resulted in non-identical behaviour, which I have to investigate.

This is still on my TODO.