vertigo_binary_search.clj

(ns bar.baz
  (:require [vertigo.core :as vc]
            [vertigo.structs :as vs]))

;; 
;; based off of work by Michał Marczyk
;; http://stackoverflow.com/questions/8949837/binary-search-in-clojure-implementation-performance
;;

(set! *warn-on-reflection* true)

(defn- lowerbound-search
  "Finds earliest occurrence of val using provided getter function"
  [getfn val size]
  (loop [l 0
         h (unchecked-dec size)
         hint 0]
    (if (<= h (unchecked-add l 1))
      (cond
        (== val (getfn l)) [l hint]
        (== val (getfn h)) [h hint]
        :else nil)
      (let [m (unchecked-add l (bit-shift-right (unchecked-subtract h l) 1))]
        (if (< (getfn m) val)
          (recur (unchecked-inc m) h m)
          (if (and (== (getfn m) val)
                   (> m hint))
            (recur l m m)
            (recur l m hint)))))))

(defn- upperbound-search
  "Finds latest occurrence of val using provided getter function."
  ([getfn val size ^long lowerbound]
     (loop [l lowerbound
            h (unchecked-dec size)]
       (if (<= h (unchecked-add l 1))
         (cond
           (== val (getfn h)) h
           (== val (getfn l)) l
           :else nil)
         (let [m (unchecked-add l (bit-shift-right (unchecked-subtract h l) 1))]
           (if (> (getfn m) val)
             (recur l m)
             (recur m h)))))))

(defn range-search
  "Finds earliest and latest occurrence of val in a vertigo typed struct. Data
   must be in sorted order. Returns a vector of two elements denoting the index
   ranges at which val was found or simply nil if val was not present."
  ([getfn val size]
    (if-let [[earliest hint] (lowerbound-search getfn val size)]
      (let [latest (upperbound-search getfn val size hint)]
        [earliest, latest])
      nil)))

;;;;;;;;;;;;;

(def size 1000)

(vs/def-typed-struct foo
  :a (vs/array vs/uint16 size)
  :b (vs/array vs/uint16 size))

(letfn [(data [] (sort (take size (repeatedly #(rand-int 100)))))]
  (def ^:foo ts (vc/marshal-seq foo [{:a (data) :b (data)}])))

(range-search #(vc/get-in ts [0 :a %]) 0 size)
(range-search #(vc/get-in ts [0 :a %]) 10 size)
(range-search #(vc/get-in ts [0 :a %]) 99 size)
(range-search #(vc/get-in ts [0 :a %]) 100 size)