key_node_list/
map.rs

1use std::borrow::Borrow;
2use std::collections::HashMap;
3use std::hash::Hash;
4
5/// An interface to the hash map operations used by
6/// [`KeyNodeList`](crate::KeyNodeList).
7///
8/// Any data structure that implements this trait can be used as the
9/// underlying hash map for [`KeyNodeList`](crate::KeyNodeList).
10pub trait Map<K, V> {
11  /// Returns the number of elements in the map.
12  ///
13  /// This operation should compute in *O*(1) time.
14  fn len(&self) -> usize;
15
16  /// Returns `true` if the map contains no elements.
17  ///
18  /// This operation should compute in *O*(1) time.
19  #[inline]
20  fn is_empty(&self) -> bool {
21    self.len() == 0
22  }
23
24  /// Clears the map, removing all key-value pairs.
25  /// Keeps the allocated memory for reuse.
26  fn clear(&mut self);
27
28  /// Returns `true` if the map contains a value for the specified key.
29  ///
30  /// The key may be any borrowed form of the map’s key type, but [`Hash`]
31  /// and [`Eq`] on the borrowed form must match those for the key type.
32  ///
33  /// This operation should compute in *O*(1) time on average.
34  #[inline]
35  fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
36  where
37    K: Hash + Eq + Borrow<Q>,
38    Q: Hash + Eq,
39  {
40    self.get(k).is_some()
41  }
42
43  /// Returns a reference to the value corresponding to the key.
44  ///
45  /// The key may be any borrowed form of the map’s key type, but [`Hash`]
46  /// and [`Eq`] on the borrowed form must match those for the key type.
47  ///
48  /// This operation should compute in *O*(1) time on average.
49  fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
50  where
51    K: Hash + Eq + Borrow<Q>,
52    Q: Hash + Eq;
53
54  /// Returns a mutable reference to the value corresponding to the key.
55  ///
56  /// The key may be any borrowed form of the map’s key type, but [`Hash`]
57  /// and [`Eq`] on the borrowed form must match those for the key type.
58  ///
59  /// This operation should compute in *O*(1) time on average.
60  fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
61  where
62    K: Hash + Eq + Borrow<Q>,
63    Q: Hash + Eq;
64
65  /// Inserts a key-value pair into the map.
66  ///
67  /// If the map did have this key present, returns an error containing the
68  /// key and the value.
69  ///
70  /// If the map did not have this key present, the key-value pair is
71  /// inserted, and [`Ok(())`](Ok) is returned.
72  ///
73  /// This operation should compute in *O*(1) time on average.
74  fn insert<T: Into<V>>(&mut self, k: K, v: T) -> Result<(), (K, T)>
75  where
76    K: Hash + Eq;
77
78  /// Removes a key from the map, returning the value at the key if the key
79  /// was previously in the map.
80  ///
81  /// The key may be any borrowed form of the map’s key type, but [`Hash`]
82  /// and [`Eq`] on the borrowed form must match those for the key type.
83  ///
84  /// This operation should compute in *O*(1) time on average.
85  #[inline]
86  fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
87  where
88    K: Hash + Eq + Borrow<Q>,
89    Q: Hash + Eq,
90  {
91    self.remove_entry(k).map(|(_, v)| v)
92  }
93
94  /// Removes a key from the map, returning the stored key and value if the
95  /// key was previously in the map.
96  ///
97  /// The key may be any borrowed form of the map’s key type, but [`Hash`]
98  /// and [`Eq`] on the borrowed form must match those for the key type.
99  ///
100  /// This operation should compute in *O*(1) time on average.
101  fn remove_entry<Q: ?Sized>(&mut self, k: &Q) -> Option<(K, V)>
102  where
103    K: Hash + Eq + Borrow<Q>,
104    Q: Hash + Eq;
105}
106
107impl<K, V> Map<K, V> for HashMap<K, V> {
108  #[inline]
109  fn len(&self) -> usize {
110    self.len()
111  }
112
113  #[inline]
114  fn clear(&mut self) {
115    self.clear()
116  }
117
118  #[inline]
119  fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
120  where
121    K: Hash + Eq + Borrow<Q>,
122    Q: Hash + Eq,
123  {
124    self.get(k)
125  }
126
127  #[inline]
128  fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
129  where
130    K: Hash + Eq + Borrow<Q>,
131    Q: Hash + Eq,
132  {
133    self.get_mut(k)
134  }
135
136  #[inline]
137  #[allow(clippy::map_entry)]
138  fn insert<T: Into<V>>(&mut self, k: K, v: T) -> Result<(), (K, T)>
139  where
140    K: Hash + Eq,
141  {
142    if self.contains_key(&k) {
143      Err((k, v))
144    } else {
145      self.insert(k, v.into());
146      Ok(())
147    }
148  }
149
150  #[inline]
151  fn remove_entry<Q: ?Sized>(&mut self, k: &Q) -> Option<(K, V)>
152  where
153    K: Hash + Eq + Borrow<Q>,
154    Q: Hash + Eq,
155  {
156    self.remove_entry(k)
157  }
158}
key_node_list/map.rs

key_node_list/
map.rs
