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