id_map/
lib.rs

1//! [`IdMap`] is a container that gives each item a unique id. Adding and removing by index is O(1).
2//!
3//! # Examples
4//!
5//! ```
6//! # use id_map::IdMap;
7//! #
8//! let mut map = IdMap::new();
9//! let blue_id = map.insert("blue");
10//! let red_id = map.insert("red");
11//!
12//! map.retain(|_, &color| color != "red");
13//!
14//! assert!(!map.contains(red_id));
15//! assert_eq!(map[blue_id], "blue");
16//! ```
17//!
18//! [`IdMap`]: struct.IdMap.html
19
20#![deny(missing_docs, missing_debug_implementations, unsafe_code)]
21
22extern crate id_set;
23
24#[cfg(test)]
25mod tests;
26
27pub use id_set::Id;
28
29use std::iter::FromIterator;
30use std::ops::{Index, IndexMut};
31use std::{cmp, fmt, mem};
32use std::{slice, vec};
33
34use id_set::IdSet;
35
36/// A container that gives each item a unique id. Internally all elements are stored contiguously.
37#[derive(Clone)]
38pub struct IdMap<T> {
39    // The set of valid indices for values.
40    ids: IdSet,
41    // The buffer of values. Indices not in ids are invalid.
42    values: Vec<Option<T>>,
43    // The smallest empty space in the vector of values, or values.len() if no space is left.
44    space: Id,
45}
46
47impl<T> IdMap<T> {
48    #[inline]
49    /// Creates an empty `IdMap<T>`.
50    pub fn new() -> Self {
51        IdMap {
52            ids: IdSet::new(),
53            values: Vec::new(),
54            space: 0,
55        }
56    }
57
58    #[inline]
59    /// Creates an `IdMap<T>` with the specified capacity.
60    pub fn with_capacity(cap: usize) -> Self {
61        IdMap {
62            ids: IdSet::with_capacity(cap),
63            values: Vec::with_capacity(cap),
64            space: 0,
65        }
66    }
67
68    #[inline]
69    /// Removes all values from the map.
70    pub fn clear(&mut self) {
71        self.drop_values();
72        self.ids.clear();
73    }
74
75    #[inline]
76    /// Returns the id that a subsequent call to insert() will produce.
77    pub fn next_id(&self) -> Id {
78        self.space
79    }
80
81    #[inline]
82    /// Returns the number of id-value pairs in the map.
83    pub fn len(&self) -> usize {
84        self.ids.len()
85    }
86
87    #[inline]
88    /// Returns the number of id-value pairs the map can hold before reallocating.
89    pub fn capacity(&self) -> usize {
90        self.ids.capacity()
91    }
92
93    #[inline]
94    /// Resizes the map such that that `capacity() >= cap`.
95    pub fn reserve(&mut self, cap: usize) {
96        self.ids.reserve(cap);
97        self.values.reserve(cap);
98    }
99
100    #[inline]
101    /// Resizes the map to minimize allocated memory.
102    pub fn shrink_to_fit(&mut self) {
103        self.ids.shrink_to_fit();
104        self.values.truncate(self.ids.capacity());
105        self.values.shrink_to(self.ids.capacity());
106    }
107
108    #[inline]
109    /// Returns a reference to the set of valid ids.
110    pub fn as_set(&self) -> &IdSet {
111        &self.ids
112    }
113
114    #[inline]
115    /// Inserts a value into an empty slot in the map and returns its id.
116    pub fn insert(&mut self, val: T) -> Id {
117        let id = self.space;
118        if id == self.values.len() {
119            self.values.resize_with(id + 1, Default::default);
120        }
121        self.values[id] = Some(val);
122        self.ids.insert(id);
123        self.find_space();
124        id
125    }
126
127    #[inline]
128    /// Inserts a value at a specific id, returning the old value if it existed.
129    pub fn insert_at(&mut self, id: Id, val: T) -> Option<T> {
130        if self.ids.insert(id) {
131            // val was not previously in the map.
132            if id == self.space {
133                self.find_space();
134            }
135            if self.values.len() < id + 1 {
136                self.values.resize_with(id + 1, Default::default);
137            }
138            self.values[id] = Some(val);
139            None
140        } else {
141            // val was previously in the map
142            Some(mem::replace(&mut self.values[id].as_mut().unwrap(), val))
143        }
144    }
145
146    #[inline]
147    /// Removes an id from the map, returning its value if it was previously in the map.
148    pub fn remove(&mut self, id: Id) -> Option<T> {
149        if self.ids.remove(id) {
150            self.space = cmp::min(self.space, id);
151            self.values[id].take()
152        } else {
153            None
154        }
155    }
156
157    #[inline]
158    /// If the id has a value, returns it, otherwise inserts a new value.
159    pub fn get_or_insert(&mut self, id: Id, val: T) -> &mut T {
160        self.get_or_insert_with(id, || val)
161    }
162
163    #[inline]
164    /// If the id has a value, returns it, otherwise inserts a new value with the provided closure.
165    pub fn get_or_insert_with<F: FnOnce() -> T>(&mut self, id: Id, f: F) -> &mut T {
166        if self.ids.insert(id) {
167            // val was not previously in the map.
168            if id == self.space {
169                self.find_space();
170            }
171            if self.values.len() < id + 1 {
172                self.values.resize_with(id + 1, Default::default);
173            }
174            self.values[id] = Some(f());
175        }
176
177        self.values[id].as_mut().unwrap()
178    }
179
180    #[inline]
181    /// Removes all ids in the set from the map.
182    pub fn remove_set(&mut self, set: &IdSet) {
183        {
184            let mut iter = self.ids.intersection(set).into_iter();
185
186            if let Some(first) = iter.next() {
187                // Set iterators are increasing so we only need to change start once.
188                self.space = cmp::min(self.space, first);
189                self.values[first] = None;
190                for id in iter {
191                    self.values[id] = None;
192                }
193            }
194        }
195
196        self.ids.inplace_difference(set);
197    }
198
199    #[inline]
200    /// Remove all values not satisfying the predicate.
201    pub fn retain<F: FnMut(Id, &T) -> bool>(&mut self, mut pred: F) {
202        let ids = &mut self.ids;
203        let values = &mut self.values;
204        let space = &mut self.space;
205        ids.retain(|id| {
206            if pred(id, values[id].as_ref().unwrap()) {
207                true
208            } else {
209                *space = cmp::min(*space, id);
210                values[id] = None;
211                false
212            }
213        })
214    }
215
216    #[inline]
217    /// Returns true if the map contains a value for the specified id.
218    pub fn contains(&self, id: Id) -> bool {
219        self.ids.contains(id)
220    }
221
222    #[inline]
223    /// Returns a reference to the value at the specified id if it is in the map.
224    pub fn get(&self, id: Id) -> Option<&T> {
225        if self.ids.contains(id) {
226            Some(self.values[id].as_ref().unwrap())
227        } else {
228            None
229        }
230    }
231
232    #[inline]
233    /// Returns a mutable reference to the value at the specified id if it is in the map.
234    pub fn get_mut(&mut self, id: Id) -> Option<&mut T> {
235        if self.ids.contains(id) {
236            Some(self.values[id].as_mut().unwrap())
237        } else {
238            None
239        }
240    }
241
242    #[inline]
243    /// An iterator over ids, in increasing order.
244    pub fn ids(&self) -> Ids {
245        Ids {
246            ids: self.ids.iter(),
247        }
248    }
249
250    #[inline]
251    /// An iterator over values, in order of increasing id.
252    pub fn values(&self) -> Values<T> {
253        Values {
254            ids: self.ids.iter(),
255            values: &self.values,
256        }
257    }
258
259    #[inline]
260    /// A mutable iterator over values, in order of increasing id.
261    pub fn values_mut(&mut self) -> ValuesMut<T> {
262        ValuesMut {
263            ids: self.ids.iter(),
264            prev: None,
265            values: self.values.iter_mut(),
266        }
267    }
268
269    #[inline]
270    /// An iterator over id-value pairs, in order of increasing id.
271    pub fn iter(&self) -> Iter<T> {
272        Iter {
273            ids: self.ids.iter(),
274            values: &self.values,
275        }
276    }
277
278    #[inline]
279    /// A mutable iterator over id-value pairs, in order of increasing id.
280    pub fn iter_mut(&mut self) -> IterMut<T> {
281        IterMut {
282            ids: self.ids.iter(),
283            prev: None,
284            values: self.values.iter_mut(),
285        }
286    }
287
288    #[inline]
289    /// A consuming iterator over id-value pairs, in order of increasing id.
290    pub fn into_iter(self) -> IntoIter<T> {
291        IntoIter {
292            ids: self.ids.into_iter(),
293            prev: None,
294            values: self.values.into_iter(),
295        }
296    }
297
298    #[cfg(test)]
299    fn assert_invariant(&self) {
300        // space should be the minimal empty space.
301        for id in 0..self.space {
302            assert!(self.ids.contains(id));
303        }
304        assert!(!self.ids.contains(self.space));
305        // values.len() should be an upper bound on ids.
306        for id in &self.ids {
307            assert!(id < self.values.len())
308        }
309    }
310
311    /// Clear the values vec.
312    fn drop_values(&mut self) {
313        for id in &self.ids {
314            self.values[id] = None;
315        }
316    }
317
318    /// Find the next empty space after one has been filled.
319    fn find_space(&mut self) {
320        // Each id corresponds to an entry in the storage so ids can never fill up.
321        self.space += 1;
322        while self.ids.contains(self.space) {
323            self.space += 1;
324        }
325    }
326}
327
328impl<T: fmt::Debug> fmt::Debug for IdMap<T> {
329    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
330        write!(f, "{{")?;
331        let mut iter = self.iter();
332        if let Some((id, val)) = iter.next() {
333            write!(f, "{:?}: {:?}", id, val)?;
334            for (id, val) in iter {
335                write!(f, ", {:?}: {:?}", id, val)?;
336            }
337        }
338        write!(f, "}}")
339    }
340}
341
342impl<T> Default for IdMap<T> {
343    #[inline]
344    fn default() -> Self {
345        IdMap::new()
346    }
347}
348
349impl<T: Eq> Eq for IdMap<T> {}
350
351impl<T: PartialEq> PartialEq for IdMap<T> {
352    fn eq(&self, other: &Self) -> bool {
353        self.ids == other.ids
354            && self
355                .ids
356                .iter()
357                .zip(&other.ids)
358                .all(|(l, r)| self.values[l].as_ref().unwrap() == other.values[r].as_ref().unwrap())
359    }
360}
361
362impl<T> Extend<T> for IdMap<T> {
363    #[inline]
364    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
365        for val in iter {
366            self.insert(val);
367        }
368    }
369}
370
371impl<T> FromIterator<T> for IdMap<T> {
372    #[inline]
373    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
374        let values = Vec::from_iter(iter.into_iter().map(Some));
375        let space = values.len();
376        let ids = IdSet::new_filled(values.len());
377        IdMap { values, space, ids }
378    }
379}
380
381impl<T> FromIterator<(Id, T)> for IdMap<T> {
382    #[inline]
383    fn from_iter<I: IntoIterator<Item = (Id, T)>>(iter: I) -> Self {
384        let iter = iter.into_iter();
385        let mut map = IdMap::with_capacity(iter.size_hint().0);
386        for (id, val) in iter {
387            map.insert_at(id, val);
388        }
389        map
390    }
391}
392
393impl<'a, T> IntoIterator for &'a IdMap<T> {
394    type Item = (Id, &'a T);
395    type IntoIter = Iter<'a, T>;
396
397    #[inline]
398    fn into_iter(self) -> Self::IntoIter {
399        self.iter()
400    }
401}
402
403impl<'a, T> IntoIterator for &'a mut IdMap<T> {
404    type Item = (Id, &'a mut T);
405    type IntoIter = IterMut<'a, T>;
406
407    #[inline]
408    fn into_iter(self) -> Self::IntoIter {
409        self.iter_mut()
410    }
411}
412
413impl<T> IntoIterator for IdMap<T> {
414    type Item = (Id, T);
415    type IntoIter = IntoIter<T>;
416
417    #[inline]
418    fn into_iter(self) -> Self::IntoIter {
419        self.into_iter()
420    }
421}
422
423impl<T> Index<Id> for IdMap<T> {
424    type Output = T;
425
426    #[inline]
427    fn index(&self, id: Id) -> &Self::Output {
428        assert!(self.ids.contains(id), "id {} out of bounds", id);
429        self.values[id].as_ref().unwrap()
430    }
431}
432
433impl<T> IndexMut<Id> for IdMap<T> {
434    #[inline]
435    fn index_mut(&mut self, id: Id) -> &mut Self::Output {
436        assert!(self.ids.contains(id), "id {} out of bounds", id);
437        self.values[id].as_mut().unwrap()
438    }
439}
440
441#[derive(Clone, Debug)]
442/// An iterator over all ids, in increasing order.
443pub struct Ids<'a> {
444    ids: id_set::Iter<'a>,
445}
446
447impl<'a> Iterator for Ids<'a> {
448    type Item = Id;
449
450    #[inline]
451    fn next(&mut self) -> Option<Self::Item> {
452        self.ids.next()
453    }
454
455    #[inline]
456    fn size_hint(&self) -> (usize, Option<usize>) {
457        self.ids.size_hint()
458    }
459}
460
461impl<'a> ExactSizeIterator for Ids<'a> {
462    #[inline]
463    fn len(&self) -> usize {
464        self.ids.len()
465    }
466}
467
468#[derive(Debug)]
469/// An iterator over all values, in order of increasing id.
470pub struct Values<'a, T: 'a> {
471    ids: id_set::Iter<'a>,
472    values: &'a [Option<T>],
473}
474
475impl<'a, T: 'a> Iterator for Values<'a, T> {
476    type Item = &'a T;
477
478    #[inline]
479    fn next(&mut self) -> Option<Self::Item> {
480        self.ids.next().map(|id| self.values[id].as_ref().unwrap())
481    }
482
483    #[inline]
484    fn size_hint(&self) -> (usize, Option<usize>) {
485        self.ids.size_hint()
486    }
487}
488
489impl<'a, T: 'a> ExactSizeIterator for Values<'a, T> {
490    #[inline]
491    fn len(&self) -> usize {
492        self.ids.len()
493    }
494}
495
496impl<'a, T: 'a> Clone for Values<'a, T> {
497    #[inline]
498    fn clone(&self) -> Self {
499        Values {
500            ids: self.ids.clone(),
501            values: self.values,
502        }
503    }
504}
505
506#[derive(Debug)]
507/// A mutable iterator over all values, in order of increasing id.
508pub struct ValuesMut<'a, T: 'a> {
509    ids: id_set::Iter<'a>,
510    prev: Option<Id>,
511    values: slice::IterMut<'a, Option<T>>,
512}
513
514impl<'a, T: 'a> Iterator for ValuesMut<'a, T> {
515    type Item = &'a mut T;
516
517    #[inline]
518    fn next(&mut self) -> Option<Self::Item> {
519        let id = self.ids.next()?;
520        let n = match self.prev {
521            Some(prev) => id - prev - 1,
522            None => 0,
523        };
524        self.prev = Some(id);
525
526        Some(self.values.nth(n).unwrap().as_mut().unwrap())
527    }
528
529    #[inline]
530    fn size_hint(&self) -> (usize, Option<usize>) {
531        self.ids.size_hint()
532    }
533}
534
535impl<'a, T: 'a> ExactSizeIterator for ValuesMut<'a, T> {
536    #[inline]
537    fn len(&self) -> usize {
538        self.ids.len()
539    }
540}
541
542#[derive(Debug)]
543/// An iterator over id-value pairs, in order of increasing id.
544pub struct Iter<'a, T: 'a> {
545    ids: id_set::Iter<'a>,
546    values: &'a [Option<T>],
547}
548
549impl<'a, T: 'a> Iterator for Iter<'a, T> {
550    type Item = (Id, &'a T);
551
552    #[inline]
553    fn next(&mut self) -> Option<Self::Item> {
554        self.ids
555            .next()
556            .map(|id| (id, self.values[id].as_ref().unwrap()))
557    }
558
559    #[inline]
560    fn size_hint(&self) -> (usize, Option<usize>) {
561        self.ids.size_hint()
562    }
563}
564
565impl<'a, T: 'a> ExactSizeIterator for Iter<'a, T> {
566    #[inline]
567    fn len(&self) -> usize {
568        self.ids.len()
569    }
570}
571
572impl<'a, T: 'a> Clone for Iter<'a, T> {
573    #[inline]
574    fn clone(&self) -> Self {
575        Iter {
576            ids: self.ids.clone(),
577            values: self.values,
578        }
579    }
580}
581
582#[derive(Debug)]
583/// A mutable iterator over id-value pairs, in order of increasing id.
584pub struct IterMut<'a, T: 'a> {
585    ids: id_set::Iter<'a>,
586    prev: Option<Id>,
587    values: slice::IterMut<'a, Option<T>>,
588}
589
590impl<'a, T: 'a> Iterator for IterMut<'a, T> {
591    type Item = (Id, &'a mut T);
592
593    #[inline]
594    fn next(&mut self) -> Option<Self::Item> {
595        let id = self.ids.next()?;
596        let n = match self.prev {
597            Some(prev) => id - prev - 1,
598            None => 0,
599        };
600        self.prev = Some(id);
601
602        Some((
603            id,
604            self.values.nth(n).unwrap().as_mut().expect("id not in map"),
605        ))
606    }
607
608    #[inline]
609    fn size_hint(&self) -> (usize, Option<usize>) {
610        self.ids.size_hint()
611    }
612}
613
614impl<'a, T: 'a> ExactSizeIterator for IterMut<'a, T> {
615    #[inline]
616    fn len(&self) -> usize {
617        self.ids.len()
618    }
619}
620
621#[derive(Clone, Debug)]
622/// A consuming iterator over id-value pairs, in order of increasing id.
623pub struct IntoIter<T> {
624    ids: id_set::IntoIter,
625    prev: Option<Id>,
626    values: vec::IntoIter<Option<T>>,
627}
628
629impl<T> Iterator for IntoIter<T> {
630    type Item = (Id, T);
631
632    #[inline]
633    fn next(&mut self) -> Option<Self::Item> {
634        let id = self.ids.next()?;
635        let n = match self.prev {
636            Some(prev) => id - prev - 1,
637            None => 0,
638        };
639        self.prev = Some(id);
640
641        Some((id, self.values.nth(n).unwrap().expect("id not in map")))
642    }
643
644    #[inline]
645    fn size_hint(&self) -> (usize, Option<usize>) {
646        self.ids.size_hint()
647    }
648}
id_map/lib.rs

id_map/
lib.rs
