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
122                .range(EventTime::MIN..t)
123                .next_back()
124                .map(|(ti, v)| (*ti, v)),
125            TCell::TCellN(map) => map
126                .range(EventTime::MIN..t)
127                .next_back()
128                .map(|(ti, v)| (*ti, v)),
129        }
130    }
131
132    pub fn last_value(&self) -> Option<(EventTime, &A)> {
133        match self {
134            TCell::Empty => None,
135            TCell::TCell1(t, v) => Some((*t, v)),
136            TCell::TCellCap(map) => map.last_key_value().map(|(t, v)| (*t, v)),
137            TCell::TCellN(map) => map.last_key_value().map(|(t, v)| (*t, v)),
138        }
139    }
140
141    #[inline]
142    pub fn len(&self) -> usize {
143        match self {
144            TCell::Empty => 0,
145            TCell::TCell1(_, _) => 1,
146            TCell::TCellCap(v) => v.len(),
147            TCell::TCellN(v) => v.len(),
148        }
149    }
150
151    #[inline]
152    pub fn is_empty(&self) -> bool {
153        self.len() == 0
154    }
155}
156
157impl<'a, A: Send + Sync> TimeIndexOps<'a> for &'a TCell<A> {
158    type IndexType = EventTime;
159    type RangeType = TimeIndexWindow<'a, Self::IndexType, TCell<A>>;
160
161    #[inline]
162    fn active(&self, w: Range<Self::IndexType>) -> bool {
163        match self {
164            TCell::Empty => false,
165            TCell::TCell1(time_index_entry, _) => w.contains(time_index_entry),
166            TCell::TCellCap(svm) => svm.active(w),
167            TCell::TCellN(btree_map) => btree_map.range(w).next().is_some(),
168        }
169    }
170
171    fn range(&self, w: Range<Self::IndexType>) -> Self::RangeType {
172        let range = match self {
173            TCell::Empty => TimeIndexWindow::Empty,
174            TCell::TCell1(t, _) => {
175                if w.contains(t) {
176                    TimeIndexWindow::All(*self)
177                } else {
178                    TimeIndexWindow::Empty
179                }
180            }
181            _ => {
182                if let Some(min_val) = self.first() {
183                    if let Some(max_val) = self.last() {
184                        if min_val >= w.start && max_val < w.end {
185                            TimeIndexWindow::All(*self)
186                        } else {
187                            TimeIndexWindow::Range {
188                                timeindex: *self,
189                                range: w,
190                            }
191                        }
192                    } else {
193                        TimeIndexWindow::Empty
194                    }
195                } else {
196                    TimeIndexWindow::Empty
197                }
198            }
199        };
200        range
201    }
202
203    fn first(&self) -> Option<Self::IndexType> {
204        match self {
205            TCell::Empty => None,
206            TCell::TCell1(t, _) => Some(*t),
207            TCell::TCellCap(svm) => svm.first_key_value().map(|(ti, _)| *ti),
208            TCell::TCellN(btm) => btm.first_key_value().map(|(ti, _)| *ti),
209        }
210    }
211
212    fn last(&self) -> Option<Self::IndexType> {
213        match self {
214            TCell::Empty => None,
215            TCell::TCell1(t, _) => Some(*t),
216            TCell::TCellCap(svm) => svm.last_key_value().map(|(ti, _)| *ti),
217            TCell::TCellN(btm) => btm.last_key_value().map(|(ti, _)| *ti),
218        }
219    }
220
221    #[allow(refining_impl_trait)]
222    fn iter(self) -> impl DoubleEndedIterator<Item = Self::IndexType> + Send + Sync + 'a {
223        match self {
224            TCell::Empty => TCellVariants::Empty(std::iter::empty()),
225            TCell::TCell1(t, _) => TCellVariants::TCell1(std::iter::once(*t)),
226            TCell::TCellCap(svm) => TCellVariants::TCellCap(svm.iter().map(|(ti, _)| *ti)),
227            TCell::TCellN(btm) => TCellVariants::TCellN(btm.keys().copied()),
228        }
229    }
230
231    fn iter_rev(self) -> impl Iterator<Item = Self::IndexType> + Send + Sync + 'a {
232        TimeIndexOps::iter(self).rev()
233    }
234
235    fn len(&self) -> usize {
236        match self {
237            TCell::Empty => 0,
238            TCell::TCell1(_, _) => 1,
239            TCell::TCellCap(svm) => svm.len(),
240            TCell::TCellN(btm) => btm.len(),
241        }
242    }
243}
244
245impl<'a, A: Send + Sync> TimeIndexLike<'a> for &'a TCell<A> {
246    #[allow(refining_impl_trait)]
247    fn range_iter(
248        self,
249        w: Range<Self::IndexType>,
250    ) -> impl DoubleEndedIterator<Item = Self::IndexType> + Send + Sync + 'a {
251        self.iter_window(w).map(|(ti, _)| *ti)
252    }
253
254    fn range_iter_rev(
255        self,
256        w: Range<Self::IndexType>,
257    ) -> impl Iterator<Item = Self::IndexType> + Send + Sync + 'a {
258        self.range_iter(w).rev()
259    }
260
261    fn range_count(&self, w: Range<Self::IndexType>) -> usize {
262        match self {
263            TCell::Empty => 0,
264            TCell::TCell1(t, _) => {
265                if w.contains(t) {
266                    1
267                } else {
268                    0
269                }
270            }
271            TCell::TCellCap(ts) => ts.range(w).count(),
272            TCell::TCellN(ts) => ts.range(w).count(),
273        }
274    }
275
276    fn last_range(&self, w: Range<Self::IndexType>) -> Option<Self::IndexType> {
277        self.iter_window(w).next_back().map(|(ti, _)| *ti)
278    }
279}
280
281#[cfg(test)]
282mod tcell_tests {
283    use super::TCell;
284    use crate::storage::timeindex::{AsTime, EventTime};
285
286    #[test]
287    fn set_new_value_for_tcell_initialized_as_empty() {
288        let mut tcell = TCell::default();
289        tcell.set(EventTime::start(16), String::from("lobster"));
290
291        assert_eq!(
292            tcell.iter().map(|(_, v)| v).collect::<Vec<_>>(),
293            vec!["lobster"]
294        );
295    }
296
297    #[test]
298    fn every_new_update_to_the_same_prop_is_recorded_as_history() {
299        let mut tcell = TCell::new(EventTime::start(1), "Pometry");
300        tcell.set(EventTime::start(2), "Pometry Inc.");
301
302        assert_eq!(
303            tcell.iter_t().collect::<Vec<_>>(),
304            vec![(1, &"Pometry"), (2, &"Pometry Inc."),]
305        );
306    }
307
308    #[test]
309    fn new_update_with_the_same_time_to_a_prop_is_ignored() {
310        let mut tcell = TCell::new(EventTime::start(1), "Pometry");
311        tcell.set(EventTime::start(1), "Pometry Inc.");
312
313        assert_eq!(
314            tcell.iter_t().collect::<Vec<_>>(),
315            vec![(1, &"Pometry Inc.")]
316        );
317    }
318
319    #[test]
320    fn updates_to_prop_can_be_iterated() {
321        let tcell: TCell<String> = TCell::default();
322
323        let actual = tcell.iter().collect::<Vec<_>>();
324        let expected = vec![];
325        assert_eq!(actual, expected);
326
327        assert_eq!(tcell.iter_t().collect::<Vec<_>>(), vec![]);
328
329        let tcell = TCell::new(EventTime::start(3), "Pometry");
330
331        assert_eq!(
332            tcell.iter().collect::<Vec<_>>(),
333            vec![(&EventTime::start(3), &"Pometry")]
334        );
335
336        assert_eq!(tcell.iter_t().collect::<Vec<_>>(), vec![(3, &"Pometry")]);
337
338        let mut tcell = TCell::new(EventTime::start(2), "Pometry");
339        tcell.set(EventTime::start(1), "Inc. Pometry");
340
341        assert_eq!(
342            // Results are ordered by time
343            tcell.iter_t().collect::<Vec<_>>(),
344            vec![(1, &"Inc. Pometry"), (2, &"Pometry"),]
345        );
346
347        assert_eq!(
348            // Results are ordered by time
349            tcell.iter().collect::<Vec<_>>(),
350            vec![
351                (&EventTime::start(1), &"Inc. Pometry"),
352                (&EventTime::start(2), &"Pometry")
353            ]
354        );
355
356        let mut tcell: TCell<i64> = TCell::default();
357        for n in 1..130 {
358            tcell.set(EventTime::start(n), n)
359        }
360
361        assert_eq!(tcell.iter_t().count(), 129);
362
363        assert_eq!(tcell.iter().count(), 129)
364    }
365
366    #[test]
367    fn updates_to_prop_can_be_window_iterated() {
368        let tcell: TCell<String> = TCell::default();
369
370        let actual = tcell
371            .iter_window(EventTime::MIN..EventTime::MAX)
372            .collect::<Vec<_>>();
373        let expected = vec![];
374        assert_eq!(actual, expected);
375
376        assert_eq!(
377            tcell.iter_window_t(i64::MIN..i64::MAX).collect::<Vec<_>>(),
378            vec![]
379        );
380
381        let tcell = TCell::new(EventTime::start(3), "Pometry");
382
383        assert_eq!(
384            tcell
385                .iter_window(EventTime::range(3..4))
386                .collect::<Vec<_>>(),
387            vec![(&EventTime(3, 0), &"Pometry")]
388        );
389
390        assert_eq!(
391            tcell.iter_window_t(3..4).collect::<Vec<_>>(),
392            vec![(3, &"Pometry")]
393        );
394
395        let mut tcell = TCell::new(EventTime::start(3), "Pometry");
396        tcell.set(EventTime::start(1), "Pometry Inc.");
397        tcell.set(EventTime::start(2), "Raphtory");
398
399        let one = EventTime::start(1);
400        let two = EventTime::start(2);
401        let three = EventTime::start(3);
402
403        assert_eq!(
404            tcell.iter_window_t(2..3).collect::<Vec<_>>(),
405            vec![(2, &"Raphtory")]
406        );
407
408        let expected = vec![];
409        assert_eq!(
410            tcell
411                .iter_window(EventTime::range(4..5))
412                .collect::<Vec<_>>(),
413            expected
414        );
415
416        assert_eq!(
417            tcell
418                .iter_window(EventTime::range(1..i64::MAX))
419                .collect::<Vec<_>>(),
420            vec![
421                (&one, &"Pometry Inc."),
422                (&two, &"Raphtory"),
423                (&three, &"Pometry")
424            ]
425        );
426
427        assert_eq!(
428            tcell
429                .iter_window(EventTime::range(3..i64::MAX))
430                .collect::<Vec<_>>(),
431            vec![(&three, &"Pometry")]
432        );
433
434        assert_eq!(
435            tcell
436                .iter_window(EventTime::range(2..i64::MAX))
437                .collect::<Vec<_>>(),
438            vec![(&two, &"Raphtory"), (&three, &"Pometry")]
439        );
440
441        let expected = vec![];
442        assert_eq!(
443            tcell
444                .iter_window(EventTime::range(5..i64::MAX))
445                .collect::<Vec<_>>(),
446            expected
447        );
448
449        assert_eq!(
450            tcell
451                .iter_window(EventTime::range(i64::MIN..4))
452                .collect::<Vec<_>>(),
453            vec![
454                (&one, &"Pometry Inc."),
455                (&two, &"Raphtory"),
456                (&three, &"Pometry")
457            ]
458        );
459
460        let expected = vec![];
461        assert_eq!(
462            tcell
463                .iter_window(EventTime::range(i64::MIN..1))
464                .collect::<Vec<_>>(),
465            expected
466        );
467
468        let mut tcell: TCell<i64> = TCell::default();
469        for n in 1..130 {
470            tcell.set(EventTime::start(n), n)
471        }
472
473        assert_eq!(tcell.iter_window_t(i64::MIN..i64::MAX).count(), 129);
474
475        assert_eq!(
476            tcell
477                .iter_window(EventTime::range(i64::MIN..i64::MAX))
478                .count(),
479            129
480        )
481    }
482}
raphtory_core/entities/properties/tcell.rs

raphtory_core/entities/properties/
tcell.rs
