src/libcore/iter/adapters/zip.rs

   1 use cmp;
   2 use super::super::{Iterator, DoubleEndedIterator, ExactSizeIterator, FusedIterator, TrustedLen};
   3
   4 /// An iterator that iterates two other iterators simultaneously.
   5 ///
   6 /// This `struct` is created by the [`zip`] method on [`Iterator`]. See its
   7 /// documentation for more.
   8 ///
   9 /// [`zip`]: trait.Iterator.html#method.zip
  10 /// [`Iterator`]: trait.Iterator.html
  11 #[derive(Clone, Debug)]
  12 #[must_use = "iterators are lazy and do nothing unless consumed"]
  13 #[stable(feature = "rust1", since = "1.0.0")]
  14 pub struct Zip<A, B> {
  15     a: A,
  16     b: B,
  17     // index and len are only used by the specialized version of zip
  18     index: usize,
  19     len: usize,
  20 }
  21
  22 #[stable(feature = "rust1", since = "1.0.0")]
  23 impl<A, B> Iterator for Zip<A, B> where A: Iterator, B: Iterator
  24 {
  25     type Item = (A::Item, B::Item);
  26
  27     #[inline]
  28     fn next(&mut self) -> Option<Self::Item> {
  29         ZipImpl::next(self)
  30     }
  31
  32     #[inline]
  33     fn size_hint(&self) -> (usize, Option<usize>) {
  34         ZipImpl::size_hint(self)
  35     }
  36
  37     #[inline]
  38     fn nth(&mut self, n: usize) -> Option<Self::Item> {
  39         ZipImpl::nth(self, n)
  40     }
  41 }
  42
  43 #[stable(feature = "rust1", since = "1.0.0")]
  44 impl<A, B> DoubleEndedIterator for Zip<A, B> where
  45     A: DoubleEndedIterator + ExactSizeIterator,
  46     B: DoubleEndedIterator + ExactSizeIterator,
  47 {
  48     #[inline]
  49     fn next_back(&mut self) -> Option<(A::Item, B::Item)> {
  50         ZipImpl::next_back(self)
  51     }
  52 }
  53
  54 // Zip specialization trait
  55 #[doc(hidden)]
  56 pub(in super::super) trait ZipImpl<A, B> {
  57     type Item;
  58     fn new(a: A, b: B) -> Self;
  59     fn next(&mut self) -> Option<Self::Item>;
  60     fn size_hint(&self) -> (usize, Option<usize>);
  61     fn nth(&mut self, n: usize) -> Option<Self::Item>;
  62     fn super_nth(&mut self, mut n: usize) -> Option<Self::Item> {
  63         while let Some(x) = self.next() {
  64             if n == 0 { return Some(x) }
  65             n -= 1;
  66         }
  67         None
  68     }
  69     fn next_back(&mut self) -> Option<Self::Item>
  70         where A: DoubleEndedIterator + ExactSizeIterator,
  71               B: DoubleEndedIterator + ExactSizeIterator;
  72 }
  73
  74 // General Zip impl
  75 #[doc(hidden)]
  76 impl<A, B> ZipImpl<A, B> for Zip<A, B>
  77     where A: Iterator, B: Iterator
  78 {
  79     type Item = (A::Item, B::Item);
  80     default fn new(a: A, b: B) -> Self {
  81         Zip {
  82             a,
  83             b,
  84             index: 0, // unused
  85             len: 0, // unused
  86         }
  87     }
  88
  89     #[inline]
  90     default fn next(&mut self) -> Option<(A::Item, B::Item)> {
  91         self.a.next().and_then(|x| {
  92             self.b.next().and_then(|y| {
  93                 Some((x, y))
  94             })
  95         })
  96     }
  97
  98     #[inline]
  99     default fn nth(&mut self, n: usize) -> Option<Self::Item> {
 100         self.super_nth(n)
 101     }
 102
 103     #[inline]
 104     default fn next_back(&mut self) -> Option<(A::Item, B::Item)>
 105         where A: DoubleEndedIterator + ExactSizeIterator,
 106               B: DoubleEndedIterator + ExactSizeIterator
 107     {
 108         let a_sz = self.a.len();
 109         let b_sz = self.b.len();
 110         if a_sz != b_sz {
 111             // Adjust a, b to equal length
 112             if a_sz > b_sz {
 113                 for _ in 0..a_sz - b_sz { self.a.next_back(); }
 114             } else {
 115                 for _ in 0..b_sz - a_sz { self.b.next_back(); }
 116             }
 117         }
 118         match (self.a.next_back(), self.b.next_back()) {
 119             (Some(x), Some(y)) => Some((x, y)),
 120             (None, None) => None,
 121             _ => unreachable!(),
 122         }
 123     }
 124
 125     #[inline]
 126     default fn size_hint(&self) -> (usize, Option<usize>) {
 127         let (a_lower, a_upper) = self.a.size_hint();
 128         let (b_lower, b_upper) = self.b.size_hint();
 129
 130         let lower = cmp::min(a_lower, b_lower);
 131
 132         let upper = match (a_upper, b_upper) {
 133             (Some(x), Some(y)) => Some(cmp::min(x,y)),
 134             (Some(x), None) => Some(x),
 135             (None, Some(y)) => Some(y),
 136             (None, None) => None
 137         };
 138
 139         (lower, upper)
 140     }
 141 }
 142
 143 #[doc(hidden)]
 144 impl<A, B> ZipImpl<A, B> for Zip<A, B>
 145     where A: TrustedRandomAccess, B: TrustedRandomAccess
 146 {
 147     fn new(a: A, b: B) -> Self {
 148         let len = cmp::min(a.len(), b.len());
 149         Zip {
 150             a,
 151             b,
 152             index: 0,
 153             len,
 154         }
 155     }
 156
 157     #[inline]
 158     fn next(&mut self) -> Option<(A::Item, B::Item)> {
 159         if self.index < self.len {
 160             let i = self.index;
 161             self.index += 1;
 162             unsafe {
 163                 Some((self.a.get_unchecked(i), self.b.get_unchecked(i)))
 164             }
 165         } else if A::may_have_side_effect() && self.index < self.a.len() {
 166             // match the base implementation's potential side effects
 167             unsafe {
 168                 self.a.get_unchecked(self.index);
 169             }
 170             self.index += 1;
 171             None
 172         } else {
 173             None
 174         }
 175     }
 176
 177     #[inline]
 178     fn size_hint(&self) -> (usize, Option<usize>) {
 179         let len = self.len - self.index;
 180         (len, Some(len))
 181     }
 182
 183     #[inline]
 184     fn nth(&mut self, n: usize) -> Option<Self::Item> {
 185         let delta = cmp::min(n, self.len - self.index);
 186         let end = self.index + delta;
 187         while self.index < end {
 188             let i = self.index;
 189             self.index += 1;
 190             if A::may_have_side_effect() {
 191                 unsafe { self.a.get_unchecked(i); }
 192             }
 193             if B::may_have_side_effect() {
 194                 unsafe { self.b.get_unchecked(i); }
 195             }
 196         }
 197
 198         self.super_nth(n - delta)
 199     }
 200
 201     #[inline]
 202     fn next_back(&mut self) -> Option<(A::Item, B::Item)>
 203         where A: DoubleEndedIterator + ExactSizeIterator,
 204               B: DoubleEndedIterator + ExactSizeIterator
 205     {
 206         // Adjust a, b to equal length
 207         if A::may_have_side_effect() {
 208             let sz = self.a.len();
 209             if sz > self.len {
 210                 for _ in 0..sz - cmp::max(self.len, self.index) {
 211                     self.a.next_back();
 212                 }
 213             }
 214         }
 215         if B::may_have_side_effect() {
 216             let sz = self.b.len();
 217             if sz > self.len {
 218                 for _ in 0..sz - self.len {
 219                     self.b.next_back();
 220                 }
 221             }
 222         }
 223         if self.index < self.len {
 224             self.len -= 1;
 225             let i = self.len;
 226             unsafe {
 227                 Some((self.a.get_unchecked(i), self.b.get_unchecked(i)))
 228             }
 229         } else {
 230             None
 231         }
 232     }
 233 }
 234
 235 #[stable(feature = "rust1", since = "1.0.0")]
 236 impl<A, B> ExactSizeIterator for Zip<A, B>
 237     where A: ExactSizeIterator, B: ExactSizeIterator {}
 238
 239 #[doc(hidden)]
 240 unsafe impl<A, B> TrustedRandomAccess for Zip<A, B>
 241     where A: TrustedRandomAccess,
 242           B: TrustedRandomAccess,
 243 {
 244     unsafe fn get_unchecked(&mut self, i: usize) -> (A::Item, B::Item) {
 245         (self.a.get_unchecked(i), self.b.get_unchecked(i))
 246     }
 247
 248     fn may_have_side_effect() -> bool {
 249         A::may_have_side_effect() || B::may_have_side_effect()
 250     }
 251 }
 252
 253 #[stable(feature = "fused", since = "1.26.0")]
 254 impl<A, B> FusedIterator for Zip<A, B>
 255     where A: FusedIterator, B: FusedIterator, {}
 256
 257 #[unstable(feature = "trusted_len", issue = "37572")]
 258 unsafe impl<A, B> TrustedLen for Zip<A, B>
 259     where A: TrustedLen, B: TrustedLen,
 260 {}
 261
 262 /// An iterator whose items are random-accessible efficiently
 263 ///
 264 /// # Safety
 265 ///
 266 /// The iterator's .len() and size_hint() must be exact.
 267 /// `.len()` must be cheap to call.
 268 ///
 269 /// .get_unchecked() must return distinct mutable references for distinct
 270 /// indices (if applicable), and must return a valid reference if index is in
 271 /// 0..self.len().
 272 pub(crate) unsafe trait TrustedRandomAccess : ExactSizeIterator {
 273     unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item;
 274     /// Returns `true` if getting an iterator element may have
 275     /// side effects. Remember to take inner iterators into account.
 276     fn may_have_side_effect() -> bool;
 277 }