palimpsest_dataflow/trace/cursor/
mod.rs

1//! Traits and types for navigating order sequences of update tuples.
2//!
3//! The `Cursor` trait contains several methods for efficiently navigating ordered collections
4//! of tuples of the form `(key, val, time, diff)`. The cursor is different from an iterator
5//! both because it allows navigation on multiple levels (key and val), but also because it
6//! supports efficient seeking (via the `seek_key` and `seek_val` methods).
7
8pub mod cursor_list;
9
10pub use self::cursor_list::CursorList;
11
12use crate::trace::implementations::LayoutExt;
13
14/// A cursor for navigating ordered `(key, val, time, diff)` updates.
15pub trait Cursor: LayoutExt {
16    /// Storage required by the cursor.
17    type Storage;
18
19    /// Indicates if the current key is valid.
20    ///
21    /// A value of `false` indicates that the cursor has exhausted all keys.
22    fn key_valid(&self, storage: &Self::Storage) -> bool;
23    /// Indicates if the current value is valid.
24    ///
25    /// A value of `false` indicates that the cursor has exhausted all values for this key.
26    fn val_valid(&self, storage: &Self::Storage) -> bool;
27
28    /// A reference to the current key. Asserts if invalid.
29    fn key<'a>(&self, storage: &'a Self::Storage) -> Self::Key<'a>;
30    /// A reference to the current value. Asserts if invalid.
31    fn val<'a>(&self, storage: &'a Self::Storage) -> Self::Val<'a>;
32
33    /// Returns a reference to the current key, if valid.
34    fn get_key<'a>(&self, storage: &'a Self::Storage) -> Option<Self::Key<'a>>;
35    /// Returns a reference to the current value, if valid.
36    fn get_val<'a>(&self, storage: &'a Self::Storage) -> Option<Self::Val<'a>>;
37
38    /// Applies `logic` to each pair of time and difference. Intended for mutation of the
39    /// closure's scope.
40    fn map_times<L: FnMut(Self::TimeGat<'_>, Self::DiffGat<'_>)>(
41        &mut self,
42        storage: &Self::Storage,
43        logic: L,
44    );
45
46    /// Advances the cursor to the next key.
47    fn step_key(&mut self, storage: &Self::Storage);
48    /// Advances the cursor to the specified key.
49    fn seek_key(&mut self, storage: &Self::Storage, key: Self::Key<'_>);
50
51    /// Advances the cursor to the next value.
52    fn step_val(&mut self, storage: &Self::Storage);
53    /// Advances the cursor to the specified value.
54    fn seek_val(&mut self, storage: &Self::Storage, val: Self::Val<'_>);
55
56    /// Rewinds the cursor to the first key.
57    fn rewind_keys(&mut self, storage: &Self::Storage);
58    /// Rewinds the cursor to the first value for current key.
59    fn rewind_vals(&mut self, storage: &Self::Storage);
60
61    /// Rewinds the cursor and outputs its contents to a Vec
62    fn to_vec<K, IK, V, IV>(
63        &mut self,
64        storage: &Self::Storage,
65        into_key: IK,
66        into_val: IV,
67    ) -> Vec<((K, V), Vec<(Self::Time, Self::Diff)>)>
68    where
69        IK: for<'a> Fn(Self::Key<'a>) -> K,
70        IV: for<'a> Fn(Self::Val<'a>) -> V,
71    {
72        let mut out = Vec::new();
73        self.rewind_keys(storage);
74        while let Some(key) = self.get_key(storage) {
75            self.rewind_vals(storage);
76            while let Some(val) = self.get_val(storage) {
77                let mut kv_out = Vec::new();
78                self.map_times(storage, |ts, r| {
79                    kv_out.push((Self::owned_time(ts), Self::owned_diff(r)));
80                });
81                out.push(((into_key(key), into_val(val)), kv_out));
82                self.step_val(storage);
83            }
84            self.step_key(storage);
85        }
86        out
87    }
88}
palimpsest_dataflow/trace/cursor/mod.rs

palimpsest_dataflow/trace/cursor/
mod.rs
