ht.clj

(definterface INode
  (getCar [])
  (getCdr [])
  (setCar [x])
  (setCdr [x]))

(deftype Node
  [^:volatile-mutable car ^:volatile-mutable cdr]
  INode
  (getCar [_] car)
  (getCdr [_] cdr)
  (setCar [this x] (set! car x) this)
  (setCdr [this x] (set! cdr x) this)

  clojure.lang.Seqable
  (seq [this] (list this car cdr)))

(definterface ILinkedList
  (getHead []))

(deftype LinkedList
  [^:volatile-mutable head]
  ILinkedList
  (getHead [_] head)

  clojure.lang.IPersistentCollection
  (cons [this x] (set! head (Node. x head)) this)

  clojure.lang.Seqable
  (seq [this]
    (loop [cur head acc ()]
      (if-not cur
        acc
        (recur (.getCdr cur) (concat acc (list (seq cur)))))))

  clojure.lang.ISeq
  (first [_] [head (.getCar head) (.getCdr head)])
  (next [this] (drop 1 this))
  (more [this] (if-let [n (next this)] n ()))

  clojure.lang.Reversible
  (rseq [this]
    (loop [new-head nil cur head nex (.getCdr cur)]
      (if-not cur
        (do (set! head new-head) this)
        (do (.setCdr cur new-head) (recur cur nex (if nex (.getCdr nex))))))))

(defn linked-list [& [cars]]
  (let [ll (LinkedList. (Node. (first cars) nil))]
    (reduce conj ll (rest cars))))

(definterface IHashTable
  (maybeResize [])
  (setOccupancy [dir])
  (nodeKey [n])
  (nodeVal [n])
  (bucketIdx [k])
  (getBucket [k])
  (setBucket [k v])
  (get [k])
  (set [k v]))

(deftype HashTable
  [^:volatile-mutable buckets
   ^:volatile-mutable occupancy
   ^:volatile-mutable size
   load-factor]
  IHashTable
  (maybeResize [this]
    (when (> (/ size occupancy) load-factor)
      (let [new-size (* size 2)
            old-buckets buckets
            new-buckets (make-array LinkedList new-size)]
        (set! size new-size)
        (set! buckets new-buckets)
        (let [kvs (mapcat (fn [i]
                            (let [bucket (aget old-buckets i)]
                              (doseq [n bucket]
                                [(.nodeKey this n) (.nodeVal this n)])))
                          (range (alength old-buckets)))]
          (doseq [[k v] kvs] (.set this k v))))))
  (setOccupancy [this dir]
    (when (= :inc dir)
      (set! occupancy (inc occupancy)))
    (.maybeResize this))
  (nodeKey [_ n] (-> n first second first))
  (nodeVal [_ n] (-> n first second second))
  (bucketIdx [_ k] (mod (hash k) size))
  (getBucket [this k] (aget buckets (.bucketIdx this k)))
  (setBucket [this k v]
    (.setOccupancy this :inc)
    (aset buckets (.bucketIdx this k) v))
  (get [this k]
    (let [bucket (.getBucket this k)]
      (loop [head (first bucket) more (next bucket)]
        (if (or (not head) (= (.nodeKey this head) k))
          (.nodeVal this head)
        (recur (first more) (next more))))))
  (set [this k v]
    (if-let [bucket (.getBucket this k)]
      (loop [head (first bucket) more (next bucket)]
        (cond
          (not head) (.setBucket this k (conj bucket [k v]))
          (= (.nodeKey this head) k) (.setCar (first head) [k v])
          :else (recur (first more) (next more))))
      (.setBucket this k (linked-list [[k v]])))
    this))

(defn hash-table [& [size load-factor]]
  (let [size (or size 16)
        load-factor (or load-factor 7/10)]
  (HashTable. (make-array LinkedList size) 0 size load-factor)))