posix_regex/
immut_vec.rs

1use alloc::vec::Vec;
2use core::cell::RefCell;
3
4pub struct ImmutVecItem<T> {
5    prev: Option<usize>,
6    data: T,
7}
8
9#[derive(Copy, Clone)]
10pub struct ImmutVec<'a, T> {
11    inner: &'a RefCell<Vec<ImmutVecItem<T>>>,
12    id: Option<usize>,
13}
14
15impl<'a, T> ImmutVec<'a, T> {
16    pub fn new(inner: &'a RefCell<Vec<ImmutVecItem<T>>>) -> Self {
17        Self { inner, id: None }
18    }
19    #[must_use = "push does nothing to the original vector"]
20    pub fn push(self, item: T) -> Self {
21        let mut inner = self.inner.borrow_mut();
22        let id = inner.len();
23        inner.push(ImmutVecItem {
24            prev: self.id,
25            data: item,
26        });
27        Self {
28            id: Some(id),
29            ..self
30        }
31    }
32}
33
34impl<'a, T: Copy> ImmutVec<'a, T> {
35    #[must_use = "pop does nothing to the original vector"]
36    pub fn pop(self) -> (Self, Option<T>) {
37        let inner = self.inner.borrow();
38        let id = match self.id {
39            None => return (self, None),
40            Some(id) => id,
41        };
42        let item = &inner[id];
43        (
44            Self {
45                id: item.prev,
46                ..self
47            },
48            Some(item.data),
49        )
50    }
51    pub fn iter_rev(self) -> ImmutVecIter<'a, T> {
52        ImmutVecIter(self)
53    }
54}
55
56pub struct ImmutVecIter<'a, T: Copy>(ImmutVec<'a, T>);
57impl<T: Copy> Iterator for ImmutVecIter<'_, T> {
58    type Item = T;
59
60    fn next(&mut self) -> Option<Self::Item> {
61        let (new, item) = self.0.pop();
62        self.0 = new;
63        item
64    }
65}
66
67#[cfg(test)]
68mod tests {
69    use alloc::vec::Vec;
70    use core::cell::RefCell;
71
72    use super::ImmutVec;
73
74    #[test]
75    fn immutvec_iter_works() {
76        let cell = RefCell::new(Vec::new());
77        let mut iv = ImmutVec::new(&cell);
78
79        for i in 0..=100 {
80            iv = iv.push(i);
81        }
82        assert_eq!(Some(100), iv.id);
83
84        for (i, j) in iv.iter_rev().zip(100..=0) {
85            assert_eq!(i, j);
86        }
87    }
88
89    #[test]
90    fn push_to_rewound_vec_sets_correct_id() {
91        let cell = RefCell::new(Vec::new());
92        let mut iv = ImmutVec::new(&cell);
93
94        for i in 0..10 {
95            iv = iv.push(i);
96        }
97        assert_eq!(Some(9), iv.id);
98
99        for _ in 0..10 {
100            (iv, _) = iv.pop();
101        }
102        assert_eq!(
103            10,
104            iv.inner.borrow().len(),
105            "Length shouldn't change from popping items"
106        );
107
108        // Pushing an item should append to the end regardless of where we are in the vector
109        assert_eq!(None, iv.id);
110        iv = iv.push(10);
111        assert_eq!(11, iv.inner.borrow().len());
112        assert_eq!(Some(10), iv.id);
113    }
114}
posix_regex/immut_vec.rs

posix_regex/
immut_vec.rs
