scoped_stack/
lib.rs

1use std::collections::HashMap;
2
3/// A scoped stack is a stack of hashmaps that allows you to push and pop scopes.
4/// When you push a scope, a new hashmap is created and pushed onto the stack.
5/// When you pop a scope, the top hashmap is popped off the stack.
6/// When you insert a value, it is inserted into the top hashmap.
7/// When you get a value, it is searched for in the top hashmap, and if it is not found, it is searched for in the next hashmap down the stack.
8/// When you remove a value, it is removed from the top hashmap, and if it is not found, it is removed from the next hashmap down the stack.
9#[derive(Debug, Clone, PartialEq)]
10pub struct ScopedStack<K, V>
11where
12  K: std::cmp::Eq + std::hash::Hash,
13{
14  values: HashMap<K, V>,
15  child: Option<Box<ScopedStack<K, V>>>,
16}
17
18impl<K, V> ScopedStack<K, V>
19where
20  K: std::cmp::Eq + std::hash::Hash,
21{
22  /// Creates a new scoped stack.
23  pub fn new() -> Self {
24    ScopedStack {
25      values: HashMap::new(),
26      child: None,
27    }
28  }
29
30  /// Pushes a new scope onto the stack.
31  pub fn push_scope(&mut self) {
32    if let Some(child) = self.child.as_mut() {
33      child.push_scope();
34    } else {
35      self.child = Some(Box::new(ScopedStack::new()));
36    }
37  }
38
39  /// Pops the top scope off the stack.
40  pub fn pop_scope(&mut self) {
41    if let Some(child) = self.child.as_mut() {
42      if child.child.is_some() {
43        child.pop_scope();
44      } else {
45        self.child = None;
46      }
47    } else {
48      self.child = None;
49    }
50  }
51
52  /// Inserts a value into the top scope.
53  pub fn insert(&mut self, key: K, value: V) {
54    if let Some(child) = self.child.as_mut() {
55      child.insert(key, value);
56    } else {
57      self.values.insert(key, value);
58    }
59  }
60
61  /// Inserts a value at the bottom-most scope where the key already exists (or the bottom scope if it does not exist)
62  pub fn insert_existing(&mut self, key: K, value: V) {
63    if self.values.contains_key(&key) {
64      self.values.insert(key, value);
65    } else if let Some(child) = self.child.as_mut() {
66      child.insert_existing(key, value);
67    } else {
68      self.values.insert(key, value);
69    }
70  }
71
72  /// Gets a value from the top scope, or any scope below it if it is not found in the top scope.
73  pub fn get(&self, key: &K) -> Option<&V> {
74    let mut value = self.values.get(key);
75    let mut child = self.child.as_ref();
76
77    loop {
78      match child {
79        Some(c) => {
80          if let Some(v) = c.values.get(key) {
81            value = Some(v);
82          }
83          child = c.child.as_ref();
84        }
85        None => break,
86      }
87    }
88
89    value
90  }
91
92  /// Checks if a value exists in the top scope, or any scope below it.
93  pub fn has(&self, key: &K) -> bool {
94    self.get(key).is_some()
95  }
96
97  /// Removes a value from the top scope, or any scope below it if it is not found in the top scope.
98  pub fn remove(&mut self, key: &K) -> Option<V> {
99    if let Some(child) = self.child.as_mut() {
100      child.remove(key)
101    } else {
102      self.values.remove(key)
103    }
104  }
105}
106
107impl<K, V> Into<HashMap<K, V>> for ScopedStack<K, V>
108where
109  K: std::cmp::Eq + std::hash::Hash,
110{
111  fn into(self) -> HashMap<K, V> {
112    let mut values = self.values;
113    if let Some(child) = self.child {
114      values.extend::<HashMap<K, V>>((*child).into());
115    }
116    values
117  }
118}
119
120#[cfg(test)]
121mod tests {
122  use super::*;
123
124  #[test]
125  fn test_new() {
126    let stack = ScopedStack::<String, String>::new();
127    assert_eq!(stack.values.len(), 0);
128    assert_eq!(stack.child, None);
129  }
130
131  #[test]
132  fn test_push() {
133    let mut stack = ScopedStack::<String, String>::new();
134    stack.push_scope();
135    assert_eq!(stack.values.len(), 0);
136    assert_eq!(stack.child.is_some(), true);
137  }
138
139  #[test]
140  fn test_push_scope() {
141    let mut stack = ScopedStack::<String, String>::new();
142    stack.push_scope();
143    assert_eq!(stack.values.len(), 0);
144    assert_eq!(stack.child.is_some(), true);
145  }
146
147  #[test]
148  fn test_pop() {
149    let mut stack = ScopedStack::<String, String>::new();
150    stack.push_scope();
151    stack.pop_scope();
152    assert_eq!(stack.values.len(), 0);
153    assert_eq!(stack.child, None);
154  }
155
156  #[test]
157  fn test_pop_scope() {
158    let mut stack = ScopedStack::<String, String>::new();
159    stack.push_scope();
160    stack.pop_scope();
161    assert_eq!(stack.values.len(), 0);
162    assert_eq!(stack.child, None);
163  }
164
165  #[test]
166  fn test_insert() {
167    let mut stack = ScopedStack::<String, String>::new();
168    stack.insert("foo".to_string(), "bar".to_string());
169    assert_eq!(stack.values.len(), 1);
170    assert_eq!(stack.values.get("foo"), Some(&"bar".to_string()));
171    assert_eq!(stack.child, None);
172  }
173
174  #[test]
175  fn test_insert_scope() {
176    let mut stack = ScopedStack::<String, String>::new();
177    stack.push_scope();
178    stack.insert("foo".to_string(), "bar".to_string());
179    assert_eq!(stack.values.len(), 0);
180    assert_eq!(stack.child.is_some(), true);
181    assert_eq!(stack.child.as_ref().unwrap().values.len(), 1);
182    assert_eq!(stack.get(&"foo".to_string()), Some(&"bar".to_string()));
183  }
184
185  #[test]
186  fn test_insert_existing_scope() {
187    let mut stack = ScopedStack::<String, String>::new();
188    stack.insert("foo".to_string(), "bar".to_string());
189    stack.push_scope();
190    stack.insert_existing("foo".to_string(), "baz".to_string());
191    stack.pop_scope();
192    assert_eq!(stack.values.len(), 1);
193    assert_eq!(stack.child, None);
194    assert_eq!(stack.get(&"foo".to_string()), Some(&"baz".to_string()));
195  }
196
197  #[test]
198  fn test_get() {
199    let mut stack = ScopedStack::<String, String>::new();
200    stack.insert("foo".to_string(), "bar".to_string());
201    assert_eq!(stack.get(&"foo".to_string()), Some(&"bar".to_string()));
202  }
203
204  #[test]
205  fn test_get_scope() {
206    let mut stack = ScopedStack::<String, String>::new();
207    stack.insert("foo".to_string(), "bar".to_string());
208    stack.push_scope();
209    stack.insert("foo".to_string(), "baz".to_string());
210    assert_eq!(stack.get(&"foo".to_string()), Some(&"baz".to_string()));
211  }
212
213  #[test]
214  fn test_has() {
215    let mut stack = ScopedStack::<String, String>::new();
216    stack.insert("foo".to_string(), "bar".to_string());
217    assert_eq!(stack.has(&"foo".to_string()), true);
218  }
219
220  #[test]
221  fn test_has_scope() {
222    let mut stack = ScopedStack::<String, String>::new();
223    stack.insert("foo".to_string(), "bar".to_string());
224    stack.push_scope();
225    stack.insert("foo".to_string(), "baz".to_string());
226    assert_eq!(stack.has(&"foo".to_string()), true);
227  }
228
229  #[test]
230  fn test_remove() {
231    let mut stack = ScopedStack::<String, String>::new();
232    stack.insert("foo".to_string(), "bar".to_string());
233    assert_eq!(stack.remove(&"foo".to_string()), Some("bar".to_string()));
234    assert_eq!(stack.values.len(), 0);
235  }
236
237  #[test]
238  fn test_remove_scope() {
239    let mut stack = ScopedStack::<String, String>::new();
240    stack.insert("foo".to_string(), "bar".to_string());
241    stack.push_scope();
242    stack.insert("foo".to_string(), "baz".to_string());
243    assert_eq!(stack.remove(&"foo".to_string()), Some("baz".to_string()));
244    assert_eq!(stack.values.len(), 1);
245    assert_eq!(stack.get(&"foo".to_string()), Some(&"bar".to_string()));
246  }
247
248  #[test]
249  fn test_into() {
250    let mut stack = ScopedStack::<String, String>::new();
251    stack.insert("foo".to_string(), "bar".to_string());
252    stack.push_scope();
253    stack.insert("foo".to_string(), "baz".to_string());
254    let map: HashMap<String, String> = stack.into();
255    assert_eq!(map.len(), 1);
256    assert_eq!(map.get(&"foo".to_string()), Some(&"baz".to_string()));
257  }
258}
scoped_stack/lib.rs

scoped_stack/
lib.rs
