vendor/itertools/benches/extra/zipslices.rs

   1 use std::cmp;
   2
   3 // Note: There are different ways to implement ZipSlices.
   4 // This version performed the best in benchmarks.
   5 //
   6 // I also implemented a version with three pointers (tptr, tend, uptr),
   7 // that mimiced slice::Iter and only checked bounds by using tptr == tend,
   8 // but that was inferior to this solution.
   9
  10 /// An iterator which iterates two slices simultaneously.
  11 ///
  12 /// `ZipSlices` acts like a double-ended `.zip()` iterator.
  13 ///
  14 /// It was intended to be more efficient than `.zip()`, and it was, then
  15 /// rustc changed how it optimizes so it can not promise improved performance
  16 /// at this time.
  17 ///
  18 /// Note that elements past the end of the shortest of the two slices are ignored.
  19 ///
  20 /// Iterator element type for `ZipSlices<T, U>` is `(T::Item, U::Item)`. For example,
  21 /// for a `ZipSlices<&'a [A], &'b mut [B]>`, the element type is `(&'a A, &'b mut B)`.
  22 #[derive(Clone)]
  23 pub struct ZipSlices<T, U> {
  24     t: T,
  25     u: U,
  26     len: usize,
  27     index: usize,
  28 }
  29
  30 impl<'a, 'b, A, B> ZipSlices<&'a [A], &'b [B]> {
  31     /// Create a new `ZipSlices` from slices `a` and `b`.
  32     ///
  33     /// Act like a double-ended `.zip()` iterator, but more efficiently.
  34     ///
  35     /// Note that elements past the end of the shortest of the two slices are ignored.
  36     #[inline(always)]
  37     pub fn new(a: &'a [A], b: &'b [B]) -> Self {
  38         let minl = cmp::min(a.len(), b.len());
  39         ZipSlices {
  40             t: a,
  41             u: b,
  42             len: minl,
  43             index: 0,
  44         }
  45     }
  46 }
  47
  48 impl<T, U> ZipSlices<T, U>
  49     where T: Slice,
  50           U: Slice
  51 {
  52     /// Create a new `ZipSlices` from slices `a` and `b`.
  53     ///
  54     /// Act like a double-ended `.zip()` iterator, but more efficiently.
  55     ///
  56     /// Note that elements past the end of the shortest of the two slices are ignored.
  57     #[inline(always)]
  58     pub fn from_slices(a: T, b: U) -> Self {
  59         let minl = cmp::min(a.len(), b.len());
  60         ZipSlices {
  61             t: a,
  62             u: b,
  63             len: minl,
  64             index: 0,
  65         }
  66     }
  67 }
  68
  69 impl<T, U> Iterator for ZipSlices<T, U>
  70     where T: Slice,
  71           U: Slice
  72 {
  73     type Item = (T::Item, U::Item);
  74
  75     #[inline(always)]
  76     fn next(&mut self) -> Option<Self::Item> {
  77         unsafe {
  78             if self.index >= self.len {
  79                 None
  80             } else {
  81                 let i = self.index;
  82                 self.index += 1;
  83                 Some((
  84                     self.t.get_unchecked(i),
  85                     self.u.get_unchecked(i)))
  86             }
  87         }
  88     }
  89
  90     #[inline]
  91     fn size_hint(&self) -> (usize, Option<usize>) {
  92         let len = self.len - self.index;
  93         (len, Some(len))
  94     }
  95 }
  96
  97 impl<T, U> DoubleEndedIterator for ZipSlices<T, U>
  98     where T: Slice,
  99           U: Slice
 100 {
 101     #[inline(always)]
 102     fn next_back(&mut self) -> Option<Self::Item> {
 103         unsafe {
 104             if self.index >= self.len {
 105                 None
 106             } else {
 107                 self.len -= 1;
 108                 let i = self.len;
 109                 Some((
 110                     self.t.get_unchecked(i),
 111                     self.u.get_unchecked(i)))
 112             }
 113         }
 114     }
 115 }
 116
 117 impl<T, U> ExactSizeIterator for ZipSlices<T, U>
 118     where T: Slice,
 119           U: Slice
 120 {}
 121
 122 unsafe impl<T, U> Slice for ZipSlices<T, U>
 123     where T: Slice,
 124           U: Slice
 125 {
 126     type Item = (T::Item, U::Item);
 127
 128     fn len(&self) -> usize {
 129         self.len - self.index
 130     }
 131
 132     unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
 133         (self.t.get_unchecked(i),
 134          self.u.get_unchecked(i))
 135     }
 136 }
 137
 138 /// A helper trait to let `ZipSlices` accept both `&[T]` and `&mut [T]`.
 139 ///
 140 /// Unsafe trait because:
 141 ///
 142 /// - Implementors must guarantee that `get_unchecked` is valid for all indices `0..len()`.
 143 pub unsafe trait Slice {
 144     /// The type of a reference to the slice's elements
 145     type Item;
 146     #[doc(hidden)]
 147     fn len(&self) -> usize;
 148     #[doc(hidden)]
 149     unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item;
 150 }
 151
 152 unsafe impl<'a, T> Slice for &'a [T] {
 153     type Item = &'a T;
 154     #[inline(always)]
 155     fn len(&self) -> usize { (**self).len() }
 156     #[inline(always)]
 157     unsafe fn get_unchecked(&mut self, i: usize) -> &'a T {
 158         debug_assert!(i < self.len());
 159         (**self).get_unchecked(i)
 160     }
 161 }
 162
 163 unsafe impl<'a, T> Slice for &'a mut [T] {
 164     type Item = &'a mut T;
 165     #[inline(always)]
 166     fn len(&self) -> usize { (**self).len() }
 167     #[inline(always)]
 168     unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut T {
 169         debug_assert!(i < self.len());
 170         // override the lifetime constraints of &mut &'a mut [T]
 171         (*(*self as *mut [T])).get_unchecked_mut(i)
 172     }
 173 }
 174
 175 #[test]
 176 fn zipslices() {
 177
 178     let xs = [1, 2, 3, 4, 5, 6];
 179     let ys = [1, 2, 3, 7];
 180     ::itertools::assert_equal(ZipSlices::new(&xs, &ys), xs.iter().zip(&ys));
 181
 182     let xs = [1, 2, 3, 4, 5, 6];
 183     let mut ys = [0; 6];
 184     for (x, y) in ZipSlices::from_slices(&xs[..], &mut ys[..]) {
 185         *y = *x;
 186     }
 187     ::itertools::assert_equal(&xs, &ys);
 188 }