ht.clj

;; Singly-Linked List
(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))

(defn node [& [car cdr]]
  (Node. car cdr))


;; Hash Table
(definterface IHashTable
  (checkOccupancy [])
  (incOccupancy [])
  (resize [])
  (hash [k])
  (head [k])
  (set [k v])
  (get [k]))

(deftype HashTable
  [^:volatile-mutable arr
   ^:volatile-mutable size
   ^:volatile-mutable occupancy
   ratio]
  IHashTable
  (checkOccupancy [this]
                  (let [cur-ratio (/ occupancy (alength arr))]
                    (> cur-ratio ratio)))
  (incOccupancy [_] (set! occupancy (inc occupancy)))
  (resize [this]
          (letfn [(get-tuples [head]
                              (loop [n head acc ()]
                                (if-not n
                                  acc
                                  (recur (.getCdr n)
                                         (cons (.getCar n) acc)))))]
            (let [kvs (loop [i 0 acc ()]
                        (if (= i (alength arr))
                          acc
                          (recur (inc i)
                                 (concat (get-tuples (aget arr i)) acc))))]
              (set! size (* 2 size))  ;; arbitrary growth factor
              (set! arr (make-array Node size))
              (doseq [[k v] kvs] (.set this k v)))))
  (hash [this k] (mod (hash k) size))
  (head [this k]
        (if-let [n (aget arr (.hash this k))]
          n
          (aset arr (.hash this k) (node))))
  (get [this k]
       (loop [n (.head this k)]
         (cond
           (nil? (.getCar n)) nil
           (= k ((.getCar n) 0)) ((.getCar n) 1)
           :else (recur (.getCdr n)))))
  (set [this k v]
       (letfn [(set-car [n & [inc?]]
                 (.setCar n (vector k v))
                 (when inc?
                   (do (.incOccupancy this)
                       (when (.checkOccupancy this)
                         (.resize this))))
                 this)]
         (loop [n (.head this k)]
           (cond
             (not (.getCar n)) (set-car n :inc)
             (= ((.getCar n) 0) k) (set-car n)
             :else (do (.setCdr n (node)) (recur (.getCdr n))))))))

(defn hash-table [& [size]]
  (let [size (or size 113)]
    (HashTable. (make-array Node size) size 0 7/10)))