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
116impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
117impl<'a, T> FusedIterator for Iter<'a, T> {}
118
119pub struct IterMut<'a, T> {
120 vec: &'a mut FixVec<T>,
121 index: usize,
122}
123
124impl<'a, T> Iterator for IterMut<'a, T> {
125 type Item = (usize, &'a mut T);
126 fn next(&mut self) -> Option<Self::Item> {
127 while self.index < self.vec.buf.len() {
128 let current_index = self.index;
129 self.index += 1;
130 if self.vec.useds.get(current_index).map(|v| *v).unwrap_or(false) {
131 unsafe {
132 let ptr = self.vec.buf.as_mut_ptr().add(current_index);
133 return Some((current_index, &mut *ptr));
134 }
135 }
136 }
137 None
138 }
139}
140
141impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
142impl<'a, T> FusedIterator for IterMut<'a, T> {}
143
144impl<T: Default> IntoIterator for FixVec<T> {
145 type Item = (usize, T);
146 type IntoIter = IntoIter<T>;
147
148 fn into_iter(self) -> Self::IntoIter {
149 IntoIter { vec: self, index: 0 }
150 }
151}
152
153pub struct IntoIter<T: Default> {
154 vec: FixVec<T>,
155 index: usize,
156}
157
158impl<T: Default> Iterator for IntoIter<T> {
159 type Item = (usize, T);
160
161 fn next(&mut self) -> Option<Self::Item> {
162 while self.index < self.vec.buf.len() {
163 let current_index = self.index;
164 self.index += 1;
165 if self.vec.useds.get(current_index).map(|v| *v).unwrap_or(false) {
166 self.vec.useds.set(current_index, false);
167 let value = std::mem::take(&mut self.vec.buf[current_index]);
168 return Some((current_index, value));
169 }
170 }
171 None
172 }
173}
174
175impl<T: Default> ExactSizeIterator for IntoIter<T> {}
176impl<T: Default> FusedIterator for IntoIter<T> {}
177
178impl<T: Default> Drop for IntoIter<T> {
179 fn drop(&mut self) {
180 while self.index < self.vec.buf.len() {
181 if self.vec.useds.get(self.index).map(|v| *v).unwrap_or(false) {
182 self.vec.useds.set(self.index, false);
183 let _ = std::mem::take(&mut self.vec.buf[self.index]);
184 }
185 self.index += 1;
186 }
187 }
188}
189
190impl<'a, T: Default> IntoIterator for &'a FixVec<T> {
191 type Item = (usize, &'a T);
192 type IntoIter = Iter<'a, T>;
193
194 fn into_iter(self) -> Self::IntoIter {
195 self.iter()
196 }
197}
198
199impl<'a, T: Default> IntoIterator for &'a mut FixVec<T> {
200 type Item = (usize, &'a mut T);
201 type IntoIter = IterMut<'a, T>;
202
203 fn into_iter(self) -> Self::IntoIter {
204 self.iter_mut()
205 }
206}
207
208pub struct Indices<'a, T> {
209 vec: &'a FixVec<T>,
210 index: usize,
211}
212
213impl<'a, T> Iterator for Indices<'a, T> {
214 type Item = usize;
215 fn next(&mut self) -> Option<Self::Item> {
216 while self.index < self.vec.buf.len() {
217 let current_index = self.index;
218 self.index += 1;
219
220 if self.vec.useds.get(current_index).map(|v| *v).unwrap_or(false) {
221 return Some(current_index);
222 }
223 }
224 None
225 }
226}
227
228impl<'a, T> ExactSizeIterator for Indices<'a, T> {}
229impl<'a, T> FusedIterator for Indices<'a, T> {}
230
231pub struct Values<'a, T> {
232 iter: Iter<'a, T>,
233}
234
235impl<'a, T> Iterator for Values<'a, T> {
236 type Item = &'a T;
237
238 fn next(&mut self) -> Option<Self::Item> {
239 self.iter.next().map(|(_, value)| value)
240 }
241
242 fn size_hint(&self) -> (usize, Option<usize>) {
243 self.iter.size_hint()
244 }
245}
246
247impl<'a, T> ExactSizeIterator for Values<'a, T> {}
248impl<'a, T> FusedIterator for Values<'a, T> {}
249
250pub struct ValuesMut<'a, T> {
251 iter: IterMut<'a, T>,
252}
253
254impl<'a, T> Iterator for ValuesMut<'a, T> {
255 type Item = &'a mut T;
256
257 fn next(&mut self) -> Option<Self::Item> {
258 self.iter.next().map(|(_, value)| value)
259 }
260
261 fn size_hint(&self) -> (usize, Option<usize>) {
262 self.iter.size_hint()
263 }
264}
265
266impl<'a, T> ExactSizeIterator for ValuesMut<'a, T> {}
267impl<'a, T> FusedIterator for ValuesMut<'a, T> {}