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
8pub mod cursor_list;
9
10pub use self::cursor_list::CursorList;
11
12use std::borrow::Borrow;
13use std::cmp::Ordering;
14
15/// A type that may be converted into and compared with another type.
16///
17/// The type must also be comparable with itself, and follow the same 
18/// order as if converting instances to `T` and comparing the results.
19pub trait MyTrait<'a> : Ord {
20    /// Owned type into which this type can be converted.
21    type Owned;
22    /// Conversion from an instance of this type to the owned type.
23    fn into_owned(self) -> Self::Owned;
24    ///
25    fn clone_onto(&self, other: &mut Self::Owned); 
26    /// Indicates that `self <= other`; used for sorting.
27    fn compare(&self, other: &Self::Owned) -> Ordering;
28    /// `self <= other`
29    fn less_equals(&self, other: &Self::Owned) -> bool {
30        self.compare(other) != Ordering::Greater
31    }
32    /// `self == other`
33    fn equals(&self, other: &Self::Owned) -> bool {
34        self.compare(other) == Ordering::Equal
35    }
36    /// `self < other`
37    fn less_than(&self, other: &Self::Owned) -> bool {
38        self.compare(other) == Ordering::Less
39    }
40    /// Borrows an owned instance as onesself.
41    fn borrow_as(other: &'a Self::Owned) -> Self; 
42}
43
44impl<'a, T: Ord+ToOwned+?Sized> MyTrait<'a> for &'a T {
45    type Owned = T::Owned;
46    fn into_owned(self) -> Self::Owned { self.to_owned() }
47    fn clone_onto(&self, other: &mut Self::Owned) { <T as ToOwned>::clone_into(self, other) }
48    fn compare(&self, other: &Self::Owned) -> Ordering { self.cmp(&other.borrow()) }
49    fn borrow_as(other: &'a Self::Owned) -> Self {
50        other.borrow()
51    }
52}
53
54/// A cursor for navigating ordered `(key, val, time, diff)` updates.
55pub trait Cursor {
56
57    /// Key by which updates are indexed.
58    type Key<'a>: Copy + Clone + MyTrait<'a, Owned = Self::KeyOwned>;
59    /// Owned version of the above.
60    type KeyOwned: Ord + Clone;
61    /// Values associated with keys.
62    type Val<'a>: Copy + Clone + MyTrait<'a, Owned = Self::ValOwned> + for<'b> PartialOrd<Self::Val<'b>>;
63    /// Owned version of the above.
64    type ValOwned: Ord + Clone;
65    /// Timestamps associated with updates
66    type Time;
67    /// Associated update.
68    type Diff: ?Sized;
69
70    /// Storage required by the cursor.
71    type Storage;
72
73    /// Indicates if the current key is valid.
74    ///
75    /// A value of `false` indicates that the cursor has exhausted all keys.
76    fn key_valid(&self, storage: &Self::Storage) -> bool;
77    /// Indicates if the current value is valid.
78    ///
79    /// A value of `false` indicates that the cursor has exhausted all values for this key.
80    fn val_valid(&self, storage: &Self::Storage) -> bool;
81
82    /// A reference to the current key. Asserts if invalid.
83    fn key<'a>(&self, storage: &'a Self::Storage) -> Self::Key<'a>;
84    /// A reference to the current value. Asserts if invalid.
85    fn val<'a>(&self, storage: &'a Self::Storage) -> Self::Val<'a>;
86
87    /// Returns a reference to the current key, if valid.
88    fn get_key<'a>(&self, storage: &'a Self::Storage) -> Option<Self::Key<'a>> {
89        if self.key_valid(storage) { Some(self.key(storage)) } else { None }
90    }
91    /// Returns a reference to the current value, if valid.
92    fn get_val<'a>(&self, storage: &'a Self::Storage) -> Option<Self::Val<'a>> {
93        if self.val_valid(storage) { Some(self.val(storage)) } else { None }
94    }
95
96    /// Applies `logic` to each pair of time and difference. Intended for mutation of the
97    /// closure's scope.
98    fn map_times<L: FnMut(&Self::Time, &Self::Diff)>(&mut self, storage: &Self::Storage, logic: L);
99
100    /// Advances the cursor to the next key.
101    fn step_key(&mut self, storage: &Self::Storage);
102    /// Advances the cursor to the specified key.
103    fn seek_key(&mut self, storage: &Self::Storage, key: Self::Key<'_>);
104    /// Convenience method to get access by reference to an owned key.
105    fn seek_key_owned(&mut self, storage: &Self::Storage, key: &Self::KeyOwned) {
106        self.seek_key(storage, MyTrait::borrow_as(key));
107    }
108
109    /// Advances the cursor to the next value.
110    fn step_val(&mut self, storage: &Self::Storage);
111    /// Advances the cursor to the specified value.
112    fn seek_val(&mut self, storage: &Self::Storage, val: Self::Val<'_>);
113
114    /// Rewinds the cursor to the first key.
115    fn rewind_keys(&mut self, storage: &Self::Storage);
116    /// Rewinds the cursor to the first value for current key.
117    fn rewind_vals(&mut self, storage: &Self::Storage);
118
119    /// Rewinds the cursor and outputs its contents to a Vec
120    fn to_vec(&mut self, storage: &Self::Storage) -> Vec<((Self::KeyOwned, Self::ValOwned), Vec<(Self::Time, Self::Diff)>)>
121    where
122        Self::Time: Clone,
123        Self::Diff: Clone,
124    {
125        let mut out = Vec::new();
126        self.rewind_keys(storage);
127        self.rewind_vals(storage);
128        while self.key_valid(storage) {
129            while self.val_valid(storage) {
130                let mut kv_out = Vec::new();
131                self.map_times(storage, |ts, r| {
132                    kv_out.push((ts.clone(), r.clone()));
133                });
134                out.push(((self.key(storage).into_owned(), self.val(storage).into_owned()), kv_out));
135                self.step_val(storage);
136            }
137            self.step_key(storage);
138        }
139        out
140    }
141}
differential_dataflow/trace/cursor/mod.rs

differential_dataflow/trace/cursor/
mod.rs
