scopegraphs_prust_lib/
hashmap.rs

1use std::{
2    collections::hash_map::DefaultHasher,
3    fmt::Debug,
4    hash::{Hash, Hasher},
5    marker::PhantomData,
6};
7
8use crate::trie::Trie;
9
10#[derive(Clone)]
11pub struct HashMap<K, V = ()> {
12    trie: Trie<bool, KeyValue<K, V>>,
13    phantom: PhantomData<K>,
14}
15
16pub type HashSet<K> = HashMap<K, ()>;
17
18#[derive(Clone, Debug)]
19struct KeyValue<K, V> {
20    key: K,
21    value: Option<V>,
22}
23
24impl<K: PartialEq, V> PartialEq for KeyValue<K, V> {
25    fn eq(&self, other: &Self) -> bool {
26        self.key == other.key
27    }
28}
29
30impl<K, V> Default for HashMap<K, V> {
31    fn default() -> Self {
32        Self::new()
33    }
34}
35
36impl<K, V> HashMap<K, V> {
37    pub fn new() -> HashMap<K, V> {
38        HashMap {
39            trie: Trie::empty_store(),
40            phantom: PhantomData,
41        }
42    }
43}
44
45impl<K: Hash + PartialEq> HashMap<K> {
46    pub fn insert(&self, value: K) -> Self {
47        self.put(value, ())
48    }
49    pub fn search(&self, value: &K) -> bool {
50        self.get(value).is_some()
51    }
52}
53
54impl<K: Hash + PartialEq, V> HashMap<K, V> {
55    pub fn put(&self, key: K, value: V) -> Self {
56        Self {
57            trie: self.trie.insert_store(
58                Self::get_bits(&key),
59                KeyValue {
60                    key,
61                    value: Some(value),
62                },
63            ),
64            phantom: PhantomData,
65        }
66    }
67
68    pub fn get(&self, k: &K) -> Option<&V> {
69        let store = self.trie.get_store(Self::get_bits(k))?;
70        let store_cloned: Vec<_> = (*store).to_vec();
71        store_cloned
72            .iter()
73            .find(|KeyValue { key, .. }| k == key)
74            .and_then(|kv| kv.value.as_ref())
75    }
76
77    pub fn delete(&self, key: K) -> Option<Self> {
78        self.trie
79            .delete_store(Self::get_bits(&key), &KeyValue { key, value: None })
80            .map(|trie| HashMap {
81                trie,
82                phantom: PhantomData,
83            })
84    }
85
86    fn get_bits(key: &K) -> Vec<bool> {
87        let mut s = DefaultHasher::new();
88        key.hash(&mut s);
89        let hash = s.finish();
90        (0..64).map(|i| hash & (1u64 << i) > 0).collect()
91    }
92}
93
94#[cfg(test)]
95mod tests {
96    use super::*;
97
98    #[test]
99    fn insert_and_retrieve_values_set() {
100        let m1 = HashMap::new();
101        let m2 = m1.insert(1238).insert(-1).insert(1238);
102        assert!(m2.search(&1238));
103        assert!(!m1.search(&-1));
104        assert!(!m2.delete(1238).unwrap().search(&1238))
105    }
106
107    #[test]
108    fn insert_and_retrieve_values() {
109        let m1 = HashMap::new();
110        let m2 = m1.put(1238, 1).put(-1, 10);
111        assert_eq!(m2.get(&1238), Some(&1));
112        assert_eq!(m1.get(&-1), None);
113    }
114
115    #[test]
116    fn handle_hash_collisions() {
117        #[derive(PartialEq, Clone)]
118        struct K {
119            x: i8,
120        }
121
122        impl Hash for K {
123            fn hash<H: Hasher>(&self, _: &mut H) {}
124        }
125
126        let m = HashMap::new().put(K { x: 1 }, 1).put(K { x: -1 }, 10);
127        assert_eq!(m.get(&K { x: 1 }), Some(&1));
128        assert_eq!(m.get(&K { x: -1 }), Some(&10));
129    }
130
131    #[test]
132    fn delete_entries() {
133        #[derive(PartialEq, Clone)]
134        struct K {
135            x: i8,
136        }
137
138        impl Hash for K {
139            fn hash<H: Hasher>(&self, _: &mut H) {}
140        }
141
142        let m = HashMap::new()
143            .put(K { x: 1 }, 1)
144            .put(K { x: -1 }, 10)
145            .delete(K { x: 1 });
146        assert!(m.is_some());
147        let m2 = m.unwrap();
148        assert_eq!(m2.get(&K { x: 1 }), None);
149        assert_eq!(m2.get(&K { x: -1 }), Some(&10));
150    }
151}
scopegraphs_prust_lib/hashmap.rs

scopegraphs_prust_lib/
hashmap.rs
