1 files changed, 123 insertions, 0 deletions
diff --git a/crdt/src/vector_clock.rs b/crdt/src/vector_clock.rs
new file mode 100644
index 0000000..e80180f
--- /dev/null
+++ b/crdt/src/vector_clock.rs
@@ -0,0 +1,123 @@
+use std::{
+    cmp::Ordering,
+    collections::{HashMap, HashSet},
+};
+
+use uuid::Uuid;
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct VectorClock(HashMap<Uuid, u64>);
+
+impl VectorClock {
+    pub fn new() -> Self {
+        Self(HashMap::new())
+    }
+
+    pub fn get(&self, actor_id: &Uuid) -> u64 {
+        self.0.get(actor_id).unwrap_or(&0).clone()
+    }
+
+    pub fn inc(&self, actor_id: &Uuid) -> Self {
+        let mut m = self.0.clone();
+        m.insert(actor_id.clone(), self.get(actor_id) + 1);
+        VectorClock(m)
+    }
+}
+
+impl PartialOrd for VectorClock {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        let orderings: HashSet<_> = self
+            .0
+            .keys()
+            .chain(other.0.keys())
+            .collect::<HashSet<_>>()
+            .into_iter()
+            .map(|actor_id| self.get(actor_id).cmp(&other.get(actor_id)))
+            .collect();
+
+        let less = orderings.contains(&Ordering::Less);
+        let greater = orderings.contains(&Ordering::Greater);
+
+        match (less, greater) {
+            (true, true) => {
+                let mut actors: Vec<_> = self.0.keys().collect();
+                actors.sort();
+
+                let mut other_actors: Vec<_> = other.0.keys().collect();
+                other_actors.sort();
+
+                Some(actors.cmp(&other_actors))
+            }
+            (true, false) => Some(Ordering::Less),
+            (false, true) => Some(Ordering::Greater),
+            (false, false) => Some(Ordering::Equal),
+        }
+    }
+}
+
+impl Ord for VectorClock {
+    fn cmp(&self, other: &Self) -> Ordering {
+        self.partial_cmp(other).unwrap()
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn vector_clock_compare() {
+        let alice_id = Uuid::now_v7();
+        let bob_id = Uuid::now_v7();
+        let carol_id = Uuid::now_v7();
+
+        assert!(alice_id < bob_id);
+        assert!(bob_id < carol_id);
+
+        let mut alice = VectorClock::new();
+        let mut bob = VectorClock::new();
+
+        assert!(alice == bob);
+        assert!(bob == alice);
+
+        bob = bob.inc(&bob_id);
+
+        assert!(alice < bob);
+        assert!(bob > alice);
+
+        alice = alice.inc(&alice_id);
+
+        assert!(alice < bob);
+        assert!(bob > alice);
+
+        alice = alice.inc(&bob_id);
+        bob = bob.inc(&alice_id);
+
+        assert!(alice == bob);
+
+        alice = alice.inc(&alice_id);
+
+        assert!(alice > bob);
+        assert!(bob < alice);
+
+        bob = bob.inc(&alice_id);
+
+        assert!(alice == bob);
+
+        alice = alice.inc(&carol_id);
+
+        assert!(alice > bob);
+        assert!(bob < alice);
+
+        bob = bob.inc(&bob_id);
+
+        assert!(alice > bob);
+        assert!(bob < alice);
+
+        let clock_a = VectorClock::new().inc(&alice_id).inc(&carol_id);
+        let clock_b = VectorClock::new().inc(&bob_id).inc(&carol_id);
+
+        assert!(clock_a < clock_b);
+        assert!(clock_b > clock_a);
+    }
+}