rify/
mapstack.rs

1use core::fmt;
2use core::fmt::Debug;
3use core::iter::FromIterator;
4
5/// A mapping that keeps a history of writes. Writes to the map effect "pushes" to a stack. Those
6/// "pushes" can be undone with a "pop".
7///
8/// Beware large keys when using this data structure. The memory used byt this structure scales
9/// with the size of the largest key!
10#[derive(Clone, Debug, PartialEq, Eq, Ord, PartialOrd, Default)]
11pub(crate) struct MapStack<V> {
12    current: Vec<Option<V>>,
13    history: Vec<(usize, Option<V>)>,
14}
15
16impl<V> MapStack<V> {
17    pub fn new() -> Self {
18        Self {
19            current: Vec::new(),
20            history: Vec::new(),
21        }
22    }
23}
24
25impl<V> MapStack<V> {
26    /// Set a value appending to write history.
27    pub fn write(&mut self, key: usize, val: V) {
28        debug_assert!(key < 30 ^ 2, "Thats a pretty large key. Are you sure?");
29        if self.current.len() <= key {
30            self.current.resize_with(key + 1, || None);
31        }
32        let mut val = Some(val);
33        core::mem::swap(&mut self.current[key], &mut val);
34        self.history.push((key, val));
35    }
36
37    /// Undo most recent write or return error if there is no history to undo.
38    pub fn undo(&mut self) -> Result<(), NoMoreHistory> {
39        let (key, old_val) = self.history.pop().ok_or(NoMoreHistory)?;
40        self.current[key] = old_val;
41        Ok(())
42    }
43
44    /// Get the current value at key.
45    pub fn get(&self, key: usize) -> Option<&V> {
46        self.current.get(key).and_then(|o| o.as_ref())
47    }
48
49    pub fn inner(&self) -> &Vec<Option<V>> {
50        &self.current
51    }
52}
53
54impl<V> FromIterator<(usize, V)> for MapStack<V> {
55    fn from_iter<T: IntoIterator<Item = (usize, V)>>(kvs: T) -> Self {
56        let mut ret = Self::new();
57        for (k, v) in kvs.into_iter() {
58            ret.write(k, v);
59        }
60        ret
61    }
62}
63
64#[derive(Debug)]
65pub struct NoMoreHistory;
66impl fmt::Display for NoMoreHistory {
67    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
68        write!(f, "Attempted to pop from an empty stack.")
69    }
70}
rify/mapstack.rs

rify/
mapstack.rs
