Unary Leapfrog on datascript.btset

btset.cljc

;; the BTset namespace needs has to be extended by the
;; following helper

(defn iter-seek 
  "Returns iterator for all X where key-from <= X."
  [^Iter iter key-from]
  (let [path (-seek (.-set iter) key-from)]
    (when-not (neg? path)
      (Iter. (.-set iter) path (.-right iter) (keys-for (.-set iter) path) (path-get path 0)))))

lftj.clj

(ns datascript.lftj
  (:require [datascript.btset :refer [btset btset-iter iter-seek]])
  (:import [datascript.btset Iter]))

;; Implementation of Leapfrog join for unary relations. Leapfrog join
;; is a simple version of Leapfrog Triejoin, due to Todd Veldhuizen.

(def leapfrog-search)

(deftype UnaryLeapfrog [iterators p]
  clojure.lang.Sequential
  clojure.lang.Seqable
  (seq [this] (when-not (some empty? (.-iterators this)) this))

  clojure.lang.ISeq
  (first [this] (first (first (.-iterators this))))
  (next [this]
    (let [iterators (.-iterators this)
          p         (.-p this)]
      (when-some [iter' (next (nth iterators p))]
        (let [next-p (long (mod (inc p) (count iterators)))]
          (leapfrog-search (assoc iterators p iter') next-p)))))
  (more [this] (or (next this) '())))

(defn leapfrog-iter [iterators p]
  (UnaryLeapfrog. iterators p))

(defn unary-leapfrog [& relations]
  (let [iterators (sort-by first (map btset-iter relations))]
    (leapfrog-search iterators 0)))

(defn leapfrog-search [sorted-iterators p]
  (let [max (first (last sorted-iterators))]
    (loop [p         p
           x'        max
           iterators (into [] sorted-iterators)]
      (let [^Iter iter (nth iterators p)]
        (if (= x' (first iter))
          (leapfrog-iter iterators p)
          (when-some [iter' (iter-seek iter x')]
            (recur
             (long (mod (inc p) (count iterators))) ;; p = p + 1 mod k
             (first iter')
             (assoc iterators p iter'))))))))


(let [A (into (btset) [0 1   3 4 5 6 7 8 9    11])
      B (into (btset) [0   2       6 7 8 9      ])
      C (into (btset) [    2   4 5     8   10   ])]
  
  ;; order shouldn't matter
  (assert (= (first (unary-leapfrog C B A))
             (first (unary-leapfrog A B C))
             (first (unary-leapfrog B C A))
             8))
  
  (assert (false? (empty? (unary-leapfrog A B C))))

  (assert (= [8] (into [] (unary-leapfrog C B A))))

  (unary-leapfrog B C A)
  )

(let [A (into (btset) [0 1 2       6 7 8])
      B (into (btset) [      3 4 5 6 7 8])
      C (into (btset) [0 1 2 3 4 5      ])]

  ;; Any pairwise join of A, B, and C will produce three values, while
  ;; the full three-way join result contains none.

  (assert (nil? (first (unary-leapfrog A B C))))
  (assert (= [] (into [] (unary-leapfrog B C A))))
  )