Commits

Moritz Heidkamp  committed 95634c4

quarter of persistent hash map

  • Participants
  • Parent commits c2a3c3f
  • Branches pv

Comments (0)

Files changed (1)

File clojurian-map.scm

+(use clojurian-syntax srfi-1 coops coops-primitive-objects)
+(use (rename (only srfi-69 hash) (hash calc-hash)))
+
+(include "clojurian-data-structure-helpers.scm")
+
+;; (deftype Box [^:mutable val])
+
+(define-record box val)
+
+;; (declare create-inode-seq create-array-node-seq reset! create-node atom deref)
+
+;; (defn ^boolean key-test [key other]
+;;   (if ^boolean (goog/isString key)
+;;     (identical? key other)
+;;     (= key other)))
+
+(define key-test equal?)
+
+;; (defn- mask [hash shift]
+;;   (bit-and (bit-shift-right-zero-fill hash shift) 0x01f))
+
+(define (mask hash shift)
+  (-> (arithmetic-shift-right/zero-fill hash shift)
+      (bitwise-and #x01f)))
+
+;; (defn- clone-and-set
+;;   ([arr i a]
+;;      (doto (aclone arr)
+;;        (aset i a)))
+;;   ([arr i a j b]
+;;      (doto (aclone arr)
+;;        (aset i a)
+;;        (aset j b))))
+
+(define clone-and-set
+  (case-lambda
+   ((vec i a)
+    (doto (vector-copy vec)
+          (vector-set! i a)))
+   ((vec i a j b)
+    (doto (vector-copy vec)
+          (vector-set! i a)
+          (vector-set! j b)))))
+
+
+;; (defn- remove-pair [arr i]
+;;   (let [new-arr (make-array (- (alength arr) 2))]
+;;     (array-copy arr 0 new-arr 0 (* 2 i))
+;;     (array-copy arr (* 2 (inc i)) new-arr (* 2 i) (- (alength new-arr) (* 2 i)))
+;;     new-arr))
+
+(define (remove-pair vec i)
+  (let ((new-vec (make-vector (- (vector-length vec) 2))))
+    (vector-copy* vec 0 new-vec 0 (* 2 i))
+    (vector-copy* vec (* 2 (+ i 1)) new-vec (* 2 i) (- (vector-length new-vec) (* 2 i)))
+    new-vec))
+
+
+;; (defn- bitmap-indexed-node-index [bitmap bit]
+;;   (bit-count (bit-and bitmap (dec bit))))
+
+(define (bitmap-indexed-node-index bitmap bit)
+  (bit-count (bitwise-and bitmap (- bit 1))))
+
+;; (defn- bitpos [hash shift]
+;;   (bit-shift-left 1 (mask hash shift)))
+
+(define (bitpos hash shift)
+  (arithmetic-shift 1 (mask hash shift)))
+
+(define-syntax define-record-class
+  (ir-macro-transformer
+   (lambda (x i c)
+     (let* ((name      (cadr x))
+            (parents   (caddr x))
+            (slots     (cdr (cadddr x)))
+            (make-name (car (cadddr x)))
+            (make-args (append-map
+                        (lambda (s) (list (list 'quote s) s))
+                        slots)))
+       `(begin
+          (define-class ,name ,parents ,slots)
+          (define (,make-name . ,slots)
+            (make ,name . ,make-args)))))))
+
+(define-record-class <bi-node> () 
+  (make-bi-node edit bitmap vec))
+
+(define +empty-bi-node+
+  (make-bi-node #f 0 (make-vector 0)))
+
+(define-syntax let-slots
+  (syntax-rules ()
+    ((_ (slot ...) object body ...)
+     (let ((slot (slot-value object 'slot)) ...)
+       body ...))))
+
+(define-generic (ensure-editable inode))
+
+;;   (ensure-editable [inode e]
+;;     (if (identical? e edit)
+;;       inode
+;;       (let [n       (bit-count bitmap)
+;;             new-arr (make-array (if (neg? n) 4 (* 2 (inc n))))]
+;;         (array-copy arr 0 new-arr 0 (* 2 n))
+;;         (BitmapIndexedNode. e bitmap new-arr))))
+
+(define-method (ensure-editable (inode <bi-node>) e)
+  (let-slots (bitmap edit vec) inode
+    (if (eq? e edit)
+        inode
+        (let* ((n       (bit-count bitmap))
+               (new-vec (make-vector (if (negative? n) 4 (* 2 (+ n 1))))))
+          (vector-copy* vec 0 new-vec 0 (* 2 n))
+          (make-bi-node e bitmap new-vec)))))
+
+;; (defn- edit-and-set
+;;   ([inode edit i a]
+;;      (let [editable (.ensure-editable inode edit)]
+;;        (aset (.-arr editable) i a)
+;;        editable))
+;;   ([inode edit i a j b]
+;;      (let [editable (.ensure-editable inode edit)]
+;;        (aset (.-arr editable) i a)
+;;        (aset (.-arr editable) j b)
+;;        editable)))
+
+(define edit-and-set
+  (case-lambda
+   ((inode edit i a)
+    (let ((editable (ensure-editable inode edit)))
+      (vector-set! (slot-value editable 'vec) i a)
+      editable))
+   ((inode edit i a j b)
+    (let* ((editable (ensure-editable inode edit))
+           (vec (slot-value editable 'vec)))
+      (vector-set! vec i a)
+      (vector-set! vec j b)
+      editable))))
+
+;; (defn- inode-kv-reduce [arr f init]
+;;   (let [len (alength arr)]
+;;     (loop [i 0 init init]
+;;       (if (< i len)
+;;         (let [init (let [k (aget arr i)]
+;;                      (if-not (nil? k)
+;;                        (f init k (aget arr (inc i)))
+;;                        (let [node (aget arr (inc i))]
+;;                          (if-not (nil? node)
+;;                            (.kv-reduce node f init)
+;;                            init))))]
+;;           (if (reduced? init)
+;;             @init
+;;             (recur (+ i 2) init)))
+;;         init))))
+
+
+;; (declare ArrayNode)
+
+;; (deftype BitmapIndexedNode [edit ^:mutable bitmap ^:mutable arr]
+;;   Object
+
+;; (deftype ArrayNode [edit ^:mutable cnt ^:mutable arr]
+
+(define-record-class <vector-node> ()
+  (make-vector-node edit cnt vec))
+
+(define-record-class <hash-collision-node> ()
+  (make-hash-collision-node edit collision-hash cnt vec))
+
+
+
+  ;; (inode-assoc! [inode edit shift hash key val added-leaf?]
+  ;;   (let [bit (bitpos hash shift)
+  ;;         idx (bitmap-indexed-node-index bitmap bit)]
+  ;;     (if (zero? (bit-and bitmap bit))
+  ;;       (let [n (bit-count bitmap)]
+  ;;         (cond
+  ;;           (< (* 2 n) (alength arr))
+  ;;           (let [editable (.ensure-editable inode edit)
+  ;;                 earr     (.-arr editable)]
+  ;;             (set! (.-val added-leaf?) true)
+  ;;             (array-copy-downward earr (* 2 idx)
+  ;;                                  earr (* 2 (inc idx))
+  ;;                                  (* 2 (- n idx)))
+  ;;             (aset earr (* 2 idx) key)
+  ;;             (aset earr (inc (* 2 idx)) val)
+  ;;             (set! (.-bitmap editable) (bit-or (.-bitmap editable) bit))
+  ;;             editable)
+
+  ;;           (>= n 16)
+  ;;           (let [nodes (make-array 32)
+  ;;                 jdx   (mask hash shift)]
+  ;;             (aset nodes jdx (.inode-assoc! cljs.core.BitmapIndexedNode/EMPTY edit (+ shift 5) hash key val added-leaf?))
+  ;;             (loop [i 0 j 0]
+  ;;               (if (< i 32)
+  ;;                 (if (zero? (bit-and (bit-shift-right-zero-fill bitmap i) 1))
+  ;;                   (recur (inc i) j)
+  ;;                   (do (aset nodes i
+  ;;                             (if-not (nil? (aget arr j))
+  ;;                               (.inode-assoc! cljs.core.BitmapIndexedNode/EMPTY
+  ;;                                              edit (+ shift 5) (cljs.core/hash (aget arr j)) (aget arr j) (aget arr (inc j)) added-leaf?)
+  ;;                               (aget arr (inc j))))
+  ;;                       (recur (inc i) (+ j 2))))))
+  ;;             (ArrayNode. edit (inc n) nodes))
+
+  ;;           :else
+  ;;           (let [new-arr (make-array (* 2 (+ n 4)))]
+  ;;             (array-copy arr 0 new-arr 0 (* 2 idx))
+  ;;             (aset new-arr (* 2 idx) key)
+  ;;             (aset new-arr (inc (* 2 idx)) val)
+  ;;             (array-copy arr (* 2 idx) new-arr (* 2 (inc idx)) (* 2 (- n idx)))
+  ;;             (set! (.-val added-leaf?) true)
+  ;;             (let [editable (.ensure-editable inode edit)]
+  ;;               (set! (.-arr editable) new-arr)
+  ;;               (set! (.-bitmap editable) (bit-or (.-bitmap editable) bit))
+  ;;               editable))))
+  ;;       (let [key-or-nil  (aget arr (* 2 idx))
+  ;;             val-or-node (aget arr (inc (* 2 idx)))]
+  ;;         (cond (nil? key-or-nil)
+  ;;               (let [n (.inode-assoc! val-or-node edit (+ shift 5) hash key val added-leaf?)]
+  ;;                 (if (identical? n val-or-node)
+  ;;                   inode
+  ;;                   (edit-and-set inode edit (inc (* 2 idx)) n)))
+
+  ;;               (key-test key key-or-nil)
+  ;;               (if (identical? val val-or-node)
+  ;;                 inode
+  ;;                 (edit-and-set inode edit (inc (* 2 idx)) val))
+
+  ;;               :else
+  ;;               (do (set! (.-val added-leaf?) true)
+  ;;                   (edit-and-set inode edit (* 2 idx) nil (inc (* 2 idx))
+  ;;                                 (create-node edit (+ shift 5) key-or-nil val-or-node hash key val))))))))
+
+
+(define (inode-assoc! inode edit shift hash key val added-leaf?)
+  (let* ((bitmap (inode-bitmap inode))
+         (vec    (inode-vec inode))
+         (bit    (bitpos hash shift))
+         (idx    (bitmap-indexed-node-index bitmap bit)))
+    (if (zero? (bitwise-and bitmap bit))
+        (let ((n (bit-count bitmap)))
+          (cond
+           ((< (* 2 n) (vector-length vec))
+            (let* ((editable (inode-ensure-editable inode edit))
+                   (evec     (inode-vec editable)))
+              (box-val-set! added-leaf? #t)
+              (vector-copy-downward evec (* 2 idx)
+                                    evec (* 2 (- idx 1))
+                                    (* 2 (- n idx)))
+              (vector-set! evec (* 2 idx) key)
+              (vector-set! evec (+ (* 2 idx) 1) val)
+              (inode-bitmap-set! editable (bitwise-ior (inode-bitmap editable) bit))
+              editable))
+
+           ((>= n 16)
+            (let ((nodes (make-vector 32))
+                  (jdx   (mask hash shift)))
+              (vector-set! nodes jdx (inode-assoc! +empty-inode+ edit (+ shift 5) hash key val added-leaf?))
+              (let loop ((i 0) (j 0))
+                (if (< i 32)
+                    (if (zero? (bitwise-and (arithmetic-shift-right/zero-fill bitmap i) 1))
+                        (loop (+ i 1) j)
+                        (begin
+                          (vector-set! nodes i
+                                       (if (vector-ref vec j)
+                                           (inode-assoc! +empty-inode+
+                                                         edit
+                                                         (+ shift 5)
+                                                         (calc-hash (vector-ref vec j))
+                                                         (vector-ref vec j)
+                                                         (vector-ref vec (+ j 1))
+                                                         added-leaf?)
+                                           (vector-ref vec (+ j 1))))
+                          (loop (+ i 1) (+ j 2))))))
+              (make-anode edit (+ n 1) nodes)))
+
+           (else
+            (let ((new-vec (make-vector (* 2 (+ n 4)))))
+              (vector-copy* vec 0 new-vec 0 (* 2 idx))
+              (vector-set! new-vec (* 2 idx) key)
+              (vector-set! new-vec (+ (* 2 idx) 1) val)
+              (vector-copy* vec (* 2 idx) new-vec (* 2 (+ idx 1)) (* 2 (- n idx)))
+              (box-val-set! added-leaf? #t)
+              (let ((editable (inode-ensure-editable inode edit)))
+                (inode-vec-set! editable new-vec)
+                (inode-bitmap-set! editable (bitwise-ior (inode-bitmap editable) bit))
+                editable)))))
+
+        (let ((key-or-nil  (vector-ref vec (* 2 idx)))
+              (val-or-node (vector-ref vec (+ (* 2 idx) 1))))
+          (cond ((not key-or-nil)
+                 (let ((n (inode-assoc! val-or-node edit (+ shift 5) hash key val added-leaf?)))
+                   (if (eq? n val-or-node)
+                       inode
+                       (edit-and-set inode edit (+ (* 2 idx) 1) n))))
+
+                ((key-test key key-or-nil)
+                 (if (eq? val val-or-node)
+                     inode
+                     (edit-and-set inode edit (+ (* 2 idx) 1) val)))
+
+                (else
+                 (box-val-set! added-leaf? #t)
+                 (edit-and-set inode edit (* 2 idx) #f (+ (* 2 idx) 1)
+                               (create-node edit (+ shift 5) key-or-nil val-or-node hash key val))))))))
+
+
+
+
+
+;; (defn- create-node
+;;   ([shift key1 val1 key2hash key2 val2]
+;;      (let [key1hash (hash key1)]
+;;        (if (== key1hash key2hash)
+;;          (HashCollisionNode. nil key1hash 2 (array key1 val1 key2 val2))
+;;          (let [added-leaf? (Box. false)]
+;;            (-> cljs.core.BitmapIndexedNode/EMPTY
+;;                (.inode-assoc shift key1hash key1 val1 added-leaf?)
+;;                (.inode-assoc shift key2hash key2 val2 added-leaf?))))))
+;;   ([edit shift key1 val1 key2hash key2 val2]
+;;      (let [key1hash (hash key1)]
+;;        (if (== key1hash key2hash)
+;;          (HashCollisionNode. nil key1hash 2 (array key1 val1 key2 val2))
+;;          (let [added-leaf? (Box. false)]
+;;            (-> cljs.core.BitmapIndexedNode/EMPTY
+;;                (.inode-assoc! edit shift key1hash key1 val1 added-leaf?)
+;;                (.inode-assoc! edit shift key2hash key2 val2 added-leaf?)))))))
+
+(define create-node
+  (case-lambda
+   ((shift key1 val1 key2hash key2 val2)
+    (let ((key1hash (calc-hash key1)))
+      (if (= key1hash key2hash)
+          (make-hash-collision-node #f key1hash 2 (vector key1 val1 key2 val2))
+          (let ((added-leaf? (make-box #f)))
+            (-> +empty-inode+
+                (inode-assoc shift key1hash key1 val1 added-leaf?)
+                (inode-assoc shift key2hash key2 val2 added-leaf?))))))
+   ((edit shift key1 val1 key2hash key2 val2)
+    (let ((key1hash (hash key1)))
+      (if (= key1hash key2hash)
+          (make-hash-collision-node #f key1hash 2 (vector key1 val1 key2 val2))
+          (let ((added-leaf? (make-box #f)))
+            (-> +empty-inode+
+                (inode-assoc! edit shift key1hash key1 val1 added-leaf?)
+                (inode-assoc! edit shift key2hash key2 val2 added-leaf?))))))))
+
+
+;;   (inode-assoc [inode shift hash key val added-leaf?]
+;;     (let [bit (bitpos hash shift)
+;;           idx (bitmap-indexed-node-index bitmap bit)]
+;;       (if (zero? (bit-and bitmap bit))
+;;         (let [n (bit-count bitmap)]
+;;           (if (>= n 16)
+;;             (let [nodes (make-array 32)
+;;                   jdx   (mask hash shift)]
+;;               (aset nodes jdx (.inode-assoc cljs.core.BitmapIndexedNode/EMPTY (+ shift 5) hash key val added-leaf?))
+;;               (loop [i 0 j 0]
+;;                 (if (< i 32)
+;;                   (if (zero? (bit-and (bit-shift-right-zero-fill bitmap i) 1))
+;;                     (recur (inc i) j)
+;;                     (do (aset nodes i
+;;                               (if-not (nil? (aget arr j))
+;;                                 (.inode-assoc cljs.core.BitmapIndexedNode/EMPTY
+;;                                               (+ shift 5) (cljs.core/hash (aget arr j)) (aget arr j) (aget arr (inc j)) added-leaf?)
+;;                                 (aget arr (inc j))))
+;;                         (recur (inc i) (+ j 2))))))
+;;               (ArrayNode. nil (inc n) nodes))
+;;             (let [new-arr (make-array (* 2 (inc n)))]
+;;               (array-copy arr 0 new-arr 0 (* 2 idx))
+;;               (aset new-arr (* 2 idx) key)
+;;               (aset new-arr (inc (* 2 idx)) val)
+;;               (array-copy arr (* 2 idx) new-arr (* 2 (inc idx)) (* 2 (- n idx)))
+;;               (set! (.-val added-leaf?) true)
+;;               (BitmapIndexedNode. nil (bit-or bitmap bit) new-arr))))
+;;         (let [key-or-nil  (aget arr (* 2 idx))
+;;               val-or-node (aget arr (inc (* 2 idx)))]
+;;           (cond (nil? key-or-nil)
+;;                 (let [n (.inode-assoc val-or-node (+ shift 5) hash key val added-leaf?)]
+;;                   (if (identical? n val-or-node)
+;;                     inode
+;;                     (BitmapIndexedNode. nil bitmap (clone-and-set arr (inc (* 2 idx)) n))))
+
+;;                 (key-test key key-or-nil)
+;;                 (if (identical? val val-or-node)
+;;                   inode
+;;                   (BitmapIndexedNode. nil bitmap (clone-and-set arr (inc (* 2 idx)) val)))
+
+;;                 :else
+;;                 (do (set! (.-val added-leaf?) true)
+;;                     (BitmapIndexedNode. nil bitmap
+;;                                         (clone-and-set arr (* 2 idx) nil (inc (* 2 idx))
+;;                                                        (create-node (+ shift 5) key-or-nil val-or-node hash key val)))))))))
+
+(define-generic (inode-assoc inode))
+
+(define-method (inode-assoc (inode <bi-node>) shift hash key val added-leaf?)
+  (let-slots (bitmap vec) inode
+    (let* ((bit    (bitpos hash shift))
+           (idx    (bitmap-indexed-node-index bitmap bit)))
+      (if (zero? (bitwise-and bitmap bit))
+          (let ((n (bit-count bitmap)))
+            (if (>= n 16)
+                (let ((nodes (make-vector 32))
+                      (jdx   (mask hash shift)))
+                  (vector-set! nodes jdx (inode-assoc +empty-bi-node+ (+ shift 5) hash key val added-leaf?))
+                  (let loop ((i 0) (j 0))
+                    (if (< i 32)
+                        (if (zero? (bitwise-and (arithmetic-shift-right/zero-fill bitmap i) 1))
+                            (loop (+ i 1) j)
+                            (begin
+                              (vector-set!
+                               nodes i
+                               (if (vector-ref vec j)
+                                   (inode-assoc +empty-bi-node+
+                                                (+ shift 5)
+                                                (calc-hash (vector-ref vec j))
+                                                (vector-ref vec j)
+                                                (vector-ref vec (+ j 1))
+                                                added-leaf?)
+                                   (vector-ref vec (+ j 1))))
+                              (loop (+ i 1) (+ j 2))))))
+                  (make-vector-node #f (+ n 1) nodes))
+                (let ((new-vec (make-vector (* 2 (+ n 1)))))
+                  (vector-copy* vec 0 new-vec 0 (* 2 idx))
+                  (vector-set! new-vec (* 2 idx) key)
+                  (vector-set! new-vec (+ (* 2 idx) 1) val)
+                  (vector-copy* vec (* 2 idx) new-vec (* 2 (+ idx 1)) (* 2 (- n idx)))
+                  (box-val-set! added-leaf? #t)
+                  (make-bi-node #f (bitwise-ior bitmap bit) new-vec))))
+          (let ((key-or-nil  (vector-ref vec (* 2 idx)))
+                (val-or-node (vector-ref vec (+ (* 2 idx) 1))))
+            (cond ((not key-or-nil)
+                   (let ((n (inode-assoc val-or-node (+ shift 5) hash key val added-leaf?)))
+                     (if (eq? n val-or-node)
+                         inode
+                         (make-bi-node #f bitmap (clone-and-set vec (+ (* 2 idx) 1) n)))))
+                  ((key-test key key-or-nil)
+                   (if (eq? val val-or-node)
+                       inode
+                       (make-bi-node #f bitmap (clone-and-set vec (+ (* 2 idx) 1) val))))
+                  (else
+                   (box-val-set! added-leaf? #t)
+                   (make-bi-node #f bitmap
+                               (->> (create-node (+ shift 5) key-or-nil val-or-node hash key val)
+                                    (clone-and-set vec
+                                                   (* 2 idx)
+                                                   #f
+                                                   (+ (* 2 idx) 1)))))))))))
+
+;;   (inode-without [inode shift hash key]
+;;     (let [bit (bitpos hash shift)]
+;;       (if (zero? (bit-and bitmap bit))
+;;         inode
+;;         (let [idx         (bitmap-indexed-node-index bitmap bit)
+;;               key-or-nil  (aget arr (* 2 idx))
+;;               val-or-node (aget arr (inc (* 2 idx)))]
+;;           (cond (nil? key-or-nil)
+;;                 (let [n (.inode-without val-or-node (+ shift 5) hash key)]
+;;                   (cond (identical? n val-or-node) inode
+;;                         (not (nil? n)) (BitmapIndexedNode. nil bitmap (clone-and-set arr (inc (* 2 idx)) n))
+;;                         (== bitmap bit) nil
+;;                         :else (BitmapIndexedNode. nil (bit-xor bitmap bit) (remove-pair arr idx))))
+;;                 (key-test key key-or-nil)
+;;                 (BitmapIndexedNode. nil (bit-xor bitmap bit) (remove-pair arr idx))
+;;                 :else inode)))))
+
+(define-generic (inode-without inode))
+
+(define-method (inode-without (inode <bi-node>) shift hash key)
+  (let-slots (bitmap vec) inode
+    (let ((bit    (bitpos hash shift)))
+      (if (zero? (bitwise-and bitmap bit))
+          inode
+          (let* ((idx         (bitmap-indexed-node-index bitmap bit))
+                 (key-or-nil  (vector-ref vec (* 2 idx)))
+                 (val-or-node (vector-ref vec (+ (* 2 idx) 1))))
+            (cond ((not  key-or-nil)
+                   (let ((n (inode-without val-or-node (+ shift 5) hash key)))
+                     (cond ((eq? n val-or-node) inode)
+                           (n (make-bi-node #f bitmap (clone-and-set vec (+ (* 2 idx) 1) n)))
+                           ((= bitmap bit) #f)
+                           (else (make-bi-node #f (bitwise-xor bitmap bit) (remove-pair vec idx))))))
+                  ((key-test key key-or-nil)
+                   (make-inode #f (bitwise-xor bitmap bit) (remove-pair vec idx)))
+                  (else inode)))))))
+
+
+;;   (inode-lookup [inode shift hash key not-found]
+;;     (let [bit (bitpos hash shift)]
+;;       (if (zero? (bit-and bitmap bit))
+;;         not-found
+;;         (let [idx         (bitmap-indexed-node-index bitmap bit)
+;;               key-or-nil  (aget arr (* 2 idx))
+;;               val-or-node (aget arr (inc (* 2 idx)))]
+;;           (cond (nil? key-or-nil)  (.inode-lookup val-or-node (+ shift 5) hash key not-found)
+;;                 (key-test key key-or-nil) val-or-node
+;;                 :else not-found)))))
+
+
+(define (inode-lookup inode shift hash key not-found)
+  (let* ((bitmap (inode-bitmap inode))
+         (vec    (inode-vec inode))
+         (bit    (bitpos hash shift)))
+    (if (zero? (bitwise-and bitmap bit))
+        not-found
+        (let* ((idx         (bitmap-indexed-node-index bitmap bit))
+               (key-or-nil  (vector-ref vec (* 2 idx)))
+               (val-or-node (vector-ref vec (- (* 2 idx) 1))))
+          (cond ((not key-or-nil)
+                 (inode-lookup val-or-node (+ shift 5) hash key not-found))
+                ((key-test key key-or-nil) val-or-node)
+                (else not-found))))))
+
+
+
+;;   (inode-find [inode shift hash key not-found]
+;;     (let [bit (bitpos hash shift)]
+;;       (if (zero? (bit-and bitmap bit))
+;;         not-found
+;;         (let [idx         (bitmap-indexed-node-index bitmap bit)
+;;               key-or-nil  (aget arr (* 2 idx))
+;;               val-or-node (aget arr (inc (* 2 idx)))]
+;;           (cond (nil? key-or-nil) (.inode-find val-or-node (+ shift 5) hash key not-found)
+;;                 (key-test key key-or-nil)          [key-or-nil val-or-node]
+;;                 :else not-found)))))
+
+
+(define (inode-find inode shift hash key not-found)
+  (let ((bitmap (inode-bitmap inode))
+        (vec    (inode-vec inode))
+        (bit (bitpos hash shift)))
+    (if (zero? (bitwise-and bitmap bit))
+        not-found
+        (let* ((idx         (bitmap-indexed-node-index bitmap bit))
+               (key-or-nil  (vector-ref vec (* 2 idx)))
+               (val-or-node (vector-ref vec (+ (* 2 idx) 1))))
+          (cond ((not key-or-nil)
+                 (inode-find val-or-node (+ shift 5) hash key not-found))
+                ((key-test key key-or-nil)
+                 ;; FIXME: how to represent kv pairs?
+                 (cons key-or-nil val-or-node))
+                (else not-found))))))
+
+;;   (inode-seq [inode]
+;;     (create-inode-seq arr))
+
+;;   (edit-and-remove-pair [inode e bit i]
+;;     (if (== bitmap bit)
+;;       nil
+;;       (let [editable (.ensure-editable inode e)
+;;             earr     (.-arr editable)
+;;             len      (alength earr)]
+;;         (set! (.-bitmap editable) (bit-xor bit (.-bitmap editable)))
+;;         (array-copy earr (* 2 (inc i))
+;;                     earr (* 2 i)
+;;                     (- len (* 2 (inc i))))
+;;         (aset earr (- len 2) nil)
+;;         (aset earr (dec len) nil)
+;;         editable)))
+
+(define (edit-and-remove-pair inode e bit i)
+  (let* ((bitmap (inode-bitmap inode)))
+    (and (not (= bitmap bit))
+         (let* ((editable (inode-ensure-editable inode e))
+                (evec     (inode-vec editable))
+                (len      (vector-length evec)))
+           (inode-bitmap-set! editable (bitwise-xor bit (inode-bitmap editable)))
+           (vector-copy* evec (* 2 (+ i 1))
+                         evec (* 2 i)
+                         (- len (* 2 (+ i 1))))
+           (vector-set! evec (- len 2) #f)
+           (vector-set! evec (- len 1) #f)
+           editable))))
+
+
+
+;;   (inode-without! [inode edit shift hash key removed-leaf?]
+;;     (let [bit (bitpos hash shift)]
+;;       (if (zero? (bit-and bitmap bit))
+;;         inode
+;;         (let [idx         (bitmap-indexed-node-index bitmap bit)
+;;               key-or-nil  (aget arr (* 2 idx))
+;;               val-or-node (aget arr (inc (* 2 idx)))]
+;;           (cond (nil? key-or-nil)
+;;                 (let [n (.inode-without! val-or-node edit (+ shift 5) hash key removed-leaf?)]
+;;                   (cond (identical? n val-or-node) inode
+;;                         (not (nil? n)) (edit-and-set inode edit (inc (* 2 idx)) n)
+;;                         (== bitmap bit) nil
+;;                         :else (.edit-and-remove-pair inode edit bit idx)))
+;;                 (key-test key key-or-nil)
+;;                 (do (aset removed-leaf? 0 true)
+;;                     (.edit-and-remove-pair inode edit bit idx))
+;;                 :else inode)))))
+
+
+(define (inode-without! inode edit shift hash key removed-leaf?)
+  (let ((bitmap (inode-bitmap inode))
+        (vec    (inode-vec inode))
+        (bit    (bitpos hash shift)))
+    (if (zero? (bitwise-and bitmap bit))
+        inode
+        (let* ((idx         (bitmap-indexed-node-index bitmap bit))
+               (key-or-nil  (vector-ref vec (* 2 idx)))
+               (val-or-node (vector-ref vec (+ (* 2 idx) 1))))
+          (cond ((not key-or-nil)
+                 (let ((n (inode-without! val-or-node edit (+ shift 5) hash key removed-leaf?)))
+                   (cond ((eq? n val-or-node) inode)
+                         (n (edit-and-set inode edit (+ (* 2 idx) 1) n))
+                         ((= bitmap bit) #f)
+                         (else (edit-and-remove-pair inode edit bit idx)))))
+                ((key-test key key-or-nil)
+                 (box-val-set! removed-leaf? #t)
+                 (edit-and-remove-pair inode edit bit idx))
+                (else inode))))))
+
+
+;;   (kv-reduce [inode f init]
+;;     (inode-kv-reduce arr f init)))
+
+;; (defn- pack-array-node [array-node edit idx]
+;;   (let [arr     (.-arr array-node)
+;;         len     (* 2 (dec (.-cnt array-node)))
+;;         new-arr (make-array len)]
+;;     (loop [i 0 j 1 bitmap 0]
+;;       (if (< i len)
+;;         (if (and (not (== i idx))
+;;                  (not (nil? (aget arr i))))
+;;           (do (aset new-arr j (aget arr i))
+;;               (recur (inc i) (+ j 2) (bit-or bitmap (bit-shift-left 1 i))))
+;;           (recur (inc i) j bitmap))
+;;         (BitmapIndexedNode. edit bitmap new-arr)))))
+
+
+(define (pack-array-node array-node edit idx)
+  (let* ((vec     (anode-vec array-node))
+         (len     (* 2 (- (anode-cnt array-node) 1)))
+         (new-vec (make-vector len)))
+    (let loop ((i 0) (j 1) (bitmap 0))
+      (if (< i len)
+          (if (and (not (= i idx))
+                   (vector-ref vec i))
+              (begin
+                (vector-set! new-vec j (vector-ref vec i))
+                (loop (+ i 1) (+ j 2) (bitwise-ior bitmap (arithmetic-shift 1 i))))
+              (loop (+ i 1) j bitmap))
+          (make-inode edit bitmap new-vec)))))
+
+
+;; (deftype ArrayNode [edit ^:mutable cnt ^:mutable arr]
+;;   Object
+;;   (inode-assoc [inode shift hash key val added-leaf?]
+;;     (let [idx  (mask hash shift)
+;;           node (aget arr idx)]
+;;       (if (nil? node)
+;;         (ArrayNode. nil (inc cnt) (clone-and-set arr idx (.inode-assoc cljs.core.BitmapIndexedNode/EMPTY (+ shift 5) hash key val added-leaf?)))
+;;         (let [n (.inode-assoc node (+ shift 5) hash key val added-leaf?)]
+;;           (if (identical? n node)
+;;             inode
+;;             (ArrayNode. nil cnt (clone-and-set arr idx n)))))))
+
+;;   (inode-without [inode shift hash key]
+;;     (let [idx  (mask hash shift)
+;;           node (aget arr idx)]
+;;       (if-not (nil? node)
+;;         (let [n (.inode-without node (+ shift 5) hash key)]
+;;           (cond
+;;             (identical? n node)
+;;             inode
+
+;;             (nil? n)
+;;             (if (<= cnt 8)
+;;               (pack-array-node inode nil idx)
+;;               (ArrayNode. nil (dec cnt) (clone-and-set arr idx n)))
+
+;;             :else
+;;             (ArrayNode. nil cnt (clone-and-set arr idx n))))
+;;         inode)))
+
+;;   (inode-lookup [inode shift hash key not-found]
+;;     (let [idx  (mask hash shift)
+;;           node (aget arr idx)]
+;;       (if-not (nil? node)
+;;         (.inode-lookup node (+ shift 5) hash key not-found)
+;;         not-found)))
+
+;;   (inode-find [inode shift hash key not-found]
+;;     (let [idx  (mask hash shift)
+;;           node (aget arr idx)]
+;;       (if-not (nil? node)
+;;         (.inode-find node (+ shift 5) hash key not-found)
+;;         not-found)))
+
+;;   (inode-seq [inode]
+;;     (create-array-node-seq arr))
+
+;;   (ensure-editable [inode e]
+;;     (if (identical? e edit)
+;;       inode
+;;       (ArrayNode. e cnt (aclone arr))))
+
+;;   (inode-assoc! [inode edit shift hash key val added-leaf?]
+;;     (let [idx  (mask hash shift)
+;;           node (aget arr idx)]
+;;       (if (nil? node)
+;;         (let [editable (edit-and-set inode edit idx (.inode-assoc! cljs.core.BitmapIndexedNode/EMPTY edit (+ shift 5) hash key val added-leaf?))]
+;;           (set! (.-cnt editable) (inc (.-cnt editable)))
+;;           editable)
+;;         (let [n (.inode-assoc! node edit (+ shift 5) hash key val added-leaf?)]
+;;           (if (identical? n node)
+;;             inode
+;;             (edit-and-set inode edit idx n))))))
+
+;;   (inode-without! [inode edit shift hash key removed-leaf?]
+;;     (let [idx  (mask hash shift)
+;;           node (aget arr idx)]
+;;       (if (nil? node)
+;;         inode
+;;         (let [n (.inode-without! node edit (+ shift 5) hash key removed-leaf?)]
+;;           (cond
+;;             (identical? n node)
+;;             inode
+
+;;             (nil? n)
+;;             (if (<= cnt 8)
+;;               (pack-array-node inode edit idx)
+;;               (let [editable (edit-and-set inode edit idx n)]
+;;                 (set! (.-cnt editable) (dec (.-cnt editable)))
+;;                 editable))
+
+;;             :else
+;;             (edit-and-set inode edit idx n))))))
+
+;;   (kv-reduce [inode f init]
+;;     (let [len (alength arr)]           ; actually 32
+;;       (loop [i 0 init init]
+;;         (if (< i len)
+;;           (let [node (aget arr i)]
+;;             (if-not (nil? node)
+;;               (let [init (.kv-reduce node f init)]
+;;                 (if (reduced? init)
+;;                   @init
+;;                   (recur (inc i) init)))))
+;;           init)))))
+
+;; (defn- hash-collision-node-find-index [arr cnt key]
+;;   (let [lim (* 2 cnt)]
+;;     (loop [i 0]
+;;       (if (< i lim)
+;;         (if (key-test key (aget arr i))
+;;           i
+;;           (recur (+ i 2)))
+;;         -1))))
+
+;; (deftype HashCollisionNode [edit
+;;                             ^:mutable collision-hash
+;;                             ^:mutable cnt
+;;                             ^:mutable arr]
+;;   Object
+;;   (inode-assoc [inode shift hash key val added-leaf?]
+;;     (if (== hash collision-hash)
+;;       (let [idx (hash-collision-node-find-index arr cnt key)]
+;;         (if (== idx -1)
+;;           (let [len (alength arr)
+;;                 new-arr (make-array (+ len 2))]
+;;             (array-copy arr 0 new-arr 0 len)
+;;             (aset new-arr len key)
+;;             (aset new-arr (inc len) val)
+;;             (set! (.-val added-leaf?) true)
+;;             (HashCollisionNode. nil collision-hash (inc cnt) new-arr))
+;;           (if (= (aget arr idx) val)
+;;             inode
+;;             (HashCollisionNode. nil collision-hash cnt (clone-and-set arr (inc idx) val)))))
+;;       (.inode-assoc (BitmapIndexedNode. nil (bitpos collision-hash shift) (array nil inode))
+;;                     shift hash key val added-leaf?)))
+
+;;   (inode-without [inode shift hash key]
+;;     (let [idx (hash-collision-node-find-index arr cnt key)]
+;;       (cond (== idx -1) inode
+;;             (== cnt 1)  nil
+;;             :else (HashCollisionNode. nil collision-hash (dec cnt) (remove-pair arr (quot idx 2))))))
+
+;;   (inode-lookup [inode shift hash key not-found]
+;;     (let [idx (hash-collision-node-find-index arr cnt key)]
+;;       (cond (< idx 0)              not-found
+;;             (key-test key (aget arr idx)) (aget arr (inc idx))
+;;             :else                  not-found)))
+
+;;   (inode-find [inode shift hash key not-found]
+;;     (let [idx (hash-collision-node-find-index arr cnt key)]
+;;       (cond (< idx 0)              not-found
+;;             (key-test key (aget arr idx)) [(aget arr idx) (aget arr (inc idx))]
+;;             :else                  not-found)))
+
+;;   (inode-seq [inode]
+;;     (create-inode-seq arr))
+
+;;   (ensure-editable [inode e]
+;;     (if (identical? e edit)
+;;       inode
+;;       (let [new-arr (make-array (* 2 (inc cnt)))]
+;;         (array-copy arr 0 new-arr 0 (* 2 cnt))
+;;         (HashCollisionNode. e collision-hash cnt new-arr))))
+
+;;   (ensure-editable-array [inode e count array]
+;;     (if (identical? e edit)
+;;       (do (set! arr array)
+;;           (set! cnt count)
+;;           inode)
+;;       (HashCollisionNode. edit collision-hash count array)))
+
+;;   (inode-assoc! [inode edit shift hash key val added-leaf?]
+;;     (if (== hash collision-hash)
+;;       (let [idx (hash-collision-node-find-index arr cnt key)]
+;;         (if (== idx -1)
+;;           (if (> (alength arr) (* 2 cnt))
+;;             (let [editable (edit-and-set inode edit (* 2 cnt) key (inc (* 2 cnt)) val)]
+;;               (set! (.-val added-leaf?) true)
+;;               (set! (.-cnt editable) (inc (.-cnt editable)))
+;;               editable)
+;;             (let [len     (alength arr)
+;;                   new-arr (make-array (+ len 2))]
+;;               (array-copy arr 0 new-arr 0 len)
+;;               (aset new-arr len key)
+;;               (aset new-arr (inc len) val)
+;;               (set! (.-val added-leaf?) true)
+;;               (.ensure-editable-array inode edit (inc cnt) new-arr)))
+;;           (if (identical? (aget arr (inc idx)) val)
+;;             inode
+;;             (edit-and-set inode edit (inc idx) val))))
+;;       (.inode-assoc! (BitmapIndexedNode. edit (bitpos collision-hash shift) (array nil inode nil nil))
+;;                      edit shift hash key val added-leaf?)))
+
+;;   (inode-without! [inode edit shift hash key removed-leaf?]
+;;     (let [idx (hash-collision-node-find-index arr cnt key)]
+;;       (if (== idx -1)
+;;         inode
+;;         (do (aset removed-leaf? 0 true)
+;;             (if (== cnt 1)
+;;               nil
+;;               (let [editable (.ensure-editable inode edit)
+;;                     earr     (.-arr editable)]
+;;                 (aset earr idx (aget earr (- (* 2 cnt) 2)))
+;;                 (aset earr (inc idx) (aget earr (dec (* 2 cnt))))
+;;                 (aset earr (dec (* 2 cnt)) nil)
+;;                 (aset earr (- (* 2 cnt) 2) nil)
+;;                 (set! (.-cnt editable) (dec (.-cnt editable)))
+;;                 editable))))))
+
+;;   (kv-reduce [inode f init]
+;;     (inode-kv-reduce arr f init)))
+
+;; (deftype NodeSeq [meta nodes i s ^:mutable __hash]
+;;   Object
+;;   (toString [this]
+;;     (pr-str this))
+
+;;   IMeta
+;;   (-meta [coll] meta)
+
+;;   IWithMeta
+;;   (-with-meta [coll meta] (NodeSeq. meta nodes i s __hash))
+
+;;   ICollection
+;;   (-conj [coll o] (cons o coll))
+
+;;   IEmptyableCollection
+;;   (-empty [coll] (with-meta cljs.core.List/EMPTY meta))
+
+;;   ICollection
+;;   (-conj [coll o] (cons o coll))
+
+;;   IEmptyableCollection
+;;   (-empty [coll] (with-meta cljs.core.List/EMPTY meta))
+
+;;   ISequential
+;;   ISeq
+;;   (-first [coll]
+;;     (if (nil? s)
+;;       [(aget nodes i) (aget nodes (inc i))]
+;;       (first s)))
+
+;;   (-rest [coll]
+;;     (if (nil? s)
+;;       (create-inode-seq nodes (+ i 2) nil)
+;;       (create-inode-seq nodes i (next s))))
+
+;;   ISeqable
+;;   (-seq [this] this)
+
+;;   IEquiv
+;;   (-equiv [coll other] (equiv-sequential coll other))
+
+;;   IHash
+;;   (-hash [coll] (caching-hash coll hash-coll __hash)))
+
+;; (defn- create-inode-seq
+;;   ([nodes]
+;;      (create-inode-seq nodes 0 nil))
+;;   ([nodes i s]
+;;      (if (nil? s)
+;;        (let [len (alength nodes)]
+;;          (loop [j i]
+;;            (if (< j len)
+;;              (if-not (nil? (aget nodes j))
+;;                (NodeSeq. nil nodes j nil nil)
+;;                (if-let [node (aget nodes (inc j))]
+;;                  (if-let [node-seq (.inode-seq node)]
+;;                    (NodeSeq. nil nodes (+ j 2) node-seq nil)
+;;                    (recur (+ j 2)))
+;;                  (recur (+ j 2)))))))
+;;        (NodeSeq. nil nodes i s nil))))
+
+;; (deftype ArrayNodeSeq [meta nodes i s ^:mutable __hash]
+;;   Object
+;;   (toString [this]
+;;     (pr-str this))
+
+;;   IMeta
+;;   (-meta [coll] meta)
+
+;;   IWithMeta
+;;   (-with-meta [coll meta] (ArrayNodeSeq. meta nodes i s __hash))
+
+;;   ICollection
+;;   (-conj [coll o] (cons o coll))
+
+;;   IEmptyableCollection
+;;   (-empty [coll] (with-meta cljs.core.List/EMPTY meta))
+
+;;   ICollection
+;;   (-conj [coll o] (cons o coll))
+
+;;   IEmptyableCollection
+;;   (-empty [coll] (with-meta cljs.core.List/EMPTY meta))
+
+;;   ISequential
+;;   ISeq
+;;   (-first [coll] (first s))
+;;   (-rest  [coll] (create-array-node-seq nil nodes i (next s)))
+
+;;   ISeqable
+;;   (-seq [this] this)
+
+;;   IEquiv
+;;   (-equiv [coll other] (equiv-sequential coll other))
+
+;;   IHash
+;;   (-hash [coll] (caching-hash coll hash-coll __hash)))
+
+;; (defn- create-array-node-seq
+;;   ([nodes] (create-array-node-seq nil nodes 0 nil))
+;;   ([meta nodes i s]
+;;      (if (nil? s)
+;;        (let [len (alength nodes)]
+;;          (loop [j i]
+;;            (if (< j len)
+;;              (if-let [nj (aget nodes j)]
+;;                (if-let [ns (.inode-seq nj)]
+;;                  (ArrayNodeSeq. meta nodes (inc j) ns nil)
+;;                  (recur (inc j)))
+;;                (recur (inc j))))))
+;;        (ArrayNodeSeq. meta nodes i s nil))))
+
+;; (declare TransientHashMap)
+
+;; (deftype PersistentHashMap [meta cnt root ^boolean has-nil? nil-val ^:mutable __hash]
+;;   Object
+;;   (toString [this]
+;;     (pr-str this))
+
+;;   IWithMeta
+;;   (-with-meta [coll meta] (PersistentHashMap. meta cnt root has-nil? nil-val __hash))
+
+;;   IMeta
+;;   (-meta [coll] meta)
+
+;;   ICollection
+;;   (-conj [coll entry]
+;;     (if (vector? entry)
+;;       (-assoc coll (-nth entry 0) (-nth entry 1))
+;;       (reduce -conj coll entry)))
+
+;;   IEmptyableCollection
+;;   (-empty [coll] (-with-meta cljs.core.PersistentHashMap/EMPTY meta))
+
+;;   IEquiv
+;;   (-equiv [coll other] (equiv-map coll other))
+
+;;   IHash
+;;   (-hash [coll] (caching-hash coll hash-imap __hash))
+
+;;   ISeqable
+;;   (-seq [coll]
+;;     (when (pos? cnt)
+;;       (let [s (if-not (nil? root) (.inode-seq root))]
+;;         (if has-nil?
+;;           (cons [nil nil-val] s)
+;;           s))))
+
+;;   ICounted
+;;   (-count [coll] cnt)
+
+;;   ILookup
+;;   (-lookup [coll k]
+;;     (-lookup coll k nil))
+
+;;   (-lookup [coll k not-found]
+;;     (cond (nil? k)    (if has-nil?
+;;                         nil-val
+;;                         not-found)
+;;           (nil? root) not-found
+;;           :else       (.inode-lookup root 0 (hash k) k not-found)))
+
+;;   IAssociative
+;;   (-assoc [coll k v]
+;;     (if (nil? k)
+;;       (if (and has-nil? (identical? v nil-val))
+;;         coll
+;;         (PersistentHashMap. meta (if has-nil? cnt (inc cnt)) root true v nil))
+;;       (let [added-leaf? (Box. false)
+;;             new-root    (-> (if (nil? root)
+;;                               cljs.core.BitmapIndexedNode/EMPTY
+;;                               root)
+;;                             (.inode-assoc 0 (hash k) k v added-leaf?))]
+;;         (if (identical? new-root root)
+;;           coll
+;;           (PersistentHashMap. meta (if ^boolean (.-val added-leaf?) (inc cnt) cnt) new-root has-nil? nil-val nil)))))
+
+;;   (-contains-key? [coll k]
+;;     (cond (nil? k)    has-nil?
+;;           (nil? root) false
+;;           :else       (not (identical? (.inode-lookup root 0 (hash k) k lookup-sentinel)
+;;                                        lookup-sentinel))))
+
+;;   IMap
+;;   (-dissoc [coll k]
+;;     (cond (nil? k)    (if has-nil?
+;;                         (PersistentHashMap. meta (dec cnt) root false nil nil)
+;;                         coll)
+;;           (nil? root) coll
+;;           :else
+;;           (let [new-root (.inode-without root 0 (hash k) k)]
+;;             (if (identical? new-root root)
+;;               coll
+;;               (PersistentHashMap. meta (dec cnt) new-root has-nil? nil-val nil)))))
+
+;;   IKVReduce
+;;   (-kv-reduce [coll f init]
+;;     (let [init (if has-nil? (f init nil nil-val) init)]
+;;       (cond
+;;         (reduced? init)          @init
+;;         (not (nil? root)) (.kv-reduce root f init)
+;;         :else                    init)))
+
+;;   IFn
+;;   (-invoke [coll k]
+;;     (-lookup coll k))
+
+;;   (-invoke [coll k not-found]
+;;     (-lookup coll k not-found))
+
+;;   IEditableCollection
+;;   (-as-transient [coll]
+;;     (TransientHashMap. (js-obj) root cnt has-nil? nil-val)))
+
+;; (set! cljs.core.PersistentHashMap/EMPTY (PersistentHashMap. nil 0 nil false nil 0))
+
+;; (set! cljs.core.PersistentHashMap/fromArrays
+;;       (fn [ks vs]
+;;         (let [len (alength ks)]
+;;           (loop [i 0 out (transient cljs.core.PersistentHashMap/EMPTY)]
+;;             (if (< i len)
+;;               (recur (inc i) (assoc! out (aget ks i) (aget vs i)))
+;;               (persistent! out))))))
+
+
+;; (defn- remove-pair [arr i]
+;;   (let [new-arr (make-array (- (alength arr) 2))]
+;;     (array-copy arr 0 new-arr 0 (* 2 i))
+;;     (array-copy arr (* 2 (inc i)) new-arr (* 2 i) (- (alength new-arr) (* 2 i)))
+;;     new-arr))
+
+;; (defn- bitmap-indexed-node-index [bitmap bit]
+;;   (bit-count (bit-and bitmap (dec bit))))
+
+;; (defn- bitpos [hash shift]
+;;   (bit-shift-left 1 (mask hash shift)))
+
+;; (defn- edit-and-set
+;;   ([inode edit i a]
+;;      (let [editable (.ensure-editable inode edit)]
+;;        (aset (.-arr editable) i a)
+;;        editable))
+;;   ([inode edit i a j b]
+;;      (let [editable (.ensure-editable inode edit)]
+;;        (aset (.-arr editable) i a)
+;;        (aset (.-arr editable) j b)
+;;        editable)))
+
+;; (defn- inode-kv-reduce [arr f init]
+;;   (let [len (alength arr)]
+;;     (loop [i 0 init init]
+;;       (if (< i len)
+;;         (let [init (let [k (aget arr i)]
+;;                      (if-not (nil? k)
+;;                        (f init k (aget arr (inc i)))
+;;                        (let [node (aget arr (inc i))]
+;;                          (if-not (nil? node)
+;;                            (.kv-reduce node f init)
+;;                            init))))]
+;;           (if (reduced? init)
+;;             @init
+;;             (recur (+ i 2) init)))
+;;         init))))
+
+;; (declare ArrayNode)
+
+;; (deftype BitmapIndexedNode [edit ^:mutable bitmap ^:mutable arr]
+;;   Object
+;;   (inode-assoc [inode shift hash key val added-leaf?]
+;;     (let [bit (bitpos hash shift)
+;;           idx (bitmap-indexed-node-index bitmap bit)]
+;;       (if (zero? (bit-and bitmap bit))
+;;         (let [n (bit-count bitmap)]
+;;           (if (>= n 16)
+;;             (let [nodes (make-array 32)
+;;                   jdx   (mask hash shift)]
+;;               (aset nodes jdx (.inode-assoc cljs.core.BitmapIndexedNode/EMPTY (+ shift 5) hash key val added-leaf?))
+;;               (loop [i 0 j 0]
+;;                 (if (< i 32)
+;;                   (if (zero? (bit-and (bit-shift-right-zero-fill bitmap i) 1))
+;;                     (recur (inc i) j)
+;;                     (do (aset nodes i
+;;                               (if-not (nil? (aget arr j))
+;;                                 (.inode-assoc cljs.core.BitmapIndexedNode/EMPTY
+;;                                               (+ shift 5) (cljs.core/hash (aget arr j)) (aget arr j) (aget arr (inc j)) added-leaf?)
+;;                                 (aget arr (inc j))))
+;;                         (recur (inc i) (+ j 2))))))
+;;               (ArrayNode. nil (inc n) nodes))
+;;             (let [new-arr (make-array (* 2 (inc n)))]
+;;               (array-copy arr 0 new-arr 0 (* 2 idx))
+;;               (aset new-arr (* 2 idx) key)
+;;               (aset new-arr (inc (* 2 idx)) val)
+;;               (array-copy arr (* 2 idx) new-arr (* 2 (inc idx)) (* 2 (- n idx)))
+;;               (set! (.-val added-leaf?) true)
+;;               (BitmapIndexedNode. nil (bit-or bitmap bit) new-arr))))
+;;         (let [key-or-nil  (aget arr (* 2 idx))
+;;               val-or-node (aget arr (inc (* 2 idx)))]
+;;           (cond (nil? key-or-nil)
+;;                 (let [n (.inode-assoc val-or-node (+ shift 5) hash key val added-leaf?)]
+;;                   (if (identical? n val-or-node)
+;;                     inode
+;;                     (BitmapIndexedNode. nil bitmap (clone-and-set arr (inc (* 2 idx)) n))))
+
+;;                 (key-test key key-or-nil)
+;;                 (if (identical? val val-or-node)
+;;                   inode
+;;                   (BitmapIndexedNode. nil bitmap (clone-and-set arr (inc (* 2 idx)) val)))
+
+;;                 :else
+;;                 (do (set! (.-val added-leaf?) true)
+;;                     (BitmapIndexedNode. nil bitmap
+;;                                         (clone-and-set arr (* 2 idx) nil (inc (* 2 idx))
+;;                                                        (create-node (+ shift 5) key-or-nil val-or-node hash key val)))))))))
+
+;;   (inode-without [inode shift hash key]
+;;     (let [bit (bitpos hash shift)]
+;;       (if (zero? (bit-and bitmap bit))
+;;         inode
+;;         (let [idx         (bitmap-indexed-node-index bitmap bit)
+;;               key-or-nil  (aget arr (* 2 idx))
+;;               val-or-node (aget arr (inc (* 2 idx)))]
+;;           (cond (nil? key-or-nil)
+;;                 (let [n (.inode-without val-or-node (+ shift 5) hash key)]
+;;                   (cond (identical? n val-or-node) inode
+;;                         (not (nil? n)) (BitmapIndexedNode. nil bitmap (clone-and-set arr (inc (* 2 idx)) n))
+;;                         (== bitmap bit) nil
+;;                         :else (BitmapIndexedNode. nil (bit-xor bitmap bit) (remove-pair arr idx))))
+;;                 (key-test key key-or-nil)
+;;                 (BitmapIndexedNode. nil (bit-xor bitmap bit) (remove-pair arr idx))
+;;                 :else inode)))))
+
+;;   (inode-lookup [inode shift hash key not-found]
+;;     (let [bit (bitpos hash shift)]
+;;       (if (zero? (bit-and bitmap bit))
+;;         not-found
+;;         (let [idx         (bitmap-indexed-node-index bitmap bit)
+;;               key-or-nil  (aget arr (* 2 idx))
+;;               val-or-node (aget arr (inc (* 2 idx)))]
+;;           (cond (nil? key-or-nil)  (.inode-lookup val-or-node (+ shift 5) hash key not-found)
+;;                 (key-test key key-or-nil) val-or-node
+;;                 :else not-found)))))
+
+;;   (inode-find [inode shift hash key not-found]
+;;     (let [bit (bitpos hash shift)]
+;;       (if (zero? (bit-and bitmap bit))
+;;         not-found
+;;         (let [idx         (bitmap-indexed-node-index bitmap bit)
+;;               key-or-nil  (aget arr (* 2 idx))
+;;               val-or-node (aget arr (inc (* 2 idx)))]
+;;           (cond (nil? key-or-nil) (.inode-find val-or-node (+ shift 5) hash key not-found)
+;;                 (key-test key key-or-nil)          [key-or-nil val-or-node]
+;;                 :else not-found)))))
+
+;;   (inode-seq [inode]
+;;     (create-inode-seq arr))
+
+;;   (ensure-editable [inode e]
+;;     (if (identical? e edit)
+;;       inode
+;;       (let [n       (bit-count bitmap)
+;;             new-arr (make-array (if (neg? n) 4 (* 2 (inc n))))]
+;;         (array-copy arr 0 new-arr 0 (* 2 n))
+;;         (BitmapIndexedNode. e bitmap new-arr))))
+
+;;   (edit-and-remove-pair [inode e bit i]
+;;     (if (== bitmap bit)
+;;       nil
+;;       (let [editable (.ensure-editable inode e)
+;;             earr     (.-arr editable)
+;;             len      (alength earr)]
+;;         (set! (.-bitmap editable) (bit-xor bit (.-bitmap editable)))
+;;         (array-copy earr (* 2 (inc i))
+;;                     earr (* 2 i)
+;;                     (- len (* 2 (inc i))))
+;;         (aset earr (- len 2) nil)
+;;         (aset earr (dec len) nil)
+;;         editable)))
+
+;;   (inode-assoc! [inode edit shift hash key val added-leaf?]
+;;     (let [bit (bitpos hash shift)
+;;           idx (bitmap-indexed-node-index bitmap bit)]
+;;       (if (zero? (bit-and bitmap bit))
+;;         (let [n (bit-count bitmap)]
+;;           (cond
+;;             (< (* 2 n) (alength arr))
+;;             (let [editable (.ensure-editable inode edit)
+;;                   earr     (.-arr editable)]
+;;               (set! (.-val added-leaf?) true)
+;;               (array-copy-downward earr (* 2 idx)
+;;                                    earr (* 2 (inc idx))
+;;                                    (* 2 (- n idx)))
+;;               (aset earr (* 2 idx) key)
+;;               (aset earr (inc (* 2 idx)) val)
+;;               (set! (.-bitmap editable) (bit-or (.-bitmap editable) bit))
+;;               editable)
+
+;;             (>= n 16)
+;;             (let [nodes (make-array 32)
+;;                   jdx   (mask hash shift)]
+;;               (aset nodes jdx (.inode-assoc! cljs.core.BitmapIndexedNode/EMPTY edit (+ shift 5) hash key val added-leaf?))
+;;               (loop [i 0 j 0]
+;;                 (if (< i 32)
+;;                   (if (zero? (bit-and (bit-shift-right-zero-fill bitmap i) 1))
+;;                     (recur (inc i) j)
+;;                     (do (aset nodes i
+;;                               (if-not (nil? (aget arr j))
+;;                                 (.inode-assoc! cljs.core.BitmapIndexedNode/EMPTY
+;;                                                edit (+ shift 5) (cljs.core/hash (aget arr j)) (aget arr j) (aget arr (inc j)) added-leaf?)
+;;                                 (aget arr (inc j))))
+;;                         (recur (inc i) (+ j 2))))))
+;;               (ArrayNode. edit (inc n) nodes))
+
+;;             :else
+;;             (let [new-arr (make-array (* 2 (+ n 4)))]
+;;               (array-copy arr 0 new-arr 0 (* 2 idx))
+;;               (aset new-arr (* 2 idx) key)
+;;               (aset new-arr (inc (* 2 idx)) val)
+;;               (array-copy arr (* 2 idx) new-arr (* 2 (inc idx)) (* 2 (- n idx)))
+;;               (set! (.-val added-leaf?) true)
+;;               (let [editable (.ensure-editable inode edit)]
+;;                 (set! (.-arr editable) new-arr)
+;;                 (set! (.-bitmap editable) (bit-or (.-bitmap editable) bit))
+;;                 editable))))
+;;         (let [key-or-nil  (aget arr (* 2 idx))
+;;               val-or-node (aget arr (inc (* 2 idx)))]
+;;           (cond (nil? key-or-nil)
+;;                 (let [n (.inode-assoc! val-or-node edit (+ shift 5) hash key val added-leaf?)]
+;;                   (if (identical? n val-or-node)
+;;                     inode
+;;                     (edit-and-set inode edit (inc (* 2 idx)) n)))
+
+;;                 (key-test key key-or-nil)
+;;                 (if (identical? val val-or-node)
+;;                   inode
+;;                   (edit-and-set inode edit (inc (* 2 idx)) val))
+
+;;                 :else
+;;                 (do (set! (.-val added-leaf?) true)
+;;                     (edit-and-set inode edit (* 2 idx) nil (inc (* 2 idx))
+;;                                   (create-node edit (+ shift 5) key-or-nil val-or-node hash key val))))))))
+
+;;   (inode-without! [inode edit shift hash key removed-leaf?]
+;;     (let [bit (bitpos hash shift)]
+;;       (if (zero? (bit-and bitmap bit))
+;;         inode
+;;         (let [idx         (bitmap-indexed-node-index bitmap bit)
+;;               key-or-nil  (aget arr (* 2 idx))
+;;               val-or-node (aget arr (inc (* 2 idx)))]
+;;           (cond (nil? key-or-nil)
+;;                 (let [n (.inode-without! val-or-node edit (+ shift 5) hash key removed-leaf?)]
+;;                   (cond (identical? n val-or-node) inode
+;;                         (not (nil? n)) (edit-and-set inode edit (inc (* 2 idx)) n)
+;;                         (== bitmap bit) nil
+;;                         :else (.edit-and-remove-pair inode edit bit idx)))
+;;                 (key-test key key-or-nil)
+;;                 (do (aset removed-leaf? 0 true)
+;;                     (.edit-and-remove-pair inode edit bit idx))
+;;                 :else inode)))))
+
+;;   (kv-reduce [inode f init]
+;;     (inode-kv-reduce arr f init)))
+
+;; (set! cljs.core.BitmapIndexedNode/EMPTY (BitmapIndexedNode. nil 0 (make-array 0)))
+
+;; (defn- pack-array-node [array-node edit idx]
+;;   (let [arr     (.-arr array-node)
+;;         len     (* 2 (dec (.-cnt array-node)))
+;;         new-arr (make-array len)]
+;;     (loop [i 0 j 1 bitmap 0]
+;;       (if (< i len)
+;;         (if (and (not (== i idx))
+;;                  (not (nil? (aget arr i))))
+;;           (do (aset new-arr j (aget arr i))
+;;               (recur (inc i) (+ j 2) (bit-or bitmap (bit-shift-left 1 i))))
+;;           (recur (inc i) j bitmap))
+;;         (BitmapIndexedNode. edit bitmap new-arr)))))
+
+;; (deftype ArrayNode [edit ^:mutable cnt ^:mutable arr]
+;;   Object
+;;   (inode-assoc [inode shift hash key val added-leaf?]
+;;     (let [idx  (mask hash shift)
+;;           node (aget arr idx)]
+;;       (if (nil? node)
+;;         (ArrayNode. nil (inc cnt) (clone-and-set arr idx (.inode-assoc cljs.core.BitmapIndexedNode/EMPTY (+ shift 5) hash key val added-leaf?)))
+;;         (let [n (.inode-assoc node (+ shift 5) hash key val added-leaf?)]
+;;           (if (identical? n node)
+;;             inode
+;;             (ArrayNode. nil cnt (clone-and-set arr idx n)))))))
+
+;;   (inode-without [inode shift hash key]
+;;     (let [idx  (mask hash shift)
+;;           node (aget arr idx)]
+;;       (if-not (nil? node)
+;;         (let [n (.inode-without node (+ shift 5) hash key)]
+;;           (cond
+;;             (identical? n node)
+;;             inode
+
+;;             (nil? n)
+;;             (if (<= cnt 8)
+;;               (pack-array-node inode nil idx)
+;;               (ArrayNode. nil (dec cnt) (clone-and-set arr idx n)))
+
+;;             :else
+;;             (ArrayNode. nil cnt (clone-and-set arr idx n))))
+;;         inode)))
+
+;;   (inode-lookup [inode shift hash key not-found]
+;;     (let [idx  (mask hash shift)
+;;           node (aget arr idx)]
+;;       (if-not (nil? node)
+;;         (.inode-lookup node (+ shift 5) hash key not-found)
+;;         not-found)))
+
+;;   (inode-find [inode shift hash key not-found]
+;;     (let [idx  (mask hash shift)
+;;           node (aget arr idx)]
+;;       (if-not (nil? node)
+;;         (.inode-find node (+ shift 5) hash key not-found)
+;;         not-found)))
+
+;;   (inode-seq [inode]
+;;     (create-array-node-seq arr))
+
+;;   (ensure-editable [inode e]
+;;     (if (identical? e edit)
+;;       inode
+;;       (ArrayNode. e cnt (aclone arr))))
+
+;;   (inode-assoc! [inode edit shift hash key val added-leaf?]
+;;     (let [idx  (mask hash shift)
+;;           node (aget arr idx)]
+;;       (if (nil? node)
+;;         (let [editable (edit-and-set inode edit idx (.inode-assoc! cljs.core.BitmapIndexedNode/EMPTY edit (+ shift 5) hash key val added-leaf?))]
+;;           (set! (.-cnt editable) (inc (.-cnt editable)))
+;;           editable)
+;;         (let [n (.inode-assoc! node edit (+ shift 5) hash key val added-leaf?)]
+;;           (if (identical? n node)
+;;             inode
+;;             (edit-and-set inode edit idx n))))))
+
+;;   (inode-without! [inode edit shift hash key removed-leaf?]
+;;     (let [idx  (mask hash shift)
+;;           node (aget arr idx)]
+;;       (if (nil? node)
+;;         inode
+;;         (let [n (.inode-without! node edit (+ shift 5) hash key removed-leaf?)]
+;;           (cond
+;;             (identical? n node)
+;;             inode
+
+;;             (nil? n)
+;;             (if (<= cnt 8)
+;;               (pack-array-node inode edit idx)
+;;               (let [editable (edit-and-set inode edit idx n)]
+;;                 (set! (.-cnt editable) (dec (.-cnt editable)))
+;;                 editable))
+
+;;             :else
+;;             (edit-and-set inode edit idx n))))))
+
+;;   (kv-reduce [inode f init]
+;;     (let [len (alength arr)]           ; actually 32
+;;       (loop [i 0 init init]
+;;         (if (< i len)
+;;           (let [node (aget arr i)]
+;;             (if-not (nil? node)
+;;               (let [init (.kv-reduce node f init)]
+;;                 (if (reduced? init)
+;;                   @init
+;;                   (recur (inc i) init)))))
+;;           init)))))
+
+;; (defn- hash-collision-node-find-index [arr cnt key]
+;;   (let [lim (* 2 cnt)]
+;;     (loop [i 0]
+;;       (if (< i lim)
+;;         (if (key-test key (aget arr i))
+;;           i
+;;           (recur (+ i 2)))
+;;         -1))))
+
+;; (deftype HashCollisionNode [edit
+;;                             ^:mutable collision-hash
+;;                             ^:mutable cnt
+;;                             ^:mutable arr]
+;;   Object
+;;   (inode-assoc [inode shift hash key val added-leaf?]
+;;     (if (== hash collision-hash)
+;;       (let [idx (hash-collision-node-find-index arr cnt key)]
+;;         (if (== idx -1)
+;;           (let [len (alength arr)
+;;                 new-arr (make-array (+ len 2))]
+;;             (array-copy arr 0 new-arr 0 len)
+;;             (aset new-arr len key)
+;;             (aset new-arr (inc len) val)
+;;             (set! (.-val added-leaf?) true)
+;;             (HashCollisionNode. nil collision-hash (inc cnt) new-arr))
+;;           (if (= (aget arr idx) val)
+;;             inode
+;;             (HashCollisionNode. nil collision-hash cnt (clone-and-set arr (inc idx) val)))))
+;;       (.inode-assoc (BitmapIndexedNode. nil (bitpos collision-hash shift) (array nil inode))
+;;                     shift hash key val added-leaf?)))
+
+;;   (inode-without [inode shift hash key]
+;;     (let [idx (hash-collision-node-find-index arr cnt key)]
+;;       (cond (== idx -1) inode
+;;             (== cnt 1)  nil
+;;             :else (HashCollisionNode. nil collision-hash (dec cnt) (remove-pair arr (quot idx 2))))))
+
+;;   (inode-lookup [inode shift hash key not-found]
+;;     (let [idx (hash-collision-node-find-index arr cnt key)]
+;;       (cond (< idx 0)              not-found
+;;             (key-test key (aget arr idx)) (aget arr (inc idx))
+;;             :else                  not-found)))
+
+;;   (inode-find [inode shift hash key not-found]
+;;     (let [idx (hash-collision-node-find-index arr cnt key)]
+;;       (cond (< idx 0)              not-found
+;;             (key-test key (aget arr idx)) [(aget arr idx) (aget arr (inc idx))]
+;;             :else                  not-found)))
+
+;;   (inode-seq [inode]
+;;     (create-inode-seq arr))
+
+;;   (ensure-editable [inode e]
+;;     (if (identical? e edit)
+;;       inode
+;;       (let [new-arr (make-array (* 2 (inc cnt)))]
+;;         (array-copy arr 0 new-arr 0 (* 2 cnt))
+;;         (HashCollisionNode. e collision-hash cnt new-arr))))
+
+;;   (ensure-editable-array [inode e count array]
+;;     (if (identical? e edit)
+;;       (do (set! arr array)
+;;           (set! cnt count)
+;;           inode)
+;;       (HashCollisionNode. edit collision-hash count array)))
+
+;;   (inode-assoc! [inode edit shift hash key val added-leaf?]
+;;     (if (== hash collision-hash)
+;;       (let [idx (hash-collision-node-find-index arr cnt key)]
+;;         (if (== idx -1)
+;;           (if (> (alength arr) (* 2 cnt))
+;;             (let [editable (edit-and-set inode edit (* 2 cnt) key (inc (* 2 cnt)) val)]
+;;               (set! (.-val added-leaf?) true)
+;;               (set! (.-cnt editable) (inc (.-cnt editable)))
+;;               editable)
+;;             (let [len     (alength arr)
+;;                   new-arr (make-array (+ len 2))]
+;;               (array-copy arr 0 new-arr 0 len)
+;;               (aset new-arr len key)
+;;               (aset new-arr (inc len) val)
+;;               (set! (.-val added-leaf?) true)
+;;               (.ensure-editable-array inode edit (inc cnt) new-arr)))
+;;           (if (identical? (aget arr (inc idx)) val)
+;;             inode
+;;             (edit-and-set inode edit (inc idx) val))))
+;;       (.inode-assoc! (BitmapIndexedNode. edit (bitpos collision-hash shift) (array nil inode nil nil))
+;;                      edit shift hash key val added-leaf?)))
+
+;;   (inode-without! [inode edit shift hash key removed-leaf?]
+;;     (let [idx (hash-collision-node-find-index arr cnt key)]
+;;       (if (== idx -1)
+;;         inode
+;;         (do (aset removed-leaf? 0 true)
+;;             (if (== cnt 1)
+;;               nil
+;;               (let [editable (.ensure-editable inode edit)
+;;                     earr     (.-arr editable)]
+;;                 (aset earr idx (aget earr (- (* 2 cnt) 2)))
+;;                 (aset earr (inc idx) (aget earr (dec (* 2 cnt))))
+;;                 (aset earr (dec (* 2 cnt)) nil)
+;;                 (aset earr (- (* 2 cnt) 2) nil)
+;;                 (set! (.-cnt editable) (dec (.-cnt editable)))
+;;                 editable))))))
+
+;;   (kv-reduce [inode f init]
+;;     (inode-kv-reduce arr f init)))
+
+;; (defn- create-node
+;;   ([shift key1 val1 key2hash key2 val2]
+;;      (let [key1hash (hash key1)]
+;;        (if (== key1hash key2hash)
+;;          (HashCollisionNode. nil key1hash 2 (array key1 val1 key2 val2))
+;;          (let [added-leaf? (Box. false)]
+;;            (-> cljs.core.BitmapIndexedNode/EMPTY
+;;                (.inode-assoc shift key1hash key1 val1 added-leaf?)
+;;                (.inode-assoc shift key2hash key2 val2 added-leaf?))))))
+;;   ([edit shift key1 val1 key2hash key2 val2]
+;;      (let [key1hash (hash key1)]
+;;        (if (== key1hash key2hash)
+;;          (HashCollisionNode. nil key1hash 2 (array key1 val1 key2 val2))
+;;          (let [added-leaf? (Box. false)]
+;;            (-> cljs.core.BitmapIndexedNode/EMPTY
+;;                (.inode-assoc! edit shift key1hash key1 val1 added-leaf?)
+;;                (.inode-assoc! edit shift key2hash key2 val2 added-leaf?)))))))
+
+;; (deftype NodeSeq [meta nodes i s ^:mutable __hash]
+;;   Object
+;;   (toString [this]
+;;     (pr-str this))
+
+;;   IMeta
+;;   (-meta [coll] meta)
+
+;;   IWithMeta
+;;   (-with-meta [coll meta] (NodeSeq. meta nodes i s __hash))
+
+;;   ICollection
+;;   (-conj [coll o] (cons o coll))
+
+;;   IEmptyableCollection
+;;   (-empty [coll] (with-meta cljs.core.List/EMPTY meta))
+
+;;   ICollection
+;;   (-conj [coll o] (cons o coll))
+
+;;   IEmptyableCollection
+;;   (-empty [coll] (with-meta cljs.core.List/EMPTY meta))
+
+;;   ISequential
+;;   ISeq
+;;   (-first [coll]
+;;     (if (nil? s)
+;;       [(aget nodes i) (aget nodes (inc i))]
+;;       (first s)))
+
+;;   (-rest [coll]
+;;     (if (nil? s)
+;;       (create-inode-seq nodes (+ i 2) nil)
+;;       (create-inode-seq nodes i (next s))))
+
+;;   ISeqable
+;;   (-seq [this] this)
+
+;;   IEquiv
+;;   (-equiv [coll other] (equiv-sequential coll other))
+
+;;   IHash
+;;   (-hash [coll] (caching-hash coll hash-coll __hash)))
+
+;; (defn- create-inode-seq
+;;   ([nodes]
+;;      (create-inode-seq nodes 0 nil))
+;;   ([nodes i s]
+;;      (if (nil? s)
+;;        (let [len (alength nodes)]
+;;          (loop [j i]
+;;            (if (< j len)
+;;              (if-not (nil? (aget nodes j))
+;;                (NodeSeq. nil nodes j nil nil)
+;;                (if-let [node (aget nodes (inc j))]
+;;                  (if-let [node-seq (.inode-seq node)]
+;;                    (NodeSeq. nil nodes (+ j 2) node-seq nil)
+;;                    (recur (+ j 2)))
+;;                  (recur (+ j 2)))))))
+;;        (NodeSeq. nil nodes i s nil))))
+
+;; (deftype ArrayNodeSeq [meta nodes i s ^:mutable __hash]
+;;   Object
+;;   (toString [this]
+;;     (pr-str this))
+
+;;   IMeta
+;;   (-meta [coll] meta)
+
+;;   IWithMeta
+;;   (-with-meta [coll meta] (ArrayNodeSeq. meta nodes i s __hash))
+
+;;   ICollection
+;;   (-conj [coll o] (cons o coll))
+
+;;   IEmptyableCollection
+;;   (-empty [coll] (with-meta cljs.core.List/EMPTY meta))
+
+;;   ICollection
+;;   (-conj [coll o] (cons o coll))
+
+;;   IEmptyableCollection
+;;   (-empty [coll] (with-meta cljs.core.List/EMPTY meta))
+
+;;   ISequential
+;;   ISeq
+;;   (-first [coll] (first s))
+;;   (-rest  [coll] (create-array-node-seq nil nodes i (next s)))
+
+;;   ISeqable
+;;   (-seq [this] this)
+
+;;   IEquiv
+;;   (-equiv [coll other] (equiv-sequential coll other))
+
+;;   IHash
+;;   (-hash [coll] (caching-hash coll hash-coll __hash)))
+
+;; (defn- create-array-node-seq
+;;   ([nodes] (create-array-node-seq nil nodes 0 nil))
+;;   ([meta nodes i s]
+;;      (if (nil? s)
+;;        (let [len (alength nodes)]
+;;          (loop [j i]
+;;            (if (< j len)
+;;              (if-let [nj (aget nodes j)]
+;;                (if-let [ns (.inode-seq nj)]
+;;                  (ArrayNodeSeq. meta nodes (inc j) ns nil)
+;;                  (recur (inc j)))
+;;                (recur (inc j))))))
+;;        (ArrayNodeSeq. meta nodes i s nil))))
+
+;; (declare TransientHashMap)
+
+;; (deftype PersistentHashMap [meta cnt root ^boolean has-nil? nil-val ^:mutable __hash]
+;;   Object
+;;   (toString [this]
+;;     (pr-str this))
+
+;;   IWithMeta
+;;   (-with-meta [coll meta] (PersistentHashMap. meta cnt root has-nil? nil-val __hash))
+
+;;   IMeta
+;;   (-meta [coll] meta)
+
+;;   ICollection
+;;   (-conj [coll entry]
+;;     (if (vector? entry)
+;;       (-assoc coll (-nth entry 0) (-nth entry 1))
+;;       (reduce -conj coll entry)))
+
+;;   IEmptyableCollection
+;;   (-empty [coll] (-with-meta cljs.core.PersistentHashMap/EMPTY meta))
+
+;;   IEquiv
+;;   (-equiv [coll other] (equiv-map coll other))
+
+;;   IHash
+;;   (-hash [coll] (caching-hash coll hash-imap __hash))
+
+;;   ISeqable
+;;   (-seq [coll]
+;;     (when (pos? cnt)
+;;       (let [s (if-not (nil? root) (.inode-seq root))]
+;;         (if has-nil?
+;;           (cons [nil nil-val] s)
+;;           s))))
+
+;;   ICounted
+;;   (-count [coll] cnt)
+
+;;   ILookup
+;;   (-lookup [coll k]
+;;     (-lookup coll k nil))
+
+;;   (-lookup [coll k not-found]
+;;     (cond (nil? k)    (if has-nil?
+;;                         nil-val
+;;                         not-found)
+;;           (nil? root) not-found
+;;           :else       (.inode-lookup root 0 (hash k) k not-found)))
+
+;;   IAssociative
+;;   (-assoc [coll k v]
+;;     (if (nil? k)
+;;       (if (and has-nil? (identical? v nil-val))
+;;         coll
+;;         (PersistentHashMap. meta (if has-nil? cnt (inc cnt)) root true v nil))
+;;       (let [added-leaf? (Box. false)
+;;             new-root    (-> (if (nil? root)
+;;                               cljs.core.BitmapIndexedNode/EMPTY
+;;                               root)
+;;                             (.inode-assoc 0 (hash k) k v added-leaf?))]
+;;         (if (identical? new-root root)
+;;           coll
+;;           (PersistentHashMap. meta (if ^boolean (.-val added-leaf?) (inc cnt) cnt) new-root has-nil? nil-val nil)))))
+
+;;   (-contains-key? [coll k]
+;;     (cond (nil? k)    has-nil?
+;;           (nil? root) false
+;;           :else       (not (identical? (.inode-lookup root 0 (hash k) k lookup-sentinel)
+;;                                        lookup-sentinel))))
+
+;;   IMap
+;;   (-dissoc [coll k]
+;;     (cond (nil? k)    (if has-nil?
+;;                         (PersistentHashMap. meta (dec cnt) root false nil nil)
+;;                         coll)
+;;           (nil? root) coll
+;;           :else
+;;           (let [new-root (.inode-without root 0 (hash k) k)]
+;;             (if (identical? new-root root)
+;;               coll
+;;               (PersistentHashMap. meta (dec cnt) new-root has-nil? nil-val nil)))))
+
+;;   IKVReduce
+;;   (-kv-reduce [coll f init]
+;;     (let [init (if has-nil? (f init nil nil-val) init)]
+;;       (cond
+;;         (reduced? init)          @init
+;;         (not (nil? root)) (.kv-reduce root f init)
+;;         :else                    init)))
+
+;;   IFn
+;;   (-invoke [coll k]
+;;     (-lookup coll k))
+
+;;   (-invoke [coll k not-found]
+;;     (-lookup coll k not-found))
+
+;;   IEditableCollection
+;;   (-as-transient [coll]
+;;     (TransientHashMap. (js-obj) root cnt has-nil? nil-val)))
+
+;; (set! cljs.core.PersistentHashMap/EMPTY (PersistentHashMap. nil 0 nil false nil 0))
+
+;; (set! cljs.core.PersistentHashMap/fromArrays
+;;       (fn [ks vs]
+;;         (let [len (alength ks)]
+;;           (loop [i 0 out (transient cljs.core.PersistentHashMap/EMPTY)]
+;;             (if (< i len)
+;;               (recur (inc i) (assoc! out (aget ks i) (aget vs i)))
+;;               (persistent! out))))))