toolbox_rs/
tiny_table.rs

1/// hash table semantics build over an unsorted vector and linear search.
2/// This is fast for small data sets with small keys up to dozens of entries.
3pub struct TinyTable<K, V> {
4    data: Vec<(K, V)>,
5}
6
7impl<K: Clone + Copy + PartialEq, V: Clone + Copy> TinyTable<K, V> {
8    pub fn contains(&self, k: &K) -> bool {
9        self.data.iter().any(|x| -> bool { x.0 == *k })
10    }
11
12    pub fn find(&self, k: &K) -> Option<&V> {
13        if let Some(entry) = self.data.iter().find(|x| x.0 == *k) {
14            return Some(&entry.1);
15        }
16        None
17    }
18
19    pub fn remove(&mut self, k: &K) -> bool {
20        if let Some(index) = self.data.iter().position(|value| value.0 == *k) {
21            self.data.swap_remove(index);
22            return true;
23        }
24        false
25    }
26
27    pub fn find_mut(&mut self, k: &K) -> Option<&mut (K, V)> {
28        self.data.iter_mut().find(|x| x.0 == *k)
29    }
30
31    pub fn insert(&mut self, k: K, v: V) -> bool {
32        let result = self.remove(&k);
33        self.data.push((k, v));
34        result
35    }
36
37    pub fn new() -> Self {
38        TinyTable { data: Vec::new() }
39    }
40
41    pub fn len(&self) -> usize {
42        self.data.len()
43    }
44
45    pub fn is_empty(&self) -> bool {
46        self.data.is_empty()
47    }
48
49    pub fn clear(&mut self) {
50        self.data.clear();
51    }
52}
53
54impl<K: Clone + Copy + PartialEq, V: Clone + Copy> Default for TinyTable<K, V> {
55    fn default() -> Self {
56        Self::new()
57    }
58}
59
60// TODO: proper implementation, rather than using unit type that must be explicitly provided
61pub type TinySet<K> = TinyTable<K, ()>;
62
63#[cfg(test)]
64mod tests {
65    use crate::tiny_table::{TinySet, TinyTable};
66
67    #[test]
68    fn insert_find_remove_table() {
69        let mut table = TinyTable::new();
70        assert!(table.is_empty());
71
72        table.insert(1, 999);
73        table.insert(0, 31337);
74
75        assert_eq!(table.len(), 2);
76        assert_eq!(table.find(&1), Some(&999));
77        assert_eq!(table.find(&0), Some(&31337));
78        assert!(table.contains(&0));
79        assert!(table.contains(&1));
80        assert!(!table.contains(&2));
81
82        table.remove(&1);
83        assert_eq!(table.len(), 1);
84        assert_eq!(table.find(&1), None);
85        assert_eq!(table.find(&0), Some(&31337));
86        assert!(table.contains(&0));
87        assert!(!table.contains(&1));
88        assert!(!table.contains(&2));
89
90        table.insert(7, 0xbeef);
91        assert_eq!(table.len(), 2);
92        assert_eq!(table.find(&1), None);
93        assert_eq!(table.find(&7), Some(&0xbeef));
94        assert_eq!(table.find(&0), Some(&31337));
95        assert!(table.contains(&0));
96        assert!(!table.contains(&1));
97        assert!(!table.contains(&2));
98        assert!(table.contains(&7));
99
100        table.clear();
101        assert!(table.is_empty());
102    }
103
104    #[test]
105    fn insert_find_remove_set() {
106        let mut table = TinySet::new();
107        assert!(table.is_empty());
108
109        table.insert(1, ());
110        table.insert(0, ());
111
112        assert_eq!(table.len(), 2);
113        assert!(table.find(&1).is_some());
114        assert!(table.find(&0).is_some());
115        assert!(table.contains(&0));
116        assert!(table.contains(&1));
117        assert!(!table.contains(&2));
118
119        assert!(table.remove(&1));
120        assert_eq!(table.len(), 1);
121        assert!(table.find(&1).is_none());
122        assert!(table.find(&0).is_some());
123        assert!(table.contains(&0));
124        assert!(!table.contains(&1));
125        assert!(!table.contains(&2));
126
127        table.insert(7, ());
128        assert_eq!(table.len(), 2);
129        assert!(table.find(&1).is_none());
130        assert!(table.find(&7).is_some());
131        assert!(table.find(&0).is_some());
132        assert!(table.contains(&0));
133        assert!(!table.contains(&1));
134        assert!(!table.contains(&2));
135        assert!(table.contains(&7));
136
137        table.clear();
138        assert!(table.is_empty());
139    }
140
141    #[test]
142    fn insert_find_mut() {
143        let mut table = TinyTable::<i32, i32>::default();
144        assert!(table.is_empty());
145
146        table.insert(1, 1);
147        table.insert(0, 2);
148
149        assert_eq!(table.find(&0), Some(&2));
150        if let Some(entry) = table.find_mut(&0) {
151            entry.1 = 0;
152        }
153        assert_eq!(table.find(&0).unwrap(), &0);
154
155        assert_eq!(table.find(&2), None);
156        if let Some(entry) = table.find_mut(&1) {
157            entry.0 = 2;
158            entry.1 = 2;
159        }
160        assert_eq!(table.find(&2).unwrap(), &2);
161    }
162}
toolbox_rs/tiny_table.rs

toolbox_rs/
tiny_table.rs
