xq/data_structure/
mod.rs

1pub mod undo;
2
3use std::{borrow::Borrow, rc::Rc};
4
5pub type PVector<T> = imbl::Vector<T>;
6pub type PHashMap<K, V> = imbl::HashMap<K, V>;
7
8#[derive(Clone, Debug)]
9pub(crate) struct PStack<T, B = [T; 32]> {
10    prev: Option<Rc<PStack<T, B>>>,
11    current: sized_chunks::InlineArray<T, B>,
12}
13
14impl<T, B> Default for PStack<T, B> {
15    fn default() -> Self {
16        Self {
17            prev: None,
18            current: sized_chunks::InlineArray::new(),
19        }
20    }
21}
22
23#[allow(dead_code)]
24impl<T: Clone, B> PStack<T, B> {
25    pub fn new() -> Self {
26        Default::default()
27    }
28
29    pub fn push(&mut self, value: T) {
30        if self.current.is_full() {
31            let built = std::mem::take(self);
32            self.prev = Some(Rc::new(built));
33        }
34        self.current.push(value)
35    }
36
37    pub fn pop(&mut self) -> Option<T> {
38        let ret = self.current.pop();
39        if ret.is_some() {
40            ret
41        } else if let Some(p) = self.prev.take() {
42            let p: &PStack<_, _> = p.borrow();
43            self.prev = p.prev.clone();
44            self.current.clone_from(&p.current);
45            self.current.pop()
46        } else {
47            None
48        }
49    }
50
51    pub fn top(&self) -> Option<&T> {
52        if self.current.is_empty() {
53            return if let Some(p) = &self.prev {
54                p.current.last()
55            } else {
56                None
57            };
58        }
59        self.current.last()
60    }
61
62    pub fn top_mut(&mut self) -> Option<&mut T> {
63        if self.current.is_empty() {
64            if let Some(p) = self.prev.take() {
65                let p: &PStack<_, _> = p.borrow();
66                self.prev = p.prev.clone();
67                self.current.clone_from(&p.current);
68            } else {
69                return None;
70            }
71        }
72        self.current.last_mut()
73    }
74}
75
76#[cfg(test)]
77mod test {
78    use super::PStack;
79
80    #[test]
81    fn test_stack() {
82        let mut v = vec![];
83        let mut s = PStack::<usize, [usize; 4]>::new();
84        for i in 0..10 {
85            s.push(i);
86            v.push(s.clone());
87        }
88        for i in 0..10 {
89            assert_eq!(Some(9 - i), s.pop());
90        }
91        assert_eq!(None, s.pop());
92        for i in 0..10 {
93            let mut s = v[i].clone();
94            for j in 0..=i {
95                assert_eq!(Some(i - j), s.pop());
96            }
97            assert_eq!(None, s.pop());
98        }
99    }
100}
xq/data_structure/mod.rs

xq/data_structure/
mod.rs
