indexed_vector/
hashmap.rs

1use std::{collections::HashMap, hash::Hash, slice::Iter};
2
3use crate::IndexedVector;
4
5/// A simple implementation of `IndexedVector` using `HashMap`.
6pub struct HashIndexedVector<K, V> {
7    map: HashMap<K, Vec<V>>,
8    key_func: Box<dyn Fn(&V) -> K>,
9}
10
11impl<K: Eq + Hash, V> HashIndexedVector<K, V> {
12    /// Create a new `HashIndexedVector` from a vector of items.
13    /// The `key_func` is used to extract the key from an item.
14    pub fn new<F: Fn(&V) -> K + 'static, C: IntoIterator<Item = V>>(data: C, key_func: F) -> Self {
15        let mut map = HashMap::new();
16        for item in data {
17            let key = key_func(&item);
18            map.entry(key).or_insert_with(Vec::new).push(item);
19        }
20        Self {
21            map,
22            key_func: Box::new(key_func),
23        }
24    }
25}
26
27impl<K: Eq + Hash, V> IndexedVector<K, V> for HashIndexedVector<K, V> {
28    fn search(&self, key: &K) -> Iter<'_, V> {
29        self.map.get(key).map_or([].iter(), |v| v.iter())
30    }
31
32    fn insert(&mut self, item: V) {
33        let key = (self.key_func)(&item);
34        self.map.entry(key).or_insert_with(Vec::new).push(item);
35    }
36}
37
38#[cfg(test)]
39mod test {
40    use crate::{HashIndexedVector, IndexedVector};
41
42    #[test]
43    fn test_hash_indexed_map() {
44        let mut map = HashIndexedVector::new(
45            vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
46            Box::new(|x: &i32| x % 3),
47        );
48        assert_eq!(map.search(&0).collect::<Vec<_>>(), vec![&3, &6, &9]);
49        assert_eq!(map.search(&1).collect::<Vec<_>>(), vec![&1, &4, &7, &10]);
50        assert_eq!(map.search(&2).collect::<Vec<_>>(), vec![&2, &5, &8]);
51        map.insert(11);
52        assert_eq!(map.search(&0).collect::<Vec<_>>(), vec![&3, &6, &9]);
53        assert_eq!(map.search(&1).collect::<Vec<_>>(), vec![&1, &4, &7, &10]);
54        assert_eq!(map.search(&2).collect::<Vec<_>>(), vec![&2, &5, &8, &11]);
55    }
56}
indexed_vector/hashmap.rs

indexed_vector/
hashmap.rs
