Skip to content

Instantly share code, notes, and snippets.

@reiddraper
Created November 25, 2011 19:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save reiddraper/2c9e46d5bd26f0779a48 to your computer and use it in GitHub Desktop.
Save reiddraper/2c9e46d5bd26f0779a48 to your computer and use it in GitHub Desktop.
(ns knockbox.sets.lww
"This is an implementation of
a state-based last-write-wins set.
`add` and `remove` operations have associated
timestamps that are used to resolve conflicts"
(:require clojure.stacktrace)
(:import (clojure.lang IPersistentSet IPersistentMap
IFn IObj RT)
(java.util Set)))
(defn- minus-deletes
"Remove deletes with
earlier timestamps
than adds"
[adds dels]
(let [favor-deletes (fn [add delete] (if (>= delete add) nil add))
no-deletes (merge-with favor-deletes
adds
(select-keys dels (keys adds)))
no-nil (fn [a] (not= (get a 1) nil))]
(map #(get % 0)
(filter no-nil no-deletes))))
(deftype LWW [^IPersistentMap adds
^IPersistentMap dels]
IPersistentSet
(disjoin [this k]
(let [now (System/nanoTime)]
(LWW. adds
(assoc dels k now))))
(cons [this k]
(let [now (System/nanoTime)]
(LWW.
(assoc adds k now)
dels)))
(empty [this]
(LWW. {} {}))
(equiv [this other]
(.equals this other))
(get [this k]
(if (> (get adds k) (get dels k))
k
nil))
(seq [this]
(keys
(minus-deletes adds dels)))
(count [this]
(count (seq this)))
IObj
(meta [this]
(.meta ^IObj adds))
(withMeta [this m]
(LWW. (.withMeta ^IObj adds m)
dels))
Object
(hashCode [this]
(hash (set (seq this))))
(equals [this other]
(or (identical? this other)
(and (instance? Set other)
(let [^Set o (cast Set other)]
(and (= (count this) (count o))
(every? #(contains? % o) (seq this)))))))
(toString [this]
"an string")
Set
(contains [this k]
(boolean (get this k)))
(containsAll [this ks]
(every? identity (map #(contains? this %) ks)))
(size [this]
(count this))
(isEmpty [this]
(= 0 (count this)))
(toArray [this]
(RT/seqToArray (seq this)))
(toArray [this dest]
(reduce (fn [idx item]
(aset dest idx item)
(inc idx))
0, (seq this))
dest))
(defn lww [] (LWW. {} {}))
(require '(knockbox.sets [lww]) :reload)
(def a (knockbox.sets.lww/lww))
(conj a :foo)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment