gen_map 0.3.0

A generational map with configurable key size, key layout and storage.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

//! Storages that implement `SlotStorage` and little else, to check that a
//! map only asks for more where a method needs it.

use crate::{GenMap, GenMapConfig, GenSlotItem, MapConfig, SlotStorage, Split};
use std::vec::Vec;

/// A `Vec` behind `SlotStorage` alone. With `ITER` it also has an owning
/// iterator, which implements `Iterator` but not `DoubleEndedIterator` or
/// `ExactSizeIterator`.
struct Bare<S, const ITER: bool>(Vec<S>);

// SAFETY: every method forwards to the `Vec`, which behaves as the trait
// describes.
unsafe impl<S, const ITER: bool> SlotStorage for Bare<S, ITER> {
    type Item = S;
    type Error = ();

    fn empty() -> Self {
        Bare(Vec::new())
    }

    fn with_capacity(capacity: usize) -> Self {
        Bare(Vec::with_capacity(capacity))
    }

    fn capacity(&self) -> usize {
        self.0.capacity()
    }

    fn as_slice(&self) -> &[S] {
        &self.0
    }

    fn as_mut_slice(&mut self) -> &mut [S] {
        &mut self.0
    }

    fn ensure_room(&mut self, _additional: usize) -> Result<(), ()> {
        Ok(())
    }

    fn try_push(&mut self, item: S) -> Result<(), S> {
        self.0.push(item);
        Ok(())
    }

    fn clear(&mut self) {
        self.0.clear();
    }
}

/// A `Vec` iterator that only implements `Iterator`, so it has no
/// `next_back` and no `len`.
struct Forwards<S>(std::vec::IntoIter<S>);

impl<S> Iterator for Forwards<S> {
    type Item = S;

    fn next(&mut self) -> Option<S> {
        self.0.next()
    }
}

impl<S> IntoIterator for Bare<S, true> {
    type Item = S;
    type IntoIter = Forwards<S>;

    fn into_iter(self) -> Forwards<S> {
        Forwards(self.0.into_iter())
    }
}

/// Its storage has no owning iterator.
struct NoIter;

impl MapConfig for NoIter {
    type KeyConfig = Split<u32, u32>;
}

impl<S: GenSlotItem> GenMapConfig<S> for NoIter {
    type Storage = Bare<S, false>;
}

/// Its storage's owning iterator is a `Forwards`.
struct ForwardIter;

impl MapConfig for ForwardIter {
    type KeyConfig = Split<u32, u32>;
}

impl<S: GenSlotItem> GenMapConfig<S> for ForwardIter {
    type Storage = Bare<S, true>;
}

#[test]
fn a_map_works_without_an_owning_iterator() {
    let mut map = GenMap::<u32, NoIter>::new_with_config();
    let a = map.insert(1);
    let b = map.insert(2);
    assert_eq!(map.remove(a), Some(1));
    let c = map.insert(3);
    assert_eq!(c.idx(), a.idx());

    // The borrowing iterators do not need anything from the storage.
    let backwards: Vec<_> = map.iter().rev().map(|(_, value)| *value).collect();
    assert_eq!(backwards, [2, 3]);
    let copy = map.clone();
    assert_eq!((copy[b], copy[c]), (2, 3));
    let drained: Vec<_> = map.drain().collect();
    assert_eq!(drained, [(c, 3), (b, 2)]);
}

#[test]
fn into_iter_works_when_the_storage_iterator_has_no_next_back() {
    let mut map = GenMap::<u32, ForwardIter>::new_with_config();
    let keys: Vec<_> = (0..4).map(|i| map.insert(i)).collect();
    map.remove(keys[1]);

    let mut iter = map.into_iter();
    // The map counts its own values, so the length is still exact.
    assert_eq!(iter.len(), 3);
    assert_eq!(iter.next(), Some((keys[0], 0)));
    assert_eq!(iter.len(), 2);
    let rest: Vec<_> = iter.collect();
    assert_eq!(rest, [(keys[2], 2), (keys[3], 3)]);
}