composable_indexes/index/im/
hashtable.rs

1//! An index backed by [`imbl::HashMap`]. Provides efficient
2//! lookups by key with O(log n) time complexity using
3//! persistent immutable data structures.
4
5use alloc::vec::Vec;
6use core::hash::Hash;
7
8use imbl::HashMap;
9
10use crate::{
11    ShallowClone,
12    core::{Index, Insert, Key, Remove, Seal},
13    index::generic::{DefaultImmutableKeySet, KeySet},
14};
15
16#[derive(Clone)]
17pub struct HashTable<T, KeySet = DefaultImmutableKeySet> {
18    data: HashMap<T, KeySet>,
19}
20
21impl<T: Eq + Hash + Clone, KeySet_: KeySet + Default> Default for HashTable<T, KeySet_> {
22    fn default() -> Self {
23        Self::new()
24    }
25}
26
27impl<T: Eq + Hash + Clone, KeySet_: KeySet + Default> HashTable<T, KeySet_> {
28    pub fn new() -> Self {
29        HashTable {
30            data: HashMap::new(),
31        }
32    }
33}
34
35impl<T: Clone, KeySet_: Clone> ShallowClone for HashTable<T, KeySet_> {}
36
37impl<In, KeySet_> Index<In> for HashTable<In, KeySet_>
38where
39    In: Eq + Hash + Clone,
40    KeySet_: KeySet + Clone,
41{
42    fn insert(&mut self, _seal: Seal, op: &Insert<In>) {
43        let mut set = self.data.get(op.new).cloned().unwrap_or_default();
44        set.insert(op.key);
45        self.data.insert(op.new.clone(), set);
46    }
47
48    fn remove(&mut self, _seal: Seal, op: &Remove<In>) {
49        let existing = self.data.get_mut(op.existing).unwrap();
50        existing.remove(&op.key);
51        if existing.is_empty() {
52            self.data.remove(op.existing);
53        }
54    }
55}
56
57impl<In, KeySet_: KeySet> HashTable<In, KeySet_> {
58    pub fn contains(&self, key: &In) -> bool
59    where
60        In: Eq + Hash,
61    {
62        self.data.contains_key(key)
63    }
64
65    pub fn count_distinct(&self) -> usize
66    where
67        In: Eq + Hash,
68    {
69        self.data.len()
70    }
71
72    pub fn get_one(&self, key: &In) -> Option<Key>
73    where
74        In: Eq + Hash,
75    {
76        self.data.get(key).and_then(|v| v.iter().next())
77    }
78
79    pub fn get_all(&self, key: &In) -> Vec<Key>
80    where
81        In: Eq + Hash,
82    {
83        self.data
84            .get(key)
85            .map(|v| v.iter().collect())
86            .unwrap_or_default()
87    }
88
89    pub fn all(&self) -> imbl::HashSet<Key> {
90        self.data.values().flat_map(|keys| keys.iter()).collect()
91    }
92}
93
94#[cfg(test)]
95mod tests {
96    use imbl::HashSet;
97
98    use crate::testutils::prop_assert_reference;
99
100    use super::*;
101
102    #[test]
103    fn test_lookup() {
104        prop_assert_reference(
105            || HashTable::<u8>::new(),
106            |db| db.query(|ix| ix.contains(&1)),
107            |xs| xs.iter().find(|i| **i == 1).is_some(),
108            None,
109        );
110    }
111
112    #[test]
113    fn test_count_distinct() {
114        prop_assert_reference(
115            || HashTable::<u8>::new(),
116            |db| db.query(|ix| ix.count_distinct()),
117            |xs| xs.iter().cloned().collect::<HashSet<u8>>().len(),
118            None,
119        );
120    }
121}
composable_indexes/index/im/hashtable.rs

composable_indexes/index/im/
hashtable.rs
