Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 1 | //! Licensed under the Apache License, Version 2.0 |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 2 | //! <https://www.apache.org/licenses/LICENSE-2.0> or the MIT license |
| 3 | //! <https://opensource.org/licenses/MIT>, at your |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 4 | //! option. This file may not be copied, modified, or distributed |
| 5 | //! except according to those terms. |
| 6 | |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 7 | mod coalesce; |
| 8 | mod map; |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 9 | mod multi_product; |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 10 | pub use self::coalesce::*; |
| 11 | pub use self::map::{map_into, map_ok, MapInto, MapOk}; |
| 12 | #[allow(deprecated)] |
| 13 | pub use self::map::MapResults; |
| 14 | #[cfg(feature = "use_alloc")] |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 15 | pub use self::multi_product::*; |
| 16 | |
| 17 | use std::fmt; |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 18 | use std::iter::{Fuse, Peekable, FromIterator, FusedIterator}; |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 19 | use std::marker::PhantomData; |
| 20 | use crate::size_hint; |
| 21 | |
| 22 | /// An iterator adaptor that alternates elements from two iterators until both |
| 23 | /// run out. |
| 24 | /// |
| 25 | /// This iterator is *fused*. |
| 26 | /// |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 27 | /// See [`.interleave()`](crate::Itertools::interleave) for more information. |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 28 | #[derive(Clone, Debug)] |
| 29 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
| 30 | pub struct Interleave<I, J> { |
| 31 | a: Fuse<I>, |
| 32 | b: Fuse<J>, |
| 33 | flag: bool, |
| 34 | } |
| 35 | |
| 36 | /// Create an iterator that interleaves elements in `i` and `j`. |
| 37 | /// |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 38 | /// [`IntoIterator`] enabled version of `i.interleave(j)`. |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 39 | /// |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 40 | /// See [`.interleave()`](crate::Itertools::interleave) for more information. |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 41 | pub fn interleave<I, J>(i: I, j: J) -> Interleave<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter> |
| 42 | where I: IntoIterator, |
| 43 | J: IntoIterator<Item = I::Item> |
| 44 | { |
| 45 | Interleave { |
| 46 | a: i.into_iter().fuse(), |
| 47 | b: j.into_iter().fuse(), |
| 48 | flag: false, |
| 49 | } |
| 50 | } |
| 51 | |
| 52 | impl<I, J> Iterator for Interleave<I, J> |
| 53 | where I: Iterator, |
| 54 | J: Iterator<Item = I::Item> |
| 55 | { |
| 56 | type Item = I::Item; |
| 57 | #[inline] |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 58 | fn next(&mut self) -> Option<Self::Item> { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 59 | self.flag = !self.flag; |
| 60 | if self.flag { |
| 61 | match self.a.next() { |
| 62 | None => self.b.next(), |
| 63 | r => r, |
| 64 | } |
| 65 | } else { |
| 66 | match self.b.next() { |
| 67 | None => self.a.next(), |
| 68 | r => r, |
| 69 | } |
| 70 | } |
| 71 | } |
| 72 | |
| 73 | fn size_hint(&self) -> (usize, Option<usize>) { |
| 74 | size_hint::add(self.a.size_hint(), self.b.size_hint()) |
| 75 | } |
| 76 | } |
| 77 | |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 78 | impl<I, J> FusedIterator for Interleave<I, J> |
| 79 | where I: Iterator, |
| 80 | J: Iterator<Item = I::Item> |
| 81 | {} |
| 82 | |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 83 | /// An iterator adaptor that alternates elements from the two iterators until |
| 84 | /// one of them runs out. |
| 85 | /// |
| 86 | /// This iterator is *fused*. |
| 87 | /// |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 88 | /// See [`.interleave_shortest()`](crate::Itertools::interleave_shortest) |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 89 | /// for more information. |
| 90 | #[derive(Clone, Debug)] |
| 91 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
| 92 | pub struct InterleaveShortest<I, J> |
| 93 | where I: Iterator, |
| 94 | J: Iterator<Item = I::Item> |
| 95 | { |
| 96 | it0: I, |
| 97 | it1: J, |
| 98 | phase: bool, // false ==> it0, true ==> it1 |
| 99 | } |
| 100 | |
| 101 | /// Create a new `InterleaveShortest` iterator. |
| 102 | pub fn interleave_shortest<I, J>(a: I, b: J) -> InterleaveShortest<I, J> |
| 103 | where I: Iterator, |
| 104 | J: Iterator<Item = I::Item> |
| 105 | { |
| 106 | InterleaveShortest { |
| 107 | it0: a, |
| 108 | it1: b, |
| 109 | phase: false, |
| 110 | } |
| 111 | } |
| 112 | |
| 113 | impl<I, J> Iterator for InterleaveShortest<I, J> |
| 114 | where I: Iterator, |
| 115 | J: Iterator<Item = I::Item> |
| 116 | { |
| 117 | type Item = I::Item; |
| 118 | |
| 119 | #[inline] |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 120 | fn next(&mut self) -> Option<Self::Item> { |
| 121 | let e = if self.phase { self.it1.next() } else { self.it0.next() }; |
| 122 | if e.is_some() { |
| 123 | self.phase = !self.phase; |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 124 | } |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 125 | e |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 126 | } |
| 127 | |
| 128 | #[inline] |
| 129 | fn size_hint(&self) -> (usize, Option<usize>) { |
| 130 | let (curr_hint, next_hint) = { |
| 131 | let it0_hint = self.it0.size_hint(); |
| 132 | let it1_hint = self.it1.size_hint(); |
| 133 | if self.phase { |
| 134 | (it1_hint, it0_hint) |
| 135 | } else { |
| 136 | (it0_hint, it1_hint) |
| 137 | } |
| 138 | }; |
| 139 | let (curr_lower, curr_upper) = curr_hint; |
| 140 | let (next_lower, next_upper) = next_hint; |
| 141 | let (combined_lower, combined_upper) = |
| 142 | size_hint::mul_scalar(size_hint::min(curr_hint, next_hint), 2); |
| 143 | let lower = |
| 144 | if curr_lower > next_lower { |
| 145 | combined_lower + 1 |
| 146 | } else { |
| 147 | combined_lower |
| 148 | }; |
| 149 | let upper = { |
| 150 | let extra_elem = match (curr_upper, next_upper) { |
| 151 | (_, None) => false, |
| 152 | (None, Some(_)) => true, |
| 153 | (Some(curr_max), Some(next_max)) => curr_max > next_max, |
| 154 | }; |
| 155 | if extra_elem { |
| 156 | combined_upper.and_then(|x| x.checked_add(1)) |
| 157 | } else { |
| 158 | combined_upper |
| 159 | } |
| 160 | }; |
| 161 | (lower, upper) |
| 162 | } |
| 163 | } |
| 164 | |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 165 | impl<I, J> FusedIterator for InterleaveShortest<I, J> |
| 166 | where I: FusedIterator, |
| 167 | J: FusedIterator<Item = I::Item> |
| 168 | {} |
| 169 | |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 170 | #[derive(Clone, Debug)] |
| 171 | /// An iterator adaptor that allows putting back a single |
| 172 | /// item to the front of the iterator. |
| 173 | /// |
| 174 | /// Iterator element type is `I::Item`. |
| 175 | pub struct PutBack<I> |
| 176 | where I: Iterator |
| 177 | { |
| 178 | top: Option<I::Item>, |
| 179 | iter: I, |
| 180 | } |
| 181 | |
| 182 | /// Create an iterator where you can put back a single item |
| 183 | pub fn put_back<I>(iterable: I) -> PutBack<I::IntoIter> |
| 184 | where I: IntoIterator |
| 185 | { |
| 186 | PutBack { |
| 187 | top: None, |
| 188 | iter: iterable.into_iter(), |
| 189 | } |
| 190 | } |
| 191 | |
| 192 | impl<I> PutBack<I> |
| 193 | where I: Iterator |
| 194 | { |
| 195 | /// put back value `value` (builder method) |
| 196 | pub fn with_value(mut self, value: I::Item) -> Self { |
| 197 | self.put_back(value); |
| 198 | self |
| 199 | } |
| 200 | |
| 201 | /// Split the `PutBack` into its parts. |
| 202 | #[inline] |
| 203 | pub fn into_parts(self) -> (Option<I::Item>, I) { |
| 204 | let PutBack{top, iter} = self; |
| 205 | (top, iter) |
| 206 | } |
| 207 | |
| 208 | /// Put back a single value to the front of the iterator. |
| 209 | /// |
| 210 | /// If a value is already in the put back slot, it is overwritten. |
| 211 | #[inline] |
| 212 | pub fn put_back(&mut self, x: I::Item) { |
| 213 | self.top = Some(x) |
| 214 | } |
| 215 | } |
| 216 | |
| 217 | impl<I> Iterator for PutBack<I> |
| 218 | where I: Iterator |
| 219 | { |
| 220 | type Item = I::Item; |
| 221 | #[inline] |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 222 | fn next(&mut self) -> Option<Self::Item> { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 223 | match self.top { |
| 224 | None => self.iter.next(), |
| 225 | ref mut some => some.take(), |
| 226 | } |
| 227 | } |
| 228 | #[inline] |
| 229 | fn size_hint(&self) -> (usize, Option<usize>) { |
| 230 | // Not ExactSizeIterator because size may be larger than usize |
| 231 | size_hint::add_scalar(self.iter.size_hint(), self.top.is_some() as usize) |
| 232 | } |
| 233 | |
| 234 | fn count(self) -> usize { |
| 235 | self.iter.count() + (self.top.is_some() as usize) |
| 236 | } |
| 237 | |
| 238 | fn last(self) -> Option<Self::Item> { |
| 239 | self.iter.last().or(self.top) |
| 240 | } |
| 241 | |
| 242 | fn nth(&mut self, n: usize) -> Option<Self::Item> { |
| 243 | match self.top { |
| 244 | None => self.iter.nth(n), |
| 245 | ref mut some => { |
| 246 | if n == 0 { |
| 247 | some.take() |
| 248 | } else { |
| 249 | *some = None; |
| 250 | self.iter.nth(n - 1) |
| 251 | } |
| 252 | } |
| 253 | } |
| 254 | } |
| 255 | |
| 256 | fn all<G>(&mut self, mut f: G) -> bool |
| 257 | where G: FnMut(Self::Item) -> bool |
| 258 | { |
| 259 | if let Some(elt) = self.top.take() { |
| 260 | if !f(elt) { |
| 261 | return false; |
| 262 | } |
| 263 | } |
| 264 | self.iter.all(f) |
| 265 | } |
| 266 | |
| 267 | fn fold<Acc, G>(mut self, init: Acc, mut f: G) -> Acc |
| 268 | where G: FnMut(Acc, Self::Item) -> Acc, |
| 269 | { |
| 270 | let mut accum = init; |
| 271 | if let Some(elt) = self.top.take() { |
| 272 | accum = f(accum, elt); |
| 273 | } |
| 274 | self.iter.fold(accum, f) |
| 275 | } |
| 276 | } |
| 277 | |
| 278 | #[derive(Debug, Clone)] |
| 279 | /// An iterator adaptor that iterates over the cartesian product of |
| 280 | /// the element sets of two iterators `I` and `J`. |
| 281 | /// |
| 282 | /// Iterator element type is `(I::Item, J::Item)`. |
| 283 | /// |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 284 | /// See [`.cartesian_product()`](crate::Itertools::cartesian_product) for more information. |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 285 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
| 286 | pub struct Product<I, J> |
| 287 | where I: Iterator |
| 288 | { |
| 289 | a: I, |
| 290 | a_cur: Option<I::Item>, |
| 291 | b: J, |
| 292 | b_orig: J, |
| 293 | } |
| 294 | |
| 295 | /// Create a new cartesian product iterator |
| 296 | /// |
| 297 | /// Iterator element type is `(I::Item, J::Item)`. |
| 298 | pub fn cartesian_product<I, J>(mut i: I, j: J) -> Product<I, J> |
| 299 | where I: Iterator, |
| 300 | J: Clone + Iterator, |
| 301 | I::Item: Clone |
| 302 | { |
| 303 | Product { |
| 304 | a_cur: i.next(), |
| 305 | a: i, |
| 306 | b: j.clone(), |
| 307 | b_orig: j, |
| 308 | } |
| 309 | } |
| 310 | |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 311 | impl<I, J> Iterator for Product<I, J> |
| 312 | where I: Iterator, |
| 313 | J: Clone + Iterator, |
| 314 | I::Item: Clone |
| 315 | { |
| 316 | type Item = (I::Item, J::Item); |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 317 | |
| 318 | fn next(&mut self) -> Option<Self::Item> { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 319 | let elt_b = match self.b.next() { |
| 320 | None => { |
| 321 | self.b = self.b_orig.clone(); |
| 322 | match self.b.next() { |
| 323 | None => return None, |
| 324 | Some(x) => { |
| 325 | self.a_cur = self.a.next(); |
| 326 | x |
| 327 | } |
| 328 | } |
| 329 | } |
| 330 | Some(x) => x |
| 331 | }; |
| 332 | match self.a_cur { |
| 333 | None => None, |
| 334 | Some(ref a) => { |
| 335 | Some((a.clone(), elt_b)) |
| 336 | } |
| 337 | } |
| 338 | } |
| 339 | |
| 340 | fn size_hint(&self) -> (usize, Option<usize>) { |
| 341 | let has_cur = self.a_cur.is_some() as usize; |
| 342 | // Not ExactSizeIterator because size may be larger than usize |
| 343 | let (b_min, b_max) = self.b.size_hint(); |
| 344 | |
| 345 | // Compute a * b_orig + b for both lower and upper bound |
| 346 | size_hint::add( |
| 347 | size_hint::mul(self.a.size_hint(), self.b_orig.size_hint()), |
| 348 | (b_min * has_cur, b_max.map(move |x| x * has_cur))) |
| 349 | } |
| 350 | |
| 351 | fn fold<Acc, G>(mut self, mut accum: Acc, mut f: G) -> Acc |
| 352 | where G: FnMut(Acc, Self::Item) -> Acc, |
| 353 | { |
| 354 | // use a split loop to handle the loose a_cur as well as avoiding to |
| 355 | // clone b_orig at the end. |
| 356 | if let Some(mut a) = self.a_cur.take() { |
| 357 | let mut b = self.b; |
| 358 | loop { |
| 359 | accum = b.fold(accum, |acc, elt| f(acc, (a.clone(), elt))); |
| 360 | |
| 361 | // we can only continue iterating a if we had a first element; |
| 362 | if let Some(next_a) = self.a.next() { |
| 363 | b = self.b_orig.clone(); |
| 364 | a = next_a; |
| 365 | } else { |
| 366 | break; |
| 367 | } |
| 368 | } |
| 369 | } |
| 370 | accum |
| 371 | } |
| 372 | } |
| 373 | |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 374 | impl<I, J> FusedIterator for Product<I, J> |
| 375 | where I: FusedIterator, |
| 376 | J: Clone + FusedIterator, |
| 377 | I::Item: Clone |
| 378 | {} |
| 379 | |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 380 | /// A “meta iterator adaptor”. Its closure receives a reference to the iterator |
| 381 | /// and may pick off as many elements as it likes, to produce the next iterator element. |
| 382 | /// |
| 383 | /// Iterator element type is *X*, if the return type of `F` is *Option\<X\>*. |
| 384 | /// |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 385 | /// See [`.batching()`](crate::Itertools::batching) for more information. |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 386 | #[derive(Clone)] |
| 387 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
| 388 | pub struct Batching<I, F> { |
| 389 | f: F, |
| 390 | iter: I, |
| 391 | } |
| 392 | |
| 393 | impl<I, F> fmt::Debug for Batching<I, F> where I: fmt::Debug { |
| 394 | debug_fmt_fields!(Batching, iter); |
| 395 | } |
| 396 | |
| 397 | /// Create a new Batching iterator. |
| 398 | pub fn batching<I, F>(iter: I, f: F) -> Batching<I, F> { |
| 399 | Batching { f, iter } |
| 400 | } |
| 401 | |
| 402 | impl<B, F, I> Iterator for Batching<I, F> |
| 403 | where I: Iterator, |
| 404 | F: FnMut(&mut I) -> Option<B> |
| 405 | { |
| 406 | type Item = B; |
| 407 | #[inline] |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 408 | fn next(&mut self) -> Option<Self::Item> { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 409 | (self.f)(&mut self.iter) |
| 410 | } |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 411 | } |
| 412 | |
| 413 | /// An iterator adaptor that steps a number elements in the base iterator |
| 414 | /// for each iteration. |
| 415 | /// |
| 416 | /// The iterator steps by yielding the next element from the base iterator, |
| 417 | /// then skipping forward *n-1* elements. |
| 418 | /// |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 419 | /// See [`.step()`](crate::Itertools::step) for more information. |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 420 | #[deprecated(note="Use std .step_by() instead", since="0.8.0")] |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 421 | #[allow(deprecated)] |
| 422 | #[derive(Clone, Debug)] |
| 423 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
| 424 | pub struct Step<I> { |
| 425 | iter: Fuse<I>, |
| 426 | skip: usize, |
| 427 | } |
| 428 | |
| 429 | /// Create a `Step` iterator. |
| 430 | /// |
| 431 | /// **Panics** if the step is 0. |
| 432 | #[allow(deprecated)] |
| 433 | pub fn step<I>(iter: I, step: usize) -> Step<I> |
| 434 | where I: Iterator |
| 435 | { |
| 436 | assert!(step != 0); |
| 437 | Step { |
| 438 | iter: iter.fuse(), |
| 439 | skip: step - 1, |
| 440 | } |
| 441 | } |
| 442 | |
| 443 | #[allow(deprecated)] |
| 444 | impl<I> Iterator for Step<I> |
| 445 | where I: Iterator |
| 446 | { |
| 447 | type Item = I::Item; |
| 448 | #[inline] |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 449 | fn next(&mut self) -> Option<Self::Item> { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 450 | let elt = self.iter.next(); |
| 451 | if self.skip > 0 { |
| 452 | self.iter.nth(self.skip - 1); |
| 453 | } |
| 454 | elt |
| 455 | } |
| 456 | |
| 457 | fn size_hint(&self) -> (usize, Option<usize>) { |
| 458 | let (low, high) = self.iter.size_hint(); |
| 459 | let div = |x: usize| { |
| 460 | if x == 0 { |
| 461 | 0 |
| 462 | } else { |
| 463 | 1 + (x - 1) / (self.skip + 1) |
| 464 | } |
| 465 | }; |
| 466 | (div(low), high.map(div)) |
| 467 | } |
| 468 | } |
| 469 | |
| 470 | // known size |
| 471 | #[allow(deprecated)] |
| 472 | impl<I> ExactSizeIterator for Step<I> |
| 473 | where I: ExactSizeIterator |
| 474 | {} |
| 475 | |
| 476 | pub trait MergePredicate<T> { |
| 477 | fn merge_pred(&mut self, a: &T, b: &T) -> bool; |
| 478 | } |
| 479 | |
| 480 | #[derive(Clone)] |
| 481 | pub struct MergeLte; |
| 482 | |
| 483 | impl<T: PartialOrd> MergePredicate<T> for MergeLte { |
| 484 | fn merge_pred(&mut self, a: &T, b: &T) -> bool { |
| 485 | a <= b |
| 486 | } |
| 487 | } |
| 488 | |
| 489 | /// An iterator adaptor that merges the two base iterators in ascending order. |
| 490 | /// If both base iterators are sorted (ascending), the result is sorted. |
| 491 | /// |
| 492 | /// Iterator element type is `I::Item`. |
| 493 | /// |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 494 | /// See [`.merge()`](crate::Itertools::merge_by) for more information. |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 495 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
| 496 | pub type Merge<I, J> = MergeBy<I, J, MergeLte>; |
| 497 | |
| 498 | /// Create an iterator that merges elements in `i` and `j`. |
| 499 | /// |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 500 | /// [`IntoIterator`] enabled version of [`Itertools::merge`](crate::Itertools::merge). |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 501 | /// |
| 502 | /// ``` |
| 503 | /// use itertools::merge; |
| 504 | /// |
| 505 | /// for elt in merge(&[1, 2, 3], &[2, 3, 4]) { |
| 506 | /// /* loop body */ |
| 507 | /// } |
| 508 | /// ``` |
| 509 | pub fn merge<I, J>(i: I, j: J) -> Merge<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter> |
| 510 | where I: IntoIterator, |
| 511 | J: IntoIterator<Item = I::Item>, |
| 512 | I::Item: PartialOrd |
| 513 | { |
| 514 | merge_by_new(i, j, MergeLte) |
| 515 | } |
| 516 | |
| 517 | /// An iterator adaptor that merges the two base iterators in ascending order. |
| 518 | /// If both base iterators are sorted (ascending), the result is sorted. |
| 519 | /// |
| 520 | /// Iterator element type is `I::Item`. |
| 521 | /// |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 522 | /// See [`.merge_by()`](crate::Itertools::merge_by) for more information. |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 523 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
| 524 | pub struct MergeBy<I, J, F> |
| 525 | where I: Iterator, |
| 526 | J: Iterator<Item = I::Item> |
| 527 | { |
| 528 | a: Peekable<I>, |
| 529 | b: Peekable<J>, |
| 530 | fused: Option<bool>, |
| 531 | cmp: F, |
| 532 | } |
| 533 | |
| 534 | impl<I, J, F> fmt::Debug for MergeBy<I, J, F> |
| 535 | where I: Iterator + fmt::Debug, J: Iterator<Item = I::Item> + fmt::Debug, |
| 536 | I::Item: fmt::Debug, |
| 537 | { |
| 538 | debug_fmt_fields!(MergeBy, a, b); |
| 539 | } |
| 540 | |
| 541 | impl<T, F: FnMut(&T, &T)->bool> MergePredicate<T> for F { |
| 542 | fn merge_pred(&mut self, a: &T, b: &T) -> bool { |
| 543 | self(a, b) |
| 544 | } |
| 545 | } |
| 546 | |
| 547 | /// Create a `MergeBy` iterator. |
| 548 | pub fn merge_by_new<I, J, F>(a: I, b: J, cmp: F) -> MergeBy<I::IntoIter, J::IntoIter, F> |
| 549 | where I: IntoIterator, |
| 550 | J: IntoIterator<Item = I::Item>, |
| 551 | F: MergePredicate<I::Item>, |
| 552 | { |
| 553 | MergeBy { |
| 554 | a: a.into_iter().peekable(), |
| 555 | b: b.into_iter().peekable(), |
| 556 | fused: None, |
| 557 | cmp, |
| 558 | } |
| 559 | } |
| 560 | |
| 561 | impl<I, J, F> Clone for MergeBy<I, J, F> |
| 562 | where I: Iterator, |
| 563 | J: Iterator<Item = I::Item>, |
| 564 | Peekable<I>: Clone, |
| 565 | Peekable<J>: Clone, |
| 566 | F: Clone |
| 567 | { |
| 568 | clone_fields!(a, b, fused, cmp); |
| 569 | } |
| 570 | |
| 571 | impl<I, J, F> Iterator for MergeBy<I, J, F> |
| 572 | where I: Iterator, |
| 573 | J: Iterator<Item = I::Item>, |
| 574 | F: MergePredicate<I::Item> |
| 575 | { |
| 576 | type Item = I::Item; |
| 577 | |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 578 | fn next(&mut self) -> Option<Self::Item> { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 579 | let less_than = match self.fused { |
| 580 | Some(lt) => lt, |
| 581 | None => match (self.a.peek(), self.b.peek()) { |
| 582 | (Some(a), Some(b)) => self.cmp.merge_pred(a, b), |
| 583 | (Some(_), None) => { |
| 584 | self.fused = Some(true); |
| 585 | true |
| 586 | } |
| 587 | (None, Some(_)) => { |
| 588 | self.fused = Some(false); |
| 589 | false |
| 590 | } |
| 591 | (None, None) => return None, |
| 592 | } |
| 593 | }; |
| 594 | if less_than { |
| 595 | self.a.next() |
| 596 | } else { |
| 597 | self.b.next() |
| 598 | } |
| 599 | } |
| 600 | |
| 601 | fn size_hint(&self) -> (usize, Option<usize>) { |
| 602 | // Not ExactSizeIterator because size may be larger than usize |
| 603 | size_hint::add(self.a.size_hint(), self.b.size_hint()) |
| 604 | } |
| 605 | } |
| 606 | |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 607 | impl<I, J, F> FusedIterator for MergeBy<I, J, F> |
| 608 | where I: FusedIterator, |
| 609 | J: FusedIterator<Item = I::Item>, |
| 610 | F: MergePredicate<I::Item> |
| 611 | {} |
| 612 | |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 613 | /// An iterator adaptor that borrows from a `Clone`-able iterator |
| 614 | /// to only pick off elements while the predicate returns `true`. |
| 615 | /// |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 616 | /// See [`.take_while_ref()`](crate::Itertools::take_while_ref) for more information. |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 617 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
| 618 | pub struct TakeWhileRef<'a, I: 'a, F> { |
| 619 | iter: &'a mut I, |
| 620 | f: F, |
| 621 | } |
| 622 | |
| 623 | impl<'a, I, F> fmt::Debug for TakeWhileRef<'a, I, F> |
| 624 | where I: Iterator + fmt::Debug, |
| 625 | { |
| 626 | debug_fmt_fields!(TakeWhileRef, iter); |
| 627 | } |
| 628 | |
| 629 | /// Create a new `TakeWhileRef` from a reference to clonable iterator. |
| 630 | pub fn take_while_ref<I, F>(iter: &mut I, f: F) -> TakeWhileRef<I, F> |
| 631 | where I: Iterator + Clone |
| 632 | { |
| 633 | TakeWhileRef { iter, f } |
| 634 | } |
| 635 | |
| 636 | impl<'a, I, F> Iterator for TakeWhileRef<'a, I, F> |
| 637 | where I: Iterator + Clone, |
| 638 | F: FnMut(&I::Item) -> bool |
| 639 | { |
| 640 | type Item = I::Item; |
| 641 | |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 642 | fn next(&mut self) -> Option<Self::Item> { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 643 | let old = self.iter.clone(); |
| 644 | match self.iter.next() { |
| 645 | None => None, |
| 646 | Some(elt) => { |
| 647 | if (self.f)(&elt) { |
| 648 | Some(elt) |
| 649 | } else { |
| 650 | *self.iter = old; |
| 651 | None |
| 652 | } |
| 653 | } |
| 654 | } |
| 655 | } |
| 656 | |
| 657 | fn size_hint(&self) -> (usize, Option<usize>) { |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 658 | (0, self.iter.size_hint().1) |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 659 | } |
| 660 | } |
| 661 | |
| 662 | /// An iterator adaptor that filters `Option<A>` iterator elements |
| 663 | /// and produces `A`. Stops on the first `None` encountered. |
| 664 | /// |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 665 | /// See [`.while_some()`](crate::Itertools::while_some) for more information. |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 666 | #[derive(Clone, Debug)] |
| 667 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
| 668 | pub struct WhileSome<I> { |
| 669 | iter: I, |
| 670 | } |
| 671 | |
| 672 | /// Create a new `WhileSome<I>`. |
| 673 | pub fn while_some<I>(iter: I) -> WhileSome<I> { |
| 674 | WhileSome { iter } |
| 675 | } |
| 676 | |
| 677 | impl<I, A> Iterator for WhileSome<I> |
| 678 | where I: Iterator<Item = Option<A>> |
| 679 | { |
| 680 | type Item = A; |
| 681 | |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 682 | fn next(&mut self) -> Option<Self::Item> { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 683 | match self.iter.next() { |
| 684 | None | Some(None) => None, |
| 685 | Some(elt) => elt, |
| 686 | } |
| 687 | } |
| 688 | |
| 689 | fn size_hint(&self) -> (usize, Option<usize>) { |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 690 | (0, self.iter.size_hint().1) |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 691 | } |
| 692 | } |
| 693 | |
| 694 | /// An iterator to iterate through all combinations in a `Clone`-able iterator that produces tuples |
| 695 | /// of a specific size. |
| 696 | /// |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 697 | /// See [`.tuple_combinations()`](crate::Itertools::tuple_combinations) for more |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 698 | /// information. |
| 699 | #[derive(Clone, Debug)] |
| 700 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
| 701 | pub struct TupleCombinations<I, T> |
| 702 | where I: Iterator, |
| 703 | T: HasCombination<I> |
| 704 | { |
| 705 | iter: T::Combination, |
| 706 | _mi: PhantomData<I>, |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 707 | } |
| 708 | |
| 709 | pub trait HasCombination<I>: Sized { |
| 710 | type Combination: From<I> + Iterator<Item = Self>; |
| 711 | } |
| 712 | |
| 713 | /// Create a new `TupleCombinations` from a clonable iterator. |
| 714 | pub fn tuple_combinations<T, I>(iter: I) -> TupleCombinations<I, T> |
| 715 | where I: Iterator + Clone, |
| 716 | I::Item: Clone, |
| 717 | T: HasCombination<I>, |
| 718 | { |
| 719 | TupleCombinations { |
| 720 | iter: T::Combination::from(iter), |
| 721 | _mi: PhantomData, |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 722 | } |
| 723 | } |
| 724 | |
| 725 | impl<I, T> Iterator for TupleCombinations<I, T> |
| 726 | where I: Iterator, |
| 727 | T: HasCombination<I>, |
| 728 | { |
| 729 | type Item = T; |
| 730 | |
| 731 | fn next(&mut self) -> Option<Self::Item> { |
| 732 | self.iter.next() |
| 733 | } |
| 734 | } |
| 735 | |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 736 | impl<I, T> FusedIterator for TupleCombinations<I, T> |
| 737 | where I: FusedIterator, |
| 738 | T: HasCombination<I>, |
| 739 | {} |
| 740 | |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 741 | #[derive(Clone, Debug)] |
| 742 | pub struct Tuple1Combination<I> { |
| 743 | iter: I, |
| 744 | } |
| 745 | |
| 746 | impl<I> From<I> for Tuple1Combination<I> { |
| 747 | fn from(iter: I) -> Self { |
| 748 | Tuple1Combination { iter } |
| 749 | } |
| 750 | } |
| 751 | |
| 752 | impl<I: Iterator> Iterator for Tuple1Combination<I> { |
| 753 | type Item = (I::Item,); |
| 754 | |
| 755 | fn next(&mut self) -> Option<Self::Item> { |
| 756 | self.iter.next().map(|x| (x,)) |
| 757 | } |
| 758 | } |
| 759 | |
| 760 | impl<I: Iterator> HasCombination<I> for (I::Item,) { |
| 761 | type Combination = Tuple1Combination<I>; |
| 762 | } |
| 763 | |
| 764 | macro_rules! impl_tuple_combination { |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 765 | ($C:ident $P:ident ; $($X:ident)*) => ( |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 766 | #[derive(Clone, Debug)] |
| 767 | pub struct $C<I: Iterator> { |
| 768 | item: Option<I::Item>, |
| 769 | iter: I, |
| 770 | c: $P<I>, |
| 771 | } |
| 772 | |
| 773 | impl<I: Iterator + Clone> From<I> for $C<I> { |
| 774 | fn from(mut iter: I) -> Self { |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 775 | Self { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 776 | item: iter.next(), |
| 777 | iter: iter.clone(), |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 778 | c: iter.into(), |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 779 | } |
| 780 | } |
| 781 | } |
| 782 | |
| 783 | impl<I: Iterator + Clone> From<I> for $C<Fuse<I>> { |
| 784 | fn from(iter: I) -> Self { |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 785 | Self::from(iter.fuse()) |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 786 | } |
| 787 | } |
| 788 | |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 789 | impl<I, A> Iterator for $C<I> |
| 790 | where I: Iterator<Item = A> + Clone, |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 791 | I::Item: Clone |
| 792 | { |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 793 | type Item = (A, $(ignore_ident!($X, A)),*); |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 794 | |
| 795 | fn next(&mut self) -> Option<Self::Item> { |
| 796 | if let Some(($($X),*,)) = self.c.next() { |
| 797 | let z = self.item.clone().unwrap(); |
| 798 | Some((z, $($X),*)) |
| 799 | } else { |
| 800 | self.item = self.iter.next(); |
| 801 | self.item.clone().and_then(|z| { |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 802 | self.c = self.iter.clone().into(); |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 803 | self.c.next().map(|($($X),*,)| (z, $($X),*)) |
| 804 | }) |
| 805 | } |
| 806 | } |
| 807 | } |
| 808 | |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 809 | impl<I, A> HasCombination<I> for (A, $(ignore_ident!($X, A)),*) |
| 810 | where I: Iterator<Item = A> + Clone, |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 811 | I::Item: Clone |
| 812 | { |
| 813 | type Combination = $C<Fuse<I>>; |
| 814 | } |
| 815 | ) |
| 816 | } |
| 817 | |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 818 | // This snippet generates the twelve `impl_tuple_combination!` invocations: |
| 819 | // use core::iter; |
| 820 | // use itertools::Itertools; |
| 821 | // |
| 822 | // for i in 2..=12 { |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 823 | // println!("impl_tuple_combination!(Tuple{arity}Combination Tuple{prev}Combination; {idents});", |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 824 | // arity = i, |
| 825 | // prev = i - 1, |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 826 | // idents = ('a'..'z').take(i - 1).join(" "), |
| 827 | // ); |
| 828 | // } |
| 829 | // It could probably be replaced by a bit more macro cleverness. |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 830 | impl_tuple_combination!(Tuple2Combination Tuple1Combination; a); |
| 831 | impl_tuple_combination!(Tuple3Combination Tuple2Combination; a b); |
| 832 | impl_tuple_combination!(Tuple4Combination Tuple3Combination; a b c); |
| 833 | impl_tuple_combination!(Tuple5Combination Tuple4Combination; a b c d); |
| 834 | impl_tuple_combination!(Tuple6Combination Tuple5Combination; a b c d e); |
| 835 | impl_tuple_combination!(Tuple7Combination Tuple6Combination; a b c d e f); |
| 836 | impl_tuple_combination!(Tuple8Combination Tuple7Combination; a b c d e f g); |
| 837 | impl_tuple_combination!(Tuple9Combination Tuple8Combination; a b c d e f g h); |
| 838 | impl_tuple_combination!(Tuple10Combination Tuple9Combination; a b c d e f g h i); |
| 839 | impl_tuple_combination!(Tuple11Combination Tuple10Combination; a b c d e f g h i j); |
| 840 | impl_tuple_combination!(Tuple12Combination Tuple11Combination; a b c d e f g h i j k); |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 841 | |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 842 | /// An iterator adapter to filter values within a nested `Result::Ok`. |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 843 | /// |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 844 | /// See [`.filter_ok()`](crate::Itertools::filter_ok) for more information. |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 845 | #[derive(Clone)] |
| 846 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 847 | pub struct FilterOk<I, F> { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 848 | iter: I, |
| 849 | f: F |
| 850 | } |
| 851 | |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 852 | /// Create a new `FilterOk` iterator. |
| 853 | pub fn filter_ok<I, F, T, E>(iter: I, f: F) -> FilterOk<I, F> |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 854 | where I: Iterator<Item = Result<T, E>>, |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 855 | F: FnMut(&T) -> bool, |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 856 | { |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 857 | FilterOk { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 858 | iter, |
| 859 | f, |
| 860 | } |
| 861 | } |
| 862 | |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 863 | impl<I, F, T, E> Iterator for FilterOk<I, F> |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 864 | where I: Iterator<Item = Result<T, E>>, |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 865 | F: FnMut(&T) -> bool, |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 866 | { |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 867 | type Item = Result<T, E>; |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 868 | |
| 869 | fn next(&mut self) -> Option<Self::Item> { |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 870 | loop { |
| 871 | match self.iter.next() { |
| 872 | Some(Ok(v)) => { |
| 873 | if (self.f)(&v) { |
| 874 | return Some(Ok(v)); |
| 875 | } |
| 876 | }, |
| 877 | Some(Err(e)) => return Some(Err(e)), |
| 878 | None => return None, |
| 879 | } |
| 880 | } |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 881 | } |
| 882 | |
| 883 | fn size_hint(&self) -> (usize, Option<usize>) { |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 884 | (0, self.iter.size_hint().1) |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 885 | } |
| 886 | |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 887 | fn fold<Acc, Fold>(self, init: Acc, fold_f: Fold) -> Acc |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 888 | where Fold: FnMut(Acc, Self::Item) -> Acc, |
| 889 | { |
| 890 | let mut f = self.f; |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 891 | self.iter.filter(|v| { |
| 892 | v.as_ref().map(&mut f).unwrap_or(true) |
| 893 | }).fold(init, fold_f) |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 894 | } |
| 895 | |
| 896 | fn collect<C>(self) -> C |
| 897 | where C: FromIterator<Self::Item> |
| 898 | { |
| 899 | let mut f = self.f; |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 900 | self.iter.filter(|v| { |
| 901 | v.as_ref().map(&mut f).unwrap_or(true) |
| 902 | }).collect() |
| 903 | } |
| 904 | } |
| 905 | |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 906 | impl<I, F, T, E> FusedIterator for FilterOk<I, F> |
| 907 | where I: FusedIterator<Item = Result<T, E>>, |
| 908 | F: FnMut(&T) -> bool, |
| 909 | {} |
| 910 | |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 911 | /// An iterator adapter to filter and apply a transformation on values within a nested `Result::Ok`. |
| 912 | /// |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 913 | /// See [`.filter_map_ok()`](crate::Itertools::filter_map_ok) for more information. |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 914 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
| 915 | pub struct FilterMapOk<I, F> { |
| 916 | iter: I, |
| 917 | f: F |
| 918 | } |
| 919 | |
| 920 | fn transpose_result<T, E>(result: Result<Option<T>, E>) -> Option<Result<T, E>> { |
| 921 | match result { |
| 922 | Ok(Some(v)) => Some(Ok(v)), |
| 923 | Ok(None) => None, |
| 924 | Err(e) => Some(Err(e)), |
| 925 | } |
| 926 | } |
| 927 | |
| 928 | /// Create a new `FilterOk` iterator. |
| 929 | pub fn filter_map_ok<I, F, T, U, E>(iter: I, f: F) -> FilterMapOk<I, F> |
| 930 | where I: Iterator<Item = Result<T, E>>, |
| 931 | F: FnMut(T) -> Option<U>, |
| 932 | { |
| 933 | FilterMapOk { |
| 934 | iter, |
| 935 | f, |
| 936 | } |
| 937 | } |
| 938 | |
| 939 | impl<I, F, T, U, E> Iterator for FilterMapOk<I, F> |
| 940 | where I: Iterator<Item = Result<T, E>>, |
| 941 | F: FnMut(T) -> Option<U>, |
| 942 | { |
| 943 | type Item = Result<U, E>; |
| 944 | |
| 945 | fn next(&mut self) -> Option<Self::Item> { |
| 946 | loop { |
| 947 | match self.iter.next() { |
| 948 | Some(Ok(v)) => { |
| 949 | if let Some(v) = (self.f)(v) { |
| 950 | return Some(Ok(v)); |
| 951 | } |
| 952 | }, |
| 953 | Some(Err(e)) => return Some(Err(e)), |
| 954 | None => return None, |
| 955 | } |
| 956 | } |
| 957 | } |
| 958 | |
| 959 | fn size_hint(&self) -> (usize, Option<usize>) { |
| 960 | (0, self.iter.size_hint().1) |
| 961 | } |
| 962 | |
| 963 | fn fold<Acc, Fold>(self, init: Acc, fold_f: Fold) -> Acc |
| 964 | where Fold: FnMut(Acc, Self::Item) -> Acc, |
| 965 | { |
| 966 | let mut f = self.f; |
| 967 | self.iter.filter_map(|v| { |
| 968 | transpose_result(v.map(&mut f)) |
| 969 | }).fold(init, fold_f) |
| 970 | } |
| 971 | |
| 972 | fn collect<C>(self) -> C |
| 973 | where C: FromIterator<Self::Item> |
| 974 | { |
| 975 | let mut f = self.f; |
| 976 | self.iter.filter_map(|v| { |
| 977 | transpose_result(v.map(&mut f)) |
| 978 | }).collect() |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 979 | } |
| 980 | } |
| 981 | |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 982 | impl<I, F, T, U, E> FusedIterator for FilterMapOk<I, F> |
| 983 | where I: FusedIterator<Item = Result<T, E>>, |
| 984 | F: FnMut(T) -> Option<U>, |
| 985 | {} |
| 986 | |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 987 | /// An iterator adapter to get the positions of each element that matches a predicate. |
| 988 | /// |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 989 | /// See [`.positions()`](crate::Itertools::positions) for more information. |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 990 | #[derive(Clone)] |
| 991 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
| 992 | pub struct Positions<I, F> { |
| 993 | iter: I, |
| 994 | f: F, |
| 995 | count: usize, |
| 996 | } |
| 997 | |
| 998 | /// Create a new `Positions` iterator. |
| 999 | pub fn positions<I, F>(iter: I, f: F) -> Positions<I, F> |
| 1000 | where I: Iterator, |
| 1001 | F: FnMut(I::Item) -> bool, |
| 1002 | { |
| 1003 | Positions { |
| 1004 | iter, |
| 1005 | f, |
| 1006 | count: 0 |
| 1007 | } |
| 1008 | } |
| 1009 | |
| 1010 | impl<I, F> Iterator for Positions<I, F> |
| 1011 | where I: Iterator, |
| 1012 | F: FnMut(I::Item) -> bool, |
| 1013 | { |
| 1014 | type Item = usize; |
| 1015 | |
| 1016 | fn next(&mut self) -> Option<Self::Item> { |
| 1017 | while let Some(v) = self.iter.next() { |
| 1018 | let i = self.count; |
| 1019 | self.count = i + 1; |
| 1020 | if (self.f)(v) { |
| 1021 | return Some(i); |
| 1022 | } |
| 1023 | } |
| 1024 | None |
| 1025 | } |
| 1026 | |
| 1027 | fn size_hint(&self) -> (usize, Option<usize>) { |
| 1028 | (0, self.iter.size_hint().1) |
| 1029 | } |
| 1030 | } |
| 1031 | |
| 1032 | impl<I, F> DoubleEndedIterator for Positions<I, F> |
| 1033 | where I: DoubleEndedIterator + ExactSizeIterator, |
| 1034 | F: FnMut(I::Item) -> bool, |
| 1035 | { |
| 1036 | fn next_back(&mut self) -> Option<Self::Item> { |
| 1037 | while let Some(v) = self.iter.next_back() { |
| 1038 | if (self.f)(v) { |
| 1039 | return Some(self.count + self.iter.len()) |
| 1040 | } |
| 1041 | } |
| 1042 | None |
| 1043 | } |
| 1044 | } |
| 1045 | |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 1046 | impl<I, F> FusedIterator for Positions<I, F> |
| 1047 | where I: FusedIterator, |
| 1048 | F: FnMut(I::Item) -> bool, |
| 1049 | {} |
| 1050 | |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 1051 | /// An iterator adapter to apply a mutating function to each element before yielding it. |
| 1052 | /// |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 1053 | /// See [`.update()`](crate::Itertools::update) for more information. |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 1054 | #[derive(Clone)] |
| 1055 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
| 1056 | pub struct Update<I, F> { |
| 1057 | iter: I, |
| 1058 | f: F, |
| 1059 | } |
| 1060 | |
| 1061 | /// Create a new `Update` iterator. |
| 1062 | pub fn update<I, F>(iter: I, f: F) -> Update<I, F> |
| 1063 | where |
| 1064 | I: Iterator, |
| 1065 | F: FnMut(&mut I::Item), |
| 1066 | { |
| 1067 | Update { iter, f } |
| 1068 | } |
| 1069 | |
| 1070 | impl<I, F> Iterator for Update<I, F> |
| 1071 | where |
| 1072 | I: Iterator, |
| 1073 | F: FnMut(&mut I::Item), |
| 1074 | { |
| 1075 | type Item = I::Item; |
| 1076 | |
| 1077 | fn next(&mut self) -> Option<Self::Item> { |
| 1078 | if let Some(mut v) = self.iter.next() { |
| 1079 | (self.f)(&mut v); |
| 1080 | Some(v) |
| 1081 | } else { |
| 1082 | None |
| 1083 | } |
| 1084 | } |
| 1085 | |
| 1086 | fn size_hint(&self) -> (usize, Option<usize>) { |
| 1087 | self.iter.size_hint() |
| 1088 | } |
| 1089 | |
| 1090 | fn fold<Acc, G>(self, init: Acc, mut g: G) -> Acc |
| 1091 | where G: FnMut(Acc, Self::Item) -> Acc, |
| 1092 | { |
| 1093 | let mut f = self.f; |
| 1094 | self.iter.fold(init, move |acc, mut v| { f(&mut v); g(acc, v) }) |
| 1095 | } |
| 1096 | |
| 1097 | // if possible, re-use inner iterator specializations in collect |
| 1098 | fn collect<C>(self) -> C |
| 1099 | where C: FromIterator<Self::Item> |
| 1100 | { |
| 1101 | let mut f = self.f; |
| 1102 | self.iter.map(move |mut v| { f(&mut v); v }).collect() |
| 1103 | } |
| 1104 | } |
| 1105 | |
| 1106 | impl<I, F> ExactSizeIterator for Update<I, F> |
| 1107 | where |
| 1108 | I: ExactSizeIterator, |
| 1109 | F: FnMut(&mut I::Item), |
| 1110 | {} |
| 1111 | |
| 1112 | impl<I, F> DoubleEndedIterator for Update<I, F> |
| 1113 | where |
| 1114 | I: DoubleEndedIterator, |
| 1115 | F: FnMut(&mut I::Item), |
| 1116 | { |
| 1117 | fn next_back(&mut self) -> Option<Self::Item> { |
| 1118 | if let Some(mut v) = self.iter.next_back() { |
| 1119 | (self.f)(&mut v); |
| 1120 | Some(v) |
| 1121 | } else { |
| 1122 | None |
| 1123 | } |
| 1124 | } |
| 1125 | } |
Joel Galenson | b593e25 | 2021-06-21 13:15:57 -0700 | [diff] [blame] | 1126 | |
| 1127 | impl<I, F> FusedIterator for Update<I, F> |
| 1128 | where |
| 1129 | I: FusedIterator, |
| 1130 | F: FnMut(&mut I::Item), |
| 1131 | {} |