pal_async/
sparsevec.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// Copyright (c) Microsoft Corporation.
// Licensed under the MIT License.

//! Utility type.

use std::ops::Index;
use std::ops::IndexMut;

/// A `Vec` whose indexes don't change as elements are added and removed.
#[derive(Debug)]
pub struct SparseVec<T>(Vec<Option<T>>);

impl<T> Default for SparseVec<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> SparseVec<T> {
    /// Creates a new sparse vector.
    pub fn new() -> Self {
        Self(Vec::new())
    }

    /// Adds an entry, returning its index.
    pub fn add(&mut self, t: T) -> usize {
        let index = self.0.iter().position(|x| x.is_none()).unwrap_or_else(|| {
            self.0.push(None);
            self.0.len() - 1
        });
        self.0[index] = Some(t);
        index
    }

    /// Removes an entry by index.
    ///
    /// # Panics
    ///
    /// Panics if `index` was not added or has already been removed.
    pub fn remove(&mut self, index: usize) -> T {
        self.0[index].take().unwrap()
    }

    /// Returns an iterator for the entries.
    pub fn iter(&self) -> impl Iterator<Item = (usize, &'_ T)> {
        self.0
            .iter()
            .enumerate()
            .filter_map(|(i, v)| v.as_ref().map(|v| (i, v)))
    }

    /// Returns a mutable iterator for the entries.
    pub fn iter_mut(&mut self) -> impl Iterator<Item = (usize, &'_ mut T)> {
        self.0
            .iter_mut()
            .enumerate()
            .filter_map(|(i, v)| v.as_mut().map(|v| (i, v)))
    }
}

impl<T> Index<usize> for SparseVec<T> {
    type Output = T;

    fn index(&self, index: usize) -> &Self::Output {
        self.0.get(index).and_then(Option::as_ref).unwrap()
    }
}

impl<T> IndexMut<usize> for SparseVec<T> {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        self.0.get_mut(index).and_then(Option::as_mut).unwrap()
    }
}