Repository: chrovis/cljam
Pull request #209 (2020-09-02 07:02:10)

Add support for fast interval finder.
This PR adds support for the data structure and  function  for intervals that overlap the specified range (chr,start,end).

codecov[bot]: # [Codecov](https://codecov.io/gh/chrovis/cljam/pull/209?src=pr&el=h1) Report
> Merging [#209](https://codecov.io/gh/chrovis/cljam/pull/209?src=pr&el=desc) into [master](https://codecov.io/gh/chrovis/cljam/commit/da4354b0f5dfa0ee92eb18dd7698959254339b53?el=desc) will **increase** coverage by `0.01%`.
> The diff coverage is `92.85%`.

[![Impacted file tree graph](https://codecov.io/gh/chrovis/cljam/pull/209/graphs/tree.svg?width=650&height=150&src=pr&token=hrCuiz6NWa)](https://codecov.io/gh/chrovis/cljam/pull/209?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master     #209      +/-   ##
==========================================
+ Coverage   87.20%   87.21%   +0.01%     
==========================================
  Files          77       78       +1     
  Lines        6331     6345      +14     
  Branches      511      512       +1     
==========================================
+ Hits         5521     5534      +13     
  Misses        299      299              
- Partials      511      512       +1     
```


| [Impacted Files](https://codecov.io/gh/chrovis/cljam/pull/209?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/cljam/util/intervals.clj](https://codecov.io/gh/chrovis/cljam/pull/209/diff?src=pr&el=tree#diff-c3JjL2NsamFtL3V0aWwvaW50ZXJ2YWxzLmNsag==) | `92.85% <92.85%> (ø)` | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/chrovis/cljam/pull/209?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/chrovis/cljam/pull/209?src=pr&el=footer). Last update [da4354b...6c774dd](https://codecov.io/gh/chrovis/cljam/pull/209?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

alumi: [![image](https://user-images.githubusercontent.com/5086013/91942927-afb34600-ed36-11ea-9915-a7b95d5ff979.png)](https://github.com/chrovis/cljam/pull/209/checks?check_run_id=1060108149) 🤔 
athos: Seems like a bug in clj-lint-action?
At a glance, [this line](https://github.com/xcoo/clj-lint-action/blob/1cc8b97397e053c1573531c37965aaec740069c0/lib/src/lint_action.clj#L111) should be `(cstr/join \: relative-files)` instead of `(cstr/join relative-files)`, I think.
niyarin: I'm sorry, I was going to check the newer clj-lint-action in the forked environment, but I made a mistake and pushed it here.
However, I found that the new clj-lint-action would fix bad annotations.
https://github.com/chrovis/cljam/runs/1061719609

I fixed the content of the lint-action comment.
alumi: @niyarin Thank you for updating `clj-lint-action`!

> I fixed the content of the lint-action comment.

But there're `are` and `testing` still referred but never used...?
niyarin: Sorry for the many mistakes :bow:
I fixed.
alumi: Never mind. Thank you! 👍 

Patch:
diff --git a/src/cljam/util/intervals.clj b/src/cljam/util/intervals.clj
new file mode 100644
index 0000000..740ac07
--- /dev/null
+++ b/src/cljam/util/intervals.clj
@@ -0,0 +1,31 @@
+(ns cljam.util.intervals
+  "Data structures for interval queries.")
+
+(defprotocol IIntervals
+  (find-overlap-intervals* [this start end]))
+
+(deftype SortedMapIntervals [m]
+  IIntervals
+  (find-overlap-intervals* [this start end]
+    (mapcat (fn [[_ x]] (drop-while #(< (:end %) start) x))
+            (subseq m <= end))))
+
+(defn- make-sorted-map-intervals
+  [intervals]
+  (->> (group-by :start intervals)
+       (map (fn [[k vs]] [k (sort-by :end vs)]))
+       (into (sorted-map))
+       (->SortedMapIntervals)))
+
+(defn index-intervals
+  "Make indexes for intervals to find overlaps."
+  [intervals]
+  (->> intervals
+       (group-by :chr)
+       (into {} (map (fn [[k vs]] [k (make-sorted-map-intervals vs)])))))
+
+(defn find-overlap-intervals
+  "Find intervals that are on the given `chr` and overlap the given interval
+  [`start` `end`] using indexes created by `index-intervals`."
+  [indexed-intervals chr start end]
+  (find-overlap-intervals* (get indexed-intervals chr) start end))


Test patch:
diff --git a/test/cljam/util/intervals_test.clj b/test/cljam/util/intervals_test.clj
new file mode 100644
index 0000000..728e839
--- /dev/null
+++ b/test/cljam/util/intervals_test.clj
@@ -0,0 +1,33 @@
+(ns cljam.util.intervals-test
+  (:require [clojure.test :refer [deftest is]]
+            [cljam.util.intervals :as intervals]))
+
+(def ^:private test-input1
+  [{:chr "chr1" :start 10 :end 100} {:chr "chr2" :start 10 :end 100}
+   {:chr "chr2" :start 150 :end 200} {:chr "chr2" :start 150 :end 250}
+   {:chr "chr2" :start 180 :end 300} {:chr "chr2" :start 181 :end 200}
+   {:chr "chr2" :start 182 :end 200} {:chr "chr2" :start 182 :end 201}
+   {:chr "chr2" :start 200 :end 400}])
+
+(deftest sorted-map-intervals-test
+  (let [smi (intervals/index-intervals test-input1)]
+    (is (= (intervals/find-overlap-intervals smi "chr1" 1 10)
+           [{:chr "chr1" :start 10 :end 100}]))
+    (is (= (intervals/find-overlap-intervals smi "chr1" 1 9) []))
+    (is (= (intervals/find-overlap-intervals smi "chr1" 100 101)
+           [{:chr "chr1" :start 10 :end 100}]))
+    (is (= (intervals/find-overlap-intervals smi "chr1" 101 102) []))
+    (is (= (intervals/find-overlap-intervals smi "chr1" 11 99)
+           [{:chr "chr1" :start 10 :end 100}]))
+    (is (= (intervals/find-overlap-intervals smi "chr2" 10 100)
+           [{:chr "chr2" :start 10 :end 100}]))
+    (is (= (intervals/find-overlap-intervals smi "chr2" 110 111) []))
+    (is (= (intervals/find-overlap-intervals smi "chr2" 90 160)
+           [{:chr "chr2" :start 10 :end 100} {:chr "chr2" :start 150 :end 200}
+            {:chr "chr2" :start 150 :end 250}]))
+    (is (= (intervals/find-overlap-intervals smi "chr2" 150 181)
+           [{:chr "chr2" :start 150 :end 200} {:chr "chr2" :start 150 :end 250}
+            {:chr "chr2" :start 180 :end 300} {:chr "chr2" :start 181 :end 200}]))
+    (is (= (intervals/find-overlap-intervals smi "chr2" 201 240)
+           [{:chr "chr2" :start 150 :end 250} {:chr "chr2" :start 180 :end 300}
+            {:chr "chr2" :start 182 :end 201} {:chr "chr2" :start 200 :end 400}]))))