1 use std::{

     2     iter,

     3     ops::{Index, IndexMut},

     4 };

     5 

     6 pub struct IndexSlab<T> {

     7     data: Vec<Option<T>>,

     8 }

     9 

    10 impl<T> IndexSlab<T> {

    11     pub fn new() -> Self {

    12         Self { data: Vec::new() }

    13     }

    14 

    15     pub fn with_capacity(capacity: usize) -> Self {

    16         Self {

    17             data: Vec::with_capacity(capacity),

    18         }

    19     }

    20 

    21     pub fn insert(&mut self, index: usize, value: T) {

    22         if index >= self.data.len() {

    23             self.data.reserve(index - self.data.len() + 1);

    24             self.data.extend((self.data.len()..index).map(|_| None));

    25             self.data.push(Some(value))

    26         } else {

    27             self.data[index] = Some(value);

    28         }

    29     }

    30 

    31     pub fn contains(&self, index: usize) -> bool {

    32         self.data.get(index).and_then(|x| x.as_ref()).is_some()

    33     }

    34 

    35     pub fn remove(&mut self, index: usize) {

    36         if let Some(x) = self.data.get_mut(index) {

    37             *x = None

    38         }

    39     }

    40 

    41     pub fn iter(&self) -> impl Iterator<Item = (usize, &T)> {

    42         self.data

    43             .iter()

    44             .enumerate()

    45             .filter_map(|(index, opt)| opt.as_ref().and_then(|x| Some((index, x))))

    46     }

    47 

    48     pub fn iter_mut(&mut self) -> impl Iterator<Item = (usize, &mut T)> {

    49         self.data

    50             .iter_mut()

    51             .enumerate()

    52             .filter_map(|(index, opt)| opt.as_mut().and_then(|x| Some((index, x))))

    53     }

    54 }

    55 

    56 impl<T> Index<usize> for IndexSlab<T> {

    57     type Output = T;

    58 

    59     fn index(&self, index: usize) -> &Self::Output {

    60         self.data[index].as_ref().unwrap()

    61     }

    62 }

    63 

    64 impl<T> IndexMut<usize> for IndexSlab<T> {

    65     fn index_mut(&mut self, index: usize) -> &mut Self::Output {

    66         self.data[index].as_mut().unwrap()

    67     }

    68 }