minerva 0.2.0

Causal ordering for distributed systems
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

extern crate alloc;

use alloc::collections::BTreeSet;
use alloc::vec::Vec;

/// Compresses an ascending exception set into maximal runs of consecutive dots,
/// each `(start, len)` with `len >= 1`. Consecutive dots fold into one run, so
/// the output is strictly separated (each run's `start` exceeds the previous
/// run's end plus one), which is exactly the canonical form the decoder demands.
pub(super) fn maximal_runs(above: &BTreeSet<u64>) -> Vec<(u64, u64)> {
    let mut runs: Vec<(u64, u64)> = Vec::new();
    for &dot in above {
        match runs.last_mut() {
            // Extend the current run when `dot` continues it. `start + len` is the
            // first dot beyond the run; it cannot overflow here because a run whose
            // end is `u64::MAX` has no larger `dot` to continue it.
            Some((start, len)) if start.checked_add(*len) == Some(dot) => *len += 1,
            _ => runs.push((dot, 1)),
        }
    }
    runs
}

/// Counts the canonical runs without allocating their representation.
pub(super) fn maximal_run_count(above: &BTreeSet<u64>) -> usize {
    let mut previous = None;
    let mut count = 0usize;
    for &dot in above {
        if previous.and_then(|last: u64| last.checked_add(1)) != Some(dot) {
            count = count.saturating_add(1);
        }
        previous = Some(dot);
    }
    count
}