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