simplemap/
lib.rs

1// Copyright 2015 Dawid Ciężarkiewicz
2// See LICENSE-MPL
3//! Simple Map with default for missing values and compacting (removal of
4//! elements with default value from underlying map).
5//!
6//! So you can just:
7//!
8//! ```
9//! use simplemap::SimpleMap;
10//!
11//! let mut map = SimpleMap::new();
12//!
13//! assert_eq!(map[0u32], 0u32);
14//! map[1] = 3;
15//! assert_eq!(map[1], 3);
16//! ```
17
18#![cfg_attr(all(test, feature="bench"), feature(test))]
19
20#[cfg(all(test, feature="bench"))]
21extern crate test;
22extern crate fnv;
23
24
25#[cfg(test)]
26extern crate rand;
27
28use std::ops::{Index, IndexMut};
29use std::collections::hash_map::Entry;
30use std::collections::HashMap;
31use std::iter::Chain;
32use std::hash::{Hash, BuildHasherDefault, BuildHasher};
33use fnv::FnvHasher;
34use std::fmt;
35
36/// SimpleMap
37///
38/// Simple Map with default for missing values and compacting (removal of
39/// elements with default value from underlying map).
40#[derive(Clone)]
41pub struct SimpleMap<K, V, S> {
42    map : HashMap<K, V, S>,
43    default : V,
44    pending : Option<(K, V)>
45}
46
47impl<K, V> SimpleMap<K, V, BuildHasherDefault<FnvHasher>>
48where K : Ord+Clone+Hash,
49      V : Clone+Eq+Default,
50{
51    /// Create a `SimpleMap`.
52    ///
53    /// `Default::default()` will be used as a default value.
54    pub fn new() -> Self {
55        let fnv = BuildHasherDefault::<FnvHasher>::default();
56        SimpleMap {
57            map : HashMap::with_hasher(fnv),
58            default: Default::default(),
59            pending: None,
60        }
61    }
62}
63
64impl<K, V, S> SimpleMap<K, V, S>
65where K : Ord+Clone+Hash,
66      V : Clone+Eq+Default,
67      S : BuildHasher+Default
68{
69    /// Create a `SimpleMap`.
70    ///
71    /// `Default::default()` will be used as a default value.
72    pub fn with_hasher(hasher : S) -> SimpleMap<K, V, S> {
73        SimpleMap {
74            map : HashMap::with_hasher(hasher),
75            default: Default::default(),
76            pending: None,
77        }
78    }
79}
80
81
82impl<K, V> SimpleMap<K, V,  BuildHasherDefault<FnvHasher>>
83where K : Ord+Clone+Hash,
84      V : Clone+Eq,
85{
86    /// Create a `SimpleMap` with custom default value.
87    pub fn new_with_default(default : V) -> Self {
88        let fnv = BuildHasherDefault::<FnvHasher>::default();
89        SimpleMap {
90            map : HashMap::with_hasher(fnv),
91            default: default,
92            pending: None,
93        }
94    }
95}
96
97
98impl<K, V, S> SimpleMap<K, V, S>
99where K : Ord+Clone+Hash,
100      V : Clone+Eq,
101      S : BuildHasher+Default,
102{
103    pub fn with_default_with_hasher(default : V, hasher: S) -> SimpleMap<K, V, S> {
104        SimpleMap {
105            map : HashMap::with_hasher(hasher),
106            default: default,
107            pending: None,
108        }
109    }
110}
111
112impl<K, V, S> SimpleMap<K, V, S>
113where K : Ord+Clone+Hash,
114      V : Clone+Eq,
115      S: BuildHasher,
116{
117    fn apply_pending(&mut self) {
118       match self.pending {
119           Some(ref pending) => {
120               let &(ref idx , ref val) = pending;
121               if *val == self.default {
122                   self.map.remove(idx);
123               } else {
124                   self.map.insert(idx.clone(), val.clone());
125               }
126           },
127           None => {}
128       }
129       self.pending = None;
130    }
131
132    /// Make sure to remove all elements with default value.
133    pub fn compact(&mut self) {
134        self.apply_pending();
135    }
136
137    /// Iterator over map elements with non-default values.
138    ///
139    /// Note: It might return elements with default value, unless `compact`
140    /// is called before `iter()`.
141    pub fn iter<'a>(&'a self) -> Chain<std::collections::hash_map::Iter<'a, K, V>, std::iter::Map<std::option::Iter<'a, (K, V)>, fn(&'a (K, V)) -> (&'a K, &'a V)>> {
142        let SimpleMap {
143            ref map,
144            ref pending,
145            ..
146        } = *self;
147
148        let f: fn(&'a (K, V)) -> (&'a K, &'a V) = ref_to_tuple_to_tuple_of_refs;
149
150        map.iter().chain(pending.iter().map(f))
151    }
152}
153
154impl<K, V, S> SimpleMap<K, V, S>
155where K : Ord+Clone+Hash,
156      V : Clone+Eq,
157      S: BuildHasher,
158{
159    /// Iterator yielding (K, V) instead of (&K, &V)
160    pub fn iter_cloned<'a>(&'a self) ->
161        Chain<
162            std::iter::Map<std::collections::hash_map::Iter<'a, K, V>, fn((&'a K, &'a V)) -> (K, V)>,
163            std::iter::Cloned<std::option::Iter<'a, (K, V)>>
164        >
165    {
166        let SimpleMap {
167            ref map,
168            ref pending,
169            ..
170        } = *self;
171
172        let f: fn((&'a K, &'a V)) -> (K, V) = tuple_of_refs_to_tuple;
173
174        map.iter().map(f).chain(pending.iter().cloned())
175    }
176
177}
178
179fn ref_to_tuple_to_tuple_of_refs<'a, K, V>(t : &'a(K, V)) -> (&'a K, &'a V) {
180    let &(ref i, ref t) = t;
181    (i, t)
182}
183
184fn tuple_of_refs_to_tuple<'a, K : Clone, V : Clone>(t : (&'a K, &'a V)) -> (K, V) {
185    let (i, t) = t;
186    (i.clone(), t.clone())
187}
188
189use std::iter::FromIterator;
190use std::iter::IntoIterator;
191
192impl<K, V, S> FromIterator<(K, V)> for SimpleMap<K, V, S>
193where K: Ord+Hash, V: Default,
194      S: BuildHasher+Default {
195    fn from_iter<I>(iterator: I) -> SimpleMap<K, V, S>
196        where I: IntoIterator<Item=(K, V)> {
197            SimpleMap {
198                default: Default::default(),
199                map: FromIterator::from_iter(iterator),
200                pending: None,
201            }
202    }
203}
204
205/// ```
206/// use simplemap::SimpleMap;
207///
208/// let mut map = SimpleMap::new();
209///
210/// let val : u32 = map[0u32];
211/// assert_eq!(val, 0);
212/// ```
213impl<K, V, S> Index<K> for SimpleMap<K, V, S>
214where K : Ord+Hash,
215      S : BuildHasher+Default,
216{
217    type Output = V;
218    fn index<'a>(&'a self, index: K) -> &'a V {
219        match self.pending {
220            Some(ref pending) => {
221               let &(ref i, ref val) = pending;
222               if *i == index {
223                   return val
224               }
225            }
226            None => {},
227        }
228
229        match self.map.get(&index) {
230            Some(entry) => entry,
231            None => &self.default,
232        }
233    }
234}
235
236/// ```
237/// use simplemap::SimpleMap;
238///
239/// let mut map = SimpleMap::new();
240///
241/// map[1u32] = 3i32;
242/// assert_eq!(map[1], 3);
243/// ```
244impl<K, V, S> IndexMut<K> for SimpleMap<K, V, S>
245where
246K : Ord+Clone+Hash,
247V : Clone+Eq,
248      S : BuildHasher+Default,
249{
250    fn index_mut<'a>(&'a mut self, index: K) -> &'a mut V {
251        self.apply_pending();
252
253        match self.map.entry(index.clone()) {
254            Entry::Occupied(entry) => {
255                self.pending = Some((index, entry.get().clone()));
256                let &mut (_, ref mut val) = self.pending.as_mut().unwrap();
257                val
258            },
259            Entry::Vacant(_) => {
260                self.pending = Some((index, self.default.clone()));
261                let &mut (_, ref mut val) = self.pending.as_mut().unwrap();
262                val
263            }
264        }
265    }
266}
267
268impl<K, V, S> fmt::Debug for SimpleMap<K, V, S>
269where K : Ord+Eq+Clone+Hash+fmt::Debug,
270      V : Clone+Eq+fmt::Debug,
271      S: BuildHasher,
272{
273    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
274        f.debug_map().entries(self.iter()).finish()
275    }
276}
277
278impl<K, V, S> Default for SimpleMap<K, V, S>
279where K : Ord+Clone+Hash,
280      V : Clone+Eq+Default,
281      S : BuildHasher+Default,
282{
283     fn default() -> Self {
284         SimpleMap::with_default_with_hasher(Default::default(), Default::default())
285     }
286}
287
288
289#[cfg(test)]
290mod tests {
291    pub use super::*;
292    use std::collections::HashMap;
293    use rand::Rng;
294    use rand;
295
296    #[test]
297    fn default() {
298        let map = SimpleMap::new_with_default(5u32);
299        assert_eq!(map[1u32], 5u32);
300    }
301
302    #[test]
303    fn iter() {
304        let mut map = SimpleMap::new();
305
306        map[0u32] = 3i32; // counts
307        map[1u32] = 0i32; // default, doesn't count
308        map[2u32] = 2i32; // counts
309        map[0u32] = 2i32; // replaces the existing one
310        let _ = map[0u32]; // shouldn't change anything
311
312        map.compact();
313        assert_eq!(map.iter().count(), 2);
314    }
315
316    #[test]
317    fn random() {
318        let mut bmap = HashMap::new();
319        let mut smap = SimpleMap::new();
320
321        let mut rng = rand::thread_rng();
322
323        for val in 0u32..10000 {
324            let idx = rng.gen_range(-5i32, 5);
325            let bval = *bmap.get(&idx).unwrap_or(&Default::default());
326            let sval = smap[idx];
327            assert_eq!(bval, sval);
328            bmap.insert(idx, val);
329            smap[idx] = val;
330        }
331    }
332
333    #[test]
334    fn strings() {
335        let mut smap = SimpleMap::new();
336
337        smap["one"] = 1u32;
338        smap["two"] = 2u32;
339
340        assert_eq!(smap["zero"], 0u32);
341    }
342
343#[cfg(feature="bench")]
344    mod bench {
345        use std::collections::BTreeMap;
346        use std::collections::HashMap;
347        use std::collections::hash_state::{DefaultState};
348        use fnv::FnvHasher;
349        use super::*;
350        use test::Bencher;
351        use test;
352#[bench]
353        fn normal_btreemap_insert(b : &mut Bencher) {
354            let mut map = BTreeMap::new();
355
356            let mut i = 0u32;
357            b.iter(|| {
358                map.insert(i, i);
359                i = i.wrapping_add(i);
360            });
361        }
362
363#[bench]
364        fn normal_btreemap_get(b : &mut Bencher) {
365            let mut map = BTreeMap::new();
366
367            for i in 0u32..10000 {
368                map.insert(i, i);
369            }
370
371            let mut i = 0u32;
372            b.iter(|| {
373                test::black_box(map.get(&i));
374                i = i.wrapping_add(i);
375            });
376        }
377
378#[bench]
379        fn normal_hashmap_insert(b : &mut Bencher) {
380            let mut map : HashMap<_, _, DefaultState<FnvHasher>> = Default::default();
381
382            let mut i = 0u32;
383            b.iter(|| {
384                map.insert(i, i);
385                i = i.wrapping_add(i);
386            });
387        }
388
389#[bench]
390        fn normal_hashmap_get(b : &mut Bencher) {
391            let mut map : HashMap<_, _, DefaultState<FnvHasher>> = Default::default();
392
393            for i in 0u32..10000 {
394                map.insert(i, i);
395            }
396
397            let mut i = 0u32;
398            b.iter(|| {
399                test::black_box(map.get(&i));
400                i = i.wrapping_add(i);
401            });
402        }
403
404
405#[bench]
406        fn compact_map_idx_assign(b : &mut Bencher) {
407            let mut map = SimpleMap::new();
408
409            let mut i = 0u32;
410            b.iter(|| {
411                map[i] = i;
412                i = i.wrapping_add(i);
413            });
414        }
415
416#[bench]
417        fn compact_map_idx_get(b : &mut Bencher) {
418            let mut map = SimpleMap::new();
419
420            for i in 0u32..10000 {
421                map[i] = i;
422            }
423
424            let mut i = 0u32;
425            b.iter(|| {
426                test::black_box(map[i]);
427                i = i.wrapping_add(i);
428            });
429        }
430    }
431}
simplemap/lib.rs

simplemap/
lib.rs
