raphtory_core/entities/properties/
tcell.rs

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

raphtory_core/entities/properties/
tcell.rs
