threshold/
traits.rs

1use std::fmt::Debug;
2use std::hash::Hash;
3
4/// Count trait to be used in `MultiSet`.
5pub trait Count: Copy {
6    /// Return a zero count.
7    fn zero() -> Self;
8
9    /// Add to the count.
10    fn add(&mut self, other: Self);
11}
12
13impl Count for u64 {
14    /// Return a zero count.
15    fn zero() -> Self {
16        0
17    }
18
19    /// Add to the count.
20    fn add(&mut self, other: Self) {
21        *self += other;
22    }
23}
24
25impl Count for (u64, u64) {
26    /// Return a zero count.
27    fn zero() -> Self {
28        (0, 0)
29    }
30
31    /// Add to the count.
32    fn add(&mut self, other: Self) {
33        self.0 += other.0;
34        self.1 += other.1;
35    }
36}
37
38/// Actor trait to be used in `Clock`'s or `TClock`'s.
39pub trait Actor: Debug + Clone + Hash + Eq + Ord {}
40impl<A: Debug + Clone + Hash + Eq + Ord> Actor for A {}
41
42/// EventSet trait to be implemented by `MaxSet`, `BelowExSet` and `AboveExSet`.
43pub trait EventSet: Clone + Debug + Default {
44    type EventIter: Iterator<Item = u64>;
45
46    /// Returns a new instance.
47    fn new() -> Self;
48
49    /// Creates a new instance from `event`.
50    fn from_event(event: u64) -> Self {
51        let mut eset = Self::new();
52        eset.add_event(event);
53        eset
54    }
55
56    /// Creates a new instance from a range of events.
57    fn from_event_range(start: u64, end: u64) -> Self {
58        let mut eset = Self::new();
59        eset.add_event_range(start, end);
60        eset
61    }
62
63    /// Creates a new instance from several `events`.
64    fn from_events<I: IntoIterator<Item = u64>>(iter: I) -> Self {
65        let mut eset = Self::new();
66        for event in iter {
67            eset.add_event(event);
68        }
69        eset
70    }
71
72    /// Generates the next event.
73    fn next_event(&mut self) -> u64;
74
75    /// Adds an event to the set.
76    fn add_event(&mut self, event: u64) -> bool;
77
78    /// Adds a range of events to the set.
79    fn add_event_range(&mut self, start: u64, end: u64) -> bool {
80        let mut res = false;
81        (start..=end).for_each(|event| {
82            let added = self.add_event(event);
83            res = res || added;
84        });
85        res
86    }
87
88    /// Checks if an event is part of the set.
89    fn is_event(&self, event: u64) -> bool;
90
91    /// Returns all events seen as a pair.
92    ///
93    /// For `MaxSet`:
94    /// - the first component is the highest event
95    /// - the second component is empty
96    ///
97    /// For `BelowExSet`:
98    /// - the first component is the highest event
99    /// - the second component is a set of exceptions
100    ///
101    /// For `AboveExSet`:
102    /// - the first component is the highest event in a contiguous sequence
103    /// - the second component is a set of outstanding events
104    ///
105    /// If we've seen events [1, 2, 3, 5, 6], this function returns in
106    /// - `MaxSet`: (6, [])
107    /// - `BelowExSet`: (6, \[4\])
108    /// - `AboveExSet`: (3, \[5, 6\])
109    fn events(&self) -> (u64, Vec<u64>);
110
111    /// Returns the frontier (the highest contiguous event seen).
112    fn frontier(&self) -> u64;
113
114    /// Merges `other` `EventSet` into `self`.
115    fn join(&mut self, other: &Self);
116
117    /// Intersects `other` `EventSet` with `self`.
118    fn meet(&mut self, other: &Self);
119
120    /// Return a list of events that remain when `other` is subtracted from
121    /// `self`.
122    fn subtracted(&self, other: &Self) -> Vec<u64>;
123
124    /// Returns an iterator containing all elements represented by this event
125    /// set.
126    fn event_iter(self) -> Self::EventIter;
127}
128
129pub fn subtract_iter<E, S>(from: E, subtract: S) -> SubtractIter<E, S>
130where
131    E: EventSet,
132    S: EventSet,
133{
134    SubtractIter {
135        event_iter: from.event_iter(),
136        subtract,
137    }
138}
139
140pub struct SubtractIter<E: EventSet, S> {
141    event_iter: E::EventIter,
142    subtract: S,
143}
144
145impl<E, S> Iterator for SubtractIter<E, S>
146where
147    E: EventSet,
148    S: EventSet,
149{
150    type Item = u64;
151
152    fn next(&mut self) -> Option<Self::Item> {
153        match self.event_iter.next() {
154            Some(event) => {
155                if self.subtract.is_event(event) {
156                    self.next()
157                } else {
158                    Some(event)
159                }
160            }
161            None => None,
162        }
163    }
164}
threshold/traits.rs

threshold/
traits.rs
