]>
Commit | Line | Data |
---|---|---|
dfeec247 | 1 | use rustc_serialize::{Decodable, Decoder, Encodable, Encoder}; |
416331ca | 2 | |
dfeec247 | 3 | use std::fmt; |
3157f602 | 4 | use std::fmt::Debug; |
dfeec247 | 5 | use std::hash::Hash; |
c295e0f8 | 6 | use std::iter::FromIterator; |
3157f602 | 7 | use std::marker::PhantomData; |
c295e0f8 | 8 | use std::ops::{Index, IndexMut, RangeBounds}; |
dfeec247 | 9 | use std::slice; |
dfeec247 | 10 | use std::vec; |
3157f602 | 11 | |
3157f602 XL |
12 | /// Represents some newtyped `usize` wrapper. |
13 | /// | |
9fa01778 | 14 | /// Purpose: avoid mixing indexes for different bitvector domains. |
a2a8927a | 15 | pub trait Idx: Copy + 'static + Eq + PartialEq + Debug + Hash { |
7cac9316 | 16 | fn new(idx: usize) -> Self; |
8faf50e0 | 17 | |
3157f602 | 18 | fn index(self) -> usize; |
8faf50e0 XL |
19 | |
20 | fn increment_by(&mut self, amount: usize) { | |
dc9dc135 XL |
21 | *self = self.plus(amount); |
22 | } | |
23 | ||
24 | fn plus(self, amount: usize) -> Self { | |
25 | Self::new(self.index() + amount) | |
8faf50e0 | 26 | } |
3157f602 XL |
27 | } |
28 | ||
29 | impl Idx for usize { | |
0531ce1d | 30 | #[inline] |
dfeec247 XL |
31 | fn new(idx: usize) -> Self { |
32 | idx | |
33 | } | |
0531ce1d | 34 | #[inline] |
dfeec247 XL |
35 | fn index(self) -> usize { |
36 | self | |
37 | } | |
3157f602 XL |
38 | } |
39 | ||
40 | impl Idx for u32 { | |
0531ce1d | 41 | #[inline] |
dfeec247 XL |
42 | fn new(idx: usize) -> Self { |
43 | assert!(idx <= u32::MAX as usize); | |
44 | idx as u32 | |
45 | } | |
0531ce1d | 46 | #[inline] |
dfeec247 XL |
47 | fn index(self) -> usize { |
48 | self as usize | |
49 | } | |
3157f602 XL |
50 | } |
51 | ||
0531ce1d | 52 | #[derive(Clone, PartialEq, Eq, Hash)] |
3157f602 XL |
53 | pub struct IndexVec<I: Idx, T> { |
54 | pub raw: Vec<T>, | |
dfeec247 | 55 | _marker: PhantomData<fn(&I)>, |
3157f602 XL |
56 | } |
57 | ||
ff7c6d11 XL |
58 | // Whether `IndexVec` is `Send` depends only on the data, |
59 | // not the phantom data. | |
60 | unsafe impl<I: Idx, T> Send for IndexVec<I, T> where T: Send {} | |
61 | ||
3dfed10e | 62 | impl<S: Encoder, I: Idx, T: Encodable<S>> Encodable<S> for IndexVec<I, T> { |
923072b8 FG |
63 | fn encode(&self, s: &mut S) { |
64 | Encodable::encode(&self.raw, s); | |
3dfed10e XL |
65 | } |
66 | } | |
67 | ||
68 | impl<D: Decoder, I: Idx, T: Decodable<D>> Decodable<D> for IndexVec<I, T> { | |
5099ac24 FG |
69 | fn decode(d: &mut D) -> Self { |
70 | IndexVec { raw: Decodable::decode(d), _marker: PhantomData } | |
3157f602 XL |
71 | } |
72 | } | |
73 | ||
74 | impl<I: Idx, T: fmt::Debug> fmt::Debug for IndexVec<I, T> { | |
9fa01778 | 75 | fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { |
3157f602 XL |
76 | fmt::Debug::fmt(&self.raw, fmt) |
77 | } | |
78 | } | |
79 | ||
3157f602 XL |
80 | impl<I: Idx, T> IndexVec<I, T> { |
81 | #[inline] | |
82 | pub fn new() -> Self { | |
83 | IndexVec { raw: Vec::new(), _marker: PhantomData } | |
84 | } | |
85 | ||
86 | #[inline] | |
94b46f34 XL |
87 | pub fn from_raw(raw: Vec<T>) -> Self { |
88 | IndexVec { raw, _marker: PhantomData } | |
89 | } | |
90 | ||
91 | #[inline] | |
3157f602 XL |
92 | pub fn with_capacity(capacity: usize) -> Self { |
93 | IndexVec { raw: Vec::with_capacity(capacity), _marker: PhantomData } | |
94 | } | |
95 | ||
96 | #[inline] | |
97 | pub fn from_elem<S>(elem: T, universe: &IndexVec<I, S>) -> Self | |
dfeec247 XL |
98 | where |
99 | T: Clone, | |
3157f602 XL |
100 | { |
101 | IndexVec { raw: vec![elem; universe.len()], _marker: PhantomData } | |
102 | } | |
103 | ||
104 | #[inline] | |
105 | pub fn from_elem_n(elem: T, n: usize) -> Self | |
dfeec247 XL |
106 | where |
107 | T: Clone, | |
3157f602 XL |
108 | { |
109 | IndexVec { raw: vec![elem; n], _marker: PhantomData } | |
110 | } | |
111 | ||
74b04a01 | 112 | /// Create an `IndexVec` with `n` elements, where the value of each |
f035d41b XL |
113 | /// element is the result of `func(i)`. (The underlying vector will |
114 | /// be allocated only once, with a capacity of at least `n`.) | |
74b04a01 XL |
115 | #[inline] |
116 | pub fn from_fn_n(func: impl FnMut(I) -> T, n: usize) -> Self { | |
117 | let indices = (0..n).map(I::new); | |
118 | Self::from_raw(indices.map(func).collect()) | |
119 | } | |
120 | ||
3157f602 XL |
121 | #[inline] |
122 | pub fn push(&mut self, d: T) -> I { | |
123 | let idx = I::new(self.len()); | |
124 | self.raw.push(d); | |
125 | idx | |
126 | } | |
127 | ||
abe05a73 XL |
128 | #[inline] |
129 | pub fn pop(&mut self) -> Option<T> { | |
130 | self.raw.pop() | |
131 | } | |
132 | ||
3157f602 XL |
133 | #[inline] |
134 | pub fn len(&self) -> usize { | |
135 | self.raw.len() | |
136 | } | |
137 | ||
0bf4aa26 XL |
138 | /// Gives the next index that will be assigned when `push` is |
139 | /// called. | |
140 | #[inline] | |
141 | pub fn next_index(&self) -> I { | |
142 | I::new(self.len()) | |
143 | } | |
144 | ||
3157f602 XL |
145 | #[inline] |
146 | pub fn is_empty(&self) -> bool { | |
147 | self.raw.is_empty() | |
148 | } | |
149 | ||
150 | #[inline] | |
151 | pub fn into_iter(self) -> vec::IntoIter<T> { | |
152 | self.raw.into_iter() | |
153 | } | |
154 | ||
155 | #[inline] | |
c295e0f8 XL |
156 | pub fn into_iter_enumerated( |
157 | self, | |
158 | ) -> impl DoubleEndedIterator<Item = (I, T)> + ExactSizeIterator { | |
159 | self.raw.into_iter().enumerate().map(|(n, t)| (I::new(n), t)) | |
3157f602 XL |
160 | } |
161 | ||
162 | #[inline] | |
9fa01778 | 163 | pub fn iter(&self) -> slice::Iter<'_, T> { |
3157f602 XL |
164 | self.raw.iter() |
165 | } | |
166 | ||
167 | #[inline] | |
c295e0f8 XL |
168 | pub fn iter_enumerated( |
169 | &self, | |
170 | ) -> impl DoubleEndedIterator<Item = (I, &T)> + ExactSizeIterator + '_ { | |
171 | self.raw.iter().enumerate().map(|(n, t)| (I::new(n), t)) | |
3157f602 XL |
172 | } |
173 | ||
174 | #[inline] | |
c295e0f8 XL |
175 | pub fn indices(&self) -> impl DoubleEndedIterator<Item = I> + ExactSizeIterator + 'static { |
176 | (0..self.len()).map(|n| I::new(n)) | |
3157f602 XL |
177 | } |
178 | ||
179 | #[inline] | |
9fa01778 | 180 | pub fn iter_mut(&mut self) -> slice::IterMut<'_, T> { |
3157f602 XL |
181 | self.raw.iter_mut() |
182 | } | |
183 | ||
184 | #[inline] | |
c295e0f8 XL |
185 | pub fn iter_enumerated_mut( |
186 | &mut self, | |
187 | ) -> impl DoubleEndedIterator<Item = (I, &mut T)> + ExactSizeIterator + '_ { | |
188 | self.raw.iter_mut().enumerate().map(|(n, t)| (I::new(n), t)) | |
3157f602 XL |
189 | } |
190 | ||
8bb4bdeb | 191 | #[inline] |
3c0e092e XL |
192 | pub fn drain<'a, R: RangeBounds<usize>>( |
193 | &'a mut self, | |
194 | range: R, | |
195 | ) -> impl Iterator<Item = T> + 'a { | |
8bb4bdeb XL |
196 | self.raw.drain(range) |
197 | } | |
198 | ||
199 | #[inline] | |
3c0e092e XL |
200 | pub fn drain_enumerated<'a, R: RangeBounds<usize>>( |
201 | &'a mut self, | |
dfeec247 | 202 | range: R, |
3c0e092e | 203 | ) -> impl Iterator<Item = (I, T)> + 'a { |
c295e0f8 | 204 | self.raw.drain(range).enumerate().map(|(n, t)| (I::new(n), t)) |
8bb4bdeb XL |
205 | } |
206 | ||
3157f602 XL |
207 | #[inline] |
208 | pub fn last(&self) -> Option<I> { | |
209 | self.len().checked_sub(1).map(I::new) | |
210 | } | |
c30ab7b3 SL |
211 | |
212 | #[inline] | |
213 | pub fn shrink_to_fit(&mut self) { | |
214 | self.raw.shrink_to_fit() | |
215 | } | |
216 | ||
217 | #[inline] | |
8faf50e0 XL |
218 | pub fn swap(&mut self, a: I, b: I) { |
219 | self.raw.swap(a.index(), b.index()) | |
c30ab7b3 SL |
220 | } |
221 | ||
222 | #[inline] | |
223 | pub fn truncate(&mut self, a: usize) { | |
224 | self.raw.truncate(a) | |
225 | } | |
8bb4bdeb XL |
226 | |
227 | #[inline] | |
228 | pub fn get(&self, index: I) -> Option<&T> { | |
229 | self.raw.get(index.index()) | |
230 | } | |
231 | ||
232 | #[inline] | |
233 | pub fn get_mut(&mut self, index: I) -> Option<&mut T> { | |
234 | self.raw.get_mut(index.index()) | |
235 | } | |
0531ce1d | 236 | |
9fa01778 | 237 | /// Returns mutable references to two distinct elements, a and b. Panics if a == b. |
0531ce1d XL |
238 | #[inline] |
239 | pub fn pick2_mut(&mut self, a: I, b: I) -> (&mut T, &mut T) { | |
240 | let (ai, bi) = (a.index(), b.index()); | |
241 | assert!(ai != bi); | |
242 | ||
243 | if ai < bi { | |
244 | let (c1, c2) = self.raw.split_at_mut(bi); | |
245 | (&mut c1[ai], &mut c2[0]) | |
246 | } else { | |
247 | let (c2, c1) = self.pick2_mut(b, a); | |
248 | (c1, c2) | |
249 | } | |
250 | } | |
251 | ||
3dfed10e XL |
252 | /// Returns mutable references to three distinct elements or panics otherwise. |
253 | #[inline] | |
254 | pub fn pick3_mut(&mut self, a: I, b: I, c: I) -> (&mut T, &mut T, &mut T) { | |
255 | let (ai, bi, ci) = (a.index(), b.index(), c.index()); | |
256 | assert!(ai != bi && bi != ci && ci != ai); | |
257 | let len = self.raw.len(); | |
258 | assert!(ai < len && bi < len && ci < len); | |
259 | let ptr = self.raw.as_mut_ptr(); | |
260 | unsafe { (&mut *ptr.add(ai), &mut *ptr.add(bi), &mut *ptr.add(ci)) } | |
261 | } | |
262 | ||
0531ce1d | 263 | pub fn convert_index_type<Ix: Idx>(self) -> IndexVec<Ix, T> { |
dfeec247 | 264 | IndexVec { raw: self.raw, _marker: PhantomData } |
0531ce1d | 265 | } |
3157f602 | 266 | |
8faf50e0 XL |
267 | /// Grows the index vector so that it contains an entry for |
268 | /// `elem`; if that is already true, then has no | |
269 | /// effect. Otherwise, inserts new values as needed by invoking | |
270 | /// `fill_value`. | |
271 | #[inline] | |
272 | pub fn ensure_contains_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) { | |
273 | let min_new_len = elem.index() + 1; | |
274 | if self.len() < min_new_len { | |
275 | self.raw.resize_with(min_new_len, fill_value); | |
276 | } | |
277 | } | |
278 | ||
8faf50e0 XL |
279 | #[inline] |
280 | pub fn resize_to_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) { | |
281 | let min_new_len = elem.index() + 1; | |
282 | self.raw.resize_with(min_new_len, fill_value); | |
283 | } | |
cc61c64b XL |
284 | } |
285 | ||
c295e0f8 XL |
286 | /// `IndexVec` is often used as a map, so it provides some map-like APIs. |
287 | impl<I: Idx, T> IndexVec<I, Option<T>> { | |
288 | #[inline] | |
289 | pub fn insert(&mut self, index: I, value: T) -> Option<T> { | |
290 | self.ensure_contains_elem(index, || None); | |
291 | self[index].replace(value) | |
292 | } | |
293 | ||
294 | #[inline] | |
295 | pub fn get_or_insert_with(&mut self, index: I, value: impl FnOnce() -> T) -> &mut T { | |
296 | self.ensure_contains_elem(index, || None); | |
297 | self[index].get_or_insert_with(value) | |
298 | } | |
299 | ||
300 | #[inline] | |
301 | pub fn remove(&mut self, index: I) -> Option<T> { | |
302 | self.ensure_contains_elem(index, || None); | |
303 | self[index].take() | |
304 | } | |
305 | } | |
306 | ||
6a06907d XL |
307 | impl<I: Idx, T: Clone> IndexVec<I, T> { |
308 | #[inline] | |
309 | pub fn resize(&mut self, new_len: usize, value: T) { | |
310 | self.raw.resize(new_len, value) | |
311 | } | |
312 | } | |
313 | ||
3b2f2976 XL |
314 | impl<I: Idx, T: Ord> IndexVec<I, T> { |
315 | #[inline] | |
316 | pub fn binary_search(&self, value: &T) -> Result<I, I> { | |
317 | match self.raw.binary_search(value) { | |
318 | Ok(i) => Ok(Idx::new(i)), | |
319 | Err(i) => Err(Idx::new(i)), | |
320 | } | |
321 | } | |
322 | } | |
323 | ||
3157f602 XL |
324 | impl<I: Idx, T> Index<I> for IndexVec<I, T> { |
325 | type Output = T; | |
326 | ||
327 | #[inline] | |
328 | fn index(&self, index: I) -> &T { | |
329 | &self.raw[index.index()] | |
330 | } | |
331 | } | |
332 | ||
333 | impl<I: Idx, T> IndexMut<I> for IndexVec<I, T> { | |
334 | #[inline] | |
335 | fn index_mut(&mut self, index: I) -> &mut T { | |
336 | &mut self.raw[index.index()] | |
337 | } | |
338 | } | |
339 | ||
7cac9316 XL |
340 | impl<I: Idx, T> Default for IndexVec<I, T> { |
341 | #[inline] | |
342 | fn default() -> Self { | |
343 | Self::new() | |
344 | } | |
345 | } | |
346 | ||
3157f602 XL |
347 | impl<I: Idx, T> Extend<T> for IndexVec<I, T> { |
348 | #[inline] | |
349 | fn extend<J: IntoIterator<Item = T>>(&mut self, iter: J) { | |
350 | self.raw.extend(iter); | |
351 | } | |
f9f354fc XL |
352 | |
353 | #[inline] | |
354 | fn extend_one(&mut self, item: T) { | |
355 | self.raw.push(item); | |
356 | } | |
357 | ||
358 | #[inline] | |
359 | fn extend_reserve(&mut self, additional: usize) { | |
360 | self.raw.reserve(additional); | |
361 | } | |
3157f602 XL |
362 | } |
363 | ||
364 | impl<I: Idx, T> FromIterator<T> for IndexVec<I, T> { | |
365 | #[inline] | |
dfeec247 XL |
366 | fn from_iter<J>(iter: J) -> Self |
367 | where | |
368 | J: IntoIterator<Item = T>, | |
369 | { | |
3157f602 XL |
370 | IndexVec { raw: FromIterator::from_iter(iter), _marker: PhantomData } |
371 | } | |
372 | } | |
373 | ||
374 | impl<I: Idx, T> IntoIterator for IndexVec<I, T> { | |
375 | type Item = T; | |
376 | type IntoIter = vec::IntoIter<T>; | |
377 | ||
378 | #[inline] | |
379 | fn into_iter(self) -> vec::IntoIter<T> { | |
380 | self.raw.into_iter() | |
381 | } | |
3157f602 XL |
382 | } |
383 | ||
384 | impl<'a, I: Idx, T> IntoIterator for &'a IndexVec<I, T> { | |
385 | type Item = &'a T; | |
386 | type IntoIter = slice::Iter<'a, T>; | |
387 | ||
388 | #[inline] | |
389 | fn into_iter(self) -> slice::Iter<'a, T> { | |
390 | self.raw.iter() | |
391 | } | |
392 | } | |
393 | ||
394 | impl<'a, I: Idx, T> IntoIterator for &'a mut IndexVec<I, T> { | |
395 | type Item = &'a mut T; | |
396 | type IntoIter = slice::IterMut<'a, T>; | |
397 | ||
398 | #[inline] | |
3b2f2976 | 399 | fn into_iter(self) -> slice::IterMut<'a, T> { |
3157f602 XL |
400 | self.raw.iter_mut() |
401 | } | |
402 | } | |
403 | ||
dfeec247 XL |
404 | #[cfg(test)] |
405 | mod tests; |