]>
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; |
3157f602 | 6 | use std::iter::{self, FromIterator}; |
3157f602 | 7 | use std::marker::PhantomData; |
0531ce1d | 8 | use std::ops::{Index, IndexMut, Range, 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. |
8faf50e0 | 15 | pub trait Idx: Copy + 'static + Ord + 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 | ||
b7449926 XL |
52 | /// Creates a struct type `S` that can be used as an index with |
53 | /// `IndexVec` and so on. | |
54 | /// | |
55 | /// There are two ways of interacting with these indices: | |
56 | /// | |
57 | /// - The `From` impls are the preferred way. So you can do | |
58 | /// `S::from(v)` with a `usize` or `u32`. And you can convert back | |
59 | /// to an integer with `u32::from(s)`. | |
60 | /// | |
61 | /// - Alternatively, you can use the methods `S::new(v)` and `s.index()` | |
62 | /// to create/return a value. | |
63 | /// | |
64 | /// Internally, the index uses a u32, so the index must not exceed | |
65 | /// `u32::MAX`. You can also customize things like the `Debug` impl, | |
66 | /// what traits are derived, and so forth via the macro. | |
ea8adc8c | 67 | #[macro_export] |
f9f354fc | 68 | #[allow_internal_unstable(step_trait, step_trait_ext, rustc_attrs)] |
ea8adc8c | 69 | macro_rules! newtype_index { |
abe05a73 XL |
70 | // ---- public rules ---- |
71 | ||
72 | // Use default constants | |
532ac7d7 | 73 | ($(#[$attrs:meta])* $v:vis struct $name:ident { .. }) => ( |
416331ca | 74 | $crate::newtype_index!( |
abe05a73 | 75 | // Leave out derives marker so we can use its absence to ensure it comes first |
532ac7d7 | 76 | @attrs [$(#[$attrs])*] |
abe05a73 | 77 | @type [$name] |
b7449926 XL |
78 | // shave off 256 indices at the end to allow space for packing these indices into enums |
79 | @max [0xFFFF_FF00] | |
80 | @vis [$v] | |
abe05a73 | 81 | @debug_format ["{}"]); |
ea8adc8c XL |
82 | ); |
83 | ||
abe05a73 | 84 | // Define any constants |
532ac7d7 | 85 | ($(#[$attrs:meta])* $v:vis struct $name:ident { $($tokens:tt)+ }) => ( |
416331ca | 86 | $crate::newtype_index!( |
abe05a73 | 87 | // Leave out derives marker so we can use its absence to ensure it comes first |
532ac7d7 | 88 | @attrs [$(#[$attrs])*] |
abe05a73 | 89 | @type [$name] |
b7449926 XL |
90 | // shave off 256 indices at the end to allow space for packing these indices into enums |
91 | @max [0xFFFF_FF00] | |
92 | @vis [$v] | |
abe05a73 XL |
93 | @debug_format ["{}"] |
94 | $($tokens)+); | |
95 | ); | |
ea8adc8c | 96 | |
abe05a73 XL |
97 | // ---- private rules ---- |
98 | ||
99 | // Base case, user-defined constants (if any) have already been defined | |
100 | (@derives [$($derives:ident,)*] | |
532ac7d7 | 101 | @attrs [$(#[$attrs:meta])*] |
abe05a73 XL |
102 | @type [$type:ident] |
103 | @max [$max:expr] | |
b7449926 | 104 | @vis [$v:vis] |
abe05a73 | 105 | @debug_format [$debug_format:tt]) => ( |
532ac7d7 | 106 | $(#[$attrs])* |
0731742a | 107 | #[derive(Copy, PartialEq, Eq, Hash, PartialOrd, Ord, $($derives),*)] |
b7449926 XL |
108 | #[rustc_layout_scalar_valid_range_end($max)] |
109 | $v struct $type { | |
110 | private: u32 | |
111 | } | |
112 | ||
0731742a | 113 | impl Clone for $type { |
6a06907d | 114 | #[inline] |
0731742a XL |
115 | fn clone(&self) -> Self { |
116 | *self | |
117 | } | |
118 | } | |
119 | ||
b7449926 XL |
120 | impl $type { |
121 | $v const MAX_AS_U32: u32 = $max; | |
122 | ||
ba9703b0 | 123 | $v const MAX: Self = Self::from_u32($max); |
b7449926 XL |
124 | |
125 | #[inline] | |
ba9703b0 | 126 | $v const fn from_usize(value: usize) -> Self { |
b7449926 XL |
127 | assert!(value <= ($max as usize)); |
128 | unsafe { | |
dfeec247 | 129 | Self::from_u32_unchecked(value as u32) |
b7449926 XL |
130 | } |
131 | } | |
132 | ||
133 | #[inline] | |
ba9703b0 | 134 | $v const fn from_u32(value: u32) -> Self { |
b7449926 XL |
135 | assert!(value <= $max); |
136 | unsafe { | |
dfeec247 | 137 | Self::from_u32_unchecked(value) |
b7449926 XL |
138 | } |
139 | } | |
140 | ||
b7449926 XL |
141 | #[inline] |
142 | $v const unsafe fn from_u32_unchecked(value: u32) -> Self { | |
dfeec247 | 143 | Self { private: value } |
b7449926 XL |
144 | } |
145 | ||
9fa01778 | 146 | /// Extracts the value of this index as an integer. |
b7449926 | 147 | #[inline] |
ba9703b0 | 148 | $v const fn index(self) -> usize { |
b7449926 XL |
149 | self.as_usize() |
150 | } | |
151 | ||
9fa01778 | 152 | /// Extracts the value of this index as a `u32`. |
b7449926 | 153 | #[inline] |
ba9703b0 | 154 | $v const fn as_u32(self) -> u32 { |
b7449926 XL |
155 | self.private |
156 | } | |
157 | ||
9fa01778 | 158 | /// Extracts the value of this index as a `usize`. |
b7449926 | 159 | #[inline] |
ba9703b0 | 160 | $v const fn as_usize(self) -> usize { |
b7449926 XL |
161 | self.as_u32() as usize |
162 | } | |
163 | } | |
ea8adc8c | 164 | |
dc9dc135 XL |
165 | impl std::ops::Add<usize> for $type { |
166 | type Output = Self; | |
167 | ||
168 | fn add(self, other: usize) -> Self { | |
dfeec247 | 169 | Self::from_usize(self.index() + other) |
dc9dc135 XL |
170 | } |
171 | } | |
172 | ||
dfeec247 | 173 | impl $crate::vec::Idx for $type { |
0531ce1d | 174 | #[inline] |
ea8adc8c | 175 | fn new(value: usize) -> Self { |
dfeec247 | 176 | Self::from_usize(value) |
ea8adc8c | 177 | } |
abe05a73 | 178 | |
0531ce1d | 179 | #[inline] |
ea8adc8c | 180 | fn index(self) -> usize { |
ba9703b0 | 181 | self.as_usize() |
ea8adc8c XL |
182 | } |
183 | } | |
184 | ||
f9f354fc | 185 | unsafe impl ::std::iter::Step for $type { |
b7449926 | 186 | #[inline] |
8faf50e0 XL |
187 | fn steps_between(start: &Self, end: &Self) -> Option<usize> { |
188 | <usize as ::std::iter::Step>::steps_between( | |
dfeec247 XL |
189 | &Self::index(*start), |
190 | &Self::index(*end), | |
8faf50e0 XL |
191 | ) |
192 | } | |
193 | ||
b7449926 | 194 | #[inline] |
f9f354fc XL |
195 | fn forward_checked(start: Self, u: usize) -> Option<Self> { |
196 | Self::index(start).checked_add(u).map(Self::from_usize) | |
8faf50e0 XL |
197 | } |
198 | ||
b7449926 | 199 | #[inline] |
f9f354fc XL |
200 | fn backward_checked(start: Self, u: usize) -> Option<Self> { |
201 | Self::index(start).checked_sub(u).map(Self::from_usize) | |
dc9dc135 | 202 | } |
8faf50e0 XL |
203 | } |
204 | ||
b7449926 XL |
205 | impl From<$type> for u32 { |
206 | #[inline] | |
207 | fn from(v: $type) -> u32 { | |
208 | v.as_u32() | |
209 | } | |
210 | } | |
211 | ||
212 | impl From<$type> for usize { | |
213 | #[inline] | |
214 | fn from(v: $type) -> usize { | |
215 | v.as_usize() | |
216 | } | |
217 | } | |
218 | ||
219 | impl From<usize> for $type { | |
220 | #[inline] | |
221 | fn from(value: usize) -> Self { | |
dfeec247 | 222 | Self::from_usize(value) |
b7449926 XL |
223 | } |
224 | } | |
225 | ||
226 | impl From<u32> for $type { | |
227 | #[inline] | |
228 | fn from(value: u32) -> Self { | |
dfeec247 | 229 | Self::from_u32(value) |
b7449926 XL |
230 | } |
231 | } | |
232 | ||
416331ca | 233 | $crate::newtype_index!( |
abe05a73 XL |
234 | @handle_debug |
235 | @derives [$($derives,)*] | |
236 | @type [$type] | |
237 | @debug_format [$debug_format]); | |
238 | ); | |
239 | ||
240 | // base case for handle_debug where format is custom. No Debug implementation is emitted. | |
241 | (@handle_debug | |
242 | @derives [$($_derives:ident,)*] | |
243 | @type [$type:ident] | |
244 | @debug_format [custom]) => (); | |
245 | ||
246 | // base case for handle_debug, no debug overrides found, so use default | |
247 | (@handle_debug | |
248 | @derives [] | |
249 | @type [$type:ident] | |
250 | @debug_format [$debug_format:tt]) => ( | |
251 | impl ::std::fmt::Debug for $type { | |
9fa01778 | 252 | fn fmt(&self, fmt: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result { |
b7449926 | 253 | write!(fmt, $debug_format, self.as_u32()) |
ea8adc8c XL |
254 | } |
255 | } | |
abe05a73 XL |
256 | ); |
257 | ||
258 | // Debug is requested for derive, don't generate any Debug implementation. | |
259 | (@handle_debug | |
260 | @derives [Debug, $($derives:ident,)*] | |
261 | @type [$type:ident] | |
262 | @debug_format [$debug_format:tt]) => (); | |
263 | ||
264 | // It's not Debug, so just pop it off the front of the derives stack and check the rest. | |
265 | (@handle_debug | |
266 | @derives [$_derive:ident, $($derives:ident,)*] | |
267 | @type [$type:ident] | |
268 | @debug_format [$debug_format:tt]) => ( | |
416331ca | 269 | $crate::newtype_index!( |
abe05a73 XL |
270 | @handle_debug |
271 | @derives [$($derives,)*] | |
272 | @type [$type] | |
273 | @debug_format [$debug_format]); | |
274 | ); | |
275 | ||
abe05a73 | 276 | // Append comma to end of derives list if it's missing |
532ac7d7 XL |
277 | (@attrs [$(#[$attrs:meta])*] |
278 | @type [$type:ident] | |
abe05a73 | 279 | @max [$max:expr] |
b7449926 | 280 | @vis [$v:vis] |
abe05a73 XL |
281 | @debug_format [$debug_format:tt] |
282 | derive [$($derives:ident),*] | |
283 | $($tokens:tt)*) => ( | |
416331ca | 284 | $crate::newtype_index!( |
532ac7d7 | 285 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
286 | @type [$type] |
287 | @max [$max] | |
b7449926 | 288 | @vis [$v] |
abe05a73 XL |
289 | @debug_format [$debug_format] |
290 | derive [$($derives,)*] | |
291 | $($tokens)*); | |
292 | ); | |
293 | ||
294 | // By not including the @derives marker in this list nor in the default args, we can force it | |
295 | // to come first if it exists. When encodable is custom, just use the derives list as-is. | |
532ac7d7 XL |
296 | (@attrs [$(#[$attrs:meta])*] |
297 | @type [$type:ident] | |
abe05a73 | 298 | @max [$max:expr] |
b7449926 | 299 | @vis [$v:vis] |
abe05a73 XL |
300 | @debug_format [$debug_format:tt] |
301 | derive [$($derives:ident,)+] | |
302 | ENCODABLE = custom | |
303 | $($tokens:tt)*) => ( | |
416331ca | 304 | $crate::newtype_index!( |
532ac7d7 | 305 | @attrs [$(#[$attrs])*] |
abe05a73 | 306 | @derives [$($derives,)+] |
abe05a73 XL |
307 | @type [$type] |
308 | @max [$max] | |
b7449926 | 309 | @vis [$v] |
abe05a73 XL |
310 | @debug_format [$debug_format] |
311 | $($tokens)*); | |
312 | ); | |
313 | ||
314 | // By not including the @derives marker in this list nor in the default args, we can force it | |
315 | // to come first if it exists. When encodable isn't custom, add serialization traits by default. | |
532ac7d7 XL |
316 | (@attrs [$(#[$attrs:meta])*] |
317 | @type [$type:ident] | |
abe05a73 | 318 | @max [$max:expr] |
b7449926 | 319 | @vis [$v:vis] |
abe05a73 XL |
320 | @debug_format [$debug_format:tt] |
321 | derive [$($derives:ident,)+] | |
322 | $($tokens:tt)*) => ( | |
416331ca | 323 | $crate::newtype_index!( |
3dfed10e | 324 | @derives [$($derives,)+] |
532ac7d7 | 325 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
326 | @type [$type] |
327 | @max [$max] | |
b7449926 | 328 | @vis [$v] |
abe05a73 XL |
329 | @debug_format [$debug_format] |
330 | $($tokens)*); | |
3dfed10e | 331 | $crate::newtype_index!(@serializable $type); |
abe05a73 XL |
332 | ); |
333 | ||
0531ce1d | 334 | // The case where no derives are added, but encodable is overridden. Don't |
abe05a73 | 335 | // derive serialization traits |
532ac7d7 XL |
336 | (@attrs [$(#[$attrs:meta])*] |
337 | @type [$type:ident] | |
abe05a73 | 338 | @max [$max:expr] |
b7449926 | 339 | @vis [$v:vis] |
abe05a73 XL |
340 | @debug_format [$debug_format:tt] |
341 | ENCODABLE = custom | |
342 | $($tokens:tt)*) => ( | |
416331ca | 343 | $crate::newtype_index!( |
abe05a73 | 344 | @derives [] |
532ac7d7 | 345 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
346 | @type [$type] |
347 | @max [$max] | |
b7449926 | 348 | @vis [$v] |
abe05a73 XL |
349 | @debug_format [$debug_format] |
350 | $($tokens)*); | |
351 | ); | |
352 | ||
353 | // The case where no derives are added, add serialization derives by default | |
532ac7d7 XL |
354 | (@attrs [$(#[$attrs:meta])*] |
355 | @type [$type:ident] | |
abe05a73 | 356 | @max [$max:expr] |
b7449926 | 357 | @vis [$v:vis] |
abe05a73 XL |
358 | @debug_format [$debug_format:tt] |
359 | $($tokens:tt)*) => ( | |
416331ca | 360 | $crate::newtype_index!( |
3dfed10e | 361 | @derives [] |
532ac7d7 | 362 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
363 | @type [$type] |
364 | @max [$max] | |
b7449926 | 365 | @vis [$v] |
abe05a73 XL |
366 | @debug_format [$debug_format] |
367 | $($tokens)*); | |
3dfed10e | 368 | $crate::newtype_index!(@serializable $type); |
0731742a XL |
369 | ); |
370 | ||
3dfed10e XL |
371 | (@serializable $type:ident) => ( |
372 | impl<D: ::rustc_serialize::Decoder> ::rustc_serialize::Decodable<D> for $type { | |
373 | fn decode(d: &mut D) -> Result<Self, D::Error> { | |
dfeec247 | 374 | d.read_u32().map(Self::from_u32) |
0731742a XL |
375 | } |
376 | } | |
3dfed10e XL |
377 | impl<E: ::rustc_serialize::Encoder> ::rustc_serialize::Encodable<E> for $type { |
378 | fn encode(&self, e: &mut E) -> Result<(), E::Error> { | |
379 | e.emit_u32(self.private) | |
380 | } | |
381 | } | |
abe05a73 XL |
382 | ); |
383 | ||
384 | // Rewrite final without comma to one that includes comma | |
385 | (@derives [$($derives:ident,)*] | |
532ac7d7 | 386 | @attrs [$(#[$attrs:meta])*] |
abe05a73 XL |
387 | @type [$type:ident] |
388 | @max [$max:expr] | |
b7449926 | 389 | @vis [$v:vis] |
abe05a73 XL |
390 | @debug_format [$debug_format:tt] |
391 | $name:ident = $constant:expr) => ( | |
416331ca | 392 | $crate::newtype_index!( |
abe05a73 | 393 | @derives [$($derives,)*] |
532ac7d7 | 394 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
395 | @type [$type] |
396 | @max [$max] | |
b7449926 | 397 | @vis [$v] |
abe05a73 XL |
398 | @debug_format [$debug_format] |
399 | $name = $constant,); | |
400 | ); | |
401 | ||
402 | // Rewrite final const without comma to one that includes comma | |
403 | (@derives [$($derives:ident,)*] | |
532ac7d7 | 404 | @attrs [$(#[$attrs:meta])*] |
abe05a73 | 405 | @type [$type:ident] |
dc9dc135 | 406 | @max [$max:expr] |
b7449926 | 407 | @vis [$v:vis] |
abe05a73 XL |
408 | @debug_format [$debug_format:tt] |
409 | $(#[doc = $doc:expr])* | |
410 | const $name:ident = $constant:expr) => ( | |
416331ca | 411 | $crate::newtype_index!( |
abe05a73 | 412 | @derives [$($derives,)*] |
532ac7d7 | 413 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
414 | @type [$type] |
415 | @max [$max] | |
b7449926 | 416 | @vis [$v] |
abe05a73 XL |
417 | @debug_format [$debug_format] |
418 | $(#[doc = $doc])* const $name = $constant,); | |
419 | ); | |
420 | ||
421 | // Replace existing default for max | |
422 | (@derives [$($derives:ident,)*] | |
532ac7d7 | 423 | @attrs [$(#[$attrs:meta])*] |
abe05a73 XL |
424 | @type [$type:ident] |
425 | @max [$_max:expr] | |
b7449926 | 426 | @vis [$v:vis] |
abe05a73 XL |
427 | @debug_format [$debug_format:tt] |
428 | MAX = $max:expr, | |
429 | $($tokens:tt)*) => ( | |
416331ca | 430 | $crate::newtype_index!( |
abe05a73 | 431 | @derives [$($derives,)*] |
532ac7d7 | 432 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
433 | @type [$type] |
434 | @max [$max] | |
b7449926 | 435 | @vis [$v] |
abe05a73 XL |
436 | @debug_format [$debug_format] |
437 | $($tokens)*); | |
438 | ); | |
439 | ||
440 | // Replace existing default for debug_format | |
441 | (@derives [$($derives:ident,)*] | |
532ac7d7 | 442 | @attrs [$(#[$attrs:meta])*] |
abe05a73 XL |
443 | @type [$type:ident] |
444 | @max [$max:expr] | |
b7449926 | 445 | @vis [$v:vis] |
abe05a73 XL |
446 | @debug_format [$_debug_format:tt] |
447 | DEBUG_FORMAT = $debug_format:tt, | |
448 | $($tokens:tt)*) => ( | |
416331ca | 449 | $crate::newtype_index!( |
abe05a73 | 450 | @derives [$($derives,)*] |
532ac7d7 | 451 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
452 | @type [$type] |
453 | @max [$max] | |
b7449926 | 454 | @vis [$v] |
abe05a73 XL |
455 | @debug_format [$debug_format] |
456 | $($tokens)*); | |
457 | ); | |
458 | ||
459 | // Assign a user-defined constant | |
460 | (@derives [$($derives:ident,)*] | |
532ac7d7 | 461 | @attrs [$(#[$attrs:meta])*] |
abe05a73 XL |
462 | @type [$type:ident] |
463 | @max [$max:expr] | |
b7449926 | 464 | @vis [$v:vis] |
abe05a73 XL |
465 | @debug_format [$debug_format:tt] |
466 | $(#[doc = $doc:expr])* | |
467 | const $name:ident = $constant:expr, | |
468 | $($tokens:tt)*) => ( | |
469 | $(#[doc = $doc])* | |
ba9703b0 | 470 | $v const $name: $type = $type::from_u32($constant); |
416331ca | 471 | $crate::newtype_index!( |
abe05a73 | 472 | @derives [$($derives,)*] |
532ac7d7 | 473 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
474 | @type [$type] |
475 | @max [$max] | |
b7449926 | 476 | @vis [$v] |
abe05a73 XL |
477 | @debug_format [$debug_format] |
478 | $($tokens)*); | |
479 | ); | |
ea8adc8c XL |
480 | } |
481 | ||
0531ce1d | 482 | #[derive(Clone, PartialEq, Eq, Hash)] |
3157f602 XL |
483 | pub struct IndexVec<I: Idx, T> { |
484 | pub raw: Vec<T>, | |
dfeec247 | 485 | _marker: PhantomData<fn(&I)>, |
3157f602 XL |
486 | } |
487 | ||
ff7c6d11 XL |
488 | // Whether `IndexVec` is `Send` depends only on the data, |
489 | // not the phantom data. | |
490 | unsafe impl<I: Idx, T> Send for IndexVec<I, T> where T: Send {} | |
491 | ||
3dfed10e XL |
492 | impl<S: Encoder, I: Idx, T: Encodable<S>> Encodable<S> for IndexVec<I, T> { |
493 | fn encode(&self, s: &mut S) -> Result<(), S::Error> { | |
416331ca | 494 | Encodable::encode(&self.raw, s) |
3157f602 XL |
495 | } |
496 | } | |
497 | ||
3dfed10e XL |
498 | impl<S: Encoder, I: Idx, T: Encodable<S>> Encodable<S> for &IndexVec<I, T> { |
499 | fn encode(&self, s: &mut S) -> Result<(), S::Error> { | |
500 | Encodable::encode(&self.raw, s) | |
501 | } | |
502 | } | |
503 | ||
504 | impl<D: Decoder, I: Idx, T: Decodable<D>> Decodable<D> for IndexVec<I, T> { | |
505 | fn decode(d: &mut D) -> Result<Self, D::Error> { | |
dfeec247 | 506 | Decodable::decode(d).map(|v| IndexVec { raw: v, _marker: PhantomData }) |
3157f602 XL |
507 | } |
508 | } | |
509 | ||
510 | impl<I: Idx, T: fmt::Debug> fmt::Debug for IndexVec<I, T> { | |
9fa01778 | 511 | fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { |
3157f602 XL |
512 | fmt::Debug::fmt(&self.raw, fmt) |
513 | } | |
514 | } | |
515 | ||
516 | pub type Enumerated<I, J> = iter::Map<iter::Enumerate<J>, IntoIdx<I>>; | |
517 | ||
518 | impl<I: Idx, T> IndexVec<I, T> { | |
519 | #[inline] | |
520 | pub fn new() -> Self { | |
521 | IndexVec { raw: Vec::new(), _marker: PhantomData } | |
522 | } | |
523 | ||
524 | #[inline] | |
94b46f34 XL |
525 | pub fn from_raw(raw: Vec<T>) -> Self { |
526 | IndexVec { raw, _marker: PhantomData } | |
527 | } | |
528 | ||
529 | #[inline] | |
3157f602 XL |
530 | pub fn with_capacity(capacity: usize) -> Self { |
531 | IndexVec { raw: Vec::with_capacity(capacity), _marker: PhantomData } | |
532 | } | |
533 | ||
534 | #[inline] | |
535 | pub fn from_elem<S>(elem: T, universe: &IndexVec<I, S>) -> Self | |
dfeec247 XL |
536 | where |
537 | T: Clone, | |
3157f602 XL |
538 | { |
539 | IndexVec { raw: vec![elem; universe.len()], _marker: PhantomData } | |
540 | } | |
541 | ||
542 | #[inline] | |
543 | pub fn from_elem_n(elem: T, n: usize) -> Self | |
dfeec247 XL |
544 | where |
545 | T: Clone, | |
3157f602 XL |
546 | { |
547 | IndexVec { raw: vec![elem; n], _marker: PhantomData } | |
548 | } | |
549 | ||
74b04a01 | 550 | /// Create an `IndexVec` with `n` elements, where the value of each |
f035d41b XL |
551 | /// element is the result of `func(i)`. (The underlying vector will |
552 | /// be allocated only once, with a capacity of at least `n`.) | |
74b04a01 XL |
553 | #[inline] |
554 | pub fn from_fn_n(func: impl FnMut(I) -> T, n: usize) -> Self { | |
555 | let indices = (0..n).map(I::new); | |
556 | Self::from_raw(indices.map(func).collect()) | |
557 | } | |
558 | ||
3157f602 XL |
559 | #[inline] |
560 | pub fn push(&mut self, d: T) -> I { | |
561 | let idx = I::new(self.len()); | |
562 | self.raw.push(d); | |
563 | idx | |
564 | } | |
565 | ||
abe05a73 XL |
566 | #[inline] |
567 | pub fn pop(&mut self) -> Option<T> { | |
568 | self.raw.pop() | |
569 | } | |
570 | ||
3157f602 XL |
571 | #[inline] |
572 | pub fn len(&self) -> usize { | |
573 | self.raw.len() | |
574 | } | |
575 | ||
0bf4aa26 XL |
576 | /// Gives the next index that will be assigned when `push` is |
577 | /// called. | |
578 | #[inline] | |
579 | pub fn next_index(&self) -> I { | |
580 | I::new(self.len()) | |
581 | } | |
582 | ||
3157f602 XL |
583 | #[inline] |
584 | pub fn is_empty(&self) -> bool { | |
585 | self.raw.is_empty() | |
586 | } | |
587 | ||
588 | #[inline] | |
589 | pub fn into_iter(self) -> vec::IntoIter<T> { | |
590 | self.raw.into_iter() | |
591 | } | |
592 | ||
593 | #[inline] | |
dfeec247 | 594 | pub fn into_iter_enumerated(self) -> Enumerated<I, vec::IntoIter<T>> { |
3157f602 XL |
595 | self.raw.into_iter().enumerate().map(IntoIdx { _marker: PhantomData }) |
596 | } | |
597 | ||
598 | #[inline] | |
9fa01778 | 599 | pub fn iter(&self) -> slice::Iter<'_, T> { |
3157f602 XL |
600 | self.raw.iter() |
601 | } | |
602 | ||
603 | #[inline] | |
dfeec247 | 604 | pub fn iter_enumerated(&self) -> Enumerated<I, slice::Iter<'_, T>> { |
3157f602 XL |
605 | self.raw.iter().enumerate().map(IntoIdx { _marker: PhantomData }) |
606 | } | |
607 | ||
608 | #[inline] | |
609 | pub fn indices(&self) -> iter::Map<Range<usize>, IntoIdx<I>> { | |
610 | (0..self.len()).map(IntoIdx { _marker: PhantomData }) | |
611 | } | |
612 | ||
613 | #[inline] | |
9fa01778 | 614 | pub fn iter_mut(&mut self) -> slice::IterMut<'_, T> { |
3157f602 XL |
615 | self.raw.iter_mut() |
616 | } | |
617 | ||
618 | #[inline] | |
dfeec247 | 619 | pub fn iter_enumerated_mut(&mut self) -> Enumerated<I, slice::IterMut<'_, T>> { |
3157f602 XL |
620 | self.raw.iter_mut().enumerate().map(IntoIdx { _marker: PhantomData }) |
621 | } | |
622 | ||
8bb4bdeb | 623 | #[inline] |
0531ce1d | 624 | pub fn drain<'a, R: RangeBounds<usize>>( |
dfeec247 XL |
625 | &'a mut self, |
626 | range: R, | |
627 | ) -> impl Iterator<Item = T> + 'a { | |
8bb4bdeb XL |
628 | self.raw.drain(range) |
629 | } | |
630 | ||
631 | #[inline] | |
0531ce1d | 632 | pub fn drain_enumerated<'a, R: RangeBounds<usize>>( |
dfeec247 XL |
633 | &'a mut self, |
634 | range: R, | |
635 | ) -> impl Iterator<Item = (I, T)> + 'a { | |
8bb4bdeb XL |
636 | self.raw.drain(range).enumerate().map(IntoIdx { _marker: PhantomData }) |
637 | } | |
638 | ||
3157f602 XL |
639 | #[inline] |
640 | pub fn last(&self) -> Option<I> { | |
641 | self.len().checked_sub(1).map(I::new) | |
642 | } | |
c30ab7b3 SL |
643 | |
644 | #[inline] | |
645 | pub fn shrink_to_fit(&mut self) { | |
646 | self.raw.shrink_to_fit() | |
647 | } | |
648 | ||
649 | #[inline] | |
8faf50e0 XL |
650 | pub fn swap(&mut self, a: I, b: I) { |
651 | self.raw.swap(a.index(), b.index()) | |
c30ab7b3 SL |
652 | } |
653 | ||
654 | #[inline] | |
655 | pub fn truncate(&mut self, a: usize) { | |
656 | self.raw.truncate(a) | |
657 | } | |
8bb4bdeb XL |
658 | |
659 | #[inline] | |
660 | pub fn get(&self, index: I) -> Option<&T> { | |
661 | self.raw.get(index.index()) | |
662 | } | |
663 | ||
664 | #[inline] | |
665 | pub fn get_mut(&mut self, index: I) -> Option<&mut T> { | |
666 | self.raw.get_mut(index.index()) | |
667 | } | |
0531ce1d | 668 | |
9fa01778 | 669 | /// Returns mutable references to two distinct elements, a and b. Panics if a == b. |
0531ce1d XL |
670 | #[inline] |
671 | pub fn pick2_mut(&mut self, a: I, b: I) -> (&mut T, &mut T) { | |
672 | let (ai, bi) = (a.index(), b.index()); | |
673 | assert!(ai != bi); | |
674 | ||
675 | if ai < bi { | |
676 | let (c1, c2) = self.raw.split_at_mut(bi); | |
677 | (&mut c1[ai], &mut c2[0]) | |
678 | } else { | |
679 | let (c2, c1) = self.pick2_mut(b, a); | |
680 | (c1, c2) | |
681 | } | |
682 | } | |
683 | ||
3dfed10e XL |
684 | /// Returns mutable references to three distinct elements or panics otherwise. |
685 | #[inline] | |
686 | pub fn pick3_mut(&mut self, a: I, b: I, c: I) -> (&mut T, &mut T, &mut T) { | |
687 | let (ai, bi, ci) = (a.index(), b.index(), c.index()); | |
688 | assert!(ai != bi && bi != ci && ci != ai); | |
689 | let len = self.raw.len(); | |
690 | assert!(ai < len && bi < len && ci < len); | |
691 | let ptr = self.raw.as_mut_ptr(); | |
692 | unsafe { (&mut *ptr.add(ai), &mut *ptr.add(bi), &mut *ptr.add(ci)) } | |
693 | } | |
694 | ||
0531ce1d | 695 | pub fn convert_index_type<Ix: Idx>(self) -> IndexVec<Ix, T> { |
dfeec247 | 696 | IndexVec { raw: self.raw, _marker: PhantomData } |
0531ce1d | 697 | } |
3157f602 | 698 | |
8faf50e0 XL |
699 | /// Grows the index vector so that it contains an entry for |
700 | /// `elem`; if that is already true, then has no | |
701 | /// effect. Otherwise, inserts new values as needed by invoking | |
702 | /// `fill_value`. | |
703 | #[inline] | |
704 | pub fn ensure_contains_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) { | |
705 | let min_new_len = elem.index() + 1; | |
706 | if self.len() < min_new_len { | |
707 | self.raw.resize_with(min_new_len, fill_value); | |
708 | } | |
709 | } | |
710 | ||
8faf50e0 XL |
711 | #[inline] |
712 | pub fn resize_to_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) { | |
713 | let min_new_len = elem.index() + 1; | |
714 | self.raw.resize_with(min_new_len, fill_value); | |
715 | } | |
cc61c64b XL |
716 | } |
717 | ||
6a06907d XL |
718 | impl<I: Idx, T: Clone> IndexVec<I, T> { |
719 | #[inline] | |
720 | pub fn resize(&mut self, new_len: usize, value: T) { | |
721 | self.raw.resize(new_len, value) | |
722 | } | |
723 | } | |
724 | ||
3b2f2976 XL |
725 | impl<I: Idx, T: Ord> IndexVec<I, T> { |
726 | #[inline] | |
727 | pub fn binary_search(&self, value: &T) -> Result<I, I> { | |
728 | match self.raw.binary_search(value) { | |
729 | Ok(i) => Ok(Idx::new(i)), | |
730 | Err(i) => Err(Idx::new(i)), | |
731 | } | |
732 | } | |
733 | } | |
734 | ||
3157f602 XL |
735 | impl<I: Idx, T> Index<I> for IndexVec<I, T> { |
736 | type Output = T; | |
737 | ||
738 | #[inline] | |
739 | fn index(&self, index: I) -> &T { | |
740 | &self.raw[index.index()] | |
741 | } | |
742 | } | |
743 | ||
744 | impl<I: Idx, T> IndexMut<I> for IndexVec<I, T> { | |
745 | #[inline] | |
746 | fn index_mut(&mut self, index: I) -> &mut T { | |
747 | &mut self.raw[index.index()] | |
748 | } | |
749 | } | |
750 | ||
7cac9316 XL |
751 | impl<I: Idx, T> Default for IndexVec<I, T> { |
752 | #[inline] | |
753 | fn default() -> Self { | |
754 | Self::new() | |
755 | } | |
756 | } | |
757 | ||
3157f602 XL |
758 | impl<I: Idx, T> Extend<T> for IndexVec<I, T> { |
759 | #[inline] | |
760 | fn extend<J: IntoIterator<Item = T>>(&mut self, iter: J) { | |
761 | self.raw.extend(iter); | |
762 | } | |
f9f354fc XL |
763 | |
764 | #[inline] | |
765 | fn extend_one(&mut self, item: T) { | |
766 | self.raw.push(item); | |
767 | } | |
768 | ||
769 | #[inline] | |
770 | fn extend_reserve(&mut self, additional: usize) { | |
771 | self.raw.reserve(additional); | |
772 | } | |
3157f602 XL |
773 | } |
774 | ||
775 | impl<I: Idx, T> FromIterator<T> for IndexVec<I, T> { | |
776 | #[inline] | |
dfeec247 XL |
777 | fn from_iter<J>(iter: J) -> Self |
778 | where | |
779 | J: IntoIterator<Item = T>, | |
780 | { | |
3157f602 XL |
781 | IndexVec { raw: FromIterator::from_iter(iter), _marker: PhantomData } |
782 | } | |
783 | } | |
784 | ||
785 | impl<I: Idx, T> IntoIterator for IndexVec<I, T> { | |
786 | type Item = T; | |
787 | type IntoIter = vec::IntoIter<T>; | |
788 | ||
789 | #[inline] | |
790 | fn into_iter(self) -> vec::IntoIter<T> { | |
791 | self.raw.into_iter() | |
792 | } | |
3157f602 XL |
793 | } |
794 | ||
795 | impl<'a, I: Idx, T> IntoIterator for &'a IndexVec<I, T> { | |
796 | type Item = &'a T; | |
797 | type IntoIter = slice::Iter<'a, T>; | |
798 | ||
799 | #[inline] | |
800 | fn into_iter(self) -> slice::Iter<'a, T> { | |
801 | self.raw.iter() | |
802 | } | |
803 | } | |
804 | ||
805 | impl<'a, I: Idx, T> IntoIterator for &'a mut IndexVec<I, T> { | |
806 | type Item = &'a mut T; | |
807 | type IntoIter = slice::IterMut<'a, T>; | |
808 | ||
809 | #[inline] | |
3b2f2976 | 810 | fn into_iter(self) -> slice::IterMut<'a, T> { |
3157f602 XL |
811 | self.raw.iter_mut() |
812 | } | |
813 | } | |
814 | ||
dfeec247 XL |
815 | pub struct IntoIdx<I: Idx> { |
816 | _marker: PhantomData<fn(&I)>, | |
817 | } | |
3157f602 XL |
818 | impl<I: Idx, T> FnOnce<((usize, T),)> for IntoIdx<I> { |
819 | type Output = (I, T); | |
820 | ||
821 | extern "rust-call" fn call_once(self, ((n, t),): ((usize, T),)) -> Self::Output { | |
822 | (I::new(n), t) | |
823 | } | |
824 | } | |
825 | ||
826 | impl<I: Idx, T> FnMut<((usize, T),)> for IntoIdx<I> { | |
827 | extern "rust-call" fn call_mut(&mut self, ((n, t),): ((usize, T),)) -> Self::Output { | |
828 | (I::new(n), t) | |
829 | } | |
830 | } | |
831 | ||
832 | impl<I: Idx> FnOnce<(usize,)> for IntoIdx<I> { | |
833 | type Output = I; | |
834 | ||
835 | extern "rust-call" fn call_once(self, (n,): (usize,)) -> Self::Output { | |
836 | I::new(n) | |
837 | } | |
838 | } | |
839 | ||
840 | impl<I: Idx> FnMut<(usize,)> for IntoIdx<I> { | |
841 | extern "rust-call" fn call_mut(&mut self, (n,): (usize,)) -> Self::Output { | |
842 | I::new(n) | |
843 | } | |
844 | } | |
dfeec247 XL |
845 | |
846 | #[cfg(test)] | |
847 | mod tests; |