differential_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
8use timely::progress::Timestamp;
9
10use crate::difference::Semigroup;
11// `pub use` for legacy reasons.
12pub use crate::IntoOwned;
13use crate::lattice::Lattice;
14
15pub mod cursor_list;
16
17pub use self::cursor_list::CursorList;
18
19/// A cursor for navigating ordered `(key, val, time, diff)` updates.
20pub trait Cursor {
21
22    /// Key by which updates are indexed.
23    type Key<'a>: Copy + Clone + Ord;
24    /// Values associated with keys.
25    type Val<'a>: Copy + Clone + Ord;
26    /// Timestamps associated with updates
27    type Time: Timestamp + Lattice + Ord + Clone;
28    /// Borrowed form of timestamp.
29    type TimeGat<'a>: Copy + IntoOwned<'a, Owned = Self::Time>;
30    /// Owned form of update difference.
31    type Diff: Semigroup + 'static;
32    /// Borrowed form of update difference.
33    type DiffGat<'a> : Copy + IntoOwned<'a, Owned = Self::Diff>;
34
35    /// Storage required by the cursor.
36    type Storage;
37
38    /// Indicates if the current key is valid.
39    ///
40    /// A value of `false` indicates that the cursor has exhausted all keys.
41    fn key_valid(&self, storage: &Self::Storage) -> bool;
42    /// Indicates if the current value is valid.
43    ///
44    /// A value of `false` indicates that the cursor has exhausted all values for this key.
45    fn val_valid(&self, storage: &Self::Storage) -> bool;
46
47    /// A reference to the current key. Asserts if invalid.
48    fn key<'a>(&self, storage: &'a Self::Storage) -> Self::Key<'a>;
49    /// A reference to the current value. Asserts if invalid.
50    fn val<'a>(&self, storage: &'a Self::Storage) -> Self::Val<'a>;
51
52    /// Returns a reference to the current key, if valid.
53    fn get_key<'a>(&self, storage: &'a Self::Storage) -> Option<Self::Key<'a>> {
54        if self.key_valid(storage) { Some(self.key(storage)) } else { None }
55    }
56    /// Returns a reference to the current value, if valid.
57    fn get_val<'a>(&self, storage: &'a Self::Storage) -> Option<Self::Val<'a>> {
58        if self.val_valid(storage) { Some(self.val(storage)) } else { None }
59    }
60
61    /// Applies `logic` to each pair of time and difference. Intended for mutation of the
62    /// closure's scope.
63    fn map_times<L: FnMut(Self::TimeGat<'_>, Self::DiffGat<'_>)>(&mut self, storage: &Self::Storage, logic: L);
64
65    /// Advances the cursor to the next key.
66    fn step_key(&mut self, storage: &Self::Storage);
67    /// Advances the cursor to the specified key.
68    fn seek_key(&mut self, storage: &Self::Storage, key: Self::Key<'_>);
69
70    /// Advances the cursor to the next value.
71    fn step_val(&mut self, storage: &Self::Storage);
72    /// Advances the cursor to the specified value.
73    fn seek_val(&mut self, storage: &Self::Storage, val: Self::Val<'_>);
74
75    /// Rewinds the cursor to the first key.
76    fn rewind_keys(&mut self, storage: &Self::Storage);
77    /// Rewinds the cursor to the first value for current key.
78    fn rewind_vals(&mut self, storage: &Self::Storage);
79
80    /// Rewinds the cursor and outputs its contents to a Vec
81    fn to_vec<K, V>(&mut self, storage: &Self::Storage) -> Vec<((K, V), Vec<(Self::Time, Self::Diff)>)>
82    where 
83        for<'a> Self::Key<'a> : IntoOwned<'a, Owned = K>,
84        for<'a> Self::Val<'a> : IntoOwned<'a, Owned = V>,
85    {
86        let mut out = Vec::new();
87        self.rewind_keys(storage);
88        while self.key_valid(storage) {
89            self.rewind_vals(storage);
90            while self.val_valid(storage) {
91                let mut kv_out = Vec::new();
92                self.map_times(storage, |ts, r| {
93                    kv_out.push((ts.into_owned(), r.into_owned()));
94                });
95                out.push(((self.key(storage).into_owned(), self.val(storage).into_owned()), kv_out));
96                self.step_val(storage);
97            }
98            self.step_key(storage);
99        }
100        out
101    }
102}
differential_dataflow/trace/cursor/mod.rs

differential_dataflow/trace/cursor/
mod.rs
