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}