pal_async/
sparsevec.rs

1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4//! Utility type.
5
6use std::ops::Index;
7use std::ops::IndexMut;
8
9/// A `Vec` whose indexes don't change as elements are added and removed.
10#[derive(Debug)]
11pub struct SparseVec<T>(Vec<Option<T>>);
12
13impl<T> Default for SparseVec<T> {
14    fn default() -> Self {
15        Self::new()
16    }
17}
18
19impl<T> SparseVec<T> {
20    /// Creates a new sparse vector.
21    pub fn new() -> Self {
22        Self(Vec::new())
23    }
24
25    /// Adds an entry, returning its index.
26    pub fn add(&mut self, t: T) -> usize {
27        let index = self.0.iter().position(|x| x.is_none()).unwrap_or_else(|| {
28            self.0.push(None);
29            self.0.len() - 1
30        });
31        self.0[index] = Some(t);
32        index
33    }
34
35    /// Removes an entry by index.
36    ///
37    /// # Panics
38    ///
39    /// Panics if `index` was not added or has already been removed.
40    pub fn remove(&mut self, index: usize) -> T {
41        self.0[index].take().unwrap()
42    }
43
44    /// Returns an iterator for the entries.
45    pub fn iter(&self) -> impl Iterator<Item = (usize, &'_ T)> {
46        self.0
47            .iter()
48            .enumerate()
49            .filter_map(|(i, v)| v.as_ref().map(|v| (i, v)))
50    }
51
52    /// Returns a mutable iterator for the entries.
53    pub fn iter_mut(&mut self) -> impl Iterator<Item = (usize, &'_ mut T)> {
54        self.0
55            .iter_mut()
56            .enumerate()
57            .filter_map(|(i, v)| v.as_mut().map(|v| (i, v)))
58    }
59}
60
61impl<T> Index<usize> for SparseVec<T> {
62    type Output = T;
63
64    fn index(&self, index: usize) -> &Self::Output {
65        self.0.get(index).and_then(Option::as_ref).unwrap()
66    }
67}
68
69impl<T> IndexMut<usize> for SparseVec<T> {
70    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
71        self.0.get_mut(index).and_then(Option::as_mut).unwrap()
72    }
73}
pal_async/sparsevec.rs

pal_async/
sparsevec.rs
