vendor/itertools-0.8.0/src/tuple_impl.rs

   1 //! Some iterator that produces tuples
   2
   3 use std::iter::Fuse;
   4
   5 /// An iterator over a incomplete tuple.
   6 ///
   7 /// See [`.tuples()`](../trait.Itertools.html#method.tuples) and
   8 /// [`Tuples::into_buffer()`](struct.Tuples.html#method.into_buffer).
   9 #[derive(Debug)]
  10 pub struct TupleBuffer<T>
  11     where T: TupleCollect
  12 {
  13     cur: usize,
  14     buf: T::Buffer,
  15 }
  16
  17 impl<T> TupleBuffer<T>
  18     where T: TupleCollect
  19 {
  20     fn new(buf: T::Buffer) -> Self {
  21         TupleBuffer {
  22             cur: 0,
  23             buf: buf,
  24         }
  25     }
  26 }
  27
  28 impl<T> Iterator for TupleBuffer<T>
  29     where T: TupleCollect
  30 {
  31     type Item = T::Item;
  32
  33     fn next(&mut self) -> Option<Self::Item> {
  34         let s = self.buf.as_mut();
  35         if let Some(ref mut item) = s.get_mut(self.cur) {
  36             self.cur += 1;
  37             item.take()
  38         } else {
  39             None
  40         }
  41     }
  42
  43     fn size_hint(&self) -> (usize, Option<usize>) {
  44         let buffer = &self.buf.as_ref()[self.cur..];
  45         let len = if buffer.len() == 0 {
  46             0
  47         } else {
  48             buffer.iter()
  49                   .position(|x| x.is_none())
  50                   .unwrap_or(buffer.len())
  51         };
  52         (len, Some(len))
  53     }
  54 }
  55
  56 impl<T> ExactSizeIterator for TupleBuffer<T>
  57     where T: TupleCollect
  58 {
  59 }
  60
  61 /// An iterator that groups the items in tuples of a specific size.
  62 ///
  63 /// See [`.tuples()`](../trait.Itertools.html#method.tuples) for more information.
  64 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
  65 pub struct Tuples<I, T>
  66     where I: Iterator<Item = T::Item>,
  67           T: TupleCollect
  68 {
  69     iter: Fuse<I>,
  70     buf: T::Buffer,
  71 }
  72
  73 /// Create a new tuples iterator.
  74 pub fn tuples<I, T>(iter: I) -> Tuples<I, T>
  75     where I: Iterator<Item = T::Item>,
  76           T: TupleCollect
  77 {
  78     Tuples {
  79         iter: iter.fuse(),
  80         buf: Default::default(),
  81     }
  82 }
  83
  84 impl<I, T> Iterator for Tuples<I, T>
  85     where I: Iterator<Item = T::Item>,
  86           T: TupleCollect
  87 {
  88     type Item = T;
  89
  90     fn next(&mut self) -> Option<T> {
  91         T::collect_from_iter(&mut self.iter, &mut self.buf)
  92     }
  93 }
  94
  95 impl<I, T> Tuples<I, T>
  96     where I: Iterator<Item = T::Item>,
  97           T: TupleCollect
  98 {
  99     /// Return a buffer with the produced items that was not enough to be grouped in a tuple.
 100     ///
 101     /// ```
 102     /// use itertools::Itertools;
 103     ///
 104     /// let mut iter = (0..5).tuples();
 105     /// assert_eq!(Some((0, 1, 2)), iter.next());
 106     /// assert_eq!(None, iter.next());
 107     /// itertools::assert_equal(vec![3, 4], iter.into_buffer());
 108     /// ```
 109     pub fn into_buffer(self) -> TupleBuffer<T> {
 110         TupleBuffer::new(self.buf)
 111     }
 112 }
 113
 114
 115 /// An iterator over all contiguous windows that produces tuples of a specific size.
 116 ///
 117 /// See [`.tuple_windows()`](../trait.Itertools.html#method.tuple_windows) for more
 118 /// information.
 119 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 120 #[derive(Debug)]
 121 pub struct TupleWindows<I, T>
 122     where I: Iterator<Item = T::Item>,
 123           T: TupleCollect
 124 {
 125     iter: I,
 126     last: Option<T>,
 127 }
 128
 129 /// Create a new tuple windows iterator.
 130 pub fn tuple_windows<I, T>(mut iter: I) -> TupleWindows<I, T>
 131     where I: Iterator<Item = T::Item>,
 132           T: TupleCollect,
 133           T::Item: Clone
 134 {
 135     use std::iter::once;
 136
 137     let mut last = None;
 138     if T::num_items() != 1 {
 139         // put in a duplicate item in front of the tuple; this simplifies
 140         // .next() function.
 141         if let Some(item) = iter.next() {
 142             let iter = once(item.clone()).chain(once(item)).chain(&mut iter);
 143             last = T::collect_from_iter_no_buf(iter);
 144         }
 145     }
 146
 147     TupleWindows {
 148         last: last,
 149         iter: iter,
 150     }
 151 }
 152
 153 impl<I, T> Iterator for TupleWindows<I, T>
 154     where I: Iterator<Item = T::Item>,
 155           T: TupleCollect + Clone,
 156           T::Item: Clone
 157 {
 158     type Item = T;
 159
 160     fn next(&mut self) -> Option<T> {
 161         if T::num_items() == 1 {
 162             return T::collect_from_iter_no_buf(&mut self.iter)
 163         }
 164         if let Some(ref mut last) = self.last {
 165             if let Some(new) = self.iter.next() {
 166                 last.left_shift_push(new);
 167                 return Some(last.clone());
 168             }
 169         }
 170         None
 171     }
 172 }
 173
 174 pub trait TupleCollect: Sized {
 175     type Item;
 176     type Buffer: Default + AsRef<[Option<Self::Item>]> + AsMut<[Option<Self::Item>]>;
 177
 178     fn collect_from_iter<I>(iter: I, buf: &mut Self::Buffer) -> Option<Self>
 179         where I: IntoIterator<Item = Self::Item>;
 180
 181     fn collect_from_iter_no_buf<I>(iter: I) -> Option<Self>
 182         where I: IntoIterator<Item = Self::Item>;
 183
 184     fn num_items() -> usize;
 185
 186     fn left_shift_push(&mut self, item: Self::Item);
 187 }
 188
 189 macro_rules! impl_tuple_collect {
 190     () => ();
 191     ($N:expr; $A:ident ; $($X:ident),* ; $($Y:ident),* ; $($Y_rev:ident),*) => (
 192         impl<$A> TupleCollect for ($($X),*,) {
 193             type Item = $A;
 194             type Buffer = [Option<$A>; $N - 1];
 195
 196             #[allow(unused_assignments, unused_mut)]
 197             fn collect_from_iter<I>(iter: I, buf: &mut Self::Buffer) -> Option<Self>
 198                 where I: IntoIterator<Item = $A>
 199             {
 200                 let mut iter = iter.into_iter();
 201                 $(
 202                     let mut $Y = None;
 203                 )*
 204
 205                 loop {
 206                     $(
 207                         $Y = iter.next();
 208                         if $Y.is_none() {
 209                             break
 210                         }
 211                     )*
 212                     return Some(($($Y.unwrap()),*,))
 213                 }
 214
 215                 let mut i = 0;
 216                 let mut s = buf.as_mut();
 217                 $(
 218                     if i < s.len() {
 219                         s[i] = $Y;
 220                         i += 1;
 221                     }
 222                 )*
 223                 return None;
 224             }
 225
 226             #[allow(unused_assignments)]
 227             fn collect_from_iter_no_buf<I>(iter: I) -> Option<Self>
 228                 where I: IntoIterator<Item = $A>
 229             {
 230                 let mut iter = iter.into_iter();
 231                 loop {
 232                     $(
 233                         let $Y = if let Some($Y) = iter.next() {
 234                             $Y
 235                         } else {
 236                             break;
 237                         };
 238                     )*
 239                     return Some(($($Y),*,))
 240                 }
 241
 242                 return None;
 243             }
 244
 245             fn num_items() -> usize {
 246                 $N
 247             }
 248
 249             fn left_shift_push(&mut self, item: $A) {
 250                 use std::mem::replace;
 251
 252                 let &mut ($(ref mut $Y),*,) = self;
 253                 let tmp = item;
 254                 $(
 255                     let tmp = replace($Y_rev, tmp);
 256                 )*
 257                 drop(tmp);
 258             }
 259         }
 260     )
 261 }
 262
 263 impl_tuple_collect!(1; A; A; a; a);
 264 impl_tuple_collect!(2; A; A, A; a, b; b, a);
 265 impl_tuple_collect!(3; A; A, A, A; a, b, c; c, b, a);
 266 impl_tuple_collect!(4; A; A, A, A, A; a, b, c, d; d, c, b, a);