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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
pub struct OptionalVec<T> {
values: Vec<Option<T>>,
holes: Vec<usize>,
}
impl<T> Default for OptionalVec<T> {
fn default() -> Self {
Self {
values: Default::default(),
holes: Default::default(),
}
}
}
impl<T> OptionalVec<T> {
#[inline]
pub fn with_capacity(cap: usize) -> Self {
Self {
values: Vec::with_capacity(cap),
holes: Default::default(),
}
}
#[inline]
pub fn insert(&mut self, elem: T) -> usize {
let idx = self.holes.pop().unwrap_or_else(|| self.values.len());
if idx < self.values.len() {
self.values[idx] = Some(elem);
} else {
self.values.push(Some(elem));
}
idx
}
#[inline]
pub fn next_idx(&self) -> usize {
self.holes.last().copied().unwrap_or_else(|| self.values.len())
}
#[inline]
pub fn remove(&mut self, idx: usize) -> T {
let val = self.values[idx].take();
self.holes.push(idx);
val.unwrap()
}
#[inline]
pub fn iter(&self) -> impl Iterator<Item = &T> {
self.values.iter().filter(|v| v.is_some()).map(|v| v.as_ref().unwrap())
}
#[inline]
pub fn len(&self) -> usize {
self.values.len() - self.holes.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
}
impl<T> std::ops::Index<usize> for OptionalVec<T> {
type Output = T;
fn index(&self, idx: usize) -> &Self::Output {
self.values[idx].as_ref().unwrap()
}
}
impl<T> std::ops::IndexMut<usize> for OptionalVec<T> {
fn index_mut(&mut self, idx: usize) -> &mut Self::Output {
self.values[idx].as_mut().unwrap()
}
}