src/librustc_data_structures/indexed_vec.rs

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