flat_map/
flat_map.rs

1use self::Entry::*;
2use std::borrow::{Borrow, BorrowMut};
3use std::cmp::Ordering;
4use std::fmt;
5use std::fmt::Debug;
6use std::hash::{Hash, Hasher};
7use std::iter::{FromIterator, Map};
8use std::mem::swap;
9use std::ops::{Index, IndexMut};
10use std::slice;
11use std::vec;
12use std::vec::Vec;
13
14#[derive(Clone, Default)]
15pub struct FlatMap<K, V> {
16    v: Vec<(K, V)>,
17}
18
19pub enum Entry<'a, K: 'a, V: 'a> {
20    Vacant(VacantEntry<'a, K, V>),
21    Occupied(OccupiedEntry<'a, K, V>),
22}
23
24pub struct VacantEntry<'a, K: 'a, V: 'a> {
25    v: &'a mut Vec<(K, V)>,
26    key: K,
27    index: usize,
28}
29
30pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
31    v: &'a mut Vec<(K, V)>,
32    index: usize,
33}
34
35pub struct IntoIter<K, V> {
36    inner: vec::IntoIter<(K, V)>,
37}
38
39pub struct IterMut<'a, K: 'a, V: 'a> {
40    inner: slice::IterMut<'a, (K, V)>,
41}
42
43pub struct ValuesMut<'a, K: 'a, V: 'a> {
44    inner: IterMut<'a, K, V>,
45}
46
47pub struct Iter<'a, K: 'a, V: 'a> {
48    inner: slice::Iter<'a, (K, V)>,
49}
50
51pub struct Keys<'a, K: 'a, V: 'a> {
52    inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>,
53}
54
55pub struct Values<'a, K: 'a, V: 'a> {
56    inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>,
57}
58
59impl<K, V> FlatMap<K, V> {
60    pub fn new() -> FlatMap<K, V> {
61        FlatMap { v: vec![] }
62    }
63
64    pub fn with_capacity(capacity: usize) -> FlatMap<K, V> {
65        FlatMap {
66            v: Vec::with_capacity(capacity),
67        }
68    }
69
70    /// Returns the number of elements the `VecMap` can hold without
71    /// reallocating.
72    ///
73    /// # Examples
74    ///
75    /// ```
76    /// use flat_map::FlatMap;
77    /// let map: FlatMap<String, String> = FlatMap::with_capacity(10);
78    /// assert!(map.capacity() >= 10);
79    /// ```
80    pub fn capacity(&self) -> usize {
81        self.v.capacity()
82    }
83
84    pub fn reserve(&mut self, additional: usize) {
85        self.v.reserve(additional)
86    }
87
88    pub fn reserve_exact(&mut self, additional: usize) {
89        self.v.reserve_exact(additional)
90    }
91
92    pub fn shrink_to_fit(&mut self) {
93        self.v.shrink_to_fit()
94    }
95
96    pub fn len(&self) -> usize {
97        self.v.len()
98    }
99
100    /// Return true if the map contains no elements.
101    ///
102    /// # Examples
103    ///
104    /// ```
105    /// use flat_map::FlatMap;
106    ///
107    /// let mut a = FlatMap::new();
108    /// assert!(a.is_empty());
109    /// a.insert("1", "a");
110    /// assert!(!a.is_empty());
111    /// ```
112    pub fn is_empty(&self) -> bool {
113        self.v.is_empty()
114    }
115
116    pub fn iter<'r>(&'r self) -> Iter<'r, K, V> {
117        Iter {
118            inner: self.v.iter(),
119        }
120    }
121
122    pub fn iter_mut(&mut self) -> IterMut<K, V> {
123        IterMut {
124            inner: self.v.iter_mut(),
125        }
126    }
127
128    pub fn values_mut(&mut self) -> ValuesMut<K, V> {
129        ValuesMut {
130            inner: self.iter_mut(),
131        }
132    }
133
134    pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
135        fn first<A, B>((a, _): (A, B)) -> A {
136            a
137        }
138        let first: fn((&'a K, &'a V)) -> &'a K = first; // coerce to fn pointer
139        Keys {
140            inner: self.iter().map(first),
141        }
142    }
143
144    pub fn values<'a>(&'a self) -> Values<'a, K, V> {
145        fn second<A, B>((_, b): (A, B)) -> B {
146            b
147        }
148        let second: fn((&'a K, &'a V)) -> &'a V = second; // coerce to fn pointer
149        Values {
150            inner: self.iter().map(second),
151        }
152    }
153
154    pub fn clear(&mut self) {
155        self.v.clear()
156    }
157
158    pub fn into_inner(self) -> Vec<(K, V)> {
159        self.v
160    }
161
162    pub fn retain<F>(&mut self, mut f: F)
163    where F: FnMut(&K, &V) -> bool
164    {
165        self.v.retain(|(v, k)| f(v, k))
166    }
167}
168
169impl<K: Ord, V> FlatMap<K, V> {
170    pub fn insert(&mut self, key: K, mut v: V) -> Option<V> {
171        match self.v[..].binary_search_by(|&(ref k, _)| k.cmp(&key)) {
172            Err(i) => {
173                self.v.insert(i, (key, v));
174                None
175            }
176            Ok(i) => {
177                let &mut (_, ref mut value) = &mut self.v[i];
178                swap(value, &mut v);
179                Some(v)
180            }
181        }
182    }
183
184    pub fn append(&mut self, other: &mut Self) {
185        self.v.reserve(other.len());
186        for (k, v) in other.v.drain(..) {
187            self.insert(k, v);
188        }
189    }
190
191    pub fn split_off(&mut self, key: &K) -> Self {
192        match self.v[..].binary_search_by(|&(ref k, _)| k.cmp(key)) {
193            Err(_) => Self::new(),
194            Ok(at) => {
195                let v = self.v.split_off(at);
196                FlatMap { v: v }
197            }
198        }
199    }
200
201    pub fn get<Q: ?Sized>(&self, q: &Q) -> Option<&V>
202    where
203        K: Borrow<Q>,
204        Q: Ord,
205    {
206        match self.v[..].binary_search_by(|&(ref k, _)| k.borrow().cmp(q)) {
207            Err(_) => None,
208            Ok(idx) => {
209                let (_, ref v) = self.v[idx];
210                Some(v)
211            }
212        }
213    }
214
215    pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
216    where
217        K: Borrow<Q>,
218        Q: Ord,
219    {
220        self.get(k).is_some()
221    }
222
223    /// Return Option<&mut V>.
224    ///
225    /// # Example
226    ///
227    /// ```
228    /// use flat_map::FlatMap;
229    ///
230    /// let mut m = FlatMap::new();
231    /// m.insert(1, "foo".to_string());
232    /// m.get_mut(&1).unwrap().push_str("bar");
233    /// assert_eq!("foobar", m.get_mut(&1).unwrap());
234    /// ```
235    pub fn get_mut<Q: ?Sized>(&mut self, q: &Q) -> Option<&mut V>
236    where
237        K: Borrow<Q>,
238        Q: Ord,
239    {
240        match self.v[..].binary_search_by(|&(ref k, _)| k.borrow().cmp(q)) {
241            Err(_) => None,
242            Ok(idx) => match self.v.get_mut(idx) {
243                Some(&mut (_, ref mut v)) => Some(v),
244                _ => None,
245            },
246        }
247    }
248
249    pub fn entry(&mut self, key: K) -> Entry<K, V> {
250        match self.v[..].binary_search_by(|&(ref k, _)| k.cmp(&key)) {
251            Err(i) => Vacant(VacantEntry {
252                v: &mut self.v,
253                key: key,
254                index: i,
255            }),
256            Ok(i) => Occupied(OccupiedEntry {
257                v: &mut self.v,
258                index: i,
259            }),
260        }
261    }
262
263    pub fn remove<Q: ?Sized>(&mut self, q: &Q) -> Option<V>
264    where
265        K: Borrow<Q>,
266        Q: Ord,
267    {
268        match self.v[..].binary_search_by(|&(ref k, _)| k.borrow().cmp(q)) {
269            Err(_) => None,
270            Ok(i) => {
271                let (_, value) = self.v.remove(i);
272                Some(value)
273            }
274        }
275    }
276}
277
278impl<'a, K: Ord, V> Entry<'a, K, V> {
279    pub fn or_insert(self, default: V) -> &'a mut V {
280        match self {
281            Occupied(entry) => entry.into_mut(),
282            Vacant(entry) => entry.insert(default),
283        }
284    }
285
286    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
287        match self {
288            Occupied(entry) => entry.into_mut(),
289            Vacant(entry) => entry.insert(default()),
290        }
291    }
292}
293
294impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
295    pub fn insert(self, value: V) -> &'a mut V {
296        self.v.insert(self.index, (self.key, value));
297        let &mut (_, ref mut value) = &mut self.v[self.index];
298        value
299    }
300}
301
302impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
303    pub fn key(&self) -> &K {
304        let (ref key, _) = self.v[self.index];
305        key
306    }
307
308    pub fn get(&self) -> &V {
309        let (_, ref value) = self.v[self.index];
310        value
311    }
312
313    pub fn get_mut(&mut self) -> &mut V {
314        let (_, ref mut value) = self.v[self.index];
315        value
316    }
317
318    pub fn into_mut(self) -> &'a mut V {
319        let &mut (_, ref mut value) = &mut self.v[self.index];
320        value
321    }
322
323    pub fn insert(&mut self, mut value: V) -> V {
324        let &mut (_, ref mut old_value) = &mut self.v[self.index];
325        swap(old_value, &mut value);
326        value
327    }
328
329    pub fn remove(self) -> V {
330        let (_, value) = self.v.remove(self.index);
331        value
332    }
333}
334
335impl<'a, K, V> Iterator for Iter<'a, K, V> {
336    type Item = (&'a K, &'a V);
337
338    fn next(&mut self) -> Option<(&'a K, &'a V)> {
339        match self.inner.next() {
340            Some(&(ref k, ref v)) => Some((k, v)),
341            None => None,
342        }
343    }
344    fn size_hint(&self) -> (usize, Option<usize>) {
345        self.inner.size_hint()
346    }
347}
348
349impl<'a, K, V> Clone for Iter<'a, K, V> {
350    fn clone(&self) -> Iter<'a, K, V> {
351        Iter {
352            inner: self.inner.clone(),
353        }
354    }
355}
356
357impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
358    fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
359        match self.inner.next_back() {
360            Some(&(ref k, ref v)) => Some((k, v)),
361            None => None,
362        }
363    }
364}
365
366impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {}
367
368impl<'a, K, V> Iterator for IterMut<'a, K, V> {
369    type Item = (&'a K, &'a mut V);
370
371    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
372        match self.inner.next() {
373            Some(&mut (ref k, ref mut v)) => Some((k, v)),
374            None => None,
375        }
376    }
377    fn size_hint(&self) -> (usize, Option<usize>) {
378        self.inner.size_hint()
379    }
380}
381
382impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
383    fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
384        match self.inner.next_back() {
385            Some(&mut (ref k, ref mut v)) => Some((k, v)),
386            None => None,
387        }
388    }
389}
390
391impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {}
392
393impl<K, V> Iterator for IntoIter<K, V> {
394    type Item = (K, V);
395
396    fn next(&mut self) -> Option<(K, V)> {
397        self.inner.next()
398    }
399    fn size_hint(&self) -> (usize, Option<usize>) {
400        self.inner.size_hint()
401    }
402}
403
404impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
405    fn next_back(&mut self) -> Option<(K, V)> {
406        self.inner.next_back()
407    }
408}
409
410impl<K, V> ExactSizeIterator for IntoIter<K, V> {}
411
412impl<K, V> IntoIterator for FlatMap<K, V> {
413    type Item = (K, V);
414    type IntoIter = IntoIter<K, V>;
415
416    fn into_iter(self) -> IntoIter<K, V> {
417        IntoIter {
418            inner: self.v.into_iter(),
419        }
420    }
421}
422
423impl<'a, K, V> IntoIterator for &'a FlatMap<K, V> {
424    type Item = (&'a K, &'a V);
425    type IntoIter = Iter<'a, K, V>;
426
427    fn into_iter(self) -> Iter<'a, K, V> {
428        Iter {
429            inner: self.v.iter(),
430        }
431    }
432}
433
434impl<'a, K, V> IntoIterator for &'a mut FlatMap<K, V> {
435    type Item = (&'a K, &'a mut V);
436    type IntoIter = IterMut<'a, K, V>;
437
438    fn into_iter(self) -> IterMut<'a, K, V> {
439        IterMut {
440            inner: self.v.iter_mut(),
441        }
442    }
443}
444
445impl<'a, K, V> Clone for Keys<'a, K, V> {
446    fn clone(&self) -> Keys<'a, K, V> {
447        Keys {
448            inner: self.inner.clone(),
449        }
450    }
451}
452
453impl<'a, K, V> Iterator for Keys<'a, K, V> {
454    type Item = &'a K;
455
456    fn next(&mut self) -> Option<&'a K> {
457        self.inner.next()
458    }
459    fn size_hint(&self) -> (usize, Option<usize>) {
460        self.inner.size_hint()
461    }
462}
463
464impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
465    fn next_back(&mut self) -> Option<&'a K> {
466        self.inner.next_back()
467    }
468}
469
470impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {}
471
472impl<'a, K, V> Clone for Values<'a, K, V> {
473    fn clone(&self) -> Values<'a, K, V> {
474        Values {
475            inner: self.inner.clone(),
476        }
477    }
478}
479
480impl<'a, K, V> Iterator for Values<'a, K, V> {
481    type Item = &'a V;
482
483    fn next(&mut self) -> Option<&'a V> {
484        self.inner.next()
485    }
486    fn size_hint(&self) -> (usize, Option<usize>) {
487        self.inner.size_hint()
488    }
489}
490
491impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
492    fn next_back(&mut self) -> Option<&'a V> {
493        self.inner.next_back()
494    }
495}
496
497impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {}
498
499impl<K: Ord, V> FromIterator<(K, V)> for FlatMap<K, V> {
500    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> FlatMap<K, V> {
501        let mut vec: Vec<_> = iter.into_iter().collect();
502        vec.sort_by(|kv1, kv2| kv1.0.cmp(&kv2.0));
503        vec.dedup_by(|kv1, kv2| kv1.0 == kv2.0);
504        Self { v: vec }
505    }
506}
507
508impl<K: Ord, V> Extend<(K, V)> for FlatMap<K, V> {
509    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
510        for (k, v) in iter {
511            self.insert(k, v);
512        }
513    }
514}
515
516impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for FlatMap<K, V> {
517    fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) {
518        self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
519    }
520}
521
522impl<K: Hash, V: Hash> Hash for FlatMap<K, V> {
523    fn hash<H: Hasher>(&self, state: &mut H) {
524        for elt in self {
525            elt.hash(state);
526        }
527    }
528}
529
530impl<K: Ord, V: Ord> Ord for FlatMap<K, V> {
531    fn cmp(&self, other: &FlatMap<K, V>) -> Ordering {
532        self.iter().cmp(other.iter())
533    }
534}
535
536impl<K: PartialEq, V: PartialEq> PartialEq for FlatMap<K, V> {
537    fn eq(&self, other: &FlatMap<K, V>) -> bool {
538        self.len() == other.len() && self.iter().zip(other).all(|(a, b)| a == b)
539    }
540}
541
542impl<K: Eq, V: Eq> Eq for FlatMap<K, V> {}
543
544impl<K: PartialOrd, V: PartialOrd> PartialOrd for FlatMap<K, V> {
545    fn partial_cmp(&self, other: &FlatMap<K, V>) -> Option<Ordering> {
546        self.iter().partial_cmp(other.iter())
547    }
548}
549
550impl<K: Debug, V: Debug> Debug for FlatMap<K, V> {
551    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
552        f.debug_map().entries(self.iter()).finish()
553    }
554}
555
556impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for FlatMap<K, V>
557where
558    K: Borrow<Q>,
559    Q: Ord,
560{
561    type Output = V;
562
563    fn index(&self, key: &Q) -> &V {
564        self.get(key).expect("no entry found for key")
565    }
566}
567
568impl<'a, K: Ord, Q: ?Sized, V> IndexMut<&'a Q> for FlatMap<K, V>
569where
570    K: BorrowMut<Q>,
571    Q: Ord,
572{
573    // type Output = &V;
574
575    fn index_mut(&mut self, key: &Q) -> &mut V {
576        self.get_mut(key).expect("no entry found for key")
577    }
578}
579
580impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
581    type Item = &'a mut V;
582
583    fn next(&mut self) -> Option<&'a mut V> {
584        self.inner.next().map(|(_, v)| v)
585    }
586
587    fn size_hint(&self) -> (usize, Option<usize>) {
588        self.inner.size_hint()
589    }
590}
591
592impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
593    fn next_back(&mut self) -> Option<&'a mut V> {
594        self.inner.next_back().map(|(_, v)| v)
595    }
596}
597
598impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
599    fn len(&self) -> usize {
600        self.inner.len()
601    }
602}
603
604#[cfg(feature = "serde1")]
605mod serde_impl {
606    // the serde serialization/deserialization is manually handled to
607    // serialize the FlatMap as a classic map
608    // and not as a vector<K, V>
609    // this way the FlatMap is serialized in json as:
610    // { "k1": "v1", "k2": "v2" }
611    // and not
612    // {"v": [["k1", "v1"],["k2", "v2"]]}
613
614    use super::FlatMap;
615    use serde::de::{Deserialize, Deserializer, MapAccess, Visitor};
616    use serde::ser::SerializeMap;
617    use serde::{Serialize, Serializer};
618    use std::fmt;
619    use std::marker::PhantomData;
620
621    impl<K, V> Serialize for FlatMap<K, V>
622    where
623        K: Ord + Serialize,
624        V: Serialize,
625    {
626        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
627        where
628            S: Serializer,
629        {
630            let mut map = serializer.serialize_map(Some(self.len()))?;
631            for (k, v) in self {
632                map.serialize_entry(k, v)?;
633            }
634            map.end()
635        }
636    }
637
638    struct FlatMapVisitor<K, V> {
639        marker: PhantomData<fn() -> FlatMap<K, V>>,
640    }
641
642    impl<K, V> FlatMapVisitor<K, V> {
643        fn new() -> Self {
644            FlatMapVisitor {
645                marker: PhantomData,
646            }
647        }
648    }
649
650    impl<'de, K: Ord, V> Visitor<'de> for FlatMapVisitor<K, V>
651    where
652        K: Deserialize<'de>,
653        V: Deserialize<'de>,
654    {
655        type Value = FlatMap<K, V>;
656
657        fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
658            formatter.write_str("a flat_map")
659        }
660
661        fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
662        where
663            M: MapAccess<'de>,
664        {
665            let mut map = FlatMap::with_capacity(access.size_hint().unwrap_or(0));
666            while let Some((key, value)) = access.next_entry()? {
667                map.insert(key, value);
668            }
669            Ok(map)
670        }
671    }
672
673    impl<'de, K: Ord, V> Deserialize<'de> for FlatMap<K, V>
674    where
675        K: Deserialize<'de>,
676        V: Deserialize<'de>,
677    {
678        fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
679        where
680            D: Deserializer<'de>,
681        {
682            deserializer.deserialize_map(FlatMapVisitor::new())
683        }
684    }
685}
flat_map/flat_map.rs

flat_map/
flat_map.rs
