1use crate::Vec;
2use core::{borrow::Borrow, fmt, iter::FromIterator, mem, ops, slice};
3
4/// A fixed capacity map / dictionary that performs lookups via linear search
5///
6/// Note that as this map doesn't use hashing so most operations are **O(N)** instead of O(1)
7
8pub struct LinearMap<K, V, const N: usize> {
9 pub(crate) buffer: Vec<(K, V), N>,
10}
11
12impl<K, V, const N: usize> LinearMap<K, V, N> {
13 /// Creates an empty `LinearMap`
14 ///
15 /// # Examples
16 ///
17 /// ```
18 /// use heapless::LinearMap;
19 ///
20 /// // allocate the map on the stack
21 /// let mut map: LinearMap<&str, isize, 8> = LinearMap::new();
22 ///
23 /// // allocate the map in a static variable
24 /// static mut MAP: LinearMap<&str, isize, 8> = LinearMap::new();
25 /// ```
26 pub const fn new() -> Self {
27 Self { buffer: Vec::new() }
28 }
29}
30
31impl<K, V, const N: usize> LinearMap<K, V, N>
32where
33 K: Eq,
34{
35 /// Returns the number of elements that the map can hold
36 ///
37 /// Computes in **O(1)** time
38 ///
39 /// # Examples
40 ///
41 /// ```
42 /// use heapless::LinearMap;
43 ///
44 /// let map: LinearMap<&str, isize, 8> = LinearMap::new();
45 /// assert_eq!(map.capacity(), 8);
46 /// ```
47 pub fn capacity(&self) -> usize {
48 N
49 }
50
51 /// Clears the map, removing all key-value pairs
52 ///
53 /// Computes in **O(1)** time
54 ///
55 /// # Examples
56 ///
57 /// ```
58 /// use heapless::LinearMap;
59 ///
60 /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
61 /// map.insert(1, "a").unwrap();
62 /// map.clear();
63 /// assert!(map.is_empty());
64 /// ```
65 pub fn clear(&mut self) {
66 self.buffer.clear()
67 }
68
69 /// Returns true if the map contains a value for the specified key.
70 ///
71 /// Computes in **O(N)** time
72 ///
73 /// # Examples
74 ///
75 /// ```
76 /// use heapless::LinearMap;
77 ///
78 /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
79 /// map.insert(1, "a").unwrap();
80 /// assert_eq!(map.contains_key(&1), true);
81 /// assert_eq!(map.contains_key(&2), false);
82 /// ```
83 pub fn contains_key(&self, key: &K) -> bool {
84 self.get(key).is_some()
85 }
86
87 /// Returns a reference to the value corresponding to the key
88 ///
89 /// Computes in **O(N)** time
90 ///
91 /// # Examples
92 ///
93 /// ```
94 /// use heapless::LinearMap;
95 ///
96 /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
97 /// map.insert(1, "a").unwrap();
98 /// assert_eq!(map.get(&1), Some(&"a"));
99 /// assert_eq!(map.get(&2), None);
100 /// ```
101 pub fn get<Q>(&self, key: &Q) -> Option<&V>
102 where
103 K: Borrow<Q>,
104 Q: Eq + ?Sized,
105 {
106 self.iter()
107 .find(|&(k, _)| k.borrow() == key)
108 .map(|(_, v)| v)
109 }
110
111 /// Returns a mutable reference to the value corresponding to the key
112 ///
113 /// Computes in **O(N)** time
114 ///
115 /// # Examples
116 ///
117 /// ```
118 /// use heapless::LinearMap;
119 ///
120 /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
121 /// map.insert(1, "a").unwrap();
122 /// if let Some(x) = map.get_mut(&1) {
123 /// *x = "b";
124 /// }
125 /// assert_eq!(map[&1], "b");
126 /// ```
127 pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
128 where
129 K: Borrow<Q>,
130 Q: Eq + ?Sized,
131 {
132 self.iter_mut()
133 .find(|&(k, _)| k.borrow() == key)
134 .map(|(_, v)| v)
135 }
136
137 /// Returns the number of elements in this map
138 ///
139 /// Computes in **O(1)** time
140 ///
141 /// # Examples
142 ///
143 /// ```
144 /// use heapless::LinearMap;
145 ///
146 /// let mut a: LinearMap<_, _, 8> = LinearMap::new();
147 /// assert_eq!(a.len(), 0);
148 /// a.insert(1, "a").unwrap();
149 /// assert_eq!(a.len(), 1);
150 /// ```
151 pub fn len(&self) -> usize {
152 self.buffer.len()
153 }
154
155 /// Inserts a key-value pair into the map.
156 ///
157 /// If the map did not have this key present, `None` is returned.
158 ///
159 /// If the map did have this key present, the value is updated, and the old value is returned.
160 ///
161 /// Computes in **O(N)** time
162 ///
163 /// # Examples
164 ///
165 /// ```
166 /// use heapless::LinearMap;
167 ///
168 /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
169 /// assert_eq!(map.insert(37, "a").unwrap(), None);
170 /// assert_eq!(map.is_empty(), false);
171 ///
172 /// map.insert(37, "b").unwrap();
173 /// assert_eq!(map.insert(37, "c").unwrap(), Some("b"));
174 /// assert_eq!(map[&37], "c");
175 /// ```
176 pub fn insert(&mut self, key: K, mut value: V) -> Result<Option<V>, (K, V)> {
177 if let Some((_, v)) = self.iter_mut().find(|&(k, _)| *k == key) {
178 mem::swap(v, &mut value);
179 return Ok(Some(value));
180 }
181
182 self.buffer.push((key, value))?;
183 Ok(None)
184 }
185
186 /// Returns true if the map contains no elements
187 ///
188 /// Computes in **O(1)** time
189 ///
190 /// # Examples
191 ///
192 /// ```
193 /// use heapless::LinearMap;
194 ///
195 /// let mut a: LinearMap<_, _, 8> = LinearMap::new();
196 /// assert!(a.is_empty());
197 /// a.insert(1, "a").unwrap();
198 /// assert!(!a.is_empty());
199 /// ```
200 pub fn is_empty(&self) -> bool {
201 self.len() == 0
202 }
203
204 /// An iterator visiting all key-value pairs in arbitrary order.
205 ///
206 /// # Examples
207 ///
208 /// ```
209 /// use heapless::LinearMap;
210 ///
211 /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
212 /// map.insert("a", 1).unwrap();
213 /// map.insert("b", 2).unwrap();
214 /// map.insert("c", 3).unwrap();
215 ///
216 /// for (key, val) in map.iter() {
217 /// println!("key: {} val: {}", key, val);
218 /// }
219 /// ```
220 pub fn iter(&self) -> Iter<'_, K, V> {
221 Iter {
222 iter: self.buffer.as_slice().iter(),
223 }
224 }
225
226 /// An iterator visiting all key-value pairs in arbitrary order, with mutable references to the
227 /// values
228 ///
229 /// # Examples
230 ///
231 /// ```
232 /// use heapless::LinearMap;
233 ///
234 /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
235 /// map.insert("a", 1).unwrap();
236 /// map.insert("b", 2).unwrap();
237 /// map.insert("c", 3).unwrap();
238 ///
239 /// // Update all values
240 /// for (_, val) in map.iter_mut() {
241 /// *val = 2;
242 /// }
243 ///
244 /// for (key, val) in &map {
245 /// println!("key: {} val: {}", key, val);
246 /// }
247 /// ```
248 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
249 IterMut {
250 iter: self.buffer.as_mut_slice().iter_mut(),
251 }
252 }
253
254 /// An iterator visiting all keys in arbitrary order
255 ///
256 /// # Examples
257 ///
258 /// ```
259 /// use heapless::LinearMap;
260 ///
261 /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
262 /// map.insert("a", 1).unwrap();
263 /// map.insert("b", 2).unwrap();
264 /// map.insert("c", 3).unwrap();
265 ///
266 /// for key in map.keys() {
267 /// println!("{}", key);
268 /// }
269 /// ```
270 pub fn keys(&self) -> impl Iterator<Item = &K> {
271 self.iter().map(|(k, _)| k)
272 }
273
274 /// Removes a key from the map, returning the value at the key if the key was previously in the
275 /// map
276 ///
277 /// Computes in **O(N)** time
278 ///
279 /// # Examples
280 ///
281 /// ```
282 /// use heapless::LinearMap;
283 ///
284 /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
285 /// map.insert(1, "a").unwrap();
286 /// assert_eq!(map.remove(&1), Some("a"));
287 /// assert_eq!(map.remove(&1), None);
288 /// ```
289 pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
290 where
291 K: Borrow<Q>,
292 Q: Eq + ?Sized,
293 {
294 let idx = self
295 .keys()
296 .enumerate()
297 .find(|&(_, k)| k.borrow() == key)
298 .map(|(idx, _)| idx);
299
300 idx.map(|idx| self.buffer.swap_remove(idx).1)
301 }
302
303 /// An iterator visiting all values in arbitrary order
304 ///
305 /// # Examples
306 ///
307 /// ```
308 /// use heapless::LinearMap;
309 ///
310 /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
311 /// map.insert("a", 1).unwrap();
312 /// map.insert("b", 2).unwrap();
313 /// map.insert("c", 3).unwrap();
314 ///
315 /// for val in map.values() {
316 /// println!("{}", val);
317 /// }
318 /// ```
319 pub fn values(&self) -> impl Iterator<Item = &V> {
320 self.iter().map(|(_, v)| v)
321 }
322
323 /// An iterator visiting all values mutably in arbitrary order
324 ///
325 /// # Examples
326 ///
327 /// ```
328 /// use heapless::LinearMap;
329 ///
330 /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
331 /// map.insert("a", 1).unwrap();
332 /// map.insert("b", 2).unwrap();
333 /// map.insert("c", 3).unwrap();
334 ///
335 /// for val in map.values_mut() {
336 /// *val += 10;
337 /// }
338 ///
339 /// for val in map.values() {
340 /// println!("{}", val);
341 /// }
342 /// ```
343 pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
344 self.iter_mut().map(|(_, v)| v)
345 }
346}
347
348impl<'a, K, V, Q, const N: usize> ops::Index<&'a Q> for LinearMap<K, V, N>
349where
350 K: Borrow<Q> + Eq,
351 Q: Eq + ?Sized,
352{
353 type Output = V;
354
355 fn index(&self, key: &Q) -> &V {
356 self.get(key).expect(msg:"no entry found for key")
357 }
358}
359
360impl<'a, K, V, Q, const N: usize> ops::IndexMut<&'a Q> for LinearMap<K, V, N>
361where
362 K: Borrow<Q> + Eq,
363 Q: Eq + ?Sized,
364{
365 fn index_mut(&mut self, key: &Q) -> &mut V {
366 self.get_mut(key).expect(msg:"no entry found for key")
367 }
368}
369
370impl<K, V, const N: usize> Default for LinearMap<K, V, N>
371where
372 K: Eq,
373{
374 fn default() -> Self {
375 Self::new()
376 }
377}
378
379impl<K, V, const N: usize> Clone for LinearMap<K, V, N>
380where
381 K: Eq + Clone,
382 V: Clone,
383{
384 fn clone(&self) -> Self {
385 Self {
386 buffer: self.buffer.clone(),
387 }
388 }
389}
390
391impl<K, V, const N: usize> fmt::Debug for LinearMap<K, V, N>
392where
393 K: Eq + fmt::Debug,
394 V: fmt::Debug,
395{
396 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
397 f.debug_map().entries(self.iter()).finish()
398 }
399}
400
401impl<K, V, const N: usize> FromIterator<(K, V)> for LinearMap<K, V, N>
402where
403 K: Eq,
404{
405 fn from_iter<I>(iter: I) -> Self
406 where
407 I: IntoIterator<Item = (K, V)>,
408 {
409 let mut out: LinearMap = Self::new();
410 out.buffer.extend(iter);
411 out
412 }
413}
414
415pub struct IntoIter<K, V, const N: usize>
416where
417 K: Eq,
418{
419 inner: <Vec<(K, V), N> as IntoIterator>::IntoIter,
420}
421
422impl<K, V, const N: usize> Iterator for IntoIter<K, V, N>
423where
424 K: Eq,
425{
426 type Item = (K, V);
427 fn next(&mut self) -> Option<Self::Item> {
428 self.inner.next()
429 }
430}
431
432impl<'a, K, V, const N: usize> IntoIterator for &'a LinearMap<K, V, N>
433where
434 K: Eq,
435{
436 type Item = (&'a K, &'a V);
437 type IntoIter = Iter<'a, K, V>;
438
439 fn into_iter(self) -> Self::IntoIter {
440 self.iter()
441 }
442}
443
444pub struct Iter<'a, K, V> {
445 iter: slice::Iter<'a, (K, V)>,
446}
447
448impl<'a, K, V> Iterator for Iter<'a, K, V> {
449 type Item = (&'a K, &'a V);
450
451 fn next(&mut self) -> Option<Self::Item> {
452 self.iter.next().map(|&(ref k: &K, ref v: &V)| (k, v))
453 }
454}
455
456impl<'a, K, V> Clone for Iter<'a, K, V> {
457 fn clone(&self) -> Self {
458 Self {
459 iter: self.iter.clone(),
460 }
461 }
462}
463
464pub struct IterMut<'a, K, V> {
465 iter: slice::IterMut<'a, (K, V)>,
466}
467
468impl<'a, K, V> Iterator for IterMut<'a, K, V> {
469 type Item = (&'a K, &'a mut V);
470
471 fn next(&mut self) -> Option<Self::Item> {
472 self.iter.next().map(|&mut (ref k: &K, ref mut v: &mut V)| (k, v))
473 }
474}
475
476impl<K, V, const N: usize, const N2: usize> PartialEq<LinearMap<K, V, N2>> for LinearMap<K, V, N>
477where
478 K: Eq,
479 V: PartialEq,
480{
481 fn eq(&self, other: &LinearMap<K, V, N2>) -> bool {
482 self.len() == other.len()
483 && self
484 .iter()
485 .all(|(key: &K, value: &V)| other.get(key).map_or(default:false, |v: &V| *value == *v))
486 }
487}
488
489impl<K, V, const N: usize> Eq for LinearMap<K, V, N>
490where
491 K: Eq,
492 V: PartialEq,
493{
494}
495
496#[cfg(test)]
497mod test {
498 use crate::LinearMap;
499
500 #[test]
501 fn static_new() {
502 static mut _L: LinearMap<i32, i32, 8> = LinearMap::new();
503 }
504
505 #[test]
506 fn partial_eq() {
507 {
508 let mut a = LinearMap::<_, _, 1>::new();
509 a.insert("k1", "v1").unwrap();
510
511 let mut b = LinearMap::<_, _, 2>::new();
512 b.insert("k1", "v1").unwrap();
513
514 assert!(a == b);
515
516 b.insert("k2", "v2").unwrap();
517
518 assert!(a != b);
519 }
520
521 {
522 let mut a = LinearMap::<_, _, 2>::new();
523 a.insert("k1", "v1").unwrap();
524 a.insert("k2", "v2").unwrap();
525
526 let mut b = LinearMap::<_, _, 2>::new();
527 b.insert("k2", "v2").unwrap();
528 b.insert("k1", "v1").unwrap();
529
530 assert!(a == b);
531 }
532 }
533
534 #[test]
535 fn drop() {
536 droppable!();
537
538 {
539 let mut v: LinearMap<i32, Droppable, 2> = LinearMap::new();
540 v.insert(0, Droppable::new()).ok().unwrap();
541 v.insert(1, Droppable::new()).ok().unwrap();
542 v.remove(&1).unwrap();
543 }
544
545 assert_eq!(Droppable::count(), 0);
546
547 {
548 let mut v: LinearMap<i32, Droppable, 2> = LinearMap::new();
549 v.insert(0, Droppable::new()).ok().unwrap();
550 v.insert(1, Droppable::new()).ok().unwrap();
551 }
552
553 assert_eq!(Droppable::count(), 0);
554 }
555}
556