shawshank 0.2.3

An efficient, generic internment structure.
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

use std::collections::{BTreeMap, HashMap};
use std::hash::{Hash, BuildHasher};

/// The interface for the key-value map internal to an [`ArenaSet`].
///
/// The Entry API is not supported, because it can't be used as is, anyway:
/// the reference passed as a key to `entry(K)` would be to something outside
/// the arena_set, which we absolutely don't want to store in the map. The Entry
/// API would have to be extended to allow changing the key before insertion.
///
/// [`ArenaSet`]: struct.ArenaSet.html
pub trait Map {
    type Key;
    type Value;

    /// Create an empty map.
    ///
    /// This is required for `ArenaSet` to function properly.
    fn new() -> Self;

    /// Create an empty map with a capacity hint.
    ///
    /// Not all implementations may support this, making it equivalent to
    /// `Map::new`.
    fn with_capacity(usize) -> Self;

    /// Get the number of pairs in the map.
    fn len(&self) -> usize;

    /// Insert a key-value pair. If there was already an entry for the key,
    /// it gets replaced, and the previous returned.
    ///
    /// This is required for `ArenaSet` to function properly.
    fn insert(&mut self, Self::Key, Self::Value) -> Option<Self::Value>;

    /// Get a value by its key.
    ///
    /// This is required for `ArenaSet` to function properly.
    fn get(&self, Self::Key) -> Option<&Self::Value>;

    /// Remove a pair by its key.
    ///
    /// This is required for `ArenaSet` to function properly.
    fn remove(&mut self, Self::Key) -> Option<Self::Value>;

    /// Reduce memory usage as much as possible.
    ///
    /// Not all implementations may support this, making it a no-op.
    fn shrink_to_fit(&mut self);
}

impl<K: Eq + Hash, V, H: Default + BuildHasher> Map for HashMap<K, V, H> {
    type Key = K;
    type Value = V;

    fn new() -> Self {
        HashMap::default()
    }

    fn with_capacity(capacity: usize) -> Self {
        HashMap::with_capacity_and_hasher(capacity, Default::default())
    }

    fn len(&self) -> usize {
        self.len()
    }

    fn insert(&mut self, k: K, v: V) -> Option<V> {
        self.insert(k, v)
    }

    fn get(&self, k: K) -> Option<&V> {
        self.get(&k)
    }

    fn remove(&mut self, k: K) -> Option<V> {
        self.remove(&k)
    }

    fn shrink_to_fit(&mut self) {
        self.shrink_to_fit();
    }
}

impl<K: Eq + Ord, V> Map for BTreeMap<K, V> {
    type Key = K;
    type Value = V;

    fn new() -> Self {
        BTreeMap::new()
    }

    fn with_capacity(_: usize) -> Self {
        BTreeMap::new()
    }

    fn len(&self) -> usize {
        self.len()
    }

    fn insert(&mut self, k: K, v: V) -> Option<V> {
        self.insert(k, v)
    }

    fn get(&self, k: K) -> Option<&V> {
        self.get(&k)
    }

    fn remove(&mut self, k: K) -> Option<V> {
        self.remove(&k)
    }

    fn shrink_to_fit(&mut self) {}
}