collecting_hashmap/lib.rs
1//! Collecting HashMap
2//!
3//! This is a HashMap that allows the user to store multiple `V` values for each `K` key. Currently
4//! it is implemented by internally keeping a `HashMap<K, Vec<V>>` and forwarding most operations
5//! to that `HashMap`. There area few calls where it does more than just forward, in order to keep
6//! the API as functionally similar to a regular `HashMap<K, V>` as possible. The main difference
7//! is with the `insert` method. Since it won't replace the original value if you `insert` another
8//! value for the same `K`, this `insert` returns nothing.
9//!
10//! The `get` and `get_mut` methods have the same signature as a regular `HashMap<K, V>`. Instead
11//! of returning the whole underlying `Vec` for a key, `get` and `get_mut` both return a reference
12//! to the first item in the `Vec`. In order to get a reference to the whole `Vec` for a key, use
13//! `get_all` and `get_all_mut`.
14//!
15//! The `Entry` API operates on the entire underlying `Vec` for a key.
16//!
17//! # Examples
18//!
19//! ```rust
20//! # extern crate collecting_hashmap;
21//! use collecting_hashmap::CollectingHashMap;
22//!
23//! # fn main() -> Result<(), Box<::std::error::Error>> {
24//! let mut map = CollectingHashMap::new();
25//! map.insert("voltron", "black");
26//! map.insert("voltron", "red");
27//! map.insert("voltron", "green");
28//! map.insert("voltron", "blue");
29//! map.insert("voltron", "yellow");
30//! assert_eq!(map.get_all("voltron"), Some(&vec!["black", "red", "green", "blue", "yellow"]));
31//! # Ok(())
32//! # }
33//! ```
34//!
35//! ```rust
36//! # extern crate collecting_hashmap;
37//! use collecting_hashmap::CollectingHashMap;
38//!
39//! # fn main() -> Result<(), Box<::std::error::Error>> {
40//! let query_string = vec![
41//! ("q", "query1"),
42//! ("t", "0m2s"),
43//! ("q", "query2"),
44//! ("q", "query3"),
45//! ];
46//! let map = query_string.into_iter().collect::<CollectingHashMap<_, _>>();
47//! assert_eq!(map.get_all("q"), Some(&vec!["query1", "query2", "query3"]));
48//! # Ok(())
49//! # }
50//! ```
51
52use std::{
53 borrow::Borrow,
54 collections::hash_map::{Drain, Entry, HashMap, Iter, IterMut, Keys, RandomState, Values, ValuesMut},
55 default::Default,
56 hash::{BuildHasher, Hash},
57 marker::PhantomData,
58};
59
60/// A hashmap that stores a vec of values for each key
61pub struct CollectingHashMap<K, V, S=RandomState>
62 where K: Hash + Eq,
63 S: BuildHasher
64{
65 store: HashMap<K, Vec<V>, S>,
66 _k: PhantomData<K>,
67 _v: PhantomData<V>,
68 _s: PhantomData<S>,
69}
70
71impl<K, V, S> Default for CollectingHashMap<K, V, S>
72 where K: Hash + Eq,
73 S: BuildHasher + Default
74{
75 fn default() -> CollectingHashMap<K, V, S> {
76 CollectingHashMap {
77 store: HashMap::with_hasher(Default::default()),
78 _k: PhantomData,
79 _v: PhantomData,
80 _s: PhantomData,
81 }
82 }
83}
84
85impl<K, V> CollectingHashMap<K, V, RandomState>
86 where K: Hash + Eq,
87{
88 /// Creates a new CollectingHashMap with the default Hasher
89 pub fn new() -> CollectingHashMap<K, V, RandomState> {
90 CollectingHashMap {
91 store: HashMap::new(),
92 .. Default::default()
93 }
94 }
95
96 /// Creates a new CollectingHashMap with the given capacity
97 pub fn with_capacity(capacity: usize) -> CollectingHashMap<K, V, RandomState> {
98 CollectingHashMap {
99 store: HashMap::with_capacity(capacity),
100 .. Default::default()
101 }
102 }
103}
104
105impl<K, V, S> CollectingHashMap<K, V, S>
106 where K: Hash + Eq,
107 S: BuildHasher,
108{
109 /// Creates a new CollectingHashMap using the given HashMap for it's backing storage
110 pub fn with_hashmap(h: HashMap<K, Vec<V>, S>) -> CollectingHashMap<K, V, S> {
111 CollectingHashMap {
112 store: h,
113 _k: PhantomData,
114 _v: PhantomData,
115 _s: PhantomData,
116 }
117 }
118
119 /// Inserts a value for the given key
120 ///
121 /// If the key is already present, this will append the value to the key's `Vec<V>`
122 pub fn insert(&mut self, k: K, v: V) {
123 // this can go back to if-let-else once when we have nll
124 {
125 if let Some(r) = self.store.get_mut(&k) {
126 r.push(v);
127 return
128 }
129 }
130 self.store.insert(k, vec![v]);
131 }
132
133 /// Retrieves a reference to a value for the given key
134 ///
135 /// If there is at least one value for the given key, this will return `&V` using the first
136 /// element of `K`s `Vec<V>`
137 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
138 where K: Borrow<Q>,
139 Q: Hash + Eq,
140 {
141 self.store.get(key).and_then(|r| r.get(0))
142 }
143
144 /// Retrieves a mutable reference to a value for the given key
145 ///
146 /// If there is at least one value for the given key, this will return `&mut V` using the first
147 /// element of `K`s `Vec<V>`
148 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
149 where K: Borrow<Q>,
150 Q: Hash + Eq,
151 {
152 self.store.get_mut(key).and_then(|r| r.get_mut(0))
153 }
154
155 /// Retrieves a reference to all values stored for the given key
156 ///
157 /// If there is at least one value present for the given key, this will return a reference to
158 /// the `Vec<V>` for the key
159 pub fn get_all<Q: ?Sized>(&self, key: &Q) -> Option<&Vec<V>>
160 where K: Borrow<Q>,
161 Q: Hash + Eq,
162 {
163 self.store.get(key)
164 }
165
166 /// Retrieves a mutable reference to all values stored for the given key
167 ///
168 /// If there is at least one value present for the given key, this will return a mutable
169 /// reference to the `Vec<V>` for the key
170 pub fn get_all_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut Vec<V>>
171 where K: Borrow<Q>,
172 Q: Hash + Eq,
173 {
174 self.store.get_mut(key)
175 }
176
177 /// Removes a set of values for the given key
178 ///
179 /// If there is a value present for the given key, this will remove all values from the
180 /// underlying `HashMap` but will ONLY return the first element. To return the entire `Vec<V>`
181 /// for the key, use `remove_all`
182 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
183 where K: Borrow<Q>,
184 Q: Hash + Eq,
185 {
186 self.store.remove(key).map(|mut v| v.remove(0))
187 }
188
189 /// Removes a set of values for the given key
190 ///
191 /// If there is a value present for the given key, this will remove all values from the
192 /// underlying `HashMap`, and return the `Vec<V>`
193 pub fn remove_all<Q: ?Sized>(&mut self, key: &Q) -> Option<Vec<V>>
194 where K: Borrow<Q>,
195 Q: Hash + Eq,
196 {
197 self.store.remove(key)
198 }
199
200 // Delegate to the underlying hashmap
201
202 /// The same as
203 /// [HashMap::hasher](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.hasher)
204 pub fn hasher(&self) -> &S {
205 self.store.hasher()
206 }
207
208 /// The same as
209 /// [HashMap::capacity](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.capacity)
210 pub fn capacity(&self) -> usize {
211 self.store.capacity()
212 }
213
214 /// The same as
215 /// [HashMap::is_empty](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.is_empty)
216 pub fn is_empty(&self) -> bool {
217 self.store.is_empty()
218 }
219
220 /// The same as
221 /// [HashMap::reserve](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.reserve)
222 pub fn reserve(&mut self, amt: usize) {
223 self.store.reserve(amt)
224 }
225
226 /// The same as
227 /// [HashMap::shrink_to_fit](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.shrink_to_fit)
228 pub fn shrink_to_fit(&mut self) {
229 self.store.shrink_to_fit()
230 }
231
232 /// The same as
233 /// [HashMap::keys](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.keys)
234 pub fn keys(&self) -> Keys<K, Vec<V>> {
235 self.store.keys()
236 }
237
238 /// The same as
239 /// [HashMap::values](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.values)
240 pub fn values(&self) -> Values<K, Vec<V>> {
241 self.store.values()
242 }
243
244 /// The same as
245 /// [HashMap::values_mut](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.values_mut)
246 pub fn values_mut(&mut self) -> ValuesMut<K, Vec<V>> {
247 self.store.values_mut()
248 }
249
250 /// The same as
251 /// [HashMap::iter](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.iter)
252 pub fn iter(&self) -> Iter<K, Vec<V>> {
253 self.store.iter()
254 }
255
256 /// The same as
257 /// [HashMap::iter_mut](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.iter_mut)
258 pub fn iter_mut(&mut self) -> IterMut<K, Vec<V>> {
259 self.store.iter_mut()
260 }
261
262 /// The same as
263 /// [HashMap::entry](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.entry)
264 pub fn entry(&mut self, key: K) -> Entry<K, Vec<V>> {
265 self.store.entry(key)
266 }
267
268 /// The same as
269 /// [HashMap::len](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.len)
270 pub fn len(&self) -> usize {
271 self.store.len()
272 }
273
274 /// The same as
275 /// [HashMap::drain](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.drain)
276 pub fn drain(&mut self) -> Drain<K, Vec<V>> {
277 self.store.drain()
278 }
279
280 /// The same as
281 /// [HashMap::clear](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.clear)
282 pub fn clear(&mut self) {
283 self.store.clear()
284 }
285
286 /// The same as
287 /// [HashMap::contains_key](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.contains_key)
288 pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
289 where K: Borrow<Q>,
290 Q: Hash + Eq
291 {
292 self.store.contains_key(k)
293 }
294
295 /// The same as
296 /// [HashMap::remove_entry](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.remove_entry)
297 pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, Vec<V>)>
298 where K: Borrow<Q>,
299 Q: Hash + Eq,
300 {
301 self.store.remove_entry(key)
302 }
303
304 /// The same as
305 /// [HashMap::retain](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.retain)
306 pub fn retain<F>(&mut self, f: F)
307 where F: FnMut(&K, &mut Vec<V>) -> bool,
308 {
309 self.store.retain(f)
310 }
311}
312
313impl<K, V, S> ::std::iter::FromIterator<(K, V)> for CollectingHashMap<K, V, S>
314 where K: Hash + Eq,
315 S: BuildHasher + Default
316{
317 fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> CollectingHashMap<K, V, S> {
318 let map = HashMap::with_hasher(Default::default());
319 let mut map = CollectingHashMap::with_hashmap(map);
320 map.extend(iter);
321 map
322 }
323}
324
325impl<K, V, S> ::std::iter::Extend<(K, V)> for CollectingHashMap<K, V, S>
326 where K: Hash + Eq,
327 S: BuildHasher
328{
329 fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
330 let iter = iter.into_iter();
331 let reserve = if self.is_empty() {
332 iter.size_hint().0
333 } else {
334 (iter.size_hint().0 + 1) / 2
335 };
336 self.reserve(reserve);
337 for (k, v) in iter {
338 self.insert(k, v);
339 }
340 }
341}
342
343#[cfg(test)]
344mod tests {
345 use super::*;
346
347 #[test]
348 fn insert_and_get() {
349 let mut h: CollectingHashMap<String, String> = CollectingHashMap::new();
350 h.insert("foo".into(), "bar".into());
351 h.insert("foo".into(), "baz".into());
352 let r = h.get("foo");
353 assert_eq!(Some(&"bar".to_string()), r);
354 }
355
356 #[test]
357 fn insert_and_get_all() {
358 let mut h = CollectingHashMap::new();
359 h.insert("foo".to_string(), "bar".to_string());
360 h.insert("foo".to_string(), "baz".to_string());
361 let r = h.get_all("foo");
362 assert_eq!(Some(&vec!["bar".to_string(), "baz".to_string()]), r);
363 }
364
365 #[test]
366 fn insert_iter_of_tuples() {
367 let data = vec![
368 ("one", "two"),
369 ("three", "four"),
370 ("one", "five"),
371 ];
372 let map: CollectingHashMap<_, _> = data.into_iter().collect();
373
374 assert_eq!(map.get_all("three"), Some(&vec!["four"]));
375 assert_eq!(map.get_all("one"), Some(&vec!["two", "five"]));
376 }
377}
378