1/// A collection that provides a map interface but is backed by vectors.
  2///
  3/// This is suitable for small key-value stores where the item count is not
  4/// large enough to overcome the overhead of a more complex algorithm.
  5///
  6/// If this meets your use cases, then [`VecMap`] should be a drop-in
  7/// replacement for [`std::collections::HashMap`] or [`crate::HashMap`]. Note
  8/// that we are adding APIs on an as-needed basis. If the API you need is not
  9/// present yet, please add it!
 10///
 11/// Because it uses vectors as a backing store, the map also iterates over items
 12/// in insertion order, like [`crate::IndexMap`].
 13///
 14/// This struct uses a struct-of-arrays (SoA) representation which tends to be
 15/// more cache efficient and promotes autovectorization when using simple key or
 16/// value types.
 17#[derive(Default)]
 18pub struct VecMap<K, V> {
 19    keys: Vec<K>,
 20    values: Vec<V>,
 21}
 22
 23impl<K, V> VecMap<K, V> {
 24    pub fn new() -> Self {
 25        Self {
 26            keys: Vec::new(),
 27            values: Vec::new(),
 28        }
 29    }
 30
 31    pub fn iter(&self) -> Iter<'_, K, V> {
 32        Iter {
 33            iter: self.keys.iter().zip(self.values.iter()),
 34        }
 35    }
 36}
 37
 38impl<K: Eq, V> VecMap<K, V> {
 39    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
 40        match self.keys.iter().position(|k| k == &key) {
 41            Some(index) => Entry::Occupied(OccupiedEntry {
 42                key: &self.keys[index],
 43                value: &mut self.values[index],
 44            }),
 45            None => Entry::Vacant(VacantEntry { map: self, key }),
 46        }
 47    }
 48}
 49
 50pub struct Iter<'a, K, V> {
 51    iter: std::iter::Zip<std::slice::Iter<'a, K>, std::slice::Iter<'a, V>>,
 52}
 53
 54impl<'a, K, V> Iterator for Iter<'a, K, V> {
 55    type Item = (&'a K, &'a V);
 56
 57    fn next(&mut self) -> Option<Self::Item> {
 58        self.iter.next()
 59    }
 60}
 61
 62pub enum Entry<'a, K, V> {
 63    Occupied(OccupiedEntry<'a, K, V>),
 64    Vacant(VacantEntry<'a, K, V>),
 65}
 66
 67impl<'a, K, V> Entry<'a, K, V> {
 68    pub fn key(&self) -> &K {
 69        match self {
 70            Entry::Occupied(entry) => entry.key,
 71            Entry::Vacant(entry) => &entry.key,
 72        }
 73    }
 74
 75    pub fn or_insert_with_key<F>(self, default: F) -> &'a mut V
 76    where
 77        F: FnOnce(&K) -> V,
 78    {
 79        match self {
 80            Entry::Occupied(entry) => entry.value,
 81            Entry::Vacant(entry) => {
 82                entry.map.values.push(default(&entry.key));
 83                entry.map.keys.push(entry.key);
 84                match entry.map.values.last_mut() {
 85                    Some(value) => value,
 86                    None => unreachable!("vec empty after pushing to it"),
 87                }
 88            }
 89        }
 90    }
 91
 92    pub fn or_insert_with<F>(self, default: F) -> &'a mut V
 93    where
 94        F: FnOnce() -> V,
 95    {
 96        self.or_insert_with_key(|_| default())
 97    }
 98
 99    pub fn or_insert(self, value: V) -> &'a mut V {
100        self.or_insert_with_key(|_| value)
101    }
102
103    pub fn or_insert_default(self) -> &'a mut V
104    where
105        V: Default,
106    {
107        self.or_insert_with_key(|_| Default::default())
108    }
109}
110
111pub struct OccupiedEntry<'a, K, V> {
112    key: &'a K,
113    value: &'a mut V,
114}
115
116pub struct VacantEntry<'a, K, V> {
117    map: &'a mut VecMap<K, V>,
118    key: K,
119}