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