haar_lib/ds/
partially_persistent_array.rs

1//! 部分永続配列
2
3/// 部分永続配列
4#[derive(Clone, Debug)]
5pub struct PartiallyPersistentArray<T> {
6    time: usize,
7    data: Vec<Vec<(usize, T)>>,
8}
9
10impl<T: Clone> PartiallyPersistentArray<T> {
11    /// 値`value`を`n`個もつ配列を作る。
12    pub fn new(value: T, n: usize) -> Self {
13        Self {
14            time: 0,
15            data: vec![vec![(0, value)]; n],
16        }
17    }
18
19    /// 最新時刻を返す。
20    pub fn latest(&self) -> usize {
21        self.time
22    }
23
24    /// 最新の配列の`index`番目の要素を`value`で更新する。
25    pub fn set(&mut self, index: usize, value: T) {
26        self.time += 1;
27        self.data[index].push((self.time, value));
28    }
29
30    /// 時刻`time`での配列の`index`番目の要素を返す。
31    pub fn get(&self, index: usize, time: usize) -> &T {
32        match self.data[index].binary_search_by_key(&time, |a| a.0) {
33            Ok(i) => &self.data[index][i].1,
34            Err(i) => &self.data[index][i - 1].1,
35        }
36    }
37
38    /// 時刻`time`での配列へのイテレータを返す。
39    pub fn iter_at(&self, time: usize) -> impl Iterator<Item = &T> {
40        self.data
41            .iter()
42            .map(move |a| match a.binary_search_by_key(&time, |a| a.0) {
43                Ok(i) => &a[i].1,
44                Err(i) => &a[i - 1].1,
45            })
46    }
47}
48
49#[cfg(test)]
50mod tests {
51    use crate::iter::collect::CollectVec;
52
53    use super::*;
54    use rand::Rng;
55
56    #[test]
57    fn test() {
58        let mut rng = rand::thread_rng();
59
60        let n = 10;
61        let t = 100;
62        let mut a = PartiallyPersistentArray::new(0, n);
63        let mut b = vec![0; n];
64
65        let mut history = vec![b.clone()];
66
67        for _ in 0..t {
68            let i = rng.gen_range(0..n);
69            let x = rng.gen::<u32>();
70
71            b[i] = x;
72            a.set(i, x);
73
74            history.push(b.clone());
75        }
76
77        for time in 0..=t {
78            assert_eq!(history[time], a.iter_at(time).cloned().collect_vec());
79        }
80    }
81}
haar_lib/ds/partially_persistent_array.rs

haar_lib/ds/
partially_persistent_array.rs
