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