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