1use bitvec::prelude::*;
2use std::iter::FusedIterator;
3use std::sync::atomic::{AtomicUsize, Ordering};
4
5#[derive(Debug, Default)]
6pub struct FixVec<T> {
7 buf: Vec<T>,
8 useds: BitVec,
9 len: AtomicUsize,
10}
11
12impl<T: Default> FixVec<T> {
13 pub fn push(&mut self, v: T) -> usize {
14 self.len.fetch_add(1, Ordering::Relaxed);
15 if let Some(pos) = self.useds.first_zero() {
16 self.buf[pos] = v;
17 self.useds.set(pos, true);
18 pos
19 } else {
20 self.buf.push(v);
21 self.useds.push(true);
22 self.buf.len() - 1
23 }
24 }
25
26 pub fn len(&self) -> usize {
27 self.len.load(Ordering::Relaxed)
28 }
29
30 pub fn pop(&mut self) -> Option<T> {
31 if let Some(idx) = self.useds.iter().enumerate().rev().find(|(_idx, val)| *val.as_ref()).map(|(idx, _)| idx) { self.remove(idx) } else { None }
32 }
33
34 pub fn remove(&mut self, pos: usize) -> Option<T> {
35 if self.useds.get(pos).map(|v| *v).unwrap_or(false) {
36 self.len.fetch_sub(1, Ordering::Relaxed);
37 self.useds.set(pos, false);
38 Some(std::mem::take(&mut self.buf[pos]))
39 } else {
40 None
41 }
42 }
43
44 pub fn get(&self, pos: usize) -> Option<&T> {
45 if self.useds.get(pos).map(|v| *v).unwrap_or(false) { self.buf.get(pos) } else { None }
46 }
47
48 pub fn get_mut(&mut self, pos: usize) -> Option<&mut T> {
49 if self.useds.get(pos).map(|v| *v).unwrap_or(false) { self.buf.get_mut(pos) } else { None }
50 }
51
52 pub fn iter(&self) -> Iter<'_, T> {
53 Iter { vec: self, index: 0 }
54 }
55
56 pub fn iter_mut(&mut self) -> IterMut<'_, T> {
57 IterMut { vec: self, index: 0 }
58 }
59
60 pub fn is_empty(&self) -> bool {
61 self.useds.not_any()
62 }
63
64 pub fn capacity(&self) -> usize {
65 self.buf.len()
66 }
67
68 pub fn clear(&mut self) {
69 self.len.store(0, Ordering::Relaxed);
70 for i in 0..self.buf.len() {
71 if self.useds.get(i).map(|v| *v).unwrap_or(false) {
72 let _ = std::mem::take(&mut self.buf[i]);
73 }
74 }
75 self.useds.fill(false);
76 }
77
78 pub fn contains(&self, index: usize) -> bool {
79 self.useds.get(index).map(|v| *v).unwrap_or(false)
80 }
81
82 pub fn indices(&self) -> Indices<'_, T> {
83 Indices { vec: self, index: 0 }
84 }
85
86 pub fn values(&self) -> Values<'_, T> {
87 Values { iter: self.iter() }
88 }
89
90 pub fn values_mut(&mut self) -> ValuesMut<'_, T> {
91 ValuesMut { iter: self.iter_mut() }
92 }
93}
94
95pub struct Iter<'a, T> {
96 vec: &'a FixVec<T>,
97 index: usize,
98}
99
100impl<'a, T> Iterator for Iter<'a, T> {
101 type Item = (usize, &'a T);
102
103 fn next(&mut self) -> Option<Self::Item> {
104 while self.index < self.vec.buf.len() {
105 let current_index = self.index;
106 self.index += 1;
107
108 if self.vec.useds.get(current_index).map(|v| *v).unwrap_or(false) {
109 return Some((current_index, &self.vec.buf[current_index]));
110 }
111 }
112 None
113 }
114
115 fn size_hint(&self) -> (usize, Option<usize>) {
116 let used_before = self.vec.useds.iter().take(self.index).filter(|b| *b.as_ref()).count();
117 let total = self.vec.useds.iter().filter(|b| *b.as_ref()).count();
118 let remaining = total.saturating_sub(used_before);
119 (remaining, Some(remaining))
120 }
121}
122
123impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
124impl<'a, T> FusedIterator for Iter<'a, T> {}
125
126pub struct IterMut<'a, T> {
127 vec: &'a mut FixVec<T>,
128 index: usize,
129}
130
131impl<'a, T> Iterator for IterMut<'a, T> {
132 type Item = (usize, &'a mut T);
133 fn next(&mut self) -> Option<Self::Item> {
134 while self.index < self.vec.buf.len() {
135 let current_index = self.index;
136 self.index += 1;
137 if self.vec.useds.get(current_index).map(|v| *v).unwrap_or(false) {
138 unsafe {
139 let ptr = self.vec.buf.as_mut_ptr().add(current_index);
140 return Some((current_index, &mut *ptr));
141 }
142 }
143 }
144 None
145 }
146
147 fn size_hint(&self) -> (usize, Option<usize>) {
148 let used_before = self.vec.useds.iter().take(self.index).filter(|b| *b.as_ref()).count();
149 let total = self.vec.useds.iter().filter(|b| *b.as_ref()).count();
150 let remaining = total.saturating_sub(used_before);
151 (remaining, Some(remaining))
152 }
153}
154
155impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
156impl<'a, T> FusedIterator for IterMut<'a, T> {}
157
158impl<T: Default> IntoIterator for FixVec<T> {
159 type Item = (usize, T);
160 type IntoIter = IntoIter<T>;
161
162 fn into_iter(self) -> Self::IntoIter {
163 IntoIter { vec: self, index: 0 }
164 }
165}
166
167pub struct IntoIter<T: Default> {
168 vec: FixVec<T>,
169 index: usize,
170}
171
172impl<T: Default> Iterator for IntoIter<T> {
173 type Item = (usize, T);
174
175 fn next(&mut self) -> Option<Self::Item> {
176 while self.index < self.vec.buf.len() {
177 let current_index = self.index;
178 self.index += 1;
179 if self.vec.useds.get(current_index).map(|v| *v).unwrap_or(false) {
180 self.vec.useds.set(current_index, false);
181 let value = std::mem::take(&mut self.vec.buf[current_index]);
182 return Some((current_index, value));
183 }
184 }
185 None
186 }
187
188 fn size_hint(&self) -> (usize, Option<usize>) {
189 let remaining = self.vec.useds.iter().skip(self.index).filter(|b| *b.as_ref()).count();
190 (remaining, Some(remaining))
191 }
192}
193
194impl<T: Default> ExactSizeIterator for IntoIter<T> {}
195impl<T: Default> FusedIterator for IntoIter<T> {}
196
197impl<T: Default> Drop for IntoIter<T> {
198 fn drop(&mut self) {
199 while self.index < self.vec.buf.len() {
200 if self.vec.useds.get(self.index).map(|v| *v).unwrap_or(false) {
201 self.vec.useds.set(self.index, false);
202 let _ = std::mem::take(&mut self.vec.buf[self.index]);
203 }
204 self.index += 1;
205 }
206 }
207}
208
209impl<'a, T: Default> IntoIterator for &'a FixVec<T> {
210 type Item = (usize, &'a T);
211 type IntoIter = Iter<'a, T>;
212
213 fn into_iter(self) -> Self::IntoIter {
214 self.iter()
215 }
216}
217
218impl<'a, T: Default> IntoIterator for &'a mut FixVec<T> {
219 type Item = (usize, &'a mut T);
220 type IntoIter = IterMut<'a, T>;
221
222 fn into_iter(self) -> Self::IntoIter {
223 self.iter_mut()
224 }
225}
226
227pub struct Indices<'a, T> {
228 vec: &'a FixVec<T>,
229 index: usize,
230}
231
232impl<'a, T> Iterator for Indices<'a, T> {
233 type Item = usize;
234 fn next(&mut self) -> Option<Self::Item> {
235 while self.index < self.vec.buf.len() {
236 let current_index = self.index;
237 self.index += 1;
238
239 if self.vec.useds.get(current_index).map(|v| *v).unwrap_or(false) {
240 return Some(current_index);
241 }
242 }
243 None
244 }
245
246 fn size_hint(&self) -> (usize, Option<usize>) {
247 let used_before = self.vec.useds.iter().take(self.index).filter(|b| *b.as_ref()).count();
248 let total = self.vec.useds.iter().filter(|b| *b.as_ref()).count();
249 let remaining = total.saturating_sub(used_before);
250 (remaining, Some(remaining))
251 }
252}
253
254impl<'a, T> ExactSizeIterator for Indices<'a, T> {}
255impl<'a, T> FusedIterator for Indices<'a, T> {}
256
257pub struct Values<'a, T> {
258 iter: Iter<'a, T>,
259}
260
261impl<'a, T> Iterator for Values<'a, T> {
262 type Item = &'a T;
263
264 fn next(&mut self) -> Option<Self::Item> {
265 self.iter.next().map(|(_, value)| value)
266 }
267
268 fn size_hint(&self) -> (usize, Option<usize>) {
269 self.iter.size_hint()
270 }
271}
272
273impl<'a, T> ExactSizeIterator for Values<'a, T> {}
274impl<'a, T> FusedIterator for Values<'a, T> {}
275
276pub struct ValuesMut<'a, T> {
277 iter: IterMut<'a, T>,
278}
279
280impl<'a, T> Iterator for ValuesMut<'a, T> {
281 type Item = &'a mut T;
282
283 fn next(&mut self) -> Option<Self::Item> {
284 self.iter.next().map(|(_, value)| value)
285 }
286
287 fn size_hint(&self) -> (usize, Option<usize>) {
288 self.iter.size_hint()
289 }
290}
291
292impl<'a, T> ExactSizeIterator for ValuesMut<'a, T> {}
293impl<'a, T> FusedIterator for ValuesMut<'a, T> {}