quick hack interval tree, allowing glob matching, build upon sorted set

itree.clj

(ns itree
  (:require [clojure.pprint :refer [pprint]]
            [taoensso.timbre :refer [info spy]]))

;; allow for [:foo nil] to glob [:foo *]; data will never be inserted
;; w/ nil, but slice/subseq elements will.
(defn cmp [x y] (if (and x y) (compare x y) 0))

(defn cmp-s [[x0 x1] [y0 y1]]
  (let [c0 (cmp x0 y0)
        c1 (cmp x1 y1)]
    (cond
      (= c0 0) c1
      (< c0 0) -1
      (> c0 0)  1)))

(defn distinct-consecutive [sequence]
  (map first (partition-by identity sequence)))

(defn slice
  ([ss a] (slice ss a a))
  ([ss a b]
   ;; do subseq from !a -> a, and a -> b -> !b; concat and dedup
   ;; do overlaps (always <= or >=) since the glob matching needs it.
   (-> (spy :info (rsubseq ss >= a >= a))
       (reverse)
       (concat (spy :info (subseq ss >= a <= b)))
       (distinct-consecutive))))

(let [e0 (sorted-set-by cmp-s)
      ds [[:a :b] [:b :x] [:b :q] [:a :d]]
      e1 (loop [e e0, [d & ds] ds]
           (if d
             (let [c (count e)
                   e (conj e d)]
               (assert (= (count e)) (inc c))
               #_(clojure.pprint/pprint e)
               (recur e ds))
             e))]
  (assert (= (seq e1) (slice e1 [nil nil])))                   ; * *
  (assert (= [[:a :b] [:a :d]] (slice e1 [:a nil])))           ; :a *
  (assert (= [[:b :q]] (slice e1 [:b :q])))                    ; :b :q (specific)
  (assert (= [[:a :d] [:b :q]] (slice e1 [:a :d] [:b :q])))    ; matching subrange
  (assert (= [[:a :d] [:b :q]] (slice e1 [:a :c] [:b :r])))    ; non-matching subrange
  (assert (= [[:b :x]] (slice e1 [:b :r] [:c nil])))           ; non-matching -> out of range
  (assert (= [] (slice e1 [:c nil])))                          ; totally out of range
  )