raphtory_core/entities/properties/
tcell.rs

1use crate::storage::timeindex::{AsTime, EventTime, TimeIndexOps, TimeIndexWindow};
2use either::Either;
3use iter_enum::{DoubleEndedIterator, ExactSizeIterator, Extend, FusedIterator, Iterator};
4use raphtory_api::core::storage::{sorted_vec_map::SVM, timeindex::TimeIndexLike};
5use serde::{Deserialize, Serialize};
6use std::{collections::BTreeMap, fmt::Debug, ops::Range};
7
8#[derive(Debug, PartialEq, Default, Clone, Serialize, Deserialize)]
9// TCells represent a value in time that can be set at multiple times and keeps a history
10pub enum TCell<A> {
11    #[default]
12    Empty,
13    TCell1(EventTime, A),
14    TCellCap(SVM<EventTime, A>),
15    TCellN(BTreeMap<EventTime, A>),
16}
17
18#[derive(Iterator, DoubleEndedIterator, ExactSizeIterator, FusedIterator, Extend)]
19enum TCellVariants<Empty, TCell1, TCellCap, TCellN> {
20    Empty(Empty),
21    TCell1(TCell1),
22    TCellCap(TCellCap),
23    TCellN(TCellN),
24}
25
26const BTREE_CUTOFF: usize = 128;
27
28impl<A: PartialEq> TCell<A> {
29    pub fn new(t: EventTime, value: A) -> Self {
30        TCell::TCell1(t, value)
31    }
32
33    #[inline]
34    pub fn set(&mut self, t: EventTime, value: A) {
35        match self {
36            TCell::Empty => {
37                *self = TCell::TCell1(t, value);
38            }
39            TCell::TCell1(t0, v) => {
40                if &t != t0 {
41                    if let TCell::TCell1(t0, value0) = std::mem::take(self) {
42                        let mut svm = SVM::new();
43                        svm.insert(t, value);
44                        svm.insert(t0, value0);
45                        *self = TCell::TCellCap(svm)
46                    }
47                } else {
48                    *v = value
49                }
50            }
51            TCell::TCellCap(svm) => {
52                if svm.len() < BTREE_CUTOFF {
53                    svm.insert(t, value);
54                } else {
55                    let svm = std::mem::take(svm);
56                    let mut btm: BTreeMap<EventTime, A> = BTreeMap::new();
57                    for (k, v) in svm.into_iter() {
58                        btm.insert(k, v);
59                    }
60                    btm.insert(t, value);
61                    *self = TCell::TCellN(btm)
62                }
63            }
64            TCell::TCellN(btm) => {
65                btm.insert(t, value);
66            }
67        }
68    }
69
70    pub fn at(&self, ti: &EventTime) -> Option<&A> {
71        match self {
72            TCell::Empty => None,
73            TCell::TCell1(t, v) => (t == ti).then_some(v),
74            TCell::TCellCap(svm) => svm.get(ti),
75            TCell::TCellN(btm) => btm.get(ti),
76        }
77    }
78}
79impl<A: Sync + Send> TCell<A> {
80    pub fn iter(&self) -> impl DoubleEndedIterator<Item = (&EventTime, &A)> + Send + Sync {
81        match self {
82            TCell::Empty => TCellVariants::Empty(std::iter::empty()),
83            TCell::TCell1(t, value) => TCellVariants::TCell1(std::iter::once((t, value))),
84            TCell::TCellCap(svm) => TCellVariants::TCellCap(svm.iter()),
85            TCell::TCellN(btm) => TCellVariants::TCellN(btm.iter()),
86        }
87    }
88
89    pub fn iter_t(&self) -> impl DoubleEndedIterator<Item = (i64, &A)> + Send + Sync {
90        self.iter().map(|(t, a)| (t.t(), a))
91    }
92
93    pub fn iter_window(
94        &self,
95        r: Range<EventTime>,
96    ) -> impl DoubleEndedIterator<Item = (&EventTime, &A)> + Send + Sync {
97        match self {
98            TCell::Empty => TCellVariants::Empty(std::iter::empty()),
99            TCell::TCell1(t, value) => TCellVariants::TCell1(if r.contains(t) {
100                Either::Left(std::iter::once((t, value)))
101            } else {
102                Either::Right(std::iter::empty())
103            }),
104            TCell::TCellCap(svm) => TCellVariants::TCellCap(svm.range(r)),
105            TCell::TCellN(btm) => TCellVariants::TCellN(btm.range(r)),
106        }
107    }
108
109    pub fn iter_window_t(
110        &self,
111        r: Range<i64>,
112    ) -> impl DoubleEndedIterator<Item = (i64, &A)> + Send + Sync + '_ {
113        self.iter_window(EventTime::range(r))
114            .map(|(t, a)| (t.t(), a))
115    }
116
117    pub fn last_before(&self, t: EventTime) -> Option<(EventTime, &A)> {
118        match self {
119            TCell::Empty => None,
120            TCell::TCell1(t2, v) => (*t2 < t).then_some((*t2, v)),
121            TCell::TCellCap(map) => map.range(EventTime::MIN..t).last().map(|(ti, v)| (*ti, v)),
122            TCell::TCellN(map) => map.range(EventTime::MIN..t).last().map(|(ti, v)| (*ti, v)),
123        }
124    }
125
126    pub fn len(&self) -> usize {
127        match self {
128            TCell::Empty => 0,
129            TCell::TCell1(_, _) => 1,
130            TCell::TCellCap(v) => v.len(),
131            TCell::TCellN(v) => v.len(),
132        }
133    }
134
135    pub fn is_empty(&self) -> bool {
136        self.len() == 0
137    }
138}
139
140impl<'a, A: Send + Sync> TimeIndexOps<'a> for &'a TCell<A> {
141    type IndexType = EventTime;
142    type RangeType = TimeIndexWindow<'a, Self::IndexType, TCell<A>>;
143
144    #[inline]
145    fn active(&self, w: Range<Self::IndexType>) -> bool {
146        match self {
147            TCell::Empty => false,
148            TCell::TCell1(time_index_entry, _) => w.contains(time_index_entry),
149            TCell::TCellCap(svm) => svm.range(w).next().is_some(),
150            TCell::TCellN(btree_map) => btree_map.range(w).next().is_some(),
151        }
152    }
153
154    fn range(&self, w: Range<Self::IndexType>) -> Self::RangeType {
155        let range = match self {
156            TCell::Empty => TimeIndexWindow::Empty,
157            TCell::TCell1(t, _) => {
158                if w.contains(t) {
159                    TimeIndexWindow::All(*self)
160                } else {
161                    TimeIndexWindow::Empty
162                }
163            }
164            _ => {
165                if let Some(min_val) = self.first() {
166                    if let Some(max_val) = self.last() {
167                        if min_val >= w.start && max_val < w.end {
168                            TimeIndexWindow::All(*self)
169                        } else {
170                            TimeIndexWindow::Range {
171                                timeindex: *self,
172                                range: w,
173                            }
174                        }
175                    } else {
176                        TimeIndexWindow::Empty
177                    }
178                } else {
179                    TimeIndexWindow::Empty
180                }
181            }
182        };
183        range
184    }
185
186    fn first(&self) -> Option<Self::IndexType> {
187        match self {
188            TCell::Empty => None,
189            TCell::TCell1(t, _) => Some(*t),
190            TCell::TCellCap(svm) => svm.first_key_value().map(|(ti, _)| *ti),
191            TCell::TCellN(btm) => btm.first_key_value().map(|(ti, _)| *ti),
192        }
193    }
194
195    fn last(&self) -> Option<Self::IndexType> {
196        match self {
197            TCell::Empty => None,
198            TCell::TCell1(t, _) => Some(*t),
199            TCell::TCellCap(svm) => svm.last_key_value().map(|(ti, _)| *ti),
200            TCell::TCellN(btm) => btm.last_key_value().map(|(ti, _)| *ti),
201        }
202    }
203
204    #[allow(refining_impl_trait)]
205    fn iter(self) -> impl DoubleEndedIterator<Item = Self::IndexType> + Send + Sync + 'a {
206        match self {
207            TCell::Empty => TCellVariants::Empty(std::iter::empty()),
208            TCell::TCell1(t, _) => TCellVariants::TCell1(std::iter::once(*t)),
209            TCell::TCellCap(svm) => TCellVariants::TCellCap(svm.iter().map(|(ti, _)| *ti)),
210            TCell::TCellN(btm) => TCellVariants::TCellN(btm.keys().copied()),
211        }
212    }
213
214    fn iter_rev(self) -> impl Iterator<Item = Self::IndexType> + Send + Sync + 'a {
215        TimeIndexOps::iter(self).rev()
216    }
217
218    fn len(&self) -> usize {
219        match self {
220            TCell::Empty => 0,
221            TCell::TCell1(_, _) => 1,
222            TCell::TCellCap(svm) => svm.len(),
223            TCell::TCellN(btm) => btm.len(),
224        }
225    }
226}
227
228impl<'a, A: Send + Sync> TimeIndexLike<'a> for &'a TCell<A> {
229    #[allow(refining_impl_trait)]
230    fn range_iter(
231        self,
232        w: Range<Self::IndexType>,
233    ) -> impl DoubleEndedIterator<Item = Self::IndexType> + Send + Sync + 'a {
234        self.iter_window(w).map(|(ti, _)| *ti)
235    }
236
237    fn range_iter_rev(
238        self,
239        w: Range<Self::IndexType>,
240    ) -> impl Iterator<Item = Self::IndexType> + Send + Sync + 'a {
241        self.range_iter(w).rev()
242    }
243
244    fn range_count(&self, w: Range<Self::IndexType>) -> usize {
245        match self {
246            TCell::Empty => 0,
247            TCell::TCell1(t, _) => {
248                if w.contains(t) {
249                    1
250                } else {
251                    0
252                }
253            }
254            TCell::TCellCap(ts) => ts.range(w).count(),
255            TCell::TCellN(ts) => ts.range(w).count(),
256        }
257    }
258
259    fn last_range(&self, w: Range<Self::IndexType>) -> Option<Self::IndexType> {
260        self.iter_window(w).next_back().map(|(ti, _)| *ti)
261    }
262}
263
264#[cfg(test)]
265mod tcell_tests {
266    use super::TCell;
267    use crate::storage::timeindex::{AsTime, EventTime};
268
269    #[test]
270    fn set_new_value_for_tcell_initialized_as_empty() {
271        let mut tcell = TCell::default();
272        tcell.set(EventTime::start(16), String::from("lobster"));
273
274        assert_eq!(
275            tcell.iter().map(|(_, v)| v).collect::<Vec<_>>(),
276            vec!["lobster"]
277        );
278    }
279
280    #[test]
281    fn every_new_update_to_the_same_prop_is_recorded_as_history() {
282        let mut tcell = TCell::new(EventTime::start(1), "Pometry");
283        tcell.set(EventTime::start(2), "Pometry Inc.");
284
285        assert_eq!(
286            tcell.iter_t().collect::<Vec<_>>(),
287            vec![(1, &"Pometry"), (2, &"Pometry Inc."),]
288        );
289    }
290
291    #[test]
292    fn new_update_with_the_same_time_to_a_prop_is_ignored() {
293        let mut tcell = TCell::new(EventTime::start(1), "Pometry");
294        tcell.set(EventTime::start(1), "Pometry Inc.");
295
296        assert_eq!(
297            tcell.iter_t().collect::<Vec<_>>(),
298            vec![(1, &"Pometry Inc.")]
299        );
300    }
301
302    #[test]
303    fn updates_to_prop_can_be_iterated() {
304        let tcell: TCell<String> = TCell::default();
305
306        let actual = tcell.iter().collect::<Vec<_>>();
307        let expected = vec![];
308        assert_eq!(actual, expected);
309
310        assert_eq!(tcell.iter_t().collect::<Vec<_>>(), vec![]);
311
312        let tcell = TCell::new(EventTime::start(3), "Pometry");
313
314        assert_eq!(
315            tcell.iter().collect::<Vec<_>>(),
316            vec![(&EventTime::start(3), &"Pometry")]
317        );
318
319        assert_eq!(tcell.iter_t().collect::<Vec<_>>(), vec![(3, &"Pometry")]);
320
321        let mut tcell = TCell::new(EventTime::start(2), "Pometry");
322        tcell.set(EventTime::start(1), "Inc. Pometry");
323
324        assert_eq!(
325            // Results are ordered by time
326            tcell.iter_t().collect::<Vec<_>>(),
327            vec![(1, &"Inc. Pometry"), (2, &"Pometry"),]
328        );
329
330        assert_eq!(
331            // Results are ordered by time
332            tcell.iter().collect::<Vec<_>>(),
333            vec![
334                (&EventTime::start(1), &"Inc. Pometry"),
335                (&EventTime::start(2), &"Pometry")
336            ]
337        );
338
339        let mut tcell: TCell<i64> = TCell::default();
340        for n in 1..130 {
341            tcell.set(EventTime::start(n), n)
342        }
343
344        assert_eq!(tcell.iter_t().count(), 129);
345
346        assert_eq!(tcell.iter().count(), 129)
347    }
348
349    #[test]
350    fn updates_to_prop_can_be_window_iterated() {
351        let tcell: TCell<String> = TCell::default();
352
353        let actual = tcell
354            .iter_window(EventTime::MIN..EventTime::MAX)
355            .collect::<Vec<_>>();
356        let expected = vec![];
357        assert_eq!(actual, expected);
358
359        assert_eq!(
360            tcell.iter_window_t(i64::MIN..i64::MAX).collect::<Vec<_>>(),
361            vec![]
362        );
363
364        let tcell = TCell::new(EventTime::start(3), "Pometry");
365
366        assert_eq!(
367            tcell
368                .iter_window(EventTime::range(3..4))
369                .collect::<Vec<_>>(),
370            vec![(&EventTime(3, 0), &"Pometry")]
371        );
372
373        assert_eq!(
374            tcell.iter_window_t(3..4).collect::<Vec<_>>(),
375            vec![(3, &"Pometry")]
376        );
377
378        let mut tcell = TCell::new(EventTime::start(3), "Pometry");
379        tcell.set(EventTime::start(1), "Pometry Inc.");
380        tcell.set(EventTime::start(2), "Raphtory");
381
382        let one = EventTime::start(1);
383        let two = EventTime::start(2);
384        let three = EventTime::start(3);
385
386        assert_eq!(
387            tcell.iter_window_t(2..3).collect::<Vec<_>>(),
388            vec![(2, &"Raphtory")]
389        );
390
391        let expected = vec![];
392        assert_eq!(
393            tcell
394                .iter_window(EventTime::range(4..5))
395                .collect::<Vec<_>>(),
396            expected
397        );
398
399        assert_eq!(
400            tcell
401                .iter_window(EventTime::range(1..i64::MAX))
402                .collect::<Vec<_>>(),
403            vec![
404                (&one, &"Pometry Inc."),
405                (&two, &"Raphtory"),
406                (&three, &"Pometry")
407            ]
408        );
409
410        assert_eq!(
411            tcell
412                .iter_window(EventTime::range(3..i64::MAX))
413                .collect::<Vec<_>>(),
414            vec![(&three, &"Pometry")]
415        );
416
417        assert_eq!(
418            tcell
419                .iter_window(EventTime::range(2..i64::MAX))
420                .collect::<Vec<_>>(),
421            vec![(&two, &"Raphtory"), (&three, &"Pometry")]
422        );
423
424        let expected = vec![];
425        assert_eq!(
426            tcell
427                .iter_window(EventTime::range(5..i64::MAX))
428                .collect::<Vec<_>>(),
429            expected
430        );
431
432        assert_eq!(
433            tcell
434                .iter_window(EventTime::range(i64::MIN..4))
435                .collect::<Vec<_>>(),
436            vec![
437                (&one, &"Pometry Inc."),
438                (&two, &"Raphtory"),
439                (&three, &"Pometry")
440            ]
441        );
442
443        let expected = vec![];
444        assert_eq!(
445            tcell
446                .iter_window(EventTime::range(i64::MIN..1))
447                .collect::<Vec<_>>(),
448            expected
449        );
450
451        let mut tcell: TCell<i64> = TCell::default();
452        for n in 1..130 {
453            tcell.set(EventTime::start(n), n)
454        }
455
456        assert_eq!(tcell.iter_window_t(i64::MIN..i64::MAX).count(), 129);
457
458        assert_eq!(
459            tcell
460                .iter_window(EventTime::range(i64::MIN..i64::MAX))
461                .count(),
462            129
463        )
464    }
465}
raphtory_core/entities/properties/tcell.rs

raphtory_core/entities/properties/
tcell.rs
