seq_map/
lib.rs

1/*
2 * Copyright (c) Peter Bjorklund. All rights reserved. https://github.com/piot/seq-map
3 * Licensed under the MIT License. See LICENSE in the project root for license information.
4 */
5
6use std::{
7    borrow::Borrow,
8    collections::HashMap,
9    error::Error,
10    fmt::{self, Debug, Display, Formatter},
11    hash::{Hash, Hasher},
12    ops::Index,
13};
14
15/// A deterministic map that preserves insertion order.
16///
17/// Internally, it uses a [`HashMap`] for quick key lookups and a [`Vec`] to maintain the order
18/// of inserted key-value pairs.
19#[derive(Clone)]
20pub struct SeqMap<K, V> {
21    key_to_index: HashMap<K, usize>, // Maps keys to their index in `entries`
22    entries: Vec<(K, V)>,            // Stores key-value pairs in insertion order
23}
24
25impl<K, V> Hash for SeqMap<K, V>
26where
27    K: Hash,
28    V: Hash,
29{
30    fn hash<H: Hasher>(&self, state: &mut H) {
31        for (key, value) in &self.entries {
32            key.hash(state);
33            value.hash(state);
34        }
35    }
36}
37
38impl<K, V> PartialEq for SeqMap<K, V>
39where
40    K: Eq,
41    V: Eq,
42{
43    fn eq(&self, other: &Self) -> bool {
44        if self.entries.len() != other.entries.len() {
45            return false;
46        }
47        self.entries
48            .iter()
49            .zip(other.entries.iter())
50            .all(|(a, b)| a == b)
51    }
52}
53
54impl<K, V> Eq for SeqMap<K, V>
55where
56    K: Eq,
57    V: Eq,
58{
59}
60
61impl<K, V> Display for SeqMap<K, V>
62where
63    K: Eq + Hash + Display,
64    V: Display,
65{
66    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
67        write!(f, "SeqMap({})", self.entries.len())?;
68        for (key, value) in &self.entries {
69            write!(f, "\n{key}: {value}")?;
70        }
71        Ok(())
72    }
73}
74
75impl<K, V> Debug for SeqMap<K, V>
76where
77    K: Eq + Hash + Debug,
78    V: Debug,
79{
80    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
81        write!(f, "SeqMap(")?;
82        let mut first = true;
83        for (key, value) in &self.entries {
84            if !first {
85                write!(f, ", ")?;
86            }
87            first = false;
88            write!(f, "{key:?}: {value:?}")?;
89        }
90        write!(f, ")")
91    }
92}
93
94/// Errors that can occur when manipulating a `SeqMap`.
95#[derive(Debug)]
96pub enum SeqMapError {
97    /// Occurs when attempting to insert a key that already exists in the map.
98    KeyAlreadyExists,
99}
100
101impl Display for SeqMapError {
102    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
103        match self {
104            SeqMapError::KeyAlreadyExists => write!(f, "The key already exists in the SeqMap."),
105        }
106    }
107}
108
109impl Error for SeqMapError {}
110
111impl<K, V> SeqMap<K, V>
112where
113    K: Eq + Hash + Clone, // Clone is because we add it to two containers
114{
115    /// Creates a new, empty `SeqMap`.
116    ///
117    /// # Examples
118    ///
119    /// ```
120    /// use seq_map::SeqMap;
121    /// let map: SeqMap<String, i32> = SeqMap::new();
122    /// ```
123    #[must_use]
124    pub fn new() -> Self {
125        Self {
126            key_to_index: HashMap::new(),
127            entries: Vec::new(),
128        }
129    }
130
131    /// Inserts a key-value pair into the map.
132    ///
133    /// Returns an error if the key already exists.
134    ///
135    /// # Errors
136    ///
137    /// Returns `SeqMapError::KeyAlreadyExists` if the key is already present.
138    ///
139    /// # Examples
140    ///
141    /// ```
142    /// use seq_map::SeqMap;
143    /// let mut map = SeqMap::new();
144    /// map.insert("key".to_string(), 42).unwrap();
145    /// assert!(map.insert("key".to_string(), 43).is_err());
146    /// ```
147    pub fn insert(&mut self, key: K, value: V) -> Result<(), SeqMapError> {
148        #[allow(clippy::map_entry)]
149        if self.key_to_index.contains_key(&key) {
150            Err(SeqMapError::KeyAlreadyExists)
151        } else {
152            self.entries.push((key.clone(), value));
153            self.key_to_index.insert(key, self.entries.len() - 1);
154            Ok(())
155        }
156    }
157
158    /// Checks if the map contains a key.
159    pub fn contains_key<Q>(&self, key: &Q) -> bool
160    where
161        K: Borrow<Q>,
162        Q: Hash + Eq + ?Sized,
163    {
164        self.key_to_index.contains_key(key)
165    }
166
167    /// Returns a mutable reference to the value corresponding to the key.
168    ///
169    /// Returns `None` if the key does not exist.
170    ///
171    /// # Examples
172    ///
173    /// ```
174    /// use seq_map::SeqMap;
175    /// let mut map = SeqMap::new();
176    /// map.insert("key".to_string(), 42).unwrap();
177    /// if let Some(value) = map.get_mut(&"key".to_string()) {
178    ///     *value = 100;
179    /// }
180    /// assert_eq!(map[&"key".to_string()], 100);
181    /// ```
182    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
183        self.key_to_index
184            .get(key)
185            .map(|&index| &mut self.entries[index].1)
186    }
187
188    /// Returns the number of key-value pairs in the map.
189    ///
190    /// # Examples
191    ///
192    /// ```
193    /// use seq_map::SeqMap;
194    /// let mut map = SeqMap::new();
195    /// assert_eq!(map.len(), 0);
196    /// map.insert("key", 42).unwrap();
197    /// assert_eq!(map.len(), 1);
198    /// ```
199    #[must_use]
200    pub fn len(&self) -> usize {
201        self.entries.len()
202    }
203
204    /// Returns `true` if the map contains no elements.
205    ///
206    /// # Examples
207    ///
208    /// ```
209    /// use seq_map::SeqMap;
210    /// let map: SeqMap<String, i32> = SeqMap::new();
211    /// assert!(map.is_empty());
212    /// ```
213    #[must_use]
214    pub fn is_empty(&self) -> bool {
215        self.entries.is_empty()
216    }
217
218    /// Returns an iterator over the keys of the map in insertion order.
219    ///
220    /// # Examples
221    ///
222    /// ```
223    /// use seq_map::SeqMap;
224    /// let mut map = SeqMap::new();
225    /// map.insert("a".to_string(), 1).unwrap();
226    /// map.insert("b".to_string(), 2).unwrap();
227    /// let keys: Vec<_> = map.keys().cloned().collect();
228    /// assert_eq!(keys, vec!["a", "b"]);
229    /// ```
230    pub fn keys(&self) -> impl Iterator<Item = &K> {
231        self.entries.iter().map(|(k, _)| k)
232    }
233
234    /// Returns an iterator over the values of the map in insertion order.
235    ///
236    /// # Examples
237    ///
238    /// ```
239    /// use seq_map::SeqMap;
240    /// let mut map = SeqMap::new();
241    /// map.insert("a".to_string(), 1).unwrap();
242    /// map.insert("b".to_string(), 2).unwrap();
243    /// let values: Vec<_> = map.values().cloned().collect();
244    /// assert_eq!(values, vec![1, 2]);
245    /// ```
246    pub fn values(&self) -> impl Iterator<Item = &V> {
247        self.entries.iter().map(|(_, v)| v)
248    }
249
250    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
251        self.entries.iter_mut().map(|(_, v)| v)
252    }
253
254    pub fn get_index<Q>(&self, key: &Q) -> Option<usize>
255    where
256        K: Borrow<Q>,
257        Q: Hash + Eq + ?Sized,
258    {
259        self.key_to_index.get(key).copied()
260    }
261
262    pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
263        self.entries.iter().map(|(k, v)| (k, v))
264    }
265
266    pub fn iter_mut(&mut self) -> impl Iterator<Item = (&K, &mut V)> {
267        self.entries.iter_mut().map(|(k, v)| (&*k, v))
268    }
269
270    /// Retrieves a reference to the value corresponding to the key.
271    ///
272    /// This method performs a faster lookup using the internal `HashMap`.
273    ///
274    /// For a slower but simpler lookup, see [`slow_get`](Self::slow_get).
275    ///
276    /// # Examples
277    ///
278    /// ```
279    /// use seq_map::SeqMap;
280    /// let mut map = SeqMap::new();
281    /// map.insert("key".to_string(), 42).unwrap();
282    /// assert_eq!(map.get(&"key".to_string()), Some(&42));
283    /// ```
284    pub fn get<Q>(&self, key: &Q) -> Option<&V>
285    where
286        K: Borrow<Q>,
287        Q: Hash + Eq + ?Sized,
288    {
289        self.key_to_index
290            .get(key)
291            .map(|&index| &self.entries[index].1)
292    }
293
294    /// Removes all elements from the map
295    pub fn clear(&mut self) {
296        self.key_to_index.clear();
297        self.entries.clear();
298    }
299
300    /// Removes a key from the map, returning the value if it existed
301    pub fn remove(&mut self, key: &K) -> Option<V> {
302        if let Some(&index) = self.key_to_index.get(key) {
303            self.key_to_index.remove(key);
304            // Update indices for all elements after the removed one
305            for k in self.entries[index + 1..].iter().map(|(k, _)| k) {
306                if let Some(idx) = self.key_to_index.get_mut(k) {
307                    *idx -= 1;
308                }
309            }
310            Some(self.entries.remove(index).1)
311        } else {
312            None
313        }
314    }
315
316    /// Removes all elements from the map and returns them as an iterator
317    pub fn drain(&mut self) -> impl Iterator<Item = (K, V)> + '_ {
318        self.key_to_index.clear();
319        self.entries.drain(..)
320    }
321}
322
323/// An entry into a `SeqMap` which may be either vacant or occupied.
324pub enum Entry<'a, K, V>
325where
326    K: Eq + Hash + Clone,
327{
328    Occupied(OccupiedEntry<'a, K, V>),
329    Vacant(VacantEntry<'a, K, V>),
330}
331
332/// A view into an occupied entry in a `SeqMap`.
333pub struct OccupiedEntry<'a, K, V>
334where
335    K: Eq + Hash + Clone,
336{
337    map: &'a mut SeqMap<K, V>,
338    index: usize,
339}
340
341/// A view into a vacant entry in a `SeqMap`.
342pub struct VacantEntry<'a, K, V>
343where
344    K: Eq + Hash + Clone,
345{
346    map: &'a mut SeqMap<K, V>,
347    key: Option<K>,
348}
349
350impl<'a, K, V> Entry<'a, K, V>
351where
352    K: Eq + Hash + Clone,
353{
354    /// Inserts the value if the entry is vacant, and returns a mutable reference to the value.
355    pub fn or_insert(&mut self, default: V) -> &mut V {
356        match self {
357            Entry::Occupied(o) => o.get_mut(),
358            Entry::Vacant(v) => v.insert(default),
359        }
360    }
361
362    /// Inserts the value computed by `f` if vacant, and returns a mutable reference.
363    pub fn or_insert_with<F: FnOnce() -> V>(&mut self, f: F) -> &mut V {
364        match self {
365            Entry::Occupied(o) => o.get_mut(),
366            Entry::Vacant(v) => v.insert(f()),
367        }
368    }
369
370    /// Inserts `Default::default()` if vacant. Requires `V: Default`.
371    pub fn or_default(&mut self) -> &mut V
372    where
373        V: Default,
374    {
375        match self {
376            Entry::Occupied(o) => o.get_mut(),
377            Entry::Vacant(v) => v.insert(V::default()),
378        }
379    }
380
381    /// If the entry is occupied, apply the closure to its value. Returns self for chaining.
382    pub fn and_modify<F: FnOnce(&mut V)>(&mut self, f: F) -> &mut Self {
383        match self {
384            Entry::Occupied(o) => {
385                f(o.get_mut());
386            }
387            Entry::Vacant(_) => {}
388        }
389        self
390    }
391}
392
393impl<'a, K, V> OccupiedEntry<'a, K, V>
394where
395    K: Eq + Hash + Clone,
396{
397    /// Gets a reference to the value in the occupied entry.
398    pub fn get(&self) -> &V {
399        &self.map.entries[self.index].1
400    }
401
402    /// Gets a mutable reference to the value in the occupied entry.
403    pub fn get_mut(&mut self) -> &mut V {
404        &mut self.map.entries[self.index].1
405    }
406
407    /// Replaces the value in the occupied entry and returns the old value.
408    pub fn insert(&mut self, value: V) -> V {
409        std::mem::replace(&mut self.map.entries[self.index].1, value)
410    }
411
412    /// Removes the entry and returns the value.
413    pub fn remove(&mut self) -> V {
414        // Clone the key to remove mapping; K: Clone is required by SeqMap impls
415        let key = self.map.entries[self.index].0.clone();
416        self.map.key_to_index.remove(&key);
417        for k in self.map.entries[self.index + 1..].iter().map(|(k, _)| k) {
418            if let Some(idx) = self.map.key_to_index.get_mut(k) {
419                *idx -= 1;
420            }
421        }
422        self.map.entries.remove(self.index).1
423    }
424}
425
426impl<'a, K, V> VacantEntry<'a, K, V>
427where
428    K: Eq + Hash + Clone,
429{
430    /// Inserts the provided value into the map and returns a mutable reference to it.
431    pub fn insert(&mut self, value: V) -> &mut V {
432        let key = self.key.take().expect("vacant entry key missing");
433        let index = self.map.entries.len();
434        self.map.entries.push((key.clone(), value));
435        self.map.key_to_index.insert(key, index);
436        &mut self.map.entries[index].1
437    }
438
439    /// Returns a reference to the key for this vacant entry.
440    pub fn key(&self) -> &K {
441        self.key.as_ref().expect("vacant entry key missing")
442    }
443}
444
445impl<K, V> Index<&K> for SeqMap<K, V>
446where
447    K: Eq + Hash + Clone,
448    V: Clone,
449{
450    type Output = V;
451
452    /// Allows accessing values using the indexing syntax (`map[&key]`).
453    ///
454    /// # Panics
455    ///
456    /// Panics if the key is not present in the map.
457    ///
458    /// # Examples
459    ///
460    /// ```
461    /// use seq_map::SeqMap;
462    /// let mut map = SeqMap::new();
463    /// map.insert("key".to_string(), 42).unwrap();
464    /// assert_eq!(map[&"key".to_string()], 42);
465    /// ```
466    fn index(&self, key: &K) -> &Self::Output {
467        self.get(key).expect("Key not found in SeqMap")
468    }
469}
470
471impl<K, V> From<&[(K, V)]> for SeqMap<K, V>
472where
473    K: Eq + Hash + Clone,
474    V: Clone,
475{
476    /// Creates a `SeqMap` from a slice of key-value pairs.
477    ///
478    /// If duplicate keys are present in the slice, the first occurrence is kept, and subsequent
479    /// duplicates are ignored.
480    ///
481    /// # Examples
482    ///
483    /// ```
484    /// use seq_map::SeqMap;
485    /// let pairs = vec![
486    ///     ("a".to_string(), 1),
487    ///     ("b".to_string(), 2),
488    /// ];
489    /// let map: SeqMap<_, _> = SeqMap::from(&pairs[..]);
490    /// assert_eq!(map.len(), 2);
491    /// ```
492    fn from(slice: &[(K, V)]) -> Self {
493        let mut map = SeqMap::new();
494        for (key, value) in slice {
495            // Ignore errors to keep the first occurrence
496            let _ = map.insert(key.clone(), value.clone());
497        }
498        map
499    }
500}
501
502/// Creates a `SeqMap` from an iterator of key-value pairs.
503///
504/// If duplicate keys are present in the iterator, the first occurrence is kept,
505/// and subsequent duplicates are silently ignored.
506impl<K: Hash, V> FromIterator<(K, V)> for SeqMap<K, V>
507where
508    K: Eq + Clone,
509    V: Clone,
510{
511    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
512        let mut map = SeqMap::new();
513        for (k, v) in iter {
514            let _ = map.insert(k, v); // Intentionally ignore errors for this trait
515        }
516        map
517    }
518}
519
520impl<'a, K, V> IntoIterator for &'a SeqMap<K, V>
521where
522    K: Eq + Hash + Clone,
523{
524    type Item = (&'a K, &'a V);
525    type IntoIter = std::iter::Map<std::slice::Iter<'a, (K, V)>, fn(&'a (K, V)) -> (&'a K, &'a V)>;
526
527    /// Returns an iterator over references to the key-value pairs in insertion order.
528    ///
529    /// This implementation allows you to iterate over references to the keys and values
530    /// without consuming the `SeqMap`. It's useful for scenarios where you want to inspect
531    /// the contents of the map without modifying it.
532    ///
533    /// # Examples
534    ///
535    /// ## Iterating Over References
536    ///
537    /// ```rust
538    /// use seq_map::SeqMap;
539    ///
540    /// let mut map = SeqMap::new();
541    /// map.insert("a".to_string(), 1).unwrap();
542    /// map.insert("b".to_string(), 2).unwrap();
543    /// map.insert("c".to_string(), 3).unwrap();
544    ///
545    /// for (key, value) in &map {
546    ///     println!("{}: {}", key, value);
547    /// }
548    /// ```
549    ///
550    /// ## Collecting into a Vector of References
551    ///
552    /// ```rust
553    /// use seq_map::SeqMap;
554    ///
555    /// let mut map = SeqMap::new();
556    /// map.insert("x".to_string(), 100).unwrap();
557    /// map.insert("y".to_string(), 200).unwrap();
558    ///
559    /// let entries: Vec<_> = (&map).into_iter().collect();
560    /// assert_eq!(
561    ///     entries,
562    ///     vec![
563    ///         (&"x".to_string(), &100),
564    ///         (&"y".to_string(), &200),
565    ///     ]
566    /// );
567    /// ```
568    fn into_iter(self) -> Self::IntoIter {
569        self.entries.iter().map(|(k, v)| (k, v))
570    }
571}
572
573impl<K, V> Default for SeqMap<K, V> {
574    /// Creates a new, empty `SeqMap`.
575    ///
576    /// # Examples
577    ///
578    /// ```
579    /// use seq_map::SeqMap;
580    /// let map: SeqMap<String, i32> = SeqMap::default();
581    /// ```
582    fn default() -> Self {
583        Self {
584            key_to_index: HashMap::default(),
585            entries: Vec::default(),
586        }
587    }
588}
589
590// Mutable reference iterator
591impl<'a, K, V> IntoIterator for &'a mut SeqMap<K, V>
592where
593    K: Eq + Hash + Clone,
594{
595    type Item = (&'a K, &'a mut V);
596    type IntoIter =
597        std::iter::Map<std::slice::IterMut<'a, (K, V)>, fn(&'a mut (K, V)) -> (&'a K, &'a mut V)>;
598
599    fn into_iter(self) -> Self::IntoIter {
600        self.entries.iter_mut().map(|(k, v)| (&*k, v))
601    }
602}
603
604// Consuming iterator
605impl<K, V> IntoIterator for SeqMap<K, V>
606where
607    K: Eq + Hash + Clone,
608{
609    type Item = (K, V);
610    type IntoIter = std::vec::IntoIter<(K, V)>;
611
612    fn into_iter(self) -> Self::IntoIter {
613        self.entries.into_iter()
614    }
615}
616
617impl<K, V> SeqMap<K, V>
618where
619    K: Eq + Hash + Clone,
620{
621    /// Provides entry API.
622    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
623        if let Some(&index) = self.key_to_index.get(&key) {
624            Entry::Occupied(OccupiedEntry { map: self, index })
625        } else {
626            Entry::Vacant(VacantEntry {
627                map: self,
628                key: Some(key),
629            })
630        }
631    }
632    pub fn into_keys(self) -> impl Iterator<Item = K> {
633        self.entries.into_iter().map(|(k, _)| k)
634    }
635
636    pub fn into_values(self) -> impl Iterator<Item = V> {
637        self.entries.into_iter().map(|(_, v)| v)
638    }
639}
640
641impl<K, V> Extend<(K, V)> for SeqMap<K, V>
642where
643    K: Eq + Hash + Clone,
644{
645    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
646        for (k, v) in iter {
647            let _ = self.insert(k, v);
648        }
649    }
650}
651
652#[cfg(test)]
653mod tests {
654    use crate::SeqMap;
655
656    #[test]
657    fn test_clear_and_drain() {
658        let mut map = SeqMap::new();
659        map.insert("a", 1).unwrap();
660        map.insert("b", 2).unwrap();
661
662        let mut other_map = SeqMap::new();
663        for (k, v) in map.drain() {
664            other_map.insert(k, v).unwrap();
665        }
666        assert!(map.is_empty());
667        assert_eq!(other_map.len(), 2);
668
669        other_map.clear();
670        assert!(other_map.is_empty());
671        assert_eq!(other_map.key_to_index.len(), 0);
672        assert_eq!(other_map.entries.len(), 0);
673    }
674}
seq_map/lib.rs

seq_map/
lib.rs
