chronofold/
iter.rs

1use std::collections::HashSet;
2use std::marker::PhantomData;
3use std::matches;
4use std::ops::{Bound, Range, RangeBounds};
5
6use crate::{
7    Author, Change, Chronofold, EarliestDeletion, FromLocalValue, LogIndex, Op, OpPayload,
8};
9
10impl<A: Author, T> Chronofold<A, T> {
11    /// Returns an iterator over the log indices in causal order.
12    ///
13    /// TODO: The name is a bit unwieldy. I'm reluctant to add it to the public
14    /// API before giving it more thought.
15    pub(crate) fn iter_log_indices_causal_range<R>(&self, range: R) -> CausalIter<'_, A, T>
16    where
17        R: RangeBounds<LogIndex>,
18    {
19        let mut current = match range.start_bound() {
20            Bound::Unbounded => self.index_after(self.root),
21            Bound::Included(idx) => Some(*idx),
22            Bound::Excluded(idx) => self.index_after(*idx),
23        };
24        if let Some((Some(Change::Root), idx)) = current.map(|idx| (self.get(idx), idx)) {
25            current = self.index_after(idx);
26        }
27        let first_excluded = match range.end_bound() {
28            Bound::Unbounded => None,
29            Bound::Included(idx) => self.index_after(*idx),
30            Bound::Excluded(idx) => Some(*idx),
31        };
32        CausalIter {
33            cfold: self,
34            current,
35            first_excluded,
36        }
37    }
38
39    /// Returns an iterator over a subtree.
40    ///
41    /// The first item is always `root`.
42    pub(crate) fn iter_subtree(&self, root: LogIndex) -> impl Iterator<Item = LogIndex> + '_ {
43        let mut subtree: HashSet<LogIndex> = HashSet::new();
44        self.iter_log_indices_causal_range(root..)
45            .filter_map(move |(_, idx, _)| {
46                if idx == root || subtree.contains(&self.references.get(&idx)?) {
47                    subtree.insert(idx);
48                    Some(idx)
49                } else {
50                    None
51                }
52            })
53    }
54
55    /// Returns an iterator over elements and their log indices in causal order.
56    pub fn iter(&self) -> Iter<A, T> {
57        self.iter_range(..)
58    }
59
60    /// Returns an iterator over elements and their log indices in causal order.
61    pub fn iter_range<R>(&self, range: R) -> Iter<A, T>
62    where
63        R: RangeBounds<LogIndex>,
64    {
65        let causal_iter = self.iter_log_indices_causal_range(range);
66        Iter { causal_iter }
67    }
68
69    /// Returns an iterator over elements in causal order.
70    pub fn iter_elements(&self) -> impl Iterator<Item = &T> {
71        self.iter().map(|(v, _)| v)
72    }
73
74    /// Returns an iterator over changes in log order.
75    pub fn iter_changes(&self) -> impl Iterator<Item = &(Change<T>, EarliestDeletion)> {
76        self.log.iter()
77    }
78
79    /// Returns an iterator over ops in log order.
80    pub fn iter_ops<'a, R, V>(&'a self, range: R) -> Ops<'a, A, T, V>
81    where
82        R: RangeBounds<LogIndex> + 'a,
83        V: FromLocalValue<'a, A, T>,
84    {
85        let oob = LogIndex(self.log.len());
86        let start = match range.start_bound() {
87            Bound::Unbounded => LogIndex(0),
88            Bound::Included(idx) => *idx,
89            Bound::Excluded(idx) => self.index_after(*idx).unwrap_or(oob),
90        }
91        .0;
92        let end = match range.end_bound() {
93            Bound::Unbounded => oob,
94            Bound::Included(idx) => self.index_after(*idx).unwrap_or(oob),
95            Bound::Excluded(idx) => *idx,
96        }
97        .0;
98        Ops {
99            cfold: self,
100            idx_iter: start..end,
101            _op_value: PhantomData,
102        }
103    }
104}
105
106pub(crate) struct CausalIter<'a, A, T> {
107    cfold: &'a Chronofold<A, T>,
108    current: Option<LogIndex>,
109    first_excluded: Option<LogIndex>,
110}
111
112impl<'a, A: Author, T> Iterator for CausalIter<'a, A, T> {
113    type Item = (&'a Change<T>, LogIndex, EarliestDeletion);
114
115    fn next(&mut self) -> Option<Self::Item> {
116        match self.current.take() {
117            Some(current) if Some(current) != self.first_excluded => {
118                self.current = self.cfold.index_after(current);
119                let (change, deleted) = &self.cfold.log[current.0];
120                Some((change, current, *deleted))
121            }
122            _ => None,
123        }
124    }
125}
126
127/// An iterator over the elements of a chronofold.
128///
129/// This struct is created by the `iter` and `iter_range` methods on
130/// `Chronofold`. See its documentation for more.
131pub struct Iter<'a, A, T> {
132    causal_iter: CausalIter<'a, A, T>,
133}
134
135impl<'a, A: Author, T> Iterator for Iter<'a, A, T> {
136    type Item = (&'a T, LogIndex);
137
138    fn next(&mut self) -> Option<Self::Item> {
139        loop {
140            let next = skip_while(&mut self.causal_iter, |(c, _, deleted)| {
141                matches!(c, Change::Delete) || deleted.is_some()
142            });
143            match next {
144                None => {
145                    return None;
146                }
147                Some((Change::Insert(v), idx, _)) => {
148                    return Some((v, idx));
149                }
150                _ => unreachable!(),
151            }
152        }
153    }
154}
155
156/// An iterator over ops representing a chronofold's changes.
157///
158/// This struct is created by the `iter_ops` method on `Chronofold`. See its
159/// documentation for more.
160pub struct Ops<'a, A, T, V> {
161    cfold: &'a Chronofold<A, T>,
162    idx_iter: Range<usize>,
163    _op_value: PhantomData<V>,
164}
165
166impl<'a, A, T, V> Iterator for Ops<'a, A, T, V>
167where
168    A: Author,
169    V: FromLocalValue<'a, A, T>,
170{
171    type Item = Op<A, V>;
172
173    fn next(&mut self) -> Option<Self::Item> {
174        let idx = LogIndex(self.idx_iter.next()?);
175        let id = self
176            .cfold
177            .timestamp(idx)
178            .expect("timestamps of already applied ops have to exist");
179        let reference = self.cfold.references.get(&idx).map(|r| {
180            self.cfold
181                .timestamp(r)
182                .expect("references of already applied ops have to exist")
183        });
184        let payload = match &self.cfold.log[idx.0].0 {
185            Change::Root => OpPayload::Root,
186            Change::Insert(v) => OpPayload::Insert(reference, V::from_local_value(v, self.cfold)),
187            Change::Delete => OpPayload::Delete(reference.expect("deletes must have a reference")),
188        };
189        Some(Op::new(id, payload))
190    }
191}
192
193/// Skips items where `predicate` returns true.
194///
195/// Note that while this works like `Iterator::skip_while`, it does not create
196/// a new iterator. Instead `iter` is modified.
197fn skip_while<I, P>(iter: &mut I, predicate: P) -> Option<I::Item>
198where
199    I: Iterator,
200    P: Fn(&I::Item) -> bool,
201{
202    loop {
203        match iter.next() {
204            Some(item) if !predicate(&item) => {
205                return Some(item);
206            }
207            None => {
208                return None;
209            }
210            _ => {}
211        }
212    }
213}
214
215#[cfg(test)]
216mod tests {
217    use super::*;
218    use crate::Timestamp;
219
220    #[test]
221    fn iter_subtree() {
222        let mut cfold = Chronofold::<u8, char>::default();
223        cfold.session(1).extend("013".chars());
224        cfold.session(1).insert_after(LogIndex(2), '2');
225        assert_eq!(
226            vec![LogIndex(2), LogIndex(4), LogIndex(3)],
227            cfold.iter_subtree(LogIndex(2)).collect::<Vec<_>>()
228        );
229    }
230
231    #[test]
232    fn iter_ops() {
233        let mut cfold = Chronofold::<u8, char>::default();
234        cfold.session(1).extend("Hi!".chars());
235        let op0 = Op::root(Timestamp(LogIndex(0), 0));
236        let op1 = Op::insert(
237            Timestamp(LogIndex(1), 1),
238            Some(Timestamp(LogIndex(0), 0)),
239            &'H',
240        );
241        let op2 = Op::insert(
242            Timestamp(LogIndex(2), 1),
243            Some(Timestamp(LogIndex(1), 1)),
244            &'i',
245        );
246        let op3 = Op::insert(
247            Timestamp(LogIndex(3), 1),
248            Some(Timestamp(LogIndex(2), 1)),
249            &'!',
250        );
251        assert_eq!(
252            vec![op0.clone(), op1.clone(), op2.clone()],
253            cfold.iter_ops(..LogIndex(3)).collect::<Vec<_>>()
254        );
255        assert_eq!(
256            vec![op2, op3],
257            cfold.iter_ops(LogIndex(2)..).collect::<Vec<_>>()
258        );
259    }
260
261    #[test]
262    fn skip_while() {
263        let mut iter = 2..10;
264        let result = super::skip_while(&mut iter, |i| i < &7);
265        assert_eq!(Some(7), result);
266        assert_eq!(vec![8, 9], iter.collect::<Vec<_>>());
267
268        let mut iter2 = 2..10;
269        let result = super::skip_while(&mut iter2, |i| i < &20);
270        assert_eq!(None, result);
271    }
272}
chronofold/iter.rs

chronofold/
iter.rs
