linear_map/lib.rs
1//! A map implemented by searching linearly in a vector.
2//!
3//! See the [`LinearMap`](struct.LinearMap.html) type for details.
4
5#![deny(missing_docs)]
6
7// Optional Serde support
8#[cfg(feature = "serde_impl")]
9pub mod serde;
10pub mod set;
11
12use std::borrow::Borrow;
13use std::fmt::{self, Debug};
14use std::iter;
15use std::mem;
16use std::ops;
17use std::slice;
18use std::vec;
19
20use self::Entry::{Occupied, Vacant};
21
22/// A map implemented by searching linearly in a vector.
23///
24/// `LinearMap`'s keys are compared using the [`Eq`][eq] trait. All search operations
25/// (`contains_key`, `get`, `get_mut`, `insert`, and `remove`) run in `O(n)` time, making this
26/// implementation suitable only for small numbers of keys. The ordering of the keys in the
27/// underlying vector is arbitrary.
28///
29/// It is a logic error for a key to be modified in such a way that the key's equality, as
30/// determined by the [`Eq`][eq] trait, changes while it is in the map. This is normally only
31/// possible through [`Cell`][cell], [`RefCell`][ref_cell], global state, I/O, or unsafe code.
32///
33/// [cell]: https://doc.rust-lang.org/nightly/std/cell/struct.Cell.html
34/// [eq]: https://doc.rust-lang.org/nightly/std/cmp/trait.Eq.html
35/// [ref_cell]: https://doc.rust-lang.org/nightly/std/cell/struct.RefCell.html
36///
37/// # Example
38///
39/// ```
40/// use linear_map::LinearMap;
41///
42/// // type inference lets us omit an explicit type signature (which
43/// // would be `LinearMap<&str, &str>` in this example).
44/// let mut book_reviews = LinearMap::new();
45///
46/// // review some books.
47/// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");
48/// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");
49/// book_reviews.insert("Pride and Prejudice", "Very enjoyable.");
50/// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");
51///
52/// // check for a specific one.
53/// if !book_reviews.contains_key("Les Misérables") {
54/// println!("We've got {} reviews, but Les Misérables ain't one.",
55/// book_reviews.len());
56/// }
57///
58/// // oops, this review has a lot of spelling mistakes. let's delete it.
59/// book_reviews.remove("The Adventures of Sherlock Holmes");
60///
61/// // look up the values associated with some keys.
62/// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
63/// for book in &to_find {
64/// match book_reviews.get(book) {
65/// Some(review) => println!("{}: {}", book, review),
66/// None => println!("{} is unreviewed.", book)
67/// }
68/// }
69///
70/// // iterate over everything.
71/// for (book, review) in &book_reviews {
72/// println!("{}: \"{}\"", book, review);
73/// }
74/// ```
75pub struct LinearMap<K, V> {
76 storage: Vec<(K, V)>,
77}
78
79impl<K: Eq, V> LinearMap<K, V> {
80 /// Creates an empty map. This method does not allocate.
81 pub fn new() -> Self {
82 LinearMap { storage: vec![] }
83 }
84
85 /// Creates an empty map with the given initial capacity.
86 pub fn with_capacity(capacity: usize) -> Self {
87 LinearMap { storage: Vec::with_capacity(capacity) }
88 }
89
90 /// Returns the number of elements the map can hold without reallocating.
91 pub fn capacity(&self) -> usize {
92 self.storage.capacity()
93 }
94
95 /// Reserves capacity for at least `additional` more to be inserted in the
96 /// map. The collection may reserve more space to avoid frequent
97 /// reallocations.
98 ///
99 /// # Panics
100 ///
101 /// Panics if the new allocation size overflows `usize`.
102 pub fn reserve(&mut self, additional: usize) {
103 self.storage.reserve(additional);
104 }
105
106 /// Reserves the minimum capacity for exactly `additional` more elemnnts to
107 /// be inserted in the map.
108 ///
109 /// Note that the allocator may give the collection more space than it
110 /// requests. Therefore capacity cannot be relied upon to be precisely
111 /// minimal. Prefer `reserve` if future insertions are expected.
112 ///
113 /// # Panics
114 ///
115 /// Panics if the new capacity overflows `usize`.
116 pub fn reserve_exact(&mut self, additional: usize) {
117 self.storage.reserve_exact(additional);
118 }
119
120 /// Shrinks the capacity of the map as much as possible.
121 ///
122 /// It will drop down as close as possible to the current length but the
123 /// allocator may still inform the map that there is more space than
124 /// necessary. Therefore capacity cannot be relid upon to be minimal.
125 pub fn shrink_to_fit(&mut self) {
126 self.storage.shrink_to_fit();
127 }
128
129 /// Returns the number of elements in the map.
130 pub fn len(&self) -> usize {
131 self.storage.len()
132 }
133
134 /// Returns true if the map contains no elements.
135 pub fn is_empty(&self) -> bool {
136 self.storage.is_empty()
137 }
138
139 /// Clears the map, removing all elements. Keeps the allocated memory for
140 /// reuse.
141 pub fn clear(&mut self) {
142 self.storage.clear();
143 }
144
145 /// Scan through the map and keep those key-value pairs where the
146 /// closure returns `true`.
147 ///
148 /// The order the elements are visited is not specified.
149 pub fn retain<F>(&mut self, mut keep_fn: F)
150 where F: FnMut(&K, &mut V) -> bool {
151 let mut del = 0;
152 {
153 let v = &mut *self.storage;
154 for i in 0..v.len() {
155 if !keep_fn(&v[i].0, &mut v[i].1) {
156 del += 1;
157 } else if del > 0 {
158 v.swap(i - del, i);
159 }
160 }
161 }
162 if del > 0 {
163 let len = self.storage.len();
164 self.storage.truncate(len - del);
165 }
166 }
167
168 /// Removes all key-value pairs from the map and returns an iterator that yields them in
169 /// arbitrary order.
170 ///
171 /// All key-value pairs are removed even if the iterator is not exhausted. However, the
172 /// behavior of this method is unspecified if the iterator is leaked.
173 ///
174 /// The iterator's item type is `(K, V)`.
175 pub fn drain(&mut self) -> Drain<K, V> {
176 Drain { iter: self.storage.drain(..) }
177 }
178
179 /// Returns an iterator yielding references to the map's keys and their corresponding values in
180 /// arbitrary order.
181 ///
182 /// The iterator's item type is `(&K, &V)`.
183 pub fn iter(&self) -> Iter<K, V> {
184 Iter { iter: self.storage.iter() }
185 }
186
187 /// Returns an iterator yielding references to the map's keys and mutable references to their
188 /// corresponding values in arbitrary order.
189 ///
190 /// The iterator's item type is `(&K, &mut V)`.
191 pub fn iter_mut(&mut self) -> IterMut<K, V> {
192 IterMut { iter: self.storage.iter_mut() }
193 }
194
195 /// Returns an iterator yielding references to the map's keys in arbitrary order.
196 ///
197 /// The iterator's item type is `&K`.
198 pub fn keys(&self) -> Keys<K, V> {
199 Keys { iter: self.iter() }
200 }
201
202 /// Returns an iterator yielding references to the map's values in arbitrary order.
203 ///
204 /// The iterator's item type is `&V`.
205 pub fn values(&self) -> Values<K, V> {
206 Values { iter: self.iter() }
207 }
208
209 /// Returns a reference to the value in the map whose key is equal to the given key.
210 ///
211 /// Returns `None` if the map contains no such key.
212 ///
213 /// The given key may be any borrowed form of the map's key type, but `Eq` on the borrowed form
214 /// *must* match that of the key type.
215 pub fn get<Q: ?Sized + Eq>(&self, key: &Q) -> Option<&V> where K: Borrow<Q> {
216 for (k, v) in self {
217 if key == k.borrow() {
218 return Some(v);
219 }
220 }
221 None
222 }
223
224 /// Returns a mutable reference to the value in the map whose key is equal to the given key.
225 ///
226 /// Returns `None` if the map contains no such key.
227 ///
228 /// The given key may be any borrowed form of the map's key type, but `Eq` on the borrowed form
229 /// *must* match that of the key type.
230 pub fn get_mut<Q: ?Sized + Eq>(&mut self, key: &Q) -> Option<&mut V> where K: Borrow<Q> {
231 for (k, v) in self {
232 if key == k.borrow() {
233 return Some(v);
234 }
235 }
236 None
237 }
238
239 /// Checks if the map contains a key that is equal to the given key.
240 ///
241 /// The given key may be any borrowed form of the map's key type, but `Eq` on the borrowed form
242 /// *must* match that of the key type.
243 pub fn contains_key<Q: ?Sized + Eq>(&self, key: &Q) -> bool where K: Borrow<Q> {
244 self.get(key).is_some()
245 }
246
247 /// Inserts a key-value pair into the map.
248 ///
249 /// Returns `None` if the map did not contain a key that is equal to the given key.
250 ///
251 /// If the map did contain such a key, its corresponding value is replaced with the given
252 /// value, and the old value is returned. The key is not updated, though. This matters for
253 /// values that can be `==` without being identical. See the [standard library's documentation]
254 /// [std] for more details.
255 ///
256 /// [std]: https://doc.rust-lang.org/nightly/std/collections/index.html#insert-and-complex-keys
257 pub fn insert(&mut self, key: K, value: V) -> Option<V> {
258 match self.entry(key) {
259 Occupied(mut e) => Some(e.insert(value)),
260 Vacant(e) => { e.insert(value); None }
261 }
262 }
263
264 /// Removes the key in the map that is equal to the given key and returns its corresponding
265 /// value.
266 ///
267 /// Returns `None` if the map contained no such key.
268 ///
269 /// The given key may be any borrowed form of the map's key type, but `Eq` on the borrowed form
270 /// *must* match that of the key type.
271 pub fn remove<Q: ?Sized + Eq>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q> {
272 for i in 0..self.storage.len() {
273 if self.storage[i].0.borrow() == key {
274 return Some(self.storage.swap_remove(i).1);
275 }
276 }
277 None
278 }
279
280 /// Returns the given key's corresponding entry in the map for in-place manipulation.
281 pub fn entry(&mut self, key: K) -> Entry<K, V> {
282 match self.storage.iter().position(|&(ref k, _)| key == *k) {
283 None => Vacant(VacantEntry {
284 map: self,
285 key: key
286 }),
287 Some(index) => Occupied(OccupiedEntry {
288 map: self,
289 index: index
290 })
291 }
292 }
293}
294
295impl<K: Clone, V: Clone> Clone for LinearMap<K, V> {
296 fn clone(&self) -> Self {
297 LinearMap { storage: self.storage.clone() }
298 }
299
300 fn clone_from(&mut self, other: &Self) {
301 self.storage.clone_from(&other.storage);
302 }
303}
304
305impl<K: Eq + Debug, V: Debug> Debug for LinearMap<K, V> {
306 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
307 f.debug_map().entries(self).finish()
308 }
309}
310
311impl<K: Eq, V> Default for LinearMap<K, V> {
312 fn default() -> Self {
313 Self::new()
314 }
315}
316
317impl<K: Eq, V> Extend<(K, V)> for LinearMap<K, V> {
318 fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, key_values: I) {
319 for (key, value) in key_values { self.insert(key, value); }
320 }
321}
322
323impl<K: Eq, V> iter::FromIterator<(K, V)> for LinearMap<K, V> {
324 fn from_iter<I: IntoIterator<Item = (K, V)>>(key_values: I) -> Self {
325 let mut map = Self::new();
326 map.extend(key_values);
327 map
328 }
329}
330
331impl<'a, K: Eq + Borrow<Q>, V, Q: ?Sized + Eq> ops::Index<&'a Q> for LinearMap<K, V> {
332 type Output = V;
333
334 fn index(&self, key: &'a Q) -> &V {
335 self.get(key).expect("key not found")
336 }
337}
338
339impl<K: Eq, V: PartialEq> PartialEq for LinearMap<K, V> {
340 fn eq(&self, other: &Self) -> bool {
341 if self.len() != other.len() {
342 return false;
343 }
344
345 for (key, value) in self {
346 if other.get(key) != Some(value) {
347 return false;
348 }
349 }
350
351 true
352 }
353}
354
355impl<K: Eq, V: Eq> Eq for LinearMap<K, V> {}
356
357impl<K: Eq, V> Into<Vec<(K, V)>> for LinearMap<K, V> {
358 fn into(self) -> Vec<(K, V)> {
359 self.storage
360 }
361}
362
363/// Creates a `LinearMap` from a list of key-value pairs.
364///
365/// The created `LinearMap` has a capacity set to the number of entries provided.
366///
367/// # Example
368///
369/// ```
370/// #[macro_use] extern crate linear_map;
371/// # fn main() {
372///
373/// let map = linear_map!{
374/// "a" => 1,
375/// "b" => 2,
376/// };
377/// assert_eq!(map["a"], 1);
378/// assert_eq!(map["b"], 2);
379/// assert_eq!(map.get("c"), None);
380/// # }
381/// ```
382#[macro_export]
383macro_rules! linear_map {
384 ($($key:expr => $value:expr,)+) => { linear_map!($($key => $value),+) };
385 ($($key:expr => $value:expr),*) => {
386 {
387 let _cap = <[&str]>::len(&[$(stringify!($key)),*]);
388 let mut _map = $crate::LinearMap::with_capacity(_cap);
389 $(
390 _map.insert($key, $value);
391 )*
392 _map
393 }
394 };
395}
396
397/// A view into a single occupied location in a `LinearMap`.
398///
399/// See [`LinearMap::entry`](struct.LinearMap.html#method.entry) for details.
400pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
401 map: &'a mut LinearMap<K, V>,
402 index: usize,
403}
404
405/// A view into a single vacant location in a `LinearMap`.
406///
407/// See [`LinearMap::entry`](struct.LinearMap.html#method.entry) for details.
408pub struct VacantEntry<'a, K: 'a, V: 'a> {
409 map: &'a mut LinearMap<K, V>,
410 key: K,
411}
412
413/// A view into a single entry in a `LinearMap`.
414///
415/// See [`LinearMap::entry`](struct.LinearMap.html#method.entry) for details.
416pub enum Entry<'a, K: 'a, V: 'a> {
417 /// An occupied entry.
418 Occupied(OccupiedEntry<'a, K, V>),
419
420 /// A vacant entry.
421 Vacant(VacantEntry<'a, K, V>)
422}
423
424impl<'a, K, V> Entry<'a, K, V> {
425 /// Ensures that the entry is occupied by inserting the given value if it is vacant.
426 ///
427 /// Returns a mutable reference to the entry's value.
428 pub fn or_insert(self, default: V) -> &'a mut V {
429 match self {
430 Occupied(entry) => entry.into_mut(),
431 Vacant(entry) => entry.insert(default)
432 }
433 }
434
435 /// Ensures that the entry is occupied by inserting the the result of the given function if it
436 /// is vacant.
437 ///
438 /// Returns a mutable reference to the entry's value.
439 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
440 match self {
441 Occupied(entry) => entry.into_mut(),
442 Vacant(entry) => entry.insert(default())
443 }
444 }
445}
446
447impl<'a, K, V> OccupiedEntry<'a, K, V> {
448 /// Returns a reference to the entry's value.
449 pub fn get(&self) -> &V {
450 &self.map.storage[self.index].1
451 }
452
453 /// Returns a mutable reference to the entry's value.
454 pub fn get_mut(&mut self) -> &mut V {
455 &mut self.map.storage[self.index].1
456 }
457
458 /// Returns a mutable reference to the entry's value with the same lifetime as the map.
459 pub fn into_mut(self) -> &'a mut V {
460 &mut self.map.storage[self.index].1
461 }
462
463 /// Replaces the entry's value with the given one and returns the previous value.
464 pub fn insert(&mut self, value: V) -> V {
465 mem::replace(self.get_mut(), value)
466 }
467
468 /// Removes the entry from the map and returns its value.
469 pub fn remove(self) -> V {
470 self.map.storage.swap_remove(self.index).1
471 }
472}
473
474impl<'a, K, V> VacantEntry<'a, K, V> {
475 /// Inserts the entry into the map with the given value.
476 ///
477 /// Returns a mutable reference to the entry's value with the same lifetime as the map.
478 pub fn insert(self, value: V) -> &'a mut V {
479 self.map.storage.push((self.key, value));
480 &mut self.map.storage.last_mut().unwrap().1
481 }
482}
483
484/// A consuming iterator over a `LinearMap`.
485///
486/// The iterator's order is arbitrary.
487///
488/// Acquire through [`IntoIterator`](struct.LinearMap.html#method.into_iter).
489pub struct IntoIter<K, V> {
490 iter: vec::IntoIter<(K, V)>,
491}
492
493impl<K, V> Iterator for IntoIter<K, V> {
494 type Item = (K, V);
495
496 fn next(&mut self) -> Option<(K, V)> {
497 self.iter.next()
498 }
499
500 fn size_hint(&self) -> (usize, Option<usize>) {
501 self.iter.size_hint()
502 }
503}
504
505impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
506 fn next_back(&mut self) -> Option<(K, V)> {
507 self.iter.next_back()
508 }
509}
510
511impl<K, V> ExactSizeIterator for IntoIter<K, V> {
512 fn len(&self) -> usize {
513 self.iter.len()
514 }
515}
516
517/// A draining iterator over a `LinearMap`.
518///
519/// See [`LinearMap::drain`](struct.LinearMap.html#method.drain) for details.
520pub struct Drain<'a, K: 'a, V: 'a> {
521 iter: vec::Drain<'a, (K, V)>,
522}
523
524/// An iterator yielding references to a `LinearMap`'s keys and their corresponding values.
525///
526/// See [`LinearMap::iter`](struct.LinearMap.html#method.iter) for details.
527pub struct Iter<'a, K: 'a, V: 'a> {
528 iter: slice::Iter<'a, (K, V)>,
529}
530
531/// An iterator yielding references to a `LinearMap`'s keys and mutable references to their
532/// corresponding values.
533///
534/// See [`LinearMap::iter_mut`](struct.LinearMap.html#method.iter_mut) for details.
535pub struct IterMut<'a, K: 'a, V: 'a> {
536 iter: slice::IterMut<'a, (K, V)>,
537}
538
539/// An iterator yielding references to a `LinearMap`'s keys in arbitrary order.
540///
541/// See [`LinearMap::keys`](struct.LinearMap.html#method.keys) for details.
542pub struct Keys<'a, K: 'a, V: 'a> {
543 iter: Iter<'a, K, V>,
544}
545
546/// An iterator yielding references to a `LinearMap`'s values in arbitrary order.
547///
548/// See [`LinearMap::values`](struct.LinearMap.html#method.values) for details.
549pub struct Values<'a, K: 'a, V: 'a> {
550 iter: Iter<'a, K, V>,
551}
552
553macro_rules! impl_iter {($typ:ty, $item:ty, $map:expr) => {
554 impl<'a, K, V> Iterator for $typ {
555 type Item = $item;
556
557 fn next(&mut self) -> Option<Self::Item> {
558 self.iter.next().map($map)
559 }
560
561 fn size_hint(&self) -> (usize, Option<usize>) {
562 self.iter.size_hint()
563 }
564 }
565
566 impl<'a, K, V> DoubleEndedIterator for $typ {
567 fn next_back(&mut self) -> Option<Self::Item> {
568 self.iter.next_back().map($map)
569 }
570 }
571
572 impl<'a, K, V> ExactSizeIterator for $typ {
573 fn len(&self) -> usize {
574 self.iter.len()
575 }
576 }
577}}
578impl_iter!{Drain<'a,K,V>, (K,V), |e| e }
579impl_iter!{Iter<'a,K,V>, (&'a K, &'a V), |e| (&e.0, &e.1) }
580impl_iter!{IterMut<'a,K,V>, (&'a K, &'a mut V), |e| (&e.0, &mut e.1) }
581impl_iter!{Keys<'a,K,V>, &'a K, |e| e.0 }
582impl_iter!{Values<'a,K,V>, &'a V, |e| e.1 }
583
584impl<'a, K, V> Clone for Iter<'a, K, V> {
585 fn clone(&self) -> Self {
586 Iter { iter: self.iter.clone() }
587 }
588}
589
590impl<'a, K, V> Clone for Keys<'a, K, V> {
591 fn clone(&self) -> Self {
592 Keys { iter: self.iter.clone() }
593 }
594}
595
596impl<'a, K, V> Clone for Values<'a, K, V> {
597 fn clone(&self) -> Self {
598 Values { iter: self.iter.clone() }
599 }
600}
601
602impl<K: Eq, V> IntoIterator for LinearMap<K, V> {
603 type Item = (K, V);
604 type IntoIter = IntoIter<K, V>;
605
606 fn into_iter(self) -> IntoIter<K, V> {
607 IntoIter { iter: self.storage.into_iter() }
608 }
609}
610
611impl<'a, K: Eq, V> IntoIterator for &'a LinearMap<K, V> {
612 type Item = (&'a K, &'a V);
613 type IntoIter = Iter<'a, K, V>;
614
615 fn into_iter(self) -> Iter<'a, K, V> {
616 self.iter()
617 }
618}
619
620impl<'a, K: Eq, V> IntoIterator for &'a mut LinearMap<K, V> {
621 type Item = (&'a K, &'a mut V);
622 type IntoIter = IterMut<'a, K, V>;
623
624 fn into_iter(self) -> IterMut<'a, K, V> {
625 self.iter_mut()
626 }
627}
628
629#[allow(dead_code)]
630fn assert_covariance() {
631 fn a<'a, K, V>(x: LinearMap<&'static K, &'static V>) -> LinearMap<&'a K, &'a V> { x }
632
633 fn b<'a, K, V>(x: IntoIter<&'static K, &'static V>) -> IntoIter<&'a K, &'a V> { x }
634
635 fn c<'i, 'a, K, V>(x: Iter<'i, &'static K, &'static V>) -> Iter<'i, &'a K, &'a V> { x }
636
637 fn d<'i, 'a, K, V>(x: Keys<'i, &'static K, &'static V>) -> Keys<'i, &'a K, &'a V> { x }
638
639 fn e<'i, 'a, K, V>(x: Values<'i, &'static K, &'static V>) -> Values<'i, &'a K, &'a V> { x }
640}