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