summaryrefslogtreecommitdiff
path: root/crdt/src/vector_clock.rs
diff options
context:
space:
mode:
authorJosh Kingsley <josh@joshkingsley.me>2025-11-23 19:27:57 +0200
committerJosh Kingsley <josh@joshkingsley.me>2025-11-23 19:27:57 +0200
commit602145c956bb594ca0d0e10601cc4ad1a71cf70d (patch)
treed9f9980bd2054cff5819d01379f5c1c55f8eb66d /crdt/src/vector_clock.rs
parentc2a6efb1b761014a90d90373cad47a14054af40b (diff)
feat: integrate web and doc packages
Diffstat (limited to 'crdt/src/vector_clock.rs')
-rw-r--r--crdt/src/vector_clock.rs156
1 files changed, 0 insertions, 156 deletions
diff --git a/crdt/src/vector_clock.rs b/crdt/src/vector_clock.rs
deleted file mode 100644
index f6ded56..0000000
--- a/crdt/src/vector_clock.rs
+++ /dev/null
@@ -1,156 +0,0 @@
-use std::{
- cmp::Ordering,
- collections::{HashMap, HashSet},
-};
-
-use uuid::Uuid;
-
-#[derive(Debug, Clone, PartialEq, Eq, Default)]
-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)
- }
-
- /// Returns true if this clock is concurrent with another (neither happens before the other)
- pub fn is_concurrent_with(&self, other: &VectorClock) -> bool {
- self.partial_cmp(other).is_none()
- }
-}
-
-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) => None,
- (true, false) => Some(Ordering::Less),
- (false, true) => Some(Ordering::Greater),
- (false, false) => Some(Ordering::Equal),
- }
- }
-}
-
-#[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!(!(alice > bob));
-
- 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!(!(alice < bob));
-
- 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_a < clock_b));
- }
-
- #[test]
- fn concurrent_clocks() {
- let alice_id = Uuid::now_v7();
- let bob_id = Uuid::now_v7();
- let carol_id = Uuid::now_v7();
-
- // Equal clocks are not concurrent
- let clock1 = VectorClock::new();
- let clock2 = VectorClock::new();
- assert!(!clock1.is_concurrent_with(&clock2));
-
- // Causally ordered clocks are not concurrent
- let clock_before = VectorClock::new().inc(&alice_id);
- let clock_after = VectorClock::new().inc(&alice_id).inc(&bob_id);
- assert!(!clock_before.is_concurrent_with(&clock_after));
- assert!(!clock_after.is_concurrent_with(&clock_before));
-
- // Clocks from different actors are concurrent
- let alice_clock = VectorClock::new().inc(&alice_id);
- let bob_clock = VectorClock::new().inc(&bob_id);
- assert!(alice_clock.is_concurrent_with(&bob_clock));
- assert!(bob_clock.is_concurrent_with(&alice_clock));
-
- // Complex concurrent case: diverged branches
- let clock_a = VectorClock::new()
- .inc(&alice_id)
- .inc(&alice_id)
- .inc(&bob_id)
- .inc(&carol_id);
-
- let clock_b = VectorClock::new()
- .inc(&alice_id)
- .inc(&alice_id)
- .inc(&bob_id)
- .inc(&bob_id);
-
- // clock_a: {alice: 2, bob: 1, carol: 1}
- // clock_b: {alice: 2, bob: 2}
- // carol: 1 > 0, but bob: 1 < 2 → concurrent
- assert!(clock_a.is_concurrent_with(&clock_b));
- }
-}