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