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