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