Revision control
Copy as Markdown
Other Tools
use std::mem;
/// A small map backed by an unsorted vector.
///
/// Maintains key uniqueness at cost of O(n) lookup/insert/remove. Maintains insertion order
/// (`insert` calls that overwrite an existing value don't change order).
#[derive(Clone, Default)]
pub struct VecMap<K, V>(Vec<(K, V)>);
impl<K: Eq, V> VecMap<K, V> {
pub fn new() -> Self {
VecMap(Vec::new())
}
pub fn is_empty(&self) -> bool {
self.0.is_empty()
}
pub fn clear(&mut self) {
self.0.clear();
}
fn find(&self, key: &K) -> Option<usize> {
for (i, (k, _)) in self.0.iter().enumerate() {
if k == key {
return Some(i);
}
}
None
}
pub fn contains(&self, key: &K) -> bool {
self.find(key).is_some()
}
pub fn get(&self, key: &K) -> Option<&V> {
match self.find(key) {
Some(i) => Some(&self.0[i].1),
None => None,
}
}
pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
match self.find(key) {
Some(i) => Some(&mut self.0[i].1),
None => None,
}
}
pub fn insert(&mut self, key: K, value: V) -> Option<V> {
if let Some(old) = self.get_mut(&key) {
return Some(mem::replace(old, value));
}
self.0.push((key, value));
None
}
pub fn remove(&mut self, key: &K) -> Option<V> {
match self.find(key) {
Some(i) => Some(self.0.remove(i).1),
None => None,
}
}
pub fn values(&self) -> impl Iterator<Item = &V> {
self.0.iter().map(|kv| &kv.1)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn empty() {
let m: VecMap<char, u32> = VecMap::new();
assert!(m.is_empty());
assert!(!m.contains(&'a'));
assert!(m.values().next().is_none());
}
#[test]
fn insert_update_get() {
let mut m: VecMap<char, u32> = VecMap::new();
assert!(m.insert('a', 1).is_none());
assert!(m.insert('b', 2).is_none());
assert_eq!(m.get(&'a'), Some(&1));
assert_eq!(m.get(&'b'), Some(&2));
*m.get_mut(&'a').unwrap() += 10;
assert_eq!(m.get(&'a'), Some(&11));
assert_eq!(m.get(&'b'), Some(&2));
}
#[test]
fn insert_overwrite() {
let mut m = VecMap::new();
assert_eq!(m.insert('a', 1), None);
assert_eq!(m.insert('b', 2), None);
assert_eq!(m.insert('a', 3), Some(1));
assert_eq!(m.insert('a', 4), Some(3));
assert_eq!(m.get(&'a').copied(), Some(4));
assert_eq!(m.get(&'b').copied(), Some(2));
assert_eq!(m.insert('b', 5), Some(2));
assert_eq!(m.get(&'a').copied(), Some(4));
assert_eq!(m.get(&'b').copied(), Some(5));
}
#[test]
fn insert_remove() {
let mut m: VecMap<char, u32> = VecMap::new();
assert_eq!(m.remove(&'a'), None);
m.insert('a', 1);
m.insert('b', 2);
assert_eq!(m.remove(&'a'), Some(1));
assert_eq!(m.remove(&'a'), None);
assert_eq!(m.remove(&'b'), Some(2));
assert!(m.is_empty());
}
#[test]
fn insertion_order() {
let mut m: VecMap<char, u32> = VecMap::new();
let values = |m: &VecMap<char, u32>| -> Vec<u32> { m.values().copied().collect() };
m.insert('b', 2);
m.insert('a', 1);
m.insert('c', 3);
assert_eq!(values(&m), vec![2, 1, 3]);
m.insert('a', 11);
m.remove(&'b');
assert_eq!(values(&m), vec![11, 3]);
m.insert('b', 2);
assert_eq!(values(&m), vec![11, 3, 2]);
}
#[test]
fn containment_equivalences() {
let mut m = VecMap::new();
for i in 0u8..=255 {
if i % 10 < 3 {
m.insert(i, i);
}
}
for i in 0u8..=255 {
if m.contains(&i) {
assert_eq!(m.get(&i).copied(), Some(i));
assert_eq!(m.get_mut(&i).copied(), Some(i));
assert_eq!(m.insert(i, i), Some(i));
assert_eq!(m.remove(&i), Some(i));
} else {
assert!(m.get(&i).is_none());
assert!(m.get_mut(&i).is_none());
assert!(m.remove(&i).is_none());
assert!(m.insert(i, i).is_none());
}
}
}
#[test]
fn clear() {
let mut m = VecMap::new();
m.clear();
assert!(m.is_empty());
m.insert('a', 1);
m.insert('b', 2);
assert!(!m.is_empty());
m.clear();
assert!(m.is_empty());
m.insert('c', 3);
assert!(!m.is_empty());
}
}