managed/
map.rs

1use core::mem;
2use core::fmt;
3use core::slice;
4use core::borrow::Borrow;
5use core::ops::{Bound, RangeBounds};
6
7#[cfg(feature = "std")]
8use std::collections::BTreeMap;
9#[cfg(feature = "std")]
10use std::collections::btree_map::{Iter as BTreeIter, IterMut as BTreeIterMut,
11                                  Range as BTreeRange};
12#[cfg(all(feature = "alloc", not(feature = "std")))]
13use alloc::collections::btree_map::BTreeMap;
14#[cfg(all(feature = "alloc", not(feature = "std")))]
15use alloc::collections::btree_map::{Iter as BTreeIter, IterMut as BTreeIterMut,
16                                    Range as BTreeRange};
17
18/// A managed map.
19///
20/// This enum can be used to represent exclusive access to maps.
21/// In Rust, exclusive access to an object is obtained by either owning the object,
22/// or owning a mutable pointer to the object; hence, "managed".
23///
24/// The purpose of this enum is providing good ergonomics with `std` present while making
25/// it possible to avoid having a heap at all (which of course means that `std` is not present).
26/// To achieve this, the variants other than `Borrow` are only available when the corresponding
27/// feature is opted in.
28///
29/// Unlike [Managed](enum.Managed.html) and [ManagedSlice](enum.ManagedSlice.html),
30/// the managed map is implemented using a B-tree map when allocation is available,
31/// and a sorted slice of key-value pairs when it is not. Thus, algorithmic complexity
32/// of operations on it depends on the kind of map.
33///
34/// A function that requires a managed object should be generic over an `Into<ManagedMap<'a, T>>`
35/// argument; then, it will be possible to pass either a `Vec<T>`, or a `&'a mut [T]`
36/// without any conversion at the call site.
37///
38/// See also [Managed](enum.Managed.html).
39pub enum ManagedMap<'a, K: 'a, V: 'a> {
40    /// Borrowed variant.
41    Borrowed(&'a mut [Option<(K, V)>]),
42    /// Owned variant, only available with the `std` or `alloc` feature enabled.
43    #[cfg(any(feature = "std", feature = "alloc"))]
44    Owned(BTreeMap<K, V>)
45}
46
47impl<'a, K: 'a, V: 'a> fmt::Debug for ManagedMap<'a, K, V>
48        where K: fmt::Debug, V: fmt::Debug {
49    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
50        match self {
51            &ManagedMap::Borrowed(ref x) => write!(f, "Borrowed({:?})", x),
52            #[cfg(any(feature = "std", feature = "alloc"))]
53            &ManagedMap::Owned(ref x)    => write!(f, "Owned({:?})", x)
54        }
55    }
56}
57
58impl<'a, K: 'a, V: 'a> From<&'a mut [Option<(K, V)>]> for ManagedMap<'a, K, V> {
59    fn from(value: &'a mut [Option<(K, V)>]) -> Self {
60        ManagedMap::Borrowed(value)
61    }
62}
63
64#[cfg(any(feature = "std", feature = "alloc"))]
65impl<'a, K: 'a, V: 'a> From<BTreeMap<K, V>> for ManagedMap<'a, K, V> {
66    fn from(value: BTreeMap<K, V>) -> Self {
67        ManagedMap::Owned(value)
68    }
69}
70
71/// Like `Option`, but with `Some` values sorting first.
72#[derive(PartialEq, Eq, PartialOrd, Ord)]
73enum RevOption<T> {
74    Some(T),
75    None
76}
77
78impl<T> From<Option<T>> for RevOption<T> {
79    fn from(other: Option<T>) -> Self {
80        match other {
81            Some(x) => RevOption::Some(x),
82            None => RevOption::None
83        }
84    }
85}
86
87impl<T> Into<Option<T>> for RevOption<T> {
88    fn into(self) -> Option<T> {
89        match self {
90            RevOption::Some(x) => Some(x),
91            RevOption::None => None
92        }
93    }
94}
95
96#[derive(Debug, Clone)]
97enum RangeInner<'a, K: 'a, V: 'a> {
98    /// Borrowed variant.
99    Borrowed { slice: &'a [Option<(K, V)>], begin: usize, end: usize },
100    /// Owned variant, only available with the `std` or `alloc` feature enabled.
101    #[cfg(any(feature = "std", feature = "alloc"))]
102    Owned(BTreeRange<'a, K, V>),
103}
104
105#[derive(Debug, Clone)]
106pub struct Range<'a, K: 'a, V: 'a>(RangeInner<'a, K, V>);
107
108impl<'a, K: 'a, V: 'a> Iterator for Range<'a, K, V> {
109    type Item = (&'a K, &'a V);
110
111    fn next(&mut self) -> Option<Self::Item> {
112        match self.0 {
113            RangeInner::Borrowed { ref slice, ref mut begin, ref end } => {
114                *begin += 1;
115                if *begin-1 >= *end {
116                    None
117                } else {
118                    match slice[*begin-1] {
119                        None => None,
120                        Some((ref k, ref v)) => Some((k, v))
121                    }
122                }
123            },
124            #[cfg(any(feature = "std", feature = "alloc"))]
125            RangeInner::Owned(ref mut range) => range.next(),
126        }
127    }
128}
129
130impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Range<'a, K, V> {
131    fn next_back(&mut self) -> Option<Self::Item> {
132        match self.0 {
133            RangeInner::Borrowed { ref slice, ref begin, ref mut end } => {
134                if *begin >= *end {
135                    None
136                } else {
137                    *end -= 1;
138                    match slice[*end] {
139                        None => None,
140                        Some((ref k, ref v)) => Some((k, v))
141                    }
142                }
143            },
144            #[cfg(any(feature = "std", feature = "alloc"))]
145            RangeInner::Owned(ref mut range) => range.next_back(),
146        }
147    }
148}
149
150fn binary_search_by_key_range<'a, K, V, Q: 'a, R>(slice: &[Option<(K, V)>], range: R) -> Result<(usize, usize), ()>
151    where K: Ord + Borrow<Q>, Q: Ord + ?Sized, R: RangeBounds<Q>
152{
153    if slice.len() == 0 {
154        return Err(())
155    }
156    let (mut left, mut right) = (0, slice.len() - 1);
157
158    macro_rules! key {
159        ( $e:expr) => { $e.as_ref().map(|&(ref key, _)| key.borrow()) }
160    }
161
162    // We cannot use slice.binary_search_by_key instead of each of the
163    // two loops here, because we need the left-most match (for begin) and
164    // the right-most match (for end), and the stdlib does not provide
165    // any of these guarantees.
166
167    // Find the beginning
168    let begin;
169    if let Bound::Unbounded = range.start_bound() {
170        begin = 0;
171    } else {
172        macro_rules! is_before_range {
173            ( $item: expr) => {
174                match &range.start_bound() {
175                    Bound::Included(ref key_begin) => $item < Some(key_begin.borrow()),
176                    Bound::Excluded(ref key_begin) => $item <= Some(key_begin.borrow()),
177                    Bound::Unbounded => unreachable!()
178                }
179            }
180        };
181        while left < right {
182            let middle = left + (right - left) / 2;
183            if is_before_range!(key!(slice[middle])) {
184                left = middle + 1;
185            } else if middle > 0 && !is_before_range!(key!(slice[middle - 1])) {
186                right = middle - 1;
187            } else {
188                left = middle;
189                break
190            }
191        }
192        if left == slice.len() || is_before_range!(key!(slice[left])) {
193            return Err(())
194        }
195        begin = left
196    };
197
198    // Find the ending
199    let end;
200    if let Bound::Unbounded = range.end_bound() {
201        end = slice.len()
202    } else {
203        macro_rules! is_after_range {
204            ( $item:expr ) => {
205                match &range.end_bound() {
206                    Bound::Included(ref key_end) => $item > Some(key_end.borrow()),
207                    Bound::Excluded(ref key_end) => $item >= Some(key_end.borrow()),
208                    Bound::Unbounded => unreachable!()
209                }
210            }
211        };
212        right = slice.len(); // no need to reset left
213        while left < right {
214            let middle = left + (right - left + 1) / 2;
215            if is_after_range!(key!(slice[middle - 1])) {
216                right = middle - 1;
217            } else if middle < slice.len() && !is_after_range!(key!(slice[middle])) {
218                left = middle + 1;
219            } else {
220                right = middle;
221                break
222            }
223        }
224        if right == 0 || is_after_range!(key!(slice[right - 1])) {
225            return Err(())
226        }
227        end = right
228    };
229
230    Ok((begin, end))
231}
232
233fn binary_search_by_key<K, V, Q>(slice: &[Option<(K, V)>], key: &Q) -> Result<usize, usize>
234    where K: Ord + Borrow<Q>, Q: Ord + ?Sized
235{
236    slice.binary_search_by_key(&RevOption::Some(key), |entry| {
237        entry.as_ref().map(|&(ref key, _)| key.borrow()).into()
238    })
239}
240
241fn pair_by_key<'a, K, Q, V>(slice: &'a [Option<(K, V)>], key: &Q) ->
242                           Result<&'a (K, V), usize>
243    where K: Ord + Borrow<Q>, Q: Ord + ?Sized
244{
245    binary_search_by_key(slice, key).map(move |idx| slice[idx].as_ref().unwrap())
246}
247
248fn pair_mut_by_key<'a, K, Q, V>(slice: &'a mut [Option<(K, V)>], key: &Q) ->
249                               Result<&'a mut (K, V), usize>
250    where K: Ord + Borrow<Q>, Q: Ord + ?Sized
251{
252    binary_search_by_key(slice, key).map(move |idx| slice[idx].as_mut().unwrap())
253}
254
255impl<'a, K: Ord + 'a, V: 'a> ManagedMap<'a, K, V> {
256    pub fn clear(&mut self) {
257        match self {
258            &mut ManagedMap::Borrowed(ref mut pairs) => {
259                for item in pairs.iter_mut() {
260                    *item = None
261                }
262            },
263            #[cfg(any(feature = "std", feature = "alloc"))]
264            &mut ManagedMap::Owned(ref mut map) => map.clear()
265        }
266    }
267
268    pub fn get<Q>(&self, key: &Q) -> Option<&V>
269        where K: Borrow<Q>, Q: Ord + ?Sized
270    {
271        match self {
272            &ManagedMap::Borrowed(ref pairs) => {
273                match pair_by_key(pairs, key.borrow()) {
274                    Ok(&(_, ref value)) => Some(value),
275                    Err(_) => None
276                }
277            },
278            #[cfg(any(feature = "std", feature = "alloc"))]
279            &ManagedMap::Owned(ref map) => map.get(key)
280        }
281    }
282
283    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
284        where K: Borrow<Q>, Q: Ord + ?Sized
285    {
286        match self {
287            &mut ManagedMap::Borrowed(ref mut pairs) => {
288                match pair_mut_by_key(pairs, key.borrow()) {
289                    Ok(&mut (_, ref mut value)) => Some(value),
290                    Err(_) => None
291                }
292            },
293            #[cfg(any(feature = "std", feature = "alloc"))]
294            &mut ManagedMap::Owned(ref mut map) => map.get_mut(key)
295        }
296    }
297
298    pub fn range<'b, 'c, Q: 'c, R>(&'b self, range: R) -> Range<'a, K, V>
299            where K: Borrow<Q>, Q: Ord + ?Sized, R: RangeBounds<Q>, 'b: 'a
300    {
301        match self {
302            &ManagedMap::Borrowed(ref pairs) => {
303                match binary_search_by_key_range(&pairs[0..self.len()], range) {
304                    Ok((begin, end)) => Range(RangeInner::Borrowed {
305                        slice: &pairs[begin..end], begin: 0, end: end-begin }),
306                    Err(()) => Range(RangeInner::Borrowed {
307                        slice: &[], begin: 0, end: 0 }),
308                }
309            },
310            #[cfg(any(feature = "std", feature = "alloc"))]
311            &ManagedMap::Owned(ref map) => {
312                Range(RangeInner::Owned(map.range(range)))
313            },
314        }
315    }
316
317    pub fn insert(&mut self, key: K, new_value: V) -> Result<Option<V>, (K, V)> {
318        match self {
319            &mut ManagedMap::Borrowed(ref mut pairs) if pairs.len() < 1 =>
320                Err((key, new_value)), // no space at all
321            &mut ManagedMap::Borrowed(ref mut pairs) => {
322                match binary_search_by_key(pairs, &key) {
323                    Err(_) if pairs[pairs.len() - 1].is_some() =>
324                        Err((key, new_value)), // full
325                    Err(idx) => {
326                        let rotate_by = pairs.len() - idx - 1;
327                        pairs[idx..].rotate_left(rotate_by);
328                        assert!(pairs[idx].is_none(), "broken invariant");
329                        pairs[idx] = Some((key, new_value));
330                        Ok(None)
331                    }
332                    Ok(idx) => {
333                        let mut swap_pair = Some((key, new_value));
334                        mem::swap(&mut pairs[idx], &mut swap_pair);
335                        let (_key, value) = swap_pair.expect("broken invariant");
336                        Ok(Some(value))
337                    }
338                }
339            },
340            #[cfg(any(feature = "std", feature = "alloc"))]
341            &mut ManagedMap::Owned(ref mut map) => Ok(map.insert(key, new_value))
342        }
343    }
344
345    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
346        where K: Borrow<Q>, Q: Ord + ?Sized
347    {
348        match self {
349            &mut ManagedMap::Borrowed(ref mut pairs) => {
350                match binary_search_by_key(pairs, key) {
351                    Ok(idx) => {
352                        let (_key, value) = pairs[idx].take().expect("broken invariant");
353                        pairs[idx..].rotate_left(1);
354                        Some(value)
355                    }
356                    Err(_) => None
357                }
358            },
359            #[cfg(any(feature = "std", feature = "alloc"))]
360            &mut ManagedMap::Owned(ref mut map) => map.remove(key)
361        }
362    }
363
364    /// ManagedMap contains no elements?
365    pub fn is_empty(&self) -> bool {
366        match self {
367            &ManagedMap::Borrowed(ref pairs) =>
368                pairs.iter().all(|item| item.is_none()),
369            #[cfg(any(feature = "std", feature = "alloc"))]
370            &ManagedMap::Owned(ref map) =>
371                map.is_empty()
372        }
373    }
374
375    /// Returns the number of elements in the ManagedMap.
376    pub fn len(&self) -> usize {
377        match self {
378            &ManagedMap::Borrowed(ref pairs) =>
379                pairs.iter()
380                .take_while(|item| item.is_some())
381                .count(),
382            #[cfg(any(feature = "std", feature = "alloc"))]
383            &ManagedMap::Owned(ref map) =>
384                map.len()
385        }
386    }
387
388    pub fn iter(&self) -> Iter<K, V> {
389        match self {
390            &ManagedMap::Borrowed(ref pairs) =>
391                Iter::Borrowed(pairs.iter()),
392            #[cfg(any(feature = "std", feature = "alloc"))]
393            &ManagedMap::Owned(ref map) =>
394                Iter::Owned(map.iter()),
395        }
396    }
397
398    pub fn iter_mut(&mut self) -> IterMut<K, V> {
399        match self {
400            &mut ManagedMap::Borrowed(ref mut pairs) =>
401                IterMut::Borrowed(pairs.iter_mut()),
402            #[cfg(any(feature = "std", feature = "alloc"))]
403            &mut ManagedMap::Owned(ref mut map) =>
404                IterMut::Owned(map.iter_mut()),
405        }
406    }
407}
408
409pub enum Iter<'a, K: 'a, V: 'a> {
410    /// Borrowed variant.
411    Borrowed(slice::Iter<'a, Option<(K, V)>>),
412    /// Owned variant, only available with the `std` or `alloc` feature enabled.
413    #[cfg(any(feature = "std", feature = "alloc"))]
414    Owned(BTreeIter<'a, K, V>),
415}
416
417impl<'a, K: Ord + 'a, V: 'a> Iterator for Iter<'a, K, V> {
418    type Item = (&'a K, &'a V);
419
420    fn next(&mut self) -> Option<Self::Item> {
421        match self {
422            &mut Iter::Borrowed(ref mut iter) =>
423                match iter.next() {
424                    Some(&Some((ref k, ref v))) => Some((&k, &v)),
425                    Some(&None) => None,
426                    None => None,
427                },
428            #[cfg(any(feature = "std", feature = "alloc"))]
429            &mut Iter::Owned(ref mut iter) =>
430                iter.next(),
431        }
432    }
433
434    fn size_hint(&self) -> (usize, Option<usize>) {
435        match self {
436            &Iter::Borrowed(ref iter) => {
437                let len = iter.clone()
438                    .take_while(|item| item.is_some())
439                    .count();
440                (len, Some(len))
441            },
442            #[cfg(any(feature = "std", feature = "alloc"))]
443            &Iter::Owned(ref iter) =>
444                iter.size_hint(),
445        }
446    }
447}
448
449pub enum IterMut<'a, K: 'a, V: 'a> {
450    /// Borrowed variant.
451    Borrowed(slice::IterMut<'a, Option<(K, V)>>),
452    /// Owned variant, only available with the `std` or `alloc` feature enabled.
453    #[cfg(any(feature = "std", feature = "alloc"))]
454    Owned(BTreeIterMut<'a, K, V>),
455}
456
457impl<'a, K: Ord + 'a, V: 'a> Iterator for IterMut<'a, K, V> {
458    type Item = (&'a K, &'a mut V);
459
460    fn next(&mut self) -> Option<Self::Item> {
461        match self {
462            &mut IterMut::Borrowed(ref mut iter) =>
463                match iter.next() {
464                    Some(&mut Some((ref k, ref mut v))) => Some((&k, v)),
465                    Some(&mut None) => None,
466                    None => None,
467                },
468            #[cfg(any(feature = "std", feature = "alloc"))]
469            &mut IterMut::Owned(ref mut iter) =>
470                iter.next(),
471        }
472    }
473
474    fn size_hint(&self) -> (usize, Option<usize>) {
475        match self {
476            &IterMut::Borrowed(ref iter) => {
477                let (_, upper) = iter.size_hint();
478                (0, upper)
479            },
480            #[cfg(any(feature = "std", feature = "alloc"))]
481            &IterMut::Owned(ref iter) =>
482                iter.size_hint(),
483        }
484    }
485}
486
487// LCOV_EXCL_START
488#[cfg(test)]
489mod test {
490    use super::ManagedMap;
491    use core::ops::Bound::*;
492
493    fn all_pairs_empty() -> [Option<(&'static str, u32)>; 4] {
494        [None; 4]
495    }
496
497    fn one_pair_full() -> [Option<(&'static str, u32)>; 4] {
498        [Some(("a", 1)), None, None, None]
499    }
500
501    fn all_pairs_full() -> [Option<(&'static str, u32)>; 4] {
502        [Some(("a", 1)), Some(("b", 2)), Some(("c", 3)), Some(("d", 4))]
503    }
504
505    fn unwrap<'a, K, V>(map: &'a ManagedMap<'a, K, V>) -> &'a [Option<(K, V)>] {
506        match map {
507            &ManagedMap::Borrowed(ref map) => map,
508            _ => unreachable!()
509        }
510    }
511
512    #[test]
513    fn test_clear() {
514        let mut pairs = all_pairs_full();
515        let mut map = ManagedMap::Borrowed(&mut pairs);
516        map.clear();
517        assert!(map.is_empty());
518        assert_eq!(map.len(), 0);
519        assert_eq!(unwrap(&map), all_pairs_empty());
520    }
521
522    #[test]
523    fn test_get_some() {
524        let mut pairs = all_pairs_full();
525        let map = ManagedMap::Borrowed(&mut pairs);
526        assert_eq!(map.len(), 4);
527        assert_eq!(map.get("a"), Some(&1));
528        assert_eq!(map.get("b"), Some(&2));
529        assert_eq!(map.get("c"), Some(&3));
530        assert_eq!(map.get("d"), Some(&4));
531    }
532
533    #[test]
534    fn test_get_some_one_pair() {
535        let mut pairs = one_pair_full();
536        let map = ManagedMap::Borrowed(&mut pairs);
537        assert_eq!(map.len(), 1);
538        assert_eq!(map.get("a"), Some(&1));
539    }
540
541    #[test]
542    fn test_get_none_full() {
543        let mut pairs = all_pairs_full();
544        let map = ManagedMap::Borrowed(&mut pairs);
545        assert_eq!(map.len(), 4);
546        assert!(!map.is_empty());
547        assert_eq!(map.get("q"), None);
548        assert_eq!(map.get("0"), None);
549    }
550
551    #[test]
552    fn test_get_none() {
553        let mut pairs = one_pair_full();
554        let map = ManagedMap::Borrowed(&mut pairs);
555        assert_eq!(map.len(), 1);
556        assert!(!map.is_empty());
557        assert_eq!(map.get("0"), None);
558        assert_eq!(map.get("q"), None);
559    }
560
561    #[test]
562    fn test_get_none_empty() {
563        let mut pairs = all_pairs_empty();
564        let map = ManagedMap::Borrowed(&mut pairs);
565        assert_eq!(map.len(), 0);
566        assert!(map.is_empty());
567        assert_eq!(map.get("q"), None);
568    }
569
570    #[test]
571    fn test_range_full_unbounded() {
572        let mut pairs = all_pairs_full();
573        let map = ManagedMap::Borrowed(&mut pairs);
574        assert_eq!(map.len(), 4);
575
576        let mut range = map.range("a"..);
577        assert_eq!(range.next(), Some((&"a", &1)));
578        assert_eq!(range.next(), Some((&"b", &2)));
579        assert_eq!(range.next(), Some((&"c", &3)));
580        assert_eq!(range.next(), Some((&"d", &4)));
581        assert_eq!(range.next(), None);
582        assert_eq!(range.next_back(), None);
583
584        let mut range = map.range("a"..);
585        assert_eq!(range.next(), Some((&"a", &1)));
586        assert_eq!(range.next_back(), Some((&"d", &4)));
587        assert_eq!(range.next_back(), Some((&"c", &3)));
588        assert_eq!(range.next(), Some((&"b", &2)));
589        assert_eq!(range.next_back(), None);
590        assert_eq!(range.next(), None);
591
592        let mut range = map.range("b"..);
593        assert_eq!(range.next(), Some((&"b", &2)));
594        assert_eq!(range.next(), Some((&"c", &3)));
595        assert_eq!(range.next(), Some((&"d", &4)));
596        assert_eq!(range.next(), None);
597        assert_eq!(range.next_back(), None);
598
599        let mut range = map.range("d"..);
600        assert_eq!(range.next(), Some((&"d", &4)));
601        assert_eq!(range.next(), None);
602        assert_eq!(range.next_back(), None);
603
604        let mut range = map.range(.."e");
605        assert_eq!(range.next(), Some((&"a", &1)));
606        assert_eq!(range.next(), Some((&"b", &2)));
607        assert_eq!(range.next(), Some((&"c", &3)));
608        assert_eq!(range.next(), Some((&"d", &4)));
609        assert_eq!(range.next(), None);
610        assert_eq!(range.next_back(), None);
611
612        let mut range = map.range(.."d");
613        assert_eq!(range.next(), Some((&"a", &1)));
614        assert_eq!(range.next(), Some((&"b", &2)));
615        assert_eq!(range.next(), Some((&"c", &3)));
616        assert_eq!(range.next(), None);
617        assert_eq!(range.next_back(), None);
618
619        let mut range = map.range(.."b");
620        assert_eq!(range.next(), Some((&"a", &1)));
621        assert_eq!(range.next(), None);
622        assert_eq!(range.next_back(), None);
623
624        let mut range = map.range(.."a");
625        assert_eq!(range.next(), None);
626        assert_eq!(range.next_back(), None);
627
628        let mut range = map.range::<&str, _>(..);
629        assert_eq!(range.next(), Some((&"a", &1)));
630        assert_eq!(range.next(), Some((&"b", &2)));
631        assert_eq!(range.next(), Some((&"c", &3)));
632        assert_eq!(range.next(), Some((&"d", &4)));
633        assert_eq!(range.next(), None);
634        assert_eq!(range.next_back(), None);
635    }
636
637    #[test]
638    fn test_range_full_exclude_left() {
639        let mut pairs = all_pairs_full();
640        let map = ManagedMap::Borrowed(&mut pairs);
641        assert_eq!(map.len(), 4);
642
643        let mut range = map.range::<&str, _>((Excluded("a"), Excluded("a")));
644        assert_eq!(range.next(), None);
645        let mut range = map.range::<&str, _>((Excluded("a"), Excluded("b")));
646        assert_eq!(range.next(), None);
647        let mut range = map.range::<&str, _>((Excluded("a"), Excluded("c")));
648        assert_eq!(range.next(), Some((&"b", &2)));
649        assert_eq!(range.next(), None);
650        let mut range = map.range::<&str, _>((Excluded("a"), Excluded("d")));
651        assert_eq!(range.next(), Some((&"b", &2)));
652        assert_eq!(range.next(), Some((&"c", &3)));
653        assert_eq!(range.next(), None);
654        let mut range = map.range::<&str, _>((Excluded("a"), Excluded("e")));
655        assert_eq!(range.next(), Some((&"b", &2)));
656        assert_eq!(range.next(), Some((&"c", &3)));
657        assert_eq!(range.next(), Some((&"d", &4)));
658        assert_eq!(range.next(), None);
659    }
660
661    #[test]
662    fn test_range_full_include_right() {
663        let mut pairs = all_pairs_full();
664        let map = ManagedMap::Borrowed(&mut pairs);
665        assert_eq!(map.len(), 4);
666
667        let mut range = map.range::<&str, _>((Included("b"), Included("a")));
668        assert_eq!(range.next(), None);
669        let mut range = map.range::<&str, _>((Included("b"), Included("b")));
670        assert_eq!(range.next(), Some((&"b", &2)));
671        assert_eq!(range.next(), None);
672        let mut range = map.range::<&str, _>((Included("b"), Included("c")));
673        assert_eq!(range.next(), Some((&"b", &2)));
674        assert_eq!(range.next(), Some((&"c", &3)));
675        assert_eq!(range.next(), None);
676        let mut range = map.range::<&str, _>((Included("b"), Included("d")));
677        assert_eq!(range.next(), Some((&"b", &2)));
678        assert_eq!(range.next(), Some((&"c", &3)));
679        assert_eq!(range.next(), Some((&"d", &4)));
680        assert_eq!(range.next(), None);
681        let mut range = map.range::<&str, _>((Included("b"), Included("e")));
682        assert_eq!(range.next(), Some((&"b", &2)));
683        assert_eq!(range.next(), Some((&"c", &3)));
684        assert_eq!(range.next(), Some((&"d", &4)));
685        assert_eq!(range.next(), None);
686
687        let mut range = map.range::<&str, _>((Included("b"), Included("a")));
688        assert_eq!(range.next_back(), None);
689        let mut range = map.range::<&str, _>((Included("b"), Included("b")));
690        assert_eq!(range.next_back(), Some((&"b", &2)));
691        assert_eq!(range.next_back(), None);
692        let mut range = map.range::<&str, _>((Included("b"), Included("c")));
693        assert_eq!(range.next_back(), Some((&"c", &3)));
694        assert_eq!(range.next_back(), Some((&"b", &2)));
695        assert_eq!(range.next_back(), None);
696        let mut range = map.range::<&str, _>((Included("b"), Included("d")));
697        assert_eq!(range.next_back(), Some((&"d", &4)));
698        assert_eq!(range.next_back(), Some((&"c", &3)));
699        assert_eq!(range.next_back(), Some((&"b", &2)));
700        assert_eq!(range.next_back(), None);
701        let mut range = map.range::<&str, _>((Included("b"), Included("e")));
702        assert_eq!(range.next_back(), Some((&"d", &4)));
703        assert_eq!(range.next_back(), Some((&"c", &3)));
704        assert_eq!(range.next_back(), Some((&"b", &2)));
705        assert_eq!(range.next_back(), None);
706    }
707
708    #[test]
709    fn test_range_full() {
710        let mut pairs = all_pairs_full();
711        let map = ManagedMap::Borrowed(&mut pairs);
712        assert_eq!(map.len(), 4);
713
714        let mut range = map.range("0".."a");
715        assert_eq!(range.next(), None);
716        let mut range = map.range("0".."b");
717        assert_eq!(range.next(), Some((&"a", &1)));
718        assert_eq!(range.next(), None);
719        let mut range = map.range("0".."c");
720        assert_eq!(range.next(), Some((&"a", &1)));
721        assert_eq!(range.next(), Some((&"b", &2)));
722        assert_eq!(range.next(), None);
723        let mut range = map.range("0".."d");
724        assert_eq!(range.next(), Some((&"a", &1)));
725        assert_eq!(range.next(), Some((&"b", &2)));
726        assert_eq!(range.next(), Some((&"c", &3)));
727        assert_eq!(range.next(), None);
728        let mut range = map.range("0".."e");
729        assert_eq!(range.next(), Some((&"a", &1)));
730        assert_eq!(range.next(), Some((&"b", &2)));
731        assert_eq!(range.next(), Some((&"c", &3)));
732        assert_eq!(range.next(), Some((&"d", &4)));
733        assert_eq!(range.next(), None);
734
735        let mut range = map.range("a".."a");
736        assert_eq!(range.next(), None);
737        let mut range = map.range("a".."b");
738        assert_eq!(range.next(), Some((&"a", &1)));
739        assert_eq!(range.next(), None);
740        let mut range = map.range("a".."c");
741        assert_eq!(range.next(), Some((&"a", &1)));
742        assert_eq!(range.next(), Some((&"b", &2)));
743        assert_eq!(range.next(), None);
744        let mut range = map.range("a".."d");
745        assert_eq!(range.next(), Some((&"a", &1)));
746        assert_eq!(range.next(), Some((&"b", &2)));
747        assert_eq!(range.next(), Some((&"c", &3)));
748        assert_eq!(range.next(), None);
749        let mut range = map.range("a".."e");
750        assert_eq!(range.next(), Some((&"a", &1)));
751        assert_eq!(range.next(), Some((&"b", &2)));
752        assert_eq!(range.next(), Some((&"c", &3)));
753        assert_eq!(range.next(), Some((&"d", &4)));
754        assert_eq!(range.next(), None);
755
756        let mut range = map.range("b".."a");
757        assert_eq!(range.next(), None);
758        let mut range = map.range("b".."b");
759        assert_eq!(range.next(), None);
760        let mut range = map.range("b".."c");
761        assert_eq!(range.next(), Some((&"b", &2)));
762        assert_eq!(range.next(), None);
763        let mut range = map.range("b".."d");
764        assert_eq!(range.next(), Some((&"b", &2)));
765        assert_eq!(range.next(), Some((&"c", &3)));
766        assert_eq!(range.next(), None);
767        let mut range = map.range("b".."e");
768        assert_eq!(range.next(), Some((&"b", &2)));
769        assert_eq!(range.next(), Some((&"c", &3)));
770        assert_eq!(range.next(), Some((&"d", &4)));
771        assert_eq!(range.next(), None);
772
773        let mut range = map.range("c".."a");
774        assert_eq!(range.next(), None);
775        let mut range = map.range("c".."b");
776        assert_eq!(range.next(), None);
777        let mut range = map.range("c".."c");
778        assert_eq!(range.next(), None);
779        let mut range = map.range("c".."d");
780        assert_eq!(range.next(), Some((&"c", &3)));
781        assert_eq!(range.next(), None);
782        let mut range = map.range("c".."e");
783        assert_eq!(range.next(), Some((&"c", &3)));
784        assert_eq!(range.next(), Some((&"d", &4)));
785        assert_eq!(range.next(), None);
786
787        let mut range = map.range("d".."a");
788        assert_eq!(range.next(), None);
789        let mut range = map.range("d".."b");
790        assert_eq!(range.next(), None);
791        let mut range = map.range("d".."c");
792        assert_eq!(range.next(), None);
793        let mut range = map.range("d".."d");
794        assert_eq!(range.next(), None);
795        let mut range = map.range("d".."e");
796        assert_eq!(range.next(), Some((&"d", &4)));
797        assert_eq!(range.next(), None);
798
799        let mut range = map.range("e".."a");
800        assert_eq!(range.next(), None);
801        let mut range = map.range("e".."b");
802        assert_eq!(range.next(), None);
803        let mut range = map.range("e".."c");
804        assert_eq!(range.next(), None);
805        let mut range = map.range("e".."d");
806        assert_eq!(range.next(), None);
807        let mut range = map.range("e".."e");
808        assert_eq!(range.next(), None);
809    }
810
811    #[test]
812    fn test_range_one_pair() {
813        let mut pairs = one_pair_full();
814        let map = ManagedMap::Borrowed(&mut pairs);
815        assert_eq!(map.len(), 1);
816
817        let mut range = map.range("0".."a");
818        assert_eq!(range.next(), None);
819        let mut range = map.range("0".."b");
820        assert_eq!(range.next(), Some((&"a", &1)));
821        assert_eq!(range.next(), None);
822        let mut range = map.range("0".."c");
823        assert_eq!(range.next(), Some((&"a", &1)));
824        assert_eq!(range.next(), None);
825
826        let mut range = map.range("a".."a");
827        assert_eq!(range.next(), None);
828        let mut range = map.range("a".."b");
829        assert_eq!(range.next(), Some((&"a", &1)));
830        assert_eq!(range.next(), None);
831        let mut range = map.range("a".."c");
832        assert_eq!(range.next(), Some((&"a", &1)));
833        assert_eq!(range.next(), None);
834
835        let mut range = map.range("b".."a");
836        assert_eq!(range.next(), None);
837        let mut range = map.range("b".."b");
838        assert_eq!(range.next(), None);
839        let mut range = map.range("b".."c");
840        assert_eq!(range.next(), None);
841    }
842
843    #[test]
844    fn test_range_empty() {
845        let mut pairs = all_pairs_empty();
846        let map = ManagedMap::Borrowed(&mut pairs);
847        assert_eq!(map.len(), 0);
848
849        let mut range = map.range("b".."a");
850        assert_eq!(range.next(), None);
851        let mut range = map.range("b".."b");
852        assert_eq!(range.next(), None);
853        let mut range = map.range("b".."c");
854        assert_eq!(range.next(), None);
855    }
856
857    #[test]
858    fn test_get_mut_some() {
859        let mut pairs = all_pairs_full();
860        let mut map = ManagedMap::Borrowed(&mut pairs);
861        assert_eq!(map.len(), 4);
862        assert!(!map.is_empty());
863        assert_eq!(map.get_mut("a"), Some(&mut 1));
864        assert_eq!(map.get_mut("b"), Some(&mut 2));
865        assert_eq!(map.get_mut("c"), Some(&mut 3));
866        assert_eq!(map.get_mut("d"), Some(&mut 4));
867    }
868
869    #[test]
870    fn test_get_mut_none() {
871        let mut pairs = one_pair_full();
872        let mut map = ManagedMap::Borrowed(&mut pairs);
873        assert_eq!(map.get_mut("q"), None);
874    }
875
876    #[test]
877    fn test_insert_empty() {
878        let mut pairs = all_pairs_empty();
879        let mut map = ManagedMap::Borrowed(&mut pairs);
880        assert_eq!(map.len(), 0);
881        assert!(map.is_empty());
882
883        assert_eq!(map.insert("a", 1), Ok(None));
884        assert_eq!(map.len(), 1);
885        assert!(!map.is_empty());
886        assert_eq!(unwrap(&map),       [Some(("a", 1)), None, None, None]);
887    }
888
889    #[test]
890    fn test_insert_replace() {
891        let mut pairs = all_pairs_empty();
892        let mut map = ManagedMap::Borrowed(&mut pairs);
893        assert_eq!(map.insert("a", 1), Ok(None));
894        assert_eq!(map.insert("a", 2), Ok(Some(1)));
895        assert_eq!(map.len(), 1);
896        assert!(!map.is_empty());
897        assert_eq!(unwrap(&map),       [Some(("a", 2)), None, None, None]);
898    }
899
900    #[test]
901    fn test_insert_full() {
902        let mut pairs = all_pairs_full();
903        let mut map = ManagedMap::Borrowed(&mut pairs);
904        assert_eq!(map.insert("q", 1), Err(("q", 1)));
905        assert_eq!(map.len(), 4);
906        assert_eq!(unwrap(&map),       all_pairs_full());
907    }
908
909    #[test]
910    fn test_insert_one() {
911        let mut pairs = one_pair_full();
912        let mut map = ManagedMap::Borrowed(&mut pairs);
913        assert_eq!(map.insert("b", 2), Ok(None));
914        assert_eq!(unwrap(&map),       [Some(("a", 1)), Some(("b", 2)), None, None]);
915    }
916
917    #[test]
918    fn test_insert_shift() {
919        let mut pairs = one_pair_full();
920        let mut map = ManagedMap::Borrowed(&mut pairs);
921        assert_eq!(map.insert("c", 3), Ok(None));
922        assert_eq!(map.insert("b", 2), Ok(None));
923        assert_eq!(unwrap(&map),       [Some(("a", 1)), Some(("b", 2)), Some(("c", 3)), None]);
924    }
925
926    #[test]
927    fn test_insert_no_space() {
928        // Zero-sized backing store
929        let mut map = ManagedMap::Borrowed(&mut []);
930        assert_eq!(map.insert("a", 1), Err(("a", 1)));
931    }
932
933    #[test]
934    fn test_remove_nonexistent() {
935        let mut pairs = one_pair_full();
936        let mut map = ManagedMap::Borrowed(&mut pairs);
937        assert_eq!(map.remove("b"), None);
938        assert_eq!(map.len(), 1);
939    }
940
941    #[test]
942    fn test_remove_one() {
943        let mut pairs = all_pairs_full();
944        let mut map = ManagedMap::Borrowed(&mut pairs);
945        assert_eq!(map.remove("a"), Some(1));
946        assert_eq!(map.len(), 3);
947        assert_eq!(unwrap(&map),    [Some(("b", 2)), Some(("c", 3)), Some(("d", 4)), None]);
948    }
949
950    #[test]
951    fn test_iter_none() {
952        let mut pairs = all_pairs_empty();
953        let map = ManagedMap::Borrowed(&mut pairs);
954        let mut iter = map.iter();
955        assert_eq!(iter.size_hint(), (0, Some(0)));
956        assert_eq!(iter.next(), None);
957    }
958
959    #[test]
960    fn test_iter_one() {
961        let mut pairs = one_pair_full();
962        let map = ManagedMap::Borrowed(&mut pairs);
963        let mut iter = map.iter();
964        assert_eq!(iter.size_hint(), (1, Some(1)));
965        assert_eq!(iter.next(), Some((&"a", &1)));
966        assert_eq!(iter.size_hint(), (0, Some(0)));
967        assert_eq!(iter.next(), None);
968    }
969
970    #[test]
971    fn test_iter_full() {
972        let mut pairs = all_pairs_full();
973        let map = ManagedMap::Borrowed(&mut pairs);
974        let mut iter = map.iter();
975        assert_eq!(iter.size_hint(), (4, Some(4)));
976        assert_eq!(iter.next(), Some((&"a", &1)));
977        assert_eq!(iter.next(), Some((&"b", &2)));
978        assert_eq!(iter.next(), Some((&"c", &3)));
979        assert_eq!(iter.next(), Some((&"d", &4)));
980        assert_eq!(iter.next(), None);
981    }
982
983    #[test]
984    fn test_iter_mut_full() {
985        let mut pairs = all_pairs_full();
986        let mut map = ManagedMap::Borrowed(&mut pairs);
987
988        {
989            let mut iter = map.iter_mut();
990            assert_eq!(iter.size_hint(), (0, Some(4)));
991            for (_k, mut v) in &mut iter {
992                *v += 1;
993            }
994            assert_eq!(iter.size_hint(), (0, Some(0)));
995            // Scope for `iter` ends here so that it can be borrowed
996            // again with the following `iter`.
997        }
998        {
999            let mut iter = map.iter();
1000            assert_eq!(iter.next(), Some((&"a", &2)));
1001            assert_eq!(iter.next(), Some((&"b", &3)));
1002            assert_eq!(iter.next(), Some((&"c", &4)));
1003            assert_eq!(iter.next(), Some((&"d", &5)));
1004            assert_eq!(iter.next(), None);
1005        }
1006    }
1007}
managed/map.rs

managed/
map.rs
