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