diff-phm.cljs

(defprotocol IDiff
        (diffable? [a b])
        (diff-data [a b]))

      (extend-type BitmapIndexedNode
        Object
        (inode-vals [a coll]
                    (reduce (fn [coll i]
                              (let [k (aget (.-arr a) (* 2 i))
                                    v (aget (.-arr a) (inc (* 2 i)))]
                                (if (nil? k)
                                  (if v (.inode-vals v coll) coll)
                                  (assoc coll k v))))
                            coll (range 16)))

        (get-item-by-idx [this idx]
                         (let [bit (bit-shift-left 1 idx)]
                           (if (zero? (bit-and (.-bitmap this) bit))
                             nil
                             (let [idx (* (bitmap-indexed-node-index (.-bitmap this) bit) 2)]
                               (aget (.-arr this) (inc idx))))))

        (get-key-by-idx [this idx]
                        (let [bit (bit-shift-left 1 idx)
                              idx (* (bitmap-indexed-node-index (.-bitmap this) bit) 2)
                              ]
                          (aget (.-arr this) idx)))
        (node? [this idx]
               (let [bit (bit-shift-left 1 idx)
                     idx (* (bitmap-indexed-node-index (.-bitmap this) bit) 2)
                     ]
                 (nil? (aget (.-arr this) idx)))))

      (extend-type ArrayNode
        Object
        (inode-vals [a coll]
                    (reduce (fn [coll i]
                              (if-let [v (aget (.-arr a) i)]
                                (.inode-vals v coll)
                                coll))
                            coll (range 32)))

        (get-item-by-idx [this idx]
                         (aget (.-arr this) idx))


        (get-key-by-idx [this idx]
                        nil)


        (node? [this idx]
               (if (aget (.-arr this) idx) true false)))

      (extend-type HashCollisionNode
        Object
        (inode-vals [a coll]
                    (reduce (fn [coll i]
                              (let [k (aget (.-arr a) (* 2 i))
                                    v (aget (.-arr a) (inc (* 2 i)))]
                                (assoc coll k v)))
                            coll (range (.-cnt a))))

        (get-item-by-idx [this idx]
                         this)


        (get-key-by-idx [this idx]
                        nil)


        (node? [this idx]
               true))


      (defn inode-diff [a b edits shift]


        (cond (identical? a b)
              edits
              :else

              (reduce (fn [edits i]
                        (let [av (.get-item-by-idx a i)
                              bv (.get-item-by-idx b i)]

                          (cond (and (nil? av) (nil? bv))
                                edits

                                (nil? av)
                                (let [node-or-val bv
                                      k (.get-key-by-idx b i)]
                                  (if (.node? b i)
                                    (update edits :b merge (.inode-vals node-or-val {}))
                                    (assoc-in edits [:b k] node-or-val)))

                                (nil? bv)
                                (let [node-or-val av
                                      k (.get-key-by-idx a i)]
                                  (if (.node? a i)
                                    (update edits :a merge (.inode-vals node-or-val {}))
                                    (assoc-in edits [:a k] node-or-val)))

                                :else
                                (let [ak (.get-key-by-idx a i)
                                      bk (.get-key-by-idx b i)]
                                  (if (identical? av bv)
                                    edits
                                    (cond (or (instance? cljs.core.HashCollisionNode a)
                                              (instance? cljs.core.HashCollisionNode b))
                                          (-> edits
                                              (update-in [:a] merge (.inode-vals a {}))
                                              (update-in [:b] merge (.inode-vals b {})))

                                          (and (.node? a i) (.node? b i))
                                          (inode-diff av bv edits (+ shift 5))

                                          (and (.node? a i) (not (nil? bk)))
                                          (inode-diff av (.inode-assoc (.-EMPTY BitmapIndexedNode)
                                                                       (+ shift 5) (cljs.core/hash bk) bk bv false)
                                                      edits (+ shift 5))

                                          (and (.node? b i) (not (nil? ak)))
                                          (inode-diff (.inode-assoc (.-EMPTY BitmapIndexedNode)
                                                                    (+ shift 5) (cljs.core/hash ak) ak av false)
                                                      bv
                                                      edits (+ shift 5))

                                          (and (not (nil? ak)) (not (nil? bk)))
                                          (-> (assoc-in edits [:a ak] av)
                                              (assoc-in [:b bk] bv))))))))
                      edits (range 0 32))))


      (extend-type PersistentHashMap
        IDiff
        (diffable? [a b]
                   (instance? PersistentHashMap b))
        (diff-data [a b]
              (let [{:keys [a b] :as d} (inode-diff (.-root a) (.-root b) {:a {} :b {}} 0)]
                (reduce (fn [edits k]
                          (if (and (contains? a k) (contains? b k)
                                   (identical? (get a k) (get b k)))
                            (-> edits
                                (dissoc-in [:a k])
                                (dissoc-in [:b k]))
                            edits))
                        d (set/union (into #{} (keys a)) (into #{} (keys b)))))))

test.txt

=> (def m1 (zipmap (range 10000) (range 10000)))

=> (time (diff-data m1 (assoc m1 42 :a)))
"Elapsed time: 0.165000 msecs"
{:a {42 42}, :b {42 :a}}


=> (butlast (time (clojure.data/diff m1 (assoc m1 42 :a))))
"Elapsed time: 251.515000 msecs"
({42 42} {42 :a})