This is a fork of dthume's data.interval-tree, purely to support newer versions of Clojure. It looks like David might be AFK for a bit; hopefully he'll come back and this can go away!
I've changed the project name (for Clojars), but left the namespaces under org.dthume; it should be a drop-in replacement for the original.
Interval Treeset built on data.finger-tree.
Largely based on the implementation described in the original paper.
codox generated documentation can be found here.
A marginalia generated walkthrough of how to use the library can be found here.
For a full set of examples, see the walkthrough.
;; just for this documentation
(require '[org.dthume.data.interval-treeset :as it])Interval Treesets sort their entries by interval. Intervals are simply pairs of values, and you can use vectors to represent them:
[5 10] ; the interval 5 - 10However you may find it convienient to use the interval function which
produces an optimised (but still compatible) interval:
(it/interval 5 10)
;; => [5 10]This uses clj-tuple to represent the pair.
Treesets can be created using interval-treeset. Because treesets take a
number of (optional) configuration options, there is no constructor which
takes items to populate the initial treeset with such as
clojure.core/vector. Instead treesets are created using interval-treeset
and then filled using into:
(def ts (into (it/interval-treeset) [[0 2] [3 5] [6 8]]))
;; => ([0 2] [3 5] [6 8])If you wish to store something other than raw intervals in the set, then provide an interval lensing function:
(def cts (into (it/interval-treeset :as-interval :span)
[{:span [6 8] :id 3} {:span [3 5] :id 2} {:span [0 2] :id 1}]))
;; => ({:span [0 2] :id 1} {:span [3 5] :id 2} {:span [6 8] :id 3})Items will be added at the correct position:
(conj ts [1 4]) ;; Amortized O(log(n))
;; => ([0 2] [1 4] [3 5] [6 8])
(count ts) ;; O(1)
;; => 3
(first ts) ;; Amortized O(1)
;; => [0 2]
(peek ts) ;; Amortized O(1)
;; => [6 8]
(nth ts 1) ;; O(log(n))
;; => [3 5](require '[org.dthume.data.interval-treeset.selection :as sel)You should probably not attempt to use or (require ... :refer :all) the
selection namespace, since it contains vars which shadow clojure.core.
- Confirm union correct wrt paper.
- Confirm complexity of intersection / difference
- Customize print-method to print as set rather than seq?
Copyright (C) 2014 David Thomas Hume. Distributed under the Eclipse Public License, the same as Clojure.