interval_tree.clj

(ns interval-tree
  (:require [clojure.spec.alpha :as s]))

;; augmented 1-D interval tree

(defrecord ^:private Node [interval highest left right])

(defn insert [{:keys [interval highest left right] :as tree} [vlow vhigh :as value]]
  (if (nil? tree)
    (Node. value vhigh nil nil)
    (if (<= vlow (first interval))
      (Node. interval (max highest vhigh) (insert left value) right)
      (Node. interval (max highest vhigh) left (insert right value)))))

(defn interval-tree [intervals]
  (if (seq intervals)
    (reduce insert nil intervals)))

(defn overlaps? [[l1 h1] [l2 h2]]
  (and (<= l2 h1)
       (<= l1 h2)))

(defn search-overlaps
  ([tree value]
   (search-overlaps tree value nil))
  ([tree [vlow vhigh :as value] result]
   (prn "search " (:interval tree))
   (cond
     (nil? tree)
     result
     
     (> vlow (:highest tree))
     result
     
     :default
     (cond->> result
       (some? (:left tree))
       (search-overlaps (:left tree) value)
       
       (overlaps? (:interval tree) value)
       (cons (:interval tree))
       
       (and (> vhigh (first (:interval tree)))
            (some? (:right tree)))
       (search-overlaps (:right tree) value)))))


(comment
  (def intervals
    [[20 35]
     [3 40]
     [29 98]
     [0 0]
     [10 14]])

  (def t (interval-tree intervals))

  (search-overlaps t [40 40])
  ; ([29 98] [3 40])
  (search-overlaps t [20 20])
  ; ([20 35] [3 40])
  (search-overlaps t [14 14])
  ; ([10 14] [3 40])

  (search-overlaps t [20 21])
  )

"1.2.3.4/28"