1 //! Traits for writing parallel programs using an iterator-style interface 2 //! 3 //! You will rarely need to interact with this module directly unless you have 4 //! need to name one of the iterator types. 5 //! 6 //! Parallel iterators make it easy to write iterator-like chains that 7 //! execute in parallel: typically all you have to do is convert the 8 //! first `.iter()` (or `iter_mut()`, `into_iter()`, etc) method into 9 //! `par_iter()` (or `par_iter_mut()`, `into_par_iter()`, etc). For 10 //! example, to compute the sum of the squares of a sequence of 11 //! integers, one might write: 12 //! 13 //! ```rust 14 //! use rayon::prelude::*; 15 //! fn sum_of_squares(input: &[i32]) -> i32 { 16 //! input.par_iter() 17 //! .map(|i| i * i) 18 //! .sum() 19 //! } 20 //! ``` 21 //! 22 //! Or, to increment all the integers in a slice, you could write: 23 //! 24 //! ```rust 25 //! use rayon::prelude::*; 26 //! fn increment_all(input: &mut [i32]) { 27 //! input.par_iter_mut() 28 //! .for_each(|p| *p += 1); 29 //! } 30 //! ``` 31 //! 32 //! To use parallel iterators, first import the traits by adding 33 //! something like `use rayon::prelude::*` to your module. You can 34 //! then call `par_iter`, `par_iter_mut`, or `into_par_iter` to get a 35 //! parallel iterator. Like a [regular iterator][], parallel 36 //! iterators work by first constructing a computation and then 37 //! executing it. 38 //! 39 //! In addition to `par_iter()` and friends, some types offer other 40 //! ways to create (or consume) parallel iterators: 41 //! 42 //! - Slices (`&[T]`, `&mut [T]`) offer methods like `par_split` and 43 //! `par_windows`, as well as various parallel sorting 44 //! operations. See [the `ParallelSlice` trait] for the full list. 45 //! - Strings (`&str`) offer methods like `par_split` and `par_lines`. 46 //! See [the `ParallelString` trait] for the full list. 47 //! - Various collections offer [`par_extend`], which grows a 48 //! collection given a parallel iterator. (If you don't have a 49 //! collection to extend, you can use [`collect()`] to create a new 50 //! one from scratch.) 51 //! 52 //! [the `ParallelSlice` trait]: ../slice/trait.ParallelSlice.html 53 //! [the `ParallelString` trait]: ../str/trait.ParallelString.html 54 //! [`par_extend`]: trait.ParallelExtend.html 55 //! [`collect()`]: trait.ParallelIterator.html#method.collect 56 //! 57 //! To see the full range of methods available on parallel iterators, 58 //! check out the [`ParallelIterator`] and [`IndexedParallelIterator`] 59 //! traits. 60 //! 61 //! If you'd like to build a custom parallel iterator, or to write your own 62 //! combinator, then check out the [split] function and the [plumbing] module. 63 //! 64 //! [regular iterator]: http://doc.rust-lang.org/std/iter/trait.Iterator.html 65 //! [`ParallelIterator`]: trait.ParallelIterator.html 66 //! [`IndexedParallelIterator`]: trait.IndexedParallelIterator.html 67 //! [split]: fn.split.html 68 //! [plumbing]: plumbing/index.html 69 //! 70 //! Note: Several of the `ParallelIterator` methods rely on a `Try` trait which 71 //! has been deliberately obscured from the public API. This trait is intended 72 //! to mirror the unstable `std::ops::Try` with implementations for `Option` and 73 //! `Result`, where `Some`/`Ok` values will let those iterators continue, but 74 //! `None`/`Err` values will exit early. 75 //! 76 //! A note about object safety: It is currently _not_ possible to wrap 77 //! a `ParallelIterator` (or any trait that depends on it) using a 78 //! `Box<dyn ParallelIterator>` or other kind of dynamic allocation, 79 //! because `ParallelIterator` is **not object-safe**. 80 //! (This keeps the implementation simpler and allows extra optimizations.) 81 82 use self::plumbing::*; 83 use self::private::Try; 84 pub use either::Either; 85 use std::cmp::{self, Ordering}; 86 use std::iter::{Product, Sum}; 87 use std::ops::Fn; 88 89 // There is a method to the madness here: 90 // 91 // - Most of these modules are private but expose certain types to the end-user 92 // (e.g., `enumerate::Enumerate`) -- specifically, the types that appear in the 93 // public API surface of the `ParallelIterator` traits. 94 // - In **this** module, those public types are always used unprefixed, which forces 95 // us to add a `pub use` and helps identify if we missed anything. 96 // - In contrast, items that appear **only** in the body of a method, 97 // e.g. `find::find()`, are always used **prefixed**, so that they 98 // can be readily distinguished. 99 100 mod par_bridge; 101 pub use self::par_bridge::{IterBridge, ParallelBridge}; 102 103 mod chain; 104 mod find; 105 mod find_first_last; 106 pub use self::chain::Chain; 107 mod chunks; 108 pub use self::chunks::Chunks; 109 mod collect; 110 mod enumerate; 111 pub use self::enumerate::Enumerate; 112 mod filter; 113 pub use self::filter::Filter; 114 mod filter_map; 115 pub use self::filter_map::FilterMap; 116 mod flat_map; 117 pub use self::flat_map::FlatMap; 118 mod flatten; 119 pub use self::flatten::Flatten; 120 mod fold; 121 mod for_each; 122 mod from_par_iter; 123 pub mod plumbing; 124 pub use self::fold::{Fold, FoldWith}; 125 mod try_fold; 126 pub use self::try_fold::{TryFold, TryFoldWith}; 127 mod reduce; 128 mod skip; 129 mod try_reduce; 130 mod try_reduce_with; 131 pub use self::skip::Skip; 132 mod splitter; 133 pub use self::splitter::{split, Split}; 134 mod take; 135 pub use self::take::Take; 136 mod map; 137 pub use self::map::Map; 138 mod map_with; 139 pub use self::map_with::{MapInit, MapWith}; 140 mod zip; 141 pub use self::zip::Zip; 142 mod zip_eq; 143 pub use self::zip_eq::ZipEq; 144 mod multizip; 145 pub use self::multizip::MultiZip; 146 mod interleave; 147 pub use self::interleave::Interleave; 148 mod interleave_shortest; 149 pub use self::interleave_shortest::InterleaveShortest; 150 mod intersperse; 151 pub use self::intersperse::Intersperse; 152 mod update; 153 pub use self::update::Update; 154 155 mod noop; 156 mod rev; 157 pub use self::rev::Rev; 158 mod len; 159 pub use self::len::{MaxLen, MinLen}; 160 161 mod cloned; 162 pub use self::cloned::Cloned; 163 mod copied; 164 pub use self::copied::Copied; 165 166 mod product; 167 mod sum; 168 169 mod inspect; 170 pub use self::inspect::Inspect; 171 mod panic_fuse; 172 pub use self::panic_fuse::PanicFuse; 173 mod while_some; 174 pub use self::while_some::WhileSome; 175 mod extend; 176 mod repeat; 177 mod unzip; 178 pub use self::repeat::{repeat, Repeat}; 179 pub use self::repeat::{repeatn, RepeatN}; 180 181 mod empty; 182 pub use self::empty::{empty, Empty}; 183 mod once; 184 pub use self::once::{once, Once}; 185 186 #[cfg(test)] 187 mod test; 188 189 /// `IntoParallelIterator` implements the conversion to a [`ParallelIterator`]. 190 /// 191 /// By implementing `IntoParallelIterator` for a type, you define how it will 192 /// transformed into an iterator. This is a parallel version of the standard 193 /// library's [`std::iter::IntoIterator`] trait. 194 /// 195 /// [`ParallelIterator`]: trait.ParallelIterator.html 196 /// [`std::iter::IntoIterator`]: https://doc.rust-lang.org/std/iter/trait.IntoIterator.html 197 pub trait IntoParallelIterator { 198 /// The parallel iterator type that will be created. 199 type Iter: ParallelIterator<Item = Self::Item>; 200 201 /// The type of item that the parallel iterator will produce. 202 type Item: Send; 203 204 /// Converts `self` into a parallel iterator. 205 /// 206 /// # Examples 207 /// 208 /// ``` 209 /// use rayon::prelude::*; 210 /// 211 /// println!("counting in parallel:"); 212 /// (0..100).into_par_iter() 213 /// .for_each(|i| println!("{}", i)); 214 /// ``` 215 /// 216 /// This conversion is often implicit for arguments to methods like [`zip`]. 217 /// 218 /// ``` 219 /// use rayon::prelude::*; 220 /// 221 /// let v: Vec<_> = (0..5).into_par_iter().zip(5..10).collect(); 222 /// assert_eq!(v, [(0, 5), (1, 6), (2, 7), (3, 8), (4, 9)]); 223 /// ``` 224 /// 225 /// [`zip`]: trait.IndexedParallelIterator.html#method.zip into_par_iter(self) -> Self::Iter226 fn into_par_iter(self) -> Self::Iter; 227 } 228 229 /// `IntoParallelRefIterator` implements the conversion to a 230 /// [`ParallelIterator`], providing shared references to the data. 231 /// 232 /// This is a parallel version of the `iter()` method 233 /// defined by various collections. 234 /// 235 /// This trait is automatically implemented 236 /// `for I where &I: IntoParallelIterator`. In most cases, users 237 /// will want to implement [`IntoParallelIterator`] rather than implement 238 /// this trait directly. 239 /// 240 /// [`ParallelIterator`]: trait.ParallelIterator.html 241 /// [`IntoParallelIterator`]: trait.IntoParallelIterator.html 242 pub trait IntoParallelRefIterator<'data> { 243 /// The type of the parallel iterator that will be returned. 244 type Iter: ParallelIterator<Item = Self::Item>; 245 246 /// The type of item that the parallel iterator will produce. 247 /// This will typically be an `&'data T` reference type. 248 type Item: Send + 'data; 249 250 /// Converts `self` into a parallel iterator. 251 /// 252 /// # Examples 253 /// 254 /// ``` 255 /// use rayon::prelude::*; 256 /// 257 /// let v: Vec<_> = (0..100).collect(); 258 /// assert_eq!(v.par_iter().sum::<i32>(), 100 * 99 / 2); 259 /// 260 /// // `v.par_iter()` is shorthand for `(&v).into_par_iter()`, 261 /// // producing the exact same references. 262 /// assert!(v.par_iter().zip(&v) 263 /// .all(|(a, b)| std::ptr::eq(a, b))); 264 /// ``` par_iter(&'data self) -> Self::Iter265 fn par_iter(&'data self) -> Self::Iter; 266 } 267 268 impl<'data, I: 'data + ?Sized> IntoParallelRefIterator<'data> for I 269 where 270 &'data I: IntoParallelIterator, 271 { 272 type Iter = <&'data I as IntoParallelIterator>::Iter; 273 type Item = <&'data I as IntoParallelIterator>::Item; 274 par_iter(&'data self) -> Self::Iter275 fn par_iter(&'data self) -> Self::Iter { 276 self.into_par_iter() 277 } 278 } 279 280 /// `IntoParallelRefMutIterator` implements the conversion to a 281 /// [`ParallelIterator`], providing mutable references to the data. 282 /// 283 /// This is a parallel version of the `iter_mut()` method 284 /// defined by various collections. 285 /// 286 /// This trait is automatically implemented 287 /// `for I where &mut I: IntoParallelIterator`. In most cases, users 288 /// will want to implement [`IntoParallelIterator`] rather than implement 289 /// this trait directly. 290 /// 291 /// [`ParallelIterator`]: trait.ParallelIterator.html 292 /// [`IntoParallelIterator`]: trait.IntoParallelIterator.html 293 pub trait IntoParallelRefMutIterator<'data> { 294 /// The type of iterator that will be created. 295 type Iter: ParallelIterator<Item = Self::Item>; 296 297 /// The type of item that will be produced; this is typically an 298 /// `&'data mut T` reference. 299 type Item: Send + 'data; 300 301 /// Creates the parallel iterator from `self`. 302 /// 303 /// # Examples 304 /// 305 /// ``` 306 /// use rayon::prelude::*; 307 /// 308 /// let mut v = vec![0usize; 5]; 309 /// v.par_iter_mut().enumerate().for_each(|(i, x)| *x = i); 310 /// assert_eq!(v, [0, 1, 2, 3, 4]); 311 /// ``` par_iter_mut(&'data mut self) -> Self::Iter312 fn par_iter_mut(&'data mut self) -> Self::Iter; 313 } 314 315 impl<'data, I: 'data + ?Sized> IntoParallelRefMutIterator<'data> for I 316 where 317 &'data mut I: IntoParallelIterator, 318 { 319 type Iter = <&'data mut I as IntoParallelIterator>::Iter; 320 type Item = <&'data mut I as IntoParallelIterator>::Item; 321 par_iter_mut(&'data mut self) -> Self::Iter322 fn par_iter_mut(&'data mut self) -> Self::Iter { 323 self.into_par_iter() 324 } 325 } 326 327 /// Parallel version of the standard iterator trait. 328 /// 329 /// The combinators on this trait are available on **all** parallel 330 /// iterators. Additional methods can be found on the 331 /// [`IndexedParallelIterator`] trait: those methods are only 332 /// available for parallel iterators where the number of items is 333 /// known in advance (so, e.g., after invoking `filter`, those methods 334 /// become unavailable). 335 /// 336 /// For examples of using parallel iterators, see [the docs on the 337 /// `iter` module][iter]. 338 /// 339 /// [iter]: index.html 340 /// [`IndexedParallelIterator`]: trait.IndexedParallelIterator.html 341 pub trait ParallelIterator: Sized + Send { 342 /// The type of item that this parallel iterator produces. 343 /// For example, if you use the [`for_each`] method, this is the type of 344 /// item that your closure will be invoked with. 345 /// 346 /// [`for_each`]: #method.for_each 347 type Item: Send; 348 349 /// Executes `OP` on each item produced by the iterator, in parallel. 350 /// 351 /// # Examples 352 /// 353 /// ``` 354 /// use rayon::prelude::*; 355 /// 356 /// (0..100).into_par_iter().for_each(|x| println!("{:?}", x)); 357 /// ``` for_each<OP>(self, op: OP) where OP: Fn(Self::Item) + Sync + Send,358 fn for_each<OP>(self, op: OP) 359 where 360 OP: Fn(Self::Item) + Sync + Send, 361 { 362 for_each::for_each(self, &op) 363 } 364 365 /// Executes `OP` on the given `init` value with each item produced by 366 /// the iterator, in parallel. 367 /// 368 /// The `init` value will be cloned only as needed to be paired with 369 /// the group of items in each rayon job. It does not require the type 370 /// to be `Sync`. 371 /// 372 /// # Examples 373 /// 374 /// ``` 375 /// use std::sync::mpsc::channel; 376 /// use rayon::prelude::*; 377 /// 378 /// let (sender, receiver) = channel(); 379 /// 380 /// (0..5).into_par_iter().for_each_with(sender, |s, x| s.send(x).unwrap()); 381 /// 382 /// let mut res: Vec<_> = receiver.iter().collect(); 383 /// 384 /// res.sort(); 385 /// 386 /// assert_eq!(&res[..], &[0, 1, 2, 3, 4]) 387 /// ``` for_each_with<OP, T>(self, init: T, op: OP) where OP: Fn(&mut T, Self::Item) + Sync + Send, T: Send + Clone,388 fn for_each_with<OP, T>(self, init: T, op: OP) 389 where 390 OP: Fn(&mut T, Self::Item) + Sync + Send, 391 T: Send + Clone, 392 { 393 self.map_with(init, op).collect() 394 } 395 396 /// Executes `OP` on a value returned by `init` with each item produced by 397 /// the iterator, in parallel. 398 /// 399 /// The `init` function will be called only as needed for a value to be 400 /// paired with the group of items in each rayon job. There is no 401 /// constraint on that returned type at all! 402 /// 403 /// # Examples 404 /// 405 /// ``` 406 /// use rand::Rng; 407 /// use rayon::prelude::*; 408 /// 409 /// let mut v = vec![0u8; 1_000_000]; 410 /// 411 /// v.par_chunks_mut(1000) 412 /// .for_each_init( 413 /// || rand::thread_rng(), 414 /// |rng, chunk| rng.fill(chunk), 415 /// ); 416 /// 417 /// // There's a remote chance that this will fail... 418 /// for i in 0u8..=255 { 419 /// assert!(v.contains(&i)); 420 /// } 421 /// ``` for_each_init<OP, INIT, T>(self, init: INIT, op: OP) where OP: Fn(&mut T, Self::Item) + Sync + Send, INIT: Fn() -> T + Sync + Send,422 fn for_each_init<OP, INIT, T>(self, init: INIT, op: OP) 423 where 424 OP: Fn(&mut T, Self::Item) + Sync + Send, 425 INIT: Fn() -> T + Sync + Send, 426 { 427 self.map_init(init, op).collect() 428 } 429 430 /// Executes a fallible `OP` on each item produced by the iterator, in parallel. 431 /// 432 /// If the `OP` returns `Result::Err` or `Option::None`, we will attempt to 433 /// stop processing the rest of the items in the iterator as soon as 434 /// possible, and we will return that terminating value. Otherwise, we will 435 /// return an empty `Result::Ok(())` or `Option::Some(())`. If there are 436 /// multiple errors in parallel, it is not specified which will be returned. 437 /// 438 /// # Examples 439 /// 440 /// ``` 441 /// use rayon::prelude::*; 442 /// use std::io::{self, Write}; 443 /// 444 /// // This will stop iteration early if there's any write error, like 445 /// // having piped output get closed on the other end. 446 /// (0..100).into_par_iter() 447 /// .try_for_each(|x| writeln!(io::stdout(), "{:?}", x)) 448 /// .expect("expected no write errors"); 449 /// ``` try_for_each<OP, R>(self, op: OP) -> R where OP: Fn(Self::Item) -> R + Sync + Send, R: Try<Ok = ()> + Send,450 fn try_for_each<OP, R>(self, op: OP) -> R 451 where 452 OP: Fn(Self::Item) -> R + Sync + Send, 453 R: Try<Ok = ()> + Send, 454 { 455 fn ok<R: Try<Ok = ()>>(_: (), _: ()) -> R { 456 R::from_ok(()) 457 } 458 459 self.map(op).try_reduce(<()>::default, ok) 460 } 461 462 /// Executes a fallible `OP` on the given `init` value with each item 463 /// produced by the iterator, in parallel. 464 /// 465 /// This combines the `init` semantics of [`for_each_with()`] and the 466 /// failure semantics of [`try_for_each()`]. 467 /// 468 /// [`for_each_with()`]: #method.for_each_with 469 /// [`try_for_each()`]: #method.try_for_each 470 /// 471 /// # Examples 472 /// 473 /// ``` 474 /// use std::sync::mpsc::channel; 475 /// use rayon::prelude::*; 476 /// 477 /// let (sender, receiver) = channel(); 478 /// 479 /// (0..5).into_par_iter() 480 /// .try_for_each_with(sender, |s, x| s.send(x)) 481 /// .expect("expected no send errors"); 482 /// 483 /// let mut res: Vec<_> = receiver.iter().collect(); 484 /// 485 /// res.sort(); 486 /// 487 /// assert_eq!(&res[..], &[0, 1, 2, 3, 4]) 488 /// ``` try_for_each_with<OP, T, R>(self, init: T, op: OP) -> R where OP: Fn(&mut T, Self::Item) -> R + Sync + Send, T: Send + Clone, R: Try<Ok = ()> + Send,489 fn try_for_each_with<OP, T, R>(self, init: T, op: OP) -> R 490 where 491 OP: Fn(&mut T, Self::Item) -> R + Sync + Send, 492 T: Send + Clone, 493 R: Try<Ok = ()> + Send, 494 { 495 fn ok<R: Try<Ok = ()>>(_: (), _: ()) -> R { 496 R::from_ok(()) 497 } 498 499 self.map_with(init, op).try_reduce(<()>::default, ok) 500 } 501 502 /// Executes a fallible `OP` on a value returned by `init` with each item 503 /// produced by the iterator, in parallel. 504 /// 505 /// This combines the `init` semantics of [`for_each_init()`] and the 506 /// failure semantics of [`try_for_each()`]. 507 /// 508 /// [`for_each_init()`]: #method.for_each_init 509 /// [`try_for_each()`]: #method.try_for_each 510 /// 511 /// # Examples 512 /// 513 /// ``` 514 /// use rand::Rng; 515 /// use rayon::prelude::*; 516 /// 517 /// let mut v = vec![0u8; 1_000_000]; 518 /// 519 /// v.par_chunks_mut(1000) 520 /// .try_for_each_init( 521 /// || rand::thread_rng(), 522 /// |rng, chunk| rng.try_fill(chunk), 523 /// ) 524 /// .expect("expected no rand errors"); 525 /// 526 /// // There's a remote chance that this will fail... 527 /// for i in 0u8..=255 { 528 /// assert!(v.contains(&i)); 529 /// } 530 /// ``` try_for_each_init<OP, INIT, T, R>(self, init: INIT, op: OP) -> R where OP: Fn(&mut T, Self::Item) -> R + Sync + Send, INIT: Fn() -> T + Sync + Send, R: Try<Ok = ()> + Send,531 fn try_for_each_init<OP, INIT, T, R>(self, init: INIT, op: OP) -> R 532 where 533 OP: Fn(&mut T, Self::Item) -> R + Sync + Send, 534 INIT: Fn() -> T + Sync + Send, 535 R: Try<Ok = ()> + Send, 536 { 537 fn ok<R: Try<Ok = ()>>(_: (), _: ()) -> R { 538 R::from_ok(()) 539 } 540 541 self.map_init(init, op).try_reduce(<()>::default, ok) 542 } 543 544 /// Counts the number of items in this parallel iterator. 545 /// 546 /// # Examples 547 /// 548 /// ``` 549 /// use rayon::prelude::*; 550 /// 551 /// let count = (0..100).into_par_iter().count(); 552 /// 553 /// assert_eq!(count, 100); 554 /// ``` count(self) -> usize555 fn count(self) -> usize { 556 fn one<T>(_: T) -> usize { 557 1 558 } 559 560 self.map(one).sum() 561 } 562 563 /// Applies `map_op` to each item of this iterator, producing a new 564 /// iterator with the results. 565 /// 566 /// # Examples 567 /// 568 /// ``` 569 /// use rayon::prelude::*; 570 /// 571 /// let mut par_iter = (0..5).into_par_iter().map(|x| x * 2); 572 /// 573 /// let doubles: Vec<_> = par_iter.collect(); 574 /// 575 /// assert_eq!(&doubles[..], &[0, 2, 4, 6, 8]); 576 /// ``` map<F, R>(self, map_op: F) -> Map<Self, F> where F: Fn(Self::Item) -> R + Sync + Send, R: Send,577 fn map<F, R>(self, map_op: F) -> Map<Self, F> 578 where 579 F: Fn(Self::Item) -> R + Sync + Send, 580 R: Send, 581 { 582 Map::new(self, map_op) 583 } 584 585 /// Applies `map_op` to the given `init` value with each item of this 586 /// iterator, producing a new iterator with the results. 587 /// 588 /// The `init` value will be cloned only as needed to be paired with 589 /// the group of items in each rayon job. It does not require the type 590 /// to be `Sync`. 591 /// 592 /// # Examples 593 /// 594 /// ``` 595 /// use std::sync::mpsc::channel; 596 /// use rayon::prelude::*; 597 /// 598 /// let (sender, receiver) = channel(); 599 /// 600 /// let a: Vec<_> = (0..5) 601 /// .into_par_iter() // iterating over i32 602 /// .map_with(sender, |s, x| { 603 /// s.send(x).unwrap(); // sending i32 values through the channel 604 /// x // returning i32 605 /// }) 606 /// .collect(); // collecting the returned values into a vector 607 /// 608 /// let mut b: Vec<_> = receiver.iter() // iterating over the values in the channel 609 /// .collect(); // and collecting them 610 /// b.sort(); 611 /// 612 /// assert_eq!(a, b); 613 /// ``` map_with<F, T, R>(self, init: T, map_op: F) -> MapWith<Self, T, F> where F: Fn(&mut T, Self::Item) -> R + Sync + Send, T: Send + Clone, R: Send,614 fn map_with<F, T, R>(self, init: T, map_op: F) -> MapWith<Self, T, F> 615 where 616 F: Fn(&mut T, Self::Item) -> R + Sync + Send, 617 T: Send + Clone, 618 R: Send, 619 { 620 MapWith::new(self, init, map_op) 621 } 622 623 /// Applies `map_op` to a value returned by `init` with each item of this 624 /// iterator, producing a new iterator with the results. 625 /// 626 /// The `init` function will be called only as needed for a value to be 627 /// paired with the group of items in each rayon job. There is no 628 /// constraint on that returned type at all! 629 /// 630 /// # Examples 631 /// 632 /// ``` 633 /// use rand::Rng; 634 /// use rayon::prelude::*; 635 /// 636 /// let a: Vec<_> = (1i32..1_000_000) 637 /// .into_par_iter() 638 /// .map_init( 639 /// || rand::thread_rng(), // get the thread-local RNG 640 /// |rng, x| if rng.gen() { // randomly negate items 641 /// -x 642 /// } else { 643 /// x 644 /// }, 645 /// ).collect(); 646 /// 647 /// // There's a remote chance that this will fail... 648 /// assert!(a.iter().any(|&x| x < 0)); 649 /// assert!(a.iter().any(|&x| x > 0)); 650 /// ``` map_init<F, INIT, T, R>(self, init: INIT, map_op: F) -> MapInit<Self, INIT, F> where F: Fn(&mut T, Self::Item) -> R + Sync + Send, INIT: Fn() -> T + Sync + Send, R: Send,651 fn map_init<F, INIT, T, R>(self, init: INIT, map_op: F) -> MapInit<Self, INIT, F> 652 where 653 F: Fn(&mut T, Self::Item) -> R + Sync + Send, 654 INIT: Fn() -> T + Sync + Send, 655 R: Send, 656 { 657 MapInit::new(self, init, map_op) 658 } 659 660 /// Creates an iterator which clones all of its elements. This may be 661 /// useful when you have an iterator over `&T`, but you need `T`, and 662 /// that type implements `Clone`. See also [`copied()`]. 663 /// 664 /// [`copied()`]: #method.copied 665 /// 666 /// # Examples 667 /// 668 /// ``` 669 /// use rayon::prelude::*; 670 /// 671 /// let a = [1, 2, 3]; 672 /// 673 /// let v_cloned: Vec<_> = a.par_iter().cloned().collect(); 674 /// 675 /// // cloned is the same as .map(|&x| x), for integers 676 /// let v_map: Vec<_> = a.par_iter().map(|&x| x).collect(); 677 /// 678 /// assert_eq!(v_cloned, vec![1, 2, 3]); 679 /// assert_eq!(v_map, vec![1, 2, 3]); 680 /// ``` cloned<'a, T>(self) -> Cloned<Self> where T: 'a + Clone + Send, Self: ParallelIterator<Item = &'a T>,681 fn cloned<'a, T>(self) -> Cloned<Self> 682 where 683 T: 'a + Clone + Send, 684 Self: ParallelIterator<Item = &'a T>, 685 { 686 Cloned::new(self) 687 } 688 689 /// Creates an iterator which copies all of its elements. This may be 690 /// useful when you have an iterator over `&T`, but you need `T`, and 691 /// that type implements `Copy`. See also [`cloned()`]. 692 /// 693 /// [`cloned()`]: #method.cloned 694 /// 695 /// # Examples 696 /// 697 /// ``` 698 /// use rayon::prelude::*; 699 /// 700 /// let a = [1, 2, 3]; 701 /// 702 /// let v_copied: Vec<_> = a.par_iter().copied().collect(); 703 /// 704 /// // copied is the same as .map(|&x| x), for integers 705 /// let v_map: Vec<_> = a.par_iter().map(|&x| x).collect(); 706 /// 707 /// assert_eq!(v_copied, vec![1, 2, 3]); 708 /// assert_eq!(v_map, vec![1, 2, 3]); 709 /// ``` copied<'a, T>(self) -> Copied<Self> where T: 'a + Copy + Send, Self: ParallelIterator<Item = &'a T>,710 fn copied<'a, T>(self) -> Copied<Self> 711 where 712 T: 'a + Copy + Send, 713 Self: ParallelIterator<Item = &'a T>, 714 { 715 Copied::new(self) 716 } 717 718 /// Applies `inspect_op` to a reference to each item of this iterator, 719 /// producing a new iterator passing through the original items. This is 720 /// often useful for debugging to see what's happening in iterator stages. 721 /// 722 /// # Examples 723 /// 724 /// ``` 725 /// use rayon::prelude::*; 726 /// 727 /// let a = [1, 4, 2, 3]; 728 /// 729 /// // this iterator sequence is complex. 730 /// let sum = a.par_iter() 731 /// .cloned() 732 /// .filter(|&x| x % 2 == 0) 733 /// .reduce(|| 0, |sum, i| sum + i); 734 /// 735 /// println!("{}", sum); 736 /// 737 /// // let's add some inspect() calls to investigate what's happening 738 /// let sum = a.par_iter() 739 /// .cloned() 740 /// .inspect(|x| println!("about to filter: {}", x)) 741 /// .filter(|&x| x % 2 == 0) 742 /// .inspect(|x| println!("made it through filter: {}", x)) 743 /// .reduce(|| 0, |sum, i| sum + i); 744 /// 745 /// println!("{}", sum); 746 /// ``` inspect<OP>(self, inspect_op: OP) -> Inspect<Self, OP> where OP: Fn(&Self::Item) + Sync + Send,747 fn inspect<OP>(self, inspect_op: OP) -> Inspect<Self, OP> 748 where 749 OP: Fn(&Self::Item) + Sync + Send, 750 { 751 Inspect::new(self, inspect_op) 752 } 753 754 /// Mutates each item of this iterator before yielding it. 755 /// 756 /// # Examples 757 /// 758 /// ``` 759 /// use rayon::prelude::*; 760 /// 761 /// let par_iter = (0..5).into_par_iter().update(|x| {*x *= 2;}); 762 /// 763 /// let doubles: Vec<_> = par_iter.collect(); 764 /// 765 /// assert_eq!(&doubles[..], &[0, 2, 4, 6, 8]); 766 /// ``` update<F>(self, update_op: F) -> Update<Self, F> where F: Fn(&mut Self::Item) + Sync + Send,767 fn update<F>(self, update_op: F) -> Update<Self, F> 768 where 769 F: Fn(&mut Self::Item) + Sync + Send, 770 { 771 Update::new(self, update_op) 772 } 773 774 /// Applies `filter_op` to each item of this iterator, producing a new 775 /// iterator with only the items that gave `true` results. 776 /// 777 /// # Examples 778 /// 779 /// ``` 780 /// use rayon::prelude::*; 781 /// 782 /// let mut par_iter = (0..10).into_par_iter().filter(|x| x % 2 == 0); 783 /// 784 /// let even_numbers: Vec<_> = par_iter.collect(); 785 /// 786 /// assert_eq!(&even_numbers[..], &[0, 2, 4, 6, 8]); 787 /// ``` filter<P>(self, filter_op: P) -> Filter<Self, P> where P: Fn(&Self::Item) -> bool + Sync + Send,788 fn filter<P>(self, filter_op: P) -> Filter<Self, P> 789 where 790 P: Fn(&Self::Item) -> bool + Sync + Send, 791 { 792 Filter::new(self, filter_op) 793 } 794 795 /// Applies `filter_op` to each item of this iterator to get an `Option`, 796 /// producing a new iterator with only the items from `Some` results. 797 /// 798 /// # Examples 799 /// 800 /// ``` 801 /// use rayon::prelude::*; 802 /// 803 /// let mut par_iter = (0..10).into_par_iter() 804 /// .filter_map(|x| { 805 /// if x % 2 == 0 { Some(x * 3) } 806 /// else { None } 807 /// }); 808 /// 809 /// let even_numbers: Vec<_> = par_iter.collect(); 810 /// 811 /// assert_eq!(&even_numbers[..], &[0, 6, 12, 18, 24]); 812 /// ``` filter_map<P, R>(self, filter_op: P) -> FilterMap<Self, P> where P: Fn(Self::Item) -> Option<R> + Sync + Send, R: Send,813 fn filter_map<P, R>(self, filter_op: P) -> FilterMap<Self, P> 814 where 815 P: Fn(Self::Item) -> Option<R> + Sync + Send, 816 R: Send, 817 { 818 FilterMap::new(self, filter_op) 819 } 820 821 /// Applies `map_op` to each item of this iterator to get nested iterators, 822 /// producing a new iterator that flattens these back into one. 823 /// 824 /// # Examples 825 /// 826 /// ``` 827 /// use rayon::prelude::*; 828 /// 829 /// let a = [[1, 2], [3, 4], [5, 6], [7, 8]]; 830 /// 831 /// let par_iter = a.par_iter().cloned().flat_map(|a| a.to_vec()); 832 /// 833 /// let vec: Vec<_> = par_iter.collect(); 834 /// 835 /// assert_eq!(&vec[..], &[1, 2, 3, 4, 5, 6, 7, 8]); 836 /// ``` flat_map<F, PI>(self, map_op: F) -> FlatMap<Self, F> where F: Fn(Self::Item) -> PI + Sync + Send, PI: IntoParallelIterator,837 fn flat_map<F, PI>(self, map_op: F) -> FlatMap<Self, F> 838 where 839 F: Fn(Self::Item) -> PI + Sync + Send, 840 PI: IntoParallelIterator, 841 { 842 FlatMap::new(self, map_op) 843 } 844 845 /// An adaptor that flattens iterable `Item`s into one large iterator 846 /// 847 /// # Examples 848 /// 849 /// ``` 850 /// use rayon::prelude::*; 851 /// 852 /// let x: Vec<Vec<_>> = vec![vec![1, 2], vec![3, 4]]; 853 /// let y: Vec<_> = x.into_par_iter().flatten().collect(); 854 /// 855 /// assert_eq!(y, vec![1, 2, 3, 4]); 856 /// ``` flatten(self) -> Flatten<Self> where Self::Item: IntoParallelIterator,857 fn flatten(self) -> Flatten<Self> 858 where 859 Self::Item: IntoParallelIterator, 860 { 861 Flatten::new(self) 862 } 863 864 /// Reduces the items in the iterator into one item using `op`. 865 /// The argument `identity` should be a closure that can produce 866 /// "identity" value which may be inserted into the sequence as 867 /// needed to create opportunities for parallel execution. So, for 868 /// example, if you are doing a summation, then `identity()` ought 869 /// to produce something that represents the zero for your type 870 /// (but consider just calling `sum()` in that case). 871 /// 872 /// # Examples 873 /// 874 /// ``` 875 /// // Iterate over a sequence of pairs `(x0, y0), ..., (xN, yN)` 876 /// // and use reduce to compute one pair `(x0 + ... + xN, y0 + ... + yN)` 877 /// // where the first/second elements are summed separately. 878 /// use rayon::prelude::*; 879 /// let sums = [(0, 1), (5, 6), (16, 2), (8, 9)] 880 /// .par_iter() // iterating over &(i32, i32) 881 /// .cloned() // iterating over (i32, i32) 882 /// .reduce(|| (0, 0), // the "identity" is 0 in both columns 883 /// |a, b| (a.0 + b.0, a.1 + b.1)); 884 /// assert_eq!(sums, (0 + 5 + 16 + 8, 1 + 6 + 2 + 9)); 885 /// ``` 886 /// 887 /// **Note:** unlike a sequential `fold` operation, the order in 888 /// which `op` will be applied to reduce the result is not fully 889 /// specified. So `op` should be [associative] or else the results 890 /// will be non-deterministic. And of course `identity()` should 891 /// produce a true identity. 892 /// 893 /// [associative]: https://en.wikipedia.org/wiki/Associative_property reduce<OP, ID>(self, identity: ID, op: OP) -> Self::Item where OP: Fn(Self::Item, Self::Item) -> Self::Item + Sync + Send, ID: Fn() -> Self::Item + Sync + Send,894 fn reduce<OP, ID>(self, identity: ID, op: OP) -> Self::Item 895 where 896 OP: Fn(Self::Item, Self::Item) -> Self::Item + Sync + Send, 897 ID: Fn() -> Self::Item + Sync + Send, 898 { 899 reduce::reduce(self, identity, op) 900 } 901 902 /// Reduces the items in the iterator into one item using `op`. 903 /// If the iterator is empty, `None` is returned; otherwise, 904 /// `Some` is returned. 905 /// 906 /// This version of `reduce` is simple but somewhat less 907 /// efficient. If possible, it is better to call `reduce()`, which 908 /// requires an identity element. 909 /// 910 /// # Examples 911 /// 912 /// ``` 913 /// use rayon::prelude::*; 914 /// let sums = [(0, 1), (5, 6), (16, 2), (8, 9)] 915 /// .par_iter() // iterating over &(i32, i32) 916 /// .cloned() // iterating over (i32, i32) 917 /// .reduce_with(|a, b| (a.0 + b.0, a.1 + b.1)) 918 /// .unwrap(); 919 /// assert_eq!(sums, (0 + 5 + 16 + 8, 1 + 6 + 2 + 9)); 920 /// ``` 921 /// 922 /// **Note:** unlike a sequential `fold` operation, the order in 923 /// which `op` will be applied to reduce the result is not fully 924 /// specified. So `op` should be [associative] or else the results 925 /// will be non-deterministic. 926 /// 927 /// [associative]: https://en.wikipedia.org/wiki/Associative_property reduce_with<OP>(self, op: OP) -> Option<Self::Item> where OP: Fn(Self::Item, Self::Item) -> Self::Item + Sync + Send,928 fn reduce_with<OP>(self, op: OP) -> Option<Self::Item> 929 where 930 OP: Fn(Self::Item, Self::Item) -> Self::Item + Sync + Send, 931 { 932 fn opt_fold<T>(op: impl Fn(T, T) -> T) -> impl Fn(Option<T>, T) -> Option<T> { 933 move |opt_a, b| match opt_a { 934 Some(a) => Some(op(a, b)), 935 None => Some(b), 936 } 937 } 938 939 fn opt_reduce<T>(op: impl Fn(T, T) -> T) -> impl Fn(Option<T>, Option<T>) -> Option<T> { 940 move |opt_a, opt_b| match (opt_a, opt_b) { 941 (Some(a), Some(b)) => Some(op(a, b)), 942 (Some(v), None) | (None, Some(v)) => Some(v), 943 (None, None) => None, 944 } 945 } 946 947 self.fold(<_>::default, opt_fold(&op)) 948 .reduce(<_>::default, opt_reduce(&op)) 949 } 950 951 /// Reduces the items in the iterator into one item using a fallible `op`. 952 /// The `identity` argument is used the same way as in [`reduce()`]. 953 /// 954 /// [`reduce()`]: #method.reduce 955 /// 956 /// If a `Result::Err` or `Option::None` item is found, or if `op` reduces 957 /// to one, we will attempt to stop processing the rest of the items in the 958 /// iterator as soon as possible, and we will return that terminating value. 959 /// Otherwise, we will return the final reduced `Result::Ok(T)` or 960 /// `Option::Some(T)`. If there are multiple errors in parallel, it is not 961 /// specified which will be returned. 962 /// 963 /// # Examples 964 /// 965 /// ``` 966 /// use rayon::prelude::*; 967 /// 968 /// // Compute the sum of squares, being careful about overflow. 969 /// fn sum_squares<I: IntoParallelIterator<Item = i32>>(iter: I) -> Option<i32> { 970 /// iter.into_par_iter() 971 /// .map(|i| i.checked_mul(i)) // square each item, 972 /// .try_reduce(|| 0, i32::checked_add) // and add them up! 973 /// } 974 /// assert_eq!(sum_squares(0..5), Some(0 + 1 + 4 + 9 + 16)); 975 /// 976 /// // The sum might overflow 977 /// assert_eq!(sum_squares(0..10_000), None); 978 /// 979 /// // Or the squares might overflow before it even reaches `try_reduce` 980 /// assert_eq!(sum_squares(1_000_000..1_000_001), None); 981 /// ``` try_reduce<T, OP, ID>(self, identity: ID, op: OP) -> Self::Item where OP: Fn(T, T) -> Self::Item + Sync + Send, ID: Fn() -> T + Sync + Send, Self::Item: Try<Ok = T>,982 fn try_reduce<T, OP, ID>(self, identity: ID, op: OP) -> Self::Item 983 where 984 OP: Fn(T, T) -> Self::Item + Sync + Send, 985 ID: Fn() -> T + Sync + Send, 986 Self::Item: Try<Ok = T>, 987 { 988 try_reduce::try_reduce(self, identity, op) 989 } 990 991 /// Reduces the items in the iterator into one item using a fallible `op`. 992 /// 993 /// Like [`reduce_with()`], if the iterator is empty, `None` is returned; 994 /// otherwise, `Some` is returned. Beyond that, it behaves like 995 /// [`try_reduce()`] for handling `Err`/`None`. 996 /// 997 /// [`reduce_with()`]: #method.reduce_with 998 /// [`try_reduce()`]: #method.try_reduce 999 /// 1000 /// For instance, with `Option` items, the return value may be: 1001 /// - `None`, the iterator was empty 1002 /// - `Some(None)`, we stopped after encountering `None`. 1003 /// - `Some(Some(x))`, the entire iterator reduced to `x`. 1004 /// 1005 /// With `Result` items, the nesting is more obvious: 1006 /// - `None`, the iterator was empty 1007 /// - `Some(Err(e))`, we stopped after encountering an error `e`. 1008 /// - `Some(Ok(x))`, the entire iterator reduced to `x`. 1009 /// 1010 /// # Examples 1011 /// 1012 /// ``` 1013 /// use rayon::prelude::*; 1014 /// 1015 /// let files = ["/dev/null", "/does/not/exist"]; 1016 /// 1017 /// // Find the biggest file 1018 /// files.into_par_iter() 1019 /// .map(|path| std::fs::metadata(path).map(|m| (path, m.len()))) 1020 /// .try_reduce_with(|a, b| { 1021 /// Ok(if a.1 >= b.1 { a } else { b }) 1022 /// }) 1023 /// .expect("Some value, since the iterator is not empty") 1024 /// .expect_err("not found"); 1025 /// ``` try_reduce_with<T, OP>(self, op: OP) -> Option<Self::Item> where OP: Fn(T, T) -> Self::Item + Sync + Send, Self::Item: Try<Ok = T>,1026 fn try_reduce_with<T, OP>(self, op: OP) -> Option<Self::Item> 1027 where 1028 OP: Fn(T, T) -> Self::Item + Sync + Send, 1029 Self::Item: Try<Ok = T>, 1030 { 1031 try_reduce_with::try_reduce_with(self, op) 1032 } 1033 1034 /// Parallel fold is similar to sequential fold except that the 1035 /// sequence of items may be subdivided before it is 1036 /// folded. Consider a list of numbers like `22 3 77 89 46`. If 1037 /// you used sequential fold to add them (`fold(0, |a,b| a+b)`, 1038 /// you would wind up first adding 0 + 22, then 22 + 3, then 25 + 1039 /// 77, and so forth. The **parallel fold** works similarly except 1040 /// that it first breaks up your list into sublists, and hence 1041 /// instead of yielding up a single sum at the end, it yields up 1042 /// multiple sums. The number of results is nondeterministic, as 1043 /// is the point where the breaks occur. 1044 /// 1045 /// So if did the same parallel fold (`fold(0, |a,b| a+b)`) on 1046 /// our example list, we might wind up with a sequence of two numbers, 1047 /// like so: 1048 /// 1049 /// ```notrust 1050 /// 22 3 77 89 46 1051 /// | | 1052 /// 102 135 1053 /// ``` 1054 /// 1055 /// Or perhaps these three numbers: 1056 /// 1057 /// ```notrust 1058 /// 22 3 77 89 46 1059 /// | | | 1060 /// 102 89 46 1061 /// ``` 1062 /// 1063 /// In general, Rayon will attempt to find good breaking points 1064 /// that keep all of your cores busy. 1065 /// 1066 /// ### Fold versus reduce 1067 /// 1068 /// The `fold()` and `reduce()` methods each take an identity element 1069 /// and a combining function, but they operate rather differently. 1070 /// 1071 /// `reduce()` requires that the identity function has the same 1072 /// type as the things you are iterating over, and it fully 1073 /// reduces the list of items into a single item. So, for example, 1074 /// imagine we are iterating over a list of bytes `bytes: [128_u8, 1075 /// 64_u8, 64_u8]`. If we used `bytes.reduce(|| 0_u8, |a: u8, b: 1076 /// u8| a + b)`, we would get an overflow. This is because `0`, 1077 /// `a`, and `b` here are all bytes, just like the numbers in the 1078 /// list (I wrote the types explicitly above, but those are the 1079 /// only types you can use). To avoid the overflow, we would need 1080 /// to do something like `bytes.map(|b| b as u32).reduce(|| 0, |a, 1081 /// b| a + b)`, in which case our result would be `256`. 1082 /// 1083 /// In contrast, with `fold()`, the identity function does not 1084 /// have to have the same type as the things you are iterating 1085 /// over, and you potentially get back many results. So, if we 1086 /// continue with the `bytes` example from the previous paragraph, 1087 /// we could do `bytes.fold(|| 0_u32, |a, b| a + (b as u32))` to 1088 /// convert our bytes into `u32`. And of course we might not get 1089 /// back a single sum. 1090 /// 1091 /// There is a more subtle distinction as well, though it's 1092 /// actually implied by the above points. When you use `reduce()`, 1093 /// your reduction function is sometimes called with values that 1094 /// were never part of your original parallel iterator (for 1095 /// example, both the left and right might be a partial sum). With 1096 /// `fold()`, in contrast, the left value in the fold function is 1097 /// always the accumulator, and the right value is always from 1098 /// your original sequence. 1099 /// 1100 /// ### Fold vs Map/Reduce 1101 /// 1102 /// Fold makes sense if you have some operation where it is 1103 /// cheaper to create groups of elements at a time. For example, 1104 /// imagine collecting characters into a string. If you were going 1105 /// to use map/reduce, you might try this: 1106 /// 1107 /// ``` 1108 /// use rayon::prelude::*; 1109 /// 1110 /// let s = 1111 /// ['a', 'b', 'c', 'd', 'e'] 1112 /// .par_iter() 1113 /// .map(|c: &char| format!("{}", c)) 1114 /// .reduce(|| String::new(), 1115 /// |mut a: String, b: String| { a.push_str(&b); a }); 1116 /// 1117 /// assert_eq!(s, "abcde"); 1118 /// ``` 1119 /// 1120 /// Because reduce produces the same type of element as its input, 1121 /// you have to first map each character into a string, and then 1122 /// you can reduce them. This means we create one string per 1123 /// element in our iterator -- not so great. Using `fold`, we can 1124 /// do this instead: 1125 /// 1126 /// ``` 1127 /// use rayon::prelude::*; 1128 /// 1129 /// let s = 1130 /// ['a', 'b', 'c', 'd', 'e'] 1131 /// .par_iter() 1132 /// .fold(|| String::new(), 1133 /// |mut s: String, c: &char| { s.push(*c); s }) 1134 /// .reduce(|| String::new(), 1135 /// |mut a: String, b: String| { a.push_str(&b); a }); 1136 /// 1137 /// assert_eq!(s, "abcde"); 1138 /// ``` 1139 /// 1140 /// Now `fold` will process groups of our characters at a time, 1141 /// and we only make one string per group. We should wind up with 1142 /// some small-ish number of strings roughly proportional to the 1143 /// number of CPUs you have (it will ultimately depend on how busy 1144 /// your processors are). Note that we still need to do a reduce 1145 /// afterwards to combine those groups of strings into a single 1146 /// string. 1147 /// 1148 /// You could use a similar trick to save partial results (e.g., a 1149 /// cache) or something similar. 1150 /// 1151 /// ### Combining fold with other operations 1152 /// 1153 /// You can combine `fold` with `reduce` if you want to produce a 1154 /// single value. This is then roughly equivalent to a map/reduce 1155 /// combination in effect: 1156 /// 1157 /// ``` 1158 /// use rayon::prelude::*; 1159 /// 1160 /// let bytes = 0..22_u8; 1161 /// let sum = bytes.into_par_iter() 1162 /// .fold(|| 0_u32, |a: u32, b: u8| a + (b as u32)) 1163 /// .sum::<u32>(); 1164 /// 1165 /// assert_eq!(sum, (0..22).sum()); // compare to sequential 1166 /// ``` fold<T, ID, F>(self, identity: ID, fold_op: F) -> Fold<Self, ID, F> where F: Fn(T, Self::Item) -> T + Sync + Send, ID: Fn() -> T + Sync + Send, T: Send,1167 fn fold<T, ID, F>(self, identity: ID, fold_op: F) -> Fold<Self, ID, F> 1168 where 1169 F: Fn(T, Self::Item) -> T + Sync + Send, 1170 ID: Fn() -> T + Sync + Send, 1171 T: Send, 1172 { 1173 Fold::new(self, identity, fold_op) 1174 } 1175 1176 /// Applies `fold_op` to the given `init` value with each item of this 1177 /// iterator, finally producing the value for further use. 1178 /// 1179 /// This works essentially like `fold(|| init.clone(), fold_op)`, except 1180 /// it doesn't require the `init` type to be `Sync`, nor any other form 1181 /// of added synchronization. 1182 /// 1183 /// # Examples 1184 /// 1185 /// ``` 1186 /// use rayon::prelude::*; 1187 /// 1188 /// let bytes = 0..22_u8; 1189 /// let sum = bytes.into_par_iter() 1190 /// .fold_with(0_u32, |a: u32, b: u8| a + (b as u32)) 1191 /// .sum::<u32>(); 1192 /// 1193 /// assert_eq!(sum, (0..22).sum()); // compare to sequential 1194 /// ``` fold_with<F, T>(self, init: T, fold_op: F) -> FoldWith<Self, T, F> where F: Fn(T, Self::Item) -> T + Sync + Send, T: Send + Clone,1195 fn fold_with<F, T>(self, init: T, fold_op: F) -> FoldWith<Self, T, F> 1196 where 1197 F: Fn(T, Self::Item) -> T + Sync + Send, 1198 T: Send + Clone, 1199 { 1200 FoldWith::new(self, init, fold_op) 1201 } 1202 1203 /// Perform a fallible parallel fold. 1204 /// 1205 /// This is a variation of [`fold()`] for operations which can fail with 1206 /// `Option::None` or `Result::Err`. The first such failure stops 1207 /// processing the local set of items, without affecting other folds in the 1208 /// iterator's subdivisions. 1209 /// 1210 /// Often, `try_fold()` will be followed by [`try_reduce()`] 1211 /// for a final reduction and global short-circuiting effect. 1212 /// 1213 /// [`fold()`]: #method.fold 1214 /// [`try_reduce()`]: #method.try_reduce 1215 /// 1216 /// # Examples 1217 /// 1218 /// ``` 1219 /// use rayon::prelude::*; 1220 /// 1221 /// let bytes = 0..22_u8; 1222 /// let sum = bytes.into_par_iter() 1223 /// .try_fold(|| 0_u32, |a: u32, b: u8| a.checked_add(b as u32)) 1224 /// .try_reduce(|| 0, u32::checked_add); 1225 /// 1226 /// assert_eq!(sum, Some((0..22).sum())); // compare to sequential 1227 /// ``` try_fold<T, R, ID, F>(self, identity: ID, fold_op: F) -> TryFold<Self, R, ID, F> where F: Fn(T, Self::Item) -> R + Sync + Send, ID: Fn() -> T + Sync + Send, R: Try<Ok = T> + Send,1228 fn try_fold<T, R, ID, F>(self, identity: ID, fold_op: F) -> TryFold<Self, R, ID, F> 1229 where 1230 F: Fn(T, Self::Item) -> R + Sync + Send, 1231 ID: Fn() -> T + Sync + Send, 1232 R: Try<Ok = T> + Send, 1233 { 1234 TryFold::new(self, identity, fold_op) 1235 } 1236 1237 /// Perform a fallible parallel fold with a cloneable `init` value. 1238 /// 1239 /// This combines the `init` semantics of [`fold_with()`] and the failure 1240 /// semantics of [`try_fold()`]. 1241 /// 1242 /// [`fold_with()`]: #method.fold_with 1243 /// [`try_fold()`]: #method.try_fold 1244 /// 1245 /// ``` 1246 /// use rayon::prelude::*; 1247 /// 1248 /// let bytes = 0..22_u8; 1249 /// let sum = bytes.into_par_iter() 1250 /// .try_fold_with(0_u32, |a: u32, b: u8| a.checked_add(b as u32)) 1251 /// .try_reduce(|| 0, u32::checked_add); 1252 /// 1253 /// assert_eq!(sum, Some((0..22).sum())); // compare to sequential 1254 /// ``` try_fold_with<F, T, R>(self, init: T, fold_op: F) -> TryFoldWith<Self, R, F> where F: Fn(T, Self::Item) -> R + Sync + Send, R: Try<Ok = T> + Send, T: Clone + Send,1255 fn try_fold_with<F, T, R>(self, init: T, fold_op: F) -> TryFoldWith<Self, R, F> 1256 where 1257 F: Fn(T, Self::Item) -> R + Sync + Send, 1258 R: Try<Ok = T> + Send, 1259 T: Clone + Send, 1260 { 1261 TryFoldWith::new(self, init, fold_op) 1262 } 1263 1264 /// Sums up the items in the iterator. 1265 /// 1266 /// Note that the order in items will be reduced is not specified, 1267 /// so if the `+` operator is not truly [associative] \(as is the 1268 /// case for floating point numbers), then the results are not 1269 /// fully deterministic. 1270 /// 1271 /// [associative]: https://en.wikipedia.org/wiki/Associative_property 1272 /// 1273 /// Basically equivalent to `self.reduce(|| 0, |a, b| a + b)`, 1274 /// except that the type of `0` and the `+` operation may vary 1275 /// depending on the type of value being produced. 1276 /// 1277 /// # Examples 1278 /// 1279 /// ``` 1280 /// use rayon::prelude::*; 1281 /// 1282 /// let a = [1, 5, 7]; 1283 /// 1284 /// let sum: i32 = a.par_iter().sum(); 1285 /// 1286 /// assert_eq!(sum, 13); 1287 /// ``` sum<S>(self) -> S where S: Send + Sum<Self::Item> + Sum<S>,1288 fn sum<S>(self) -> S 1289 where 1290 S: Send + Sum<Self::Item> + Sum<S>, 1291 { 1292 sum::sum(self) 1293 } 1294 1295 /// Multiplies all the items in the iterator. 1296 /// 1297 /// Note that the order in items will be reduced is not specified, 1298 /// so if the `*` operator is not truly [associative] \(as is the 1299 /// case for floating point numbers), then the results are not 1300 /// fully deterministic. 1301 /// 1302 /// [associative]: https://en.wikipedia.org/wiki/Associative_property 1303 /// 1304 /// Basically equivalent to `self.reduce(|| 1, |a, b| a * b)`, 1305 /// except that the type of `1` and the `*` operation may vary 1306 /// depending on the type of value being produced. 1307 /// 1308 /// # Examples 1309 /// 1310 /// ``` 1311 /// use rayon::prelude::*; 1312 /// 1313 /// fn factorial(n: u32) -> u32 { 1314 /// (1..n+1).into_par_iter().product() 1315 /// } 1316 /// 1317 /// assert_eq!(factorial(0), 1); 1318 /// assert_eq!(factorial(1), 1); 1319 /// assert_eq!(factorial(5), 120); 1320 /// ``` product<P>(self) -> P where P: Send + Product<Self::Item> + Product<P>,1321 fn product<P>(self) -> P 1322 where 1323 P: Send + Product<Self::Item> + Product<P>, 1324 { 1325 product::product(self) 1326 } 1327 1328 /// Computes the minimum of all the items in the iterator. If the 1329 /// iterator is empty, `None` is returned; otherwise, `Some(min)` 1330 /// is returned. 1331 /// 1332 /// Note that the order in which the items will be reduced is not 1333 /// specified, so if the `Ord` impl is not truly associative, then 1334 /// the results are not deterministic. 1335 /// 1336 /// Basically equivalent to `self.reduce_with(|a, b| cmp::min(a, b))`. 1337 /// 1338 /// # Examples 1339 /// 1340 /// ``` 1341 /// use rayon::prelude::*; 1342 /// 1343 /// let a = [45, 74, 32]; 1344 /// 1345 /// assert_eq!(a.par_iter().min(), Some(&32)); 1346 /// 1347 /// let b: [i32; 0] = []; 1348 /// 1349 /// assert_eq!(b.par_iter().min(), None); 1350 /// ``` min(self) -> Option<Self::Item> where Self::Item: Ord,1351 fn min(self) -> Option<Self::Item> 1352 where 1353 Self::Item: Ord, 1354 { 1355 self.reduce_with(cmp::min) 1356 } 1357 1358 /// Computes the minimum of all the items in the iterator with respect to 1359 /// the given comparison function. If the iterator is empty, `None` is 1360 /// returned; otherwise, `Some(min)` is returned. 1361 /// 1362 /// Note that the order in which the items will be reduced is not 1363 /// specified, so if the comparison function is not associative, then 1364 /// the results are not deterministic. 1365 /// 1366 /// # Examples 1367 /// 1368 /// ``` 1369 /// use rayon::prelude::*; 1370 /// 1371 /// let a = [-3_i32, 77, 53, 240, -1]; 1372 /// 1373 /// assert_eq!(a.par_iter().min_by(|x, y| x.cmp(y)), Some(&-3)); 1374 /// ``` min_by<F>(self, f: F) -> Option<Self::Item> where F: Sync + Send + Fn(&Self::Item, &Self::Item) -> Ordering,1375 fn min_by<F>(self, f: F) -> Option<Self::Item> 1376 where 1377 F: Sync + Send + Fn(&Self::Item, &Self::Item) -> Ordering, 1378 { 1379 fn min<T>(f: impl Fn(&T, &T) -> Ordering) -> impl Fn(T, T) -> T { 1380 move |a, b| match f(&a, &b) { 1381 Ordering::Greater => b, 1382 _ => a, 1383 } 1384 } 1385 1386 self.reduce_with(min(f)) 1387 } 1388 1389 /// Computes the item that yields the minimum value for the given 1390 /// function. If the iterator is empty, `None` is returned; 1391 /// otherwise, `Some(item)` is returned. 1392 /// 1393 /// Note that the order in which the items will be reduced is not 1394 /// specified, so if the `Ord` impl is not truly associative, then 1395 /// the results are not deterministic. 1396 /// 1397 /// # Examples 1398 /// 1399 /// ``` 1400 /// use rayon::prelude::*; 1401 /// 1402 /// let a = [-3_i32, 34, 2, 5, -10, -3, -23]; 1403 /// 1404 /// assert_eq!(a.par_iter().min_by_key(|x| x.abs()), Some(&2)); 1405 /// ``` min_by_key<K, F>(self, f: F) -> Option<Self::Item> where K: Ord + Send, F: Sync + Send + Fn(&Self::Item) -> K,1406 fn min_by_key<K, F>(self, f: F) -> Option<Self::Item> 1407 where 1408 K: Ord + Send, 1409 F: Sync + Send + Fn(&Self::Item) -> K, 1410 { 1411 fn key<T, K>(f: impl Fn(&T) -> K) -> impl Fn(T) -> (K, T) { 1412 move |x| (f(&x), x) 1413 } 1414 1415 fn min_key<T, K: Ord>(a: (K, T), b: (K, T)) -> (K, T) { 1416 match (a.0).cmp(&b.0) { 1417 Ordering::Greater => b, 1418 _ => a, 1419 } 1420 } 1421 1422 let (_, x) = self.map(key(f)).reduce_with(min_key)?; 1423 Some(x) 1424 } 1425 1426 /// Computes the maximum of all the items in the iterator. If the 1427 /// iterator is empty, `None` is returned; otherwise, `Some(max)` 1428 /// is returned. 1429 /// 1430 /// Note that the order in which the items will be reduced is not 1431 /// specified, so if the `Ord` impl is not truly associative, then 1432 /// the results are not deterministic. 1433 /// 1434 /// Basically equivalent to `self.reduce_with(|a, b| cmp::max(a, b))`. 1435 /// 1436 /// # Examples 1437 /// 1438 /// ``` 1439 /// use rayon::prelude::*; 1440 /// 1441 /// let a = [45, 74, 32]; 1442 /// 1443 /// assert_eq!(a.par_iter().max(), Some(&74)); 1444 /// 1445 /// let b: [i32; 0] = []; 1446 /// 1447 /// assert_eq!(b.par_iter().max(), None); 1448 /// ``` max(self) -> Option<Self::Item> where Self::Item: Ord,1449 fn max(self) -> Option<Self::Item> 1450 where 1451 Self::Item: Ord, 1452 { 1453 self.reduce_with(cmp::max) 1454 } 1455 1456 /// Computes the maximum of all the items in the iterator with respect to 1457 /// the given comparison function. If the iterator is empty, `None` is 1458 /// returned; otherwise, `Some(min)` is returned. 1459 /// 1460 /// Note that the order in which the items will be reduced is not 1461 /// specified, so if the comparison function is not associative, then 1462 /// the results are not deterministic. 1463 /// 1464 /// # Examples 1465 /// 1466 /// ``` 1467 /// use rayon::prelude::*; 1468 /// 1469 /// let a = [-3_i32, 77, 53, 240, -1]; 1470 /// 1471 /// assert_eq!(a.par_iter().max_by(|x, y| x.abs().cmp(&y.abs())), Some(&240)); 1472 /// ``` max_by<F>(self, f: F) -> Option<Self::Item> where F: Sync + Send + Fn(&Self::Item, &Self::Item) -> Ordering,1473 fn max_by<F>(self, f: F) -> Option<Self::Item> 1474 where 1475 F: Sync + Send + Fn(&Self::Item, &Self::Item) -> Ordering, 1476 { 1477 fn max<T>(f: impl Fn(&T, &T) -> Ordering) -> impl Fn(T, T) -> T { 1478 move |a, b| match f(&a, &b) { 1479 Ordering::Greater => a, 1480 _ => b, 1481 } 1482 } 1483 1484 self.reduce_with(max(f)) 1485 } 1486 1487 /// Computes the item that yields the maximum value for the given 1488 /// function. If the iterator is empty, `None` is returned; 1489 /// otherwise, `Some(item)` is returned. 1490 /// 1491 /// Note that the order in which the items will be reduced is not 1492 /// specified, so if the `Ord` impl is not truly associative, then 1493 /// the results are not deterministic. 1494 /// 1495 /// # Examples 1496 /// 1497 /// ``` 1498 /// use rayon::prelude::*; 1499 /// 1500 /// let a = [-3_i32, 34, 2, 5, -10, -3, -23]; 1501 /// 1502 /// assert_eq!(a.par_iter().max_by_key(|x| x.abs()), Some(&34)); 1503 /// ``` max_by_key<K, F>(self, f: F) -> Option<Self::Item> where K: Ord + Send, F: Sync + Send + Fn(&Self::Item) -> K,1504 fn max_by_key<K, F>(self, f: F) -> Option<Self::Item> 1505 where 1506 K: Ord + Send, 1507 F: Sync + Send + Fn(&Self::Item) -> K, 1508 { 1509 fn key<T, K>(f: impl Fn(&T) -> K) -> impl Fn(T) -> (K, T) { 1510 move |x| (f(&x), x) 1511 } 1512 1513 fn max_key<T, K: Ord>(a: (K, T), b: (K, T)) -> (K, T) { 1514 match (a.0).cmp(&b.0) { 1515 Ordering::Greater => a, 1516 _ => b, 1517 } 1518 } 1519 1520 let (_, x) = self.map(key(f)).reduce_with(max_key)?; 1521 Some(x) 1522 } 1523 1524 /// Takes two iterators and creates a new iterator over both. 1525 /// 1526 /// # Examples 1527 /// 1528 /// ``` 1529 /// use rayon::prelude::*; 1530 /// 1531 /// let a = [0, 1, 2]; 1532 /// let b = [9, 8, 7]; 1533 /// 1534 /// let par_iter = a.par_iter().chain(b.par_iter()); 1535 /// 1536 /// let chained: Vec<_> = par_iter.cloned().collect(); 1537 /// 1538 /// assert_eq!(&chained[..], &[0, 1, 2, 9, 8, 7]); 1539 /// ``` chain<C>(self, chain: C) -> Chain<Self, C::Iter> where C: IntoParallelIterator<Item = Self::Item>,1540 fn chain<C>(self, chain: C) -> Chain<Self, C::Iter> 1541 where 1542 C: IntoParallelIterator<Item = Self::Item>, 1543 { 1544 Chain::new(self, chain.into_par_iter()) 1545 } 1546 1547 /// Searches for **some** item in the parallel iterator that 1548 /// matches the given predicate and returns it. This operation 1549 /// is similar to [`find` on sequential iterators][find] but 1550 /// the item returned may not be the **first** one in the parallel 1551 /// sequence which matches, since we search the entire sequence in parallel. 1552 /// 1553 /// Once a match is found, we will attempt to stop processing 1554 /// the rest of the items in the iterator as soon as possible 1555 /// (just as `find` stops iterating once a match is found). 1556 /// 1557 /// [find]: https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.find 1558 /// 1559 /// # Examples 1560 /// 1561 /// ``` 1562 /// use rayon::prelude::*; 1563 /// 1564 /// let a = [1, 2, 3, 3]; 1565 /// 1566 /// assert_eq!(a.par_iter().find_any(|&&x| x == 3), Some(&3)); 1567 /// 1568 /// assert_eq!(a.par_iter().find_any(|&&x| x == 100), None); 1569 /// ``` find_any<P>(self, predicate: P) -> Option<Self::Item> where P: Fn(&Self::Item) -> bool + Sync + Send,1570 fn find_any<P>(self, predicate: P) -> Option<Self::Item> 1571 where 1572 P: Fn(&Self::Item) -> bool + Sync + Send, 1573 { 1574 find::find(self, predicate) 1575 } 1576 1577 /// Searches for the sequentially **first** item in the parallel iterator 1578 /// that matches the given predicate and returns it. 1579 /// 1580 /// Once a match is found, all attempts to the right of the match 1581 /// will be stopped, while attempts to the left must continue in case 1582 /// an earlier match is found. 1583 /// 1584 /// Note that not all parallel iterators have a useful order, much like 1585 /// sequential `HashMap` iteration, so "first" may be nebulous. If you 1586 /// just want the first match that discovered anywhere in the iterator, 1587 /// `find_any` is a better choice. 1588 /// 1589 /// # Examples 1590 /// 1591 /// ``` 1592 /// use rayon::prelude::*; 1593 /// 1594 /// let a = [1, 2, 3, 3]; 1595 /// 1596 /// assert_eq!(a.par_iter().find_first(|&&x| x == 3), Some(&3)); 1597 /// 1598 /// assert_eq!(a.par_iter().find_first(|&&x| x == 100), None); 1599 /// ``` find_first<P>(self, predicate: P) -> Option<Self::Item> where P: Fn(&Self::Item) -> bool + Sync + Send,1600 fn find_first<P>(self, predicate: P) -> Option<Self::Item> 1601 where 1602 P: Fn(&Self::Item) -> bool + Sync + Send, 1603 { 1604 find_first_last::find_first(self, predicate) 1605 } 1606 1607 /// Searches for the sequentially **last** item in the parallel iterator 1608 /// that matches the given predicate and returns it. 1609 /// 1610 /// Once a match is found, all attempts to the left of the match 1611 /// will be stopped, while attempts to the right must continue in case 1612 /// a later match is found. 1613 /// 1614 /// Note that not all parallel iterators have a useful order, much like 1615 /// sequential `HashMap` iteration, so "last" may be nebulous. When the 1616 /// order doesn't actually matter to you, `find_any` is a better choice. 1617 /// 1618 /// # Examples 1619 /// 1620 /// ``` 1621 /// use rayon::prelude::*; 1622 /// 1623 /// let a = [1, 2, 3, 3]; 1624 /// 1625 /// assert_eq!(a.par_iter().find_last(|&&x| x == 3), Some(&3)); 1626 /// 1627 /// assert_eq!(a.par_iter().find_last(|&&x| x == 100), None); 1628 /// ``` find_last<P>(self, predicate: P) -> Option<Self::Item> where P: Fn(&Self::Item) -> bool + Sync + Send,1629 fn find_last<P>(self, predicate: P) -> Option<Self::Item> 1630 where 1631 P: Fn(&Self::Item) -> bool + Sync + Send, 1632 { 1633 find_first_last::find_last(self, predicate) 1634 } 1635 1636 /// Applies the given predicate to the items in the parallel iterator 1637 /// and returns **any** non-None result of the map operation. 1638 /// 1639 /// Once a non-None value is produced from the map operation, we will 1640 /// attempt to stop processing the rest of the items in the iterator 1641 /// as soon as possible. 1642 /// 1643 /// Note that this method only returns **some** item in the parallel 1644 /// iterator that is not None from the map predicate. The item returned 1645 /// may not be the **first** non-None value produced in the parallel 1646 /// sequence, since the entire sequence is mapped over in parallel. 1647 /// 1648 /// # Examples 1649 /// 1650 /// ``` 1651 /// use rayon::prelude::*; 1652 /// 1653 /// let c = ["lol", "NaN", "5", "5"]; 1654 /// 1655 /// let first_number = c.par_iter().find_map_first(|s| s.parse().ok()); 1656 /// 1657 /// assert_eq!(first_number, Some(5)); 1658 /// ``` find_map_any<P, R>(self, predicate: P) -> Option<R> where P: Fn(Self::Item) -> Option<R> + Sync + Send, R: Send,1659 fn find_map_any<P, R>(self, predicate: P) -> Option<R> 1660 where 1661 P: Fn(Self::Item) -> Option<R> + Sync + Send, 1662 R: Send, 1663 { 1664 fn yes<T>(_: &T) -> bool { 1665 true 1666 } 1667 self.filter_map(predicate).find_any(yes) 1668 } 1669 1670 /// Applies the given predicate to the items in the parallel iterator and 1671 /// returns the sequentially **first** non-None result of the map operation. 1672 /// 1673 /// Once a non-None value is produced from the map operation, all attempts 1674 /// to the right of the match will be stopped, while attempts to the left 1675 /// must continue in case an earlier match is found. 1676 /// 1677 /// Note that not all parallel iterators have a useful order, much like 1678 /// sequential `HashMap` iteration, so "first" may be nebulous. If you 1679 /// just want the first non-None value discovered anywhere in the iterator, 1680 /// `find_map_any` is a better choice. 1681 /// 1682 /// # Examples 1683 /// 1684 /// ``` 1685 /// use rayon::prelude::*; 1686 /// 1687 /// let c = ["lol", "NaN", "2", "5"]; 1688 /// 1689 /// let first_number = c.par_iter().find_map_first(|s| s.parse().ok()); 1690 /// 1691 /// assert_eq!(first_number, Some(2)); 1692 /// ``` find_map_first<P, R>(self, predicate: P) -> Option<R> where P: Fn(Self::Item) -> Option<R> + Sync + Send, R: Send,1693 fn find_map_first<P, R>(self, predicate: P) -> Option<R> 1694 where 1695 P: Fn(Self::Item) -> Option<R> + Sync + Send, 1696 R: Send, 1697 { 1698 fn yes<T>(_: &T) -> bool { 1699 true 1700 } 1701 self.filter_map(predicate).find_first(yes) 1702 } 1703 1704 /// Applies the given predicate to the items in the parallel iterator and 1705 /// returns the sequentially **last** non-None result of the map operation. 1706 /// 1707 /// Once a non-None value is produced from the map operation, all attempts 1708 /// to the left of the match will be stopped, while attempts to the right 1709 /// must continue in case a later match is found. 1710 /// 1711 /// Note that not all parallel iterators have a useful order, much like 1712 /// sequential `HashMap` iteration, so "first" may be nebulous. If you 1713 /// just want the first non-None value discovered anywhere in the iterator, 1714 /// `find_map_any` is a better choice. 1715 /// 1716 /// # Examples 1717 /// 1718 /// ``` 1719 /// use rayon::prelude::*; 1720 /// 1721 /// let c = ["lol", "NaN", "2", "5"]; 1722 /// 1723 /// let first_number = c.par_iter().find_map_last(|s| s.parse().ok()); 1724 /// 1725 /// assert_eq!(first_number, Some(5)); 1726 /// ``` find_map_last<P, R>(self, predicate: P) -> Option<R> where P: Fn(Self::Item) -> Option<R> + Sync + Send, R: Send,1727 fn find_map_last<P, R>(self, predicate: P) -> Option<R> 1728 where 1729 P: Fn(Self::Item) -> Option<R> + Sync + Send, 1730 R: Send, 1731 { 1732 fn yes<T>(_: &T) -> bool { 1733 true 1734 } 1735 self.filter_map(predicate).find_last(yes) 1736 } 1737 1738 #[doc(hidden)] 1739 #[deprecated(note = "parallel `find` does not search in order -- use `find_any`, \\ 1740 `find_first`, or `find_last`")] find<P>(self, predicate: P) -> Option<Self::Item> where P: Fn(&Self::Item) -> bool + Sync + Send,1741 fn find<P>(self, predicate: P) -> Option<Self::Item> 1742 where 1743 P: Fn(&Self::Item) -> bool + Sync + Send, 1744 { 1745 self.find_any(predicate) 1746 } 1747 1748 /// Searches for **some** item in the parallel iterator that 1749 /// matches the given predicate, and if so returns true. Once 1750 /// a match is found, we'll attempt to stop process the rest 1751 /// of the items. Proving that there's no match, returning false, 1752 /// does require visiting every item. 1753 /// 1754 /// # Examples 1755 /// 1756 /// ``` 1757 /// use rayon::prelude::*; 1758 /// 1759 /// let a = [0, 12, 3, 4, 0, 23, 0]; 1760 /// 1761 /// let is_valid = a.par_iter().any(|&x| x > 10); 1762 /// 1763 /// assert!(is_valid); 1764 /// ``` any<P>(self, predicate: P) -> bool where P: Fn(Self::Item) -> bool + Sync + Send,1765 fn any<P>(self, predicate: P) -> bool 1766 where 1767 P: Fn(Self::Item) -> bool + Sync + Send, 1768 { 1769 self.map(predicate).find_any(bool::clone).is_some() 1770 } 1771 1772 /// Tests that every item in the parallel iterator matches the given 1773 /// predicate, and if so returns true. If a counter-example is found, 1774 /// we'll attempt to stop processing more items, then return false. 1775 /// 1776 /// # Examples 1777 /// 1778 /// ``` 1779 /// use rayon::prelude::*; 1780 /// 1781 /// let a = [0, 12, 3, 4, 0, 23, 0]; 1782 /// 1783 /// let is_valid = a.par_iter().all(|&x| x > 10); 1784 /// 1785 /// assert!(!is_valid); 1786 /// ``` all<P>(self, predicate: P) -> bool where P: Fn(Self::Item) -> bool + Sync + Send,1787 fn all<P>(self, predicate: P) -> bool 1788 where 1789 P: Fn(Self::Item) -> bool + Sync + Send, 1790 { 1791 #[inline] 1792 fn is_false(x: &bool) -> bool { 1793 !x 1794 } 1795 1796 self.map(predicate).find_any(is_false).is_none() 1797 } 1798 1799 /// Creates an iterator over the `Some` items of this iterator, halting 1800 /// as soon as any `None` is found. 1801 /// 1802 /// # Examples 1803 /// 1804 /// ``` 1805 /// use rayon::prelude::*; 1806 /// use std::sync::atomic::{AtomicUsize, Ordering}; 1807 /// 1808 /// let counter = AtomicUsize::new(0); 1809 /// let value = (0_i32..2048) 1810 /// .into_par_iter() 1811 /// .map(|x| { 1812 /// counter.fetch_add(1, Ordering::SeqCst); 1813 /// if x < 1024 { Some(x) } else { None } 1814 /// }) 1815 /// .while_some() 1816 /// .max(); 1817 /// 1818 /// assert!(value < Some(1024)); 1819 /// assert!(counter.load(Ordering::SeqCst) < 2048); // should not have visited every single one 1820 /// ``` while_some<T>(self) -> WhileSome<Self> where Self: ParallelIterator<Item = Option<T>>, T: Send,1821 fn while_some<T>(self) -> WhileSome<Self> 1822 where 1823 Self: ParallelIterator<Item = Option<T>>, 1824 T: Send, 1825 { 1826 WhileSome::new(self) 1827 } 1828 1829 /// Wraps an iterator with a fuse in case of panics, to halt all threads 1830 /// as soon as possible. 1831 /// 1832 /// Panics within parallel iterators are always propagated to the caller, 1833 /// but they don't always halt the rest of the iterator right away, due to 1834 /// the internal semantics of [`join`]. This adaptor makes a greater effort 1835 /// to stop processing other items sooner, with the cost of additional 1836 /// synchronization overhead, which may also inhibit some optimizations. 1837 /// 1838 /// [`join`]: ../fn.join.html#panics 1839 /// 1840 /// # Examples 1841 /// 1842 /// If this code didn't use `panic_fuse()`, it would continue processing 1843 /// many more items in other threads (with long sleep delays) before the 1844 /// panic is finally propagated. 1845 /// 1846 /// ```should_panic 1847 /// use rayon::prelude::*; 1848 /// use std::{thread, time}; 1849 /// 1850 /// (0..1_000_000) 1851 /// .into_par_iter() 1852 /// .panic_fuse() 1853 /// .for_each(|i| { 1854 /// // simulate some work 1855 /// thread::sleep(time::Duration::from_secs(1)); 1856 /// assert!(i > 0); // oops! 1857 /// }); 1858 /// ``` panic_fuse(self) -> PanicFuse<Self>1859 fn panic_fuse(self) -> PanicFuse<Self> { 1860 PanicFuse::new(self) 1861 } 1862 1863 /// Create a fresh collection containing all the element produced 1864 /// by this parallel iterator. 1865 /// 1866 /// You may prefer to use `collect_into_vec()`, which allocates more 1867 /// efficiently with precise knowledge of how many elements the 1868 /// iterator contains, and even allows you to reuse an existing 1869 /// vector's backing store rather than allocating a fresh vector. 1870 /// 1871 /// # Examples 1872 /// 1873 /// ``` 1874 /// use rayon::prelude::*; 1875 /// 1876 /// let sync_vec: Vec<_> = (0..100).into_iter().collect(); 1877 /// 1878 /// let async_vec: Vec<_> = (0..100).into_par_iter().collect(); 1879 /// 1880 /// assert_eq!(sync_vec, async_vec); 1881 /// ``` collect<C>(self) -> C where C: FromParallelIterator<Self::Item>,1882 fn collect<C>(self) -> C 1883 where 1884 C: FromParallelIterator<Self::Item>, 1885 { 1886 C::from_par_iter(self) 1887 } 1888 1889 /// Unzips the items of a parallel iterator into a pair of arbitrary 1890 /// `ParallelExtend` containers. 1891 /// 1892 /// You may prefer to use `unzip_into_vecs()`, which allocates more 1893 /// efficiently with precise knowledge of how many elements the 1894 /// iterator contains, and even allows you to reuse existing 1895 /// vectors' backing stores rather than allocating fresh vectors. 1896 /// 1897 /// # Examples 1898 /// 1899 /// ``` 1900 /// use rayon::prelude::*; 1901 /// 1902 /// let a = [(0, 1), (1, 2), (2, 3), (3, 4)]; 1903 /// 1904 /// let (left, right): (Vec<_>, Vec<_>) = a.par_iter().cloned().unzip(); 1905 /// 1906 /// assert_eq!(left, [0, 1, 2, 3]); 1907 /// assert_eq!(right, [1, 2, 3, 4]); 1908 /// ``` 1909 /// 1910 /// Nested pairs can be unzipped too. 1911 /// 1912 /// ``` 1913 /// use rayon::prelude::*; 1914 /// 1915 /// let (values, (squares, cubes)): (Vec<_>, (Vec<_>, Vec<_>)) = (0..4).into_par_iter() 1916 /// .map(|i| (i, (i * i, i * i * i))) 1917 /// .unzip(); 1918 /// 1919 /// assert_eq!(values, [0, 1, 2, 3]); 1920 /// assert_eq!(squares, [0, 1, 4, 9]); 1921 /// assert_eq!(cubes, [0, 1, 8, 27]); 1922 /// ``` unzip<A, B, FromA, FromB>(self) -> (FromA, FromB) where Self: ParallelIterator<Item = (A, B)>, FromA: Default + Send + ParallelExtend<A>, FromB: Default + Send + ParallelExtend<B>, A: Send, B: Send,1923 fn unzip<A, B, FromA, FromB>(self) -> (FromA, FromB) 1924 where 1925 Self: ParallelIterator<Item = (A, B)>, 1926 FromA: Default + Send + ParallelExtend<A>, 1927 FromB: Default + Send + ParallelExtend<B>, 1928 A: Send, 1929 B: Send, 1930 { 1931 unzip::unzip(self) 1932 } 1933 1934 /// Partitions the items of a parallel iterator into a pair of arbitrary 1935 /// `ParallelExtend` containers. Items for which the `predicate` returns 1936 /// true go into the first container, and the rest go into the second. 1937 /// 1938 /// Note: unlike the standard `Iterator::partition`, this allows distinct 1939 /// collection types for the left and right items. This is more flexible, 1940 /// but may require new type annotations when converting sequential code 1941 /// that used type inferrence assuming the two were the same. 1942 /// 1943 /// # Examples 1944 /// 1945 /// ``` 1946 /// use rayon::prelude::*; 1947 /// 1948 /// let (left, right): (Vec<_>, Vec<_>) = (0..8).into_par_iter().partition(|x| x % 2 == 0); 1949 /// 1950 /// assert_eq!(left, [0, 2, 4, 6]); 1951 /// assert_eq!(right, [1, 3, 5, 7]); 1952 /// ``` partition<A, B, P>(self, predicate: P) -> (A, B) where A: Default + Send + ParallelExtend<Self::Item>, B: Default + Send + ParallelExtend<Self::Item>, P: Fn(&Self::Item) -> bool + Sync + Send,1953 fn partition<A, B, P>(self, predicate: P) -> (A, B) 1954 where 1955 A: Default + Send + ParallelExtend<Self::Item>, 1956 B: Default + Send + ParallelExtend<Self::Item>, 1957 P: Fn(&Self::Item) -> bool + Sync + Send, 1958 { 1959 unzip::partition(self, predicate) 1960 } 1961 1962 /// Partitions and maps the items of a parallel iterator into a pair of 1963 /// arbitrary `ParallelExtend` containers. `Either::Left` items go into 1964 /// the first container, and `Either::Right` items go into the second. 1965 /// 1966 /// # Examples 1967 /// 1968 /// ``` 1969 /// use rayon::prelude::*; 1970 /// use rayon::iter::Either; 1971 /// 1972 /// let (left, right): (Vec<_>, Vec<_>) = (0..8).into_par_iter() 1973 /// .partition_map(|x| { 1974 /// if x % 2 == 0 { 1975 /// Either::Left(x * 4) 1976 /// } else { 1977 /// Either::Right(x * 3) 1978 /// } 1979 /// }); 1980 /// 1981 /// assert_eq!(left, [0, 8, 16, 24]); 1982 /// assert_eq!(right, [3, 9, 15, 21]); 1983 /// ``` 1984 /// 1985 /// Nested `Either` enums can be split as well. 1986 /// 1987 /// ``` 1988 /// use rayon::prelude::*; 1989 /// use rayon::iter::Either::*; 1990 /// 1991 /// let ((fizzbuzz, fizz), (buzz, other)): ((Vec<_>, Vec<_>), (Vec<_>, Vec<_>)) = (1..20) 1992 /// .into_par_iter() 1993 /// .partition_map(|x| match (x % 3, x % 5) { 1994 /// (0, 0) => Left(Left(x)), 1995 /// (0, _) => Left(Right(x)), 1996 /// (_, 0) => Right(Left(x)), 1997 /// (_, _) => Right(Right(x)), 1998 /// }); 1999 /// 2000 /// assert_eq!(fizzbuzz, [15]); 2001 /// assert_eq!(fizz, [3, 6, 9, 12, 18]); 2002 /// assert_eq!(buzz, [5, 10]); 2003 /// assert_eq!(other, [1, 2, 4, 7, 8, 11, 13, 14, 16, 17, 19]); 2004 /// ``` partition_map<A, B, P, L, R>(self, predicate: P) -> (A, B) where A: Default + Send + ParallelExtend<L>, B: Default + Send + ParallelExtend<R>, P: Fn(Self::Item) -> Either<L, R> + Sync + Send, L: Send, R: Send,2005 fn partition_map<A, B, P, L, R>(self, predicate: P) -> (A, B) 2006 where 2007 A: Default + Send + ParallelExtend<L>, 2008 B: Default + Send + ParallelExtend<R>, 2009 P: Fn(Self::Item) -> Either<L, R> + Sync + Send, 2010 L: Send, 2011 R: Send, 2012 { 2013 unzip::partition_map(self, predicate) 2014 } 2015 2016 /// Intersperses clones of an element between items of this iterator. 2017 /// 2018 /// # Examples 2019 /// 2020 /// ``` 2021 /// use rayon::prelude::*; 2022 /// 2023 /// let x = vec![1, 2, 3]; 2024 /// let r: Vec<_> = x.into_par_iter().intersperse(-1).collect(); 2025 /// 2026 /// assert_eq!(r, vec![1, -1, 2, -1, 3]); 2027 /// ``` intersperse(self, element: Self::Item) -> Intersperse<Self> where Self::Item: Clone,2028 fn intersperse(self, element: Self::Item) -> Intersperse<Self> 2029 where 2030 Self::Item: Clone, 2031 { 2032 Intersperse::new(self, element) 2033 } 2034 2035 /// Internal method used to define the behavior of this parallel 2036 /// iterator. You should not need to call this directly. 2037 /// 2038 /// This method causes the iterator `self` to start producing 2039 /// items and to feed them to the consumer `consumer` one by one. 2040 /// It may split the consumer before doing so to create the 2041 /// opportunity to produce in parallel. 2042 /// 2043 /// See the [README] for more details on the internals of parallel 2044 /// iterators. 2045 /// 2046 /// [README]: README.md drive_unindexed<C>(self, consumer: C) -> C::Result where C: UnindexedConsumer<Self::Item>2047 fn drive_unindexed<C>(self, consumer: C) -> C::Result 2048 where 2049 C: UnindexedConsumer<Self::Item>; 2050 2051 /// Internal method used to define the behavior of this parallel 2052 /// iterator. You should not need to call this directly. 2053 /// 2054 /// Returns the number of items produced by this iterator, if known 2055 /// statically. This can be used by consumers to trigger special fast 2056 /// paths. Therefore, if `Some(_)` is returned, this iterator must only 2057 /// use the (indexed) `Consumer` methods when driving a consumer, such 2058 /// as `split_at()`. Calling `UnindexedConsumer::split_off_left()` or 2059 /// other `UnindexedConsumer` methods -- or returning an inaccurate 2060 /// value -- may result in panics. 2061 /// 2062 /// This method is currently used to optimize `collect` for want 2063 /// of true Rust specialization; it may be removed when 2064 /// specialization is stable. opt_len(&self) -> Option<usize>2065 fn opt_len(&self) -> Option<usize> { 2066 None 2067 } 2068 } 2069 2070 impl<T: ParallelIterator> IntoParallelIterator for T { 2071 type Iter = T; 2072 type Item = T::Item; 2073 into_par_iter(self) -> T2074 fn into_par_iter(self) -> T { 2075 self 2076 } 2077 } 2078 2079 /// An iterator that supports "random access" to its data, meaning 2080 /// that you can split it at arbitrary indices and draw data from 2081 /// those points. 2082 /// 2083 /// **Note:** Not implemented for `u64`, `i64`, `u128`, or `i128` ranges 2084 pub trait IndexedParallelIterator: ParallelIterator { 2085 /// Collects the results of the iterator into the specified 2086 /// vector. The vector is always truncated before execution 2087 /// begins. If possible, reusing the vector across calls can lead 2088 /// to better performance since it reuses the same backing buffer. 2089 /// 2090 /// # Examples 2091 /// 2092 /// ``` 2093 /// use rayon::prelude::*; 2094 /// 2095 /// // any prior data will be truncated 2096 /// let mut vec = vec![-1, -2, -3]; 2097 /// 2098 /// (0..5).into_par_iter() 2099 /// .collect_into_vec(&mut vec); 2100 /// 2101 /// assert_eq!(vec, [0, 1, 2, 3, 4]); 2102 /// ``` collect_into_vec(self, target: &mut Vec<Self::Item>)2103 fn collect_into_vec(self, target: &mut Vec<Self::Item>) { 2104 collect::collect_into_vec(self, target); 2105 } 2106 2107 /// Unzips the results of the iterator into the specified 2108 /// vectors. The vectors are always truncated before execution 2109 /// begins. If possible, reusing the vectors across calls can lead 2110 /// to better performance since they reuse the same backing buffer. 2111 /// 2112 /// # Examples 2113 /// 2114 /// ``` 2115 /// use rayon::prelude::*; 2116 /// 2117 /// // any prior data will be truncated 2118 /// let mut left = vec![42; 10]; 2119 /// let mut right = vec![-1; 10]; 2120 /// 2121 /// (10..15).into_par_iter() 2122 /// .enumerate() 2123 /// .unzip_into_vecs(&mut left, &mut right); 2124 /// 2125 /// assert_eq!(left, [0, 1, 2, 3, 4]); 2126 /// assert_eq!(right, [10, 11, 12, 13, 14]); 2127 /// ``` unzip_into_vecs<A, B>(self, left: &mut Vec<A>, right: &mut Vec<B>) where Self: IndexedParallelIterator<Item = (A, B)>, A: Send, B: Send,2128 fn unzip_into_vecs<A, B>(self, left: &mut Vec<A>, right: &mut Vec<B>) 2129 where 2130 Self: IndexedParallelIterator<Item = (A, B)>, 2131 A: Send, 2132 B: Send, 2133 { 2134 collect::unzip_into_vecs(self, left, right); 2135 } 2136 2137 /// Iterate over tuples `(A, B)`, where the items `A` are from 2138 /// this iterator and `B` are from the iterator given as argument. 2139 /// Like the `zip` method on ordinary iterators, if the two 2140 /// iterators are of unequal length, you only get the items they 2141 /// have in common. 2142 /// 2143 /// # Examples 2144 /// 2145 /// ``` 2146 /// use rayon::prelude::*; 2147 /// 2148 /// let result: Vec<_> = (1..4) 2149 /// .into_par_iter() 2150 /// .zip(vec!['a', 'b', 'c']) 2151 /// .collect(); 2152 /// 2153 /// assert_eq!(result, [(1, 'a'), (2, 'b'), (3, 'c')]); 2154 /// ``` zip<Z>(self, zip_op: Z) -> Zip<Self, Z::Iter> where Z: IntoParallelIterator, Z::Iter: IndexedParallelIterator,2155 fn zip<Z>(self, zip_op: Z) -> Zip<Self, Z::Iter> 2156 where 2157 Z: IntoParallelIterator, 2158 Z::Iter: IndexedParallelIterator, 2159 { 2160 Zip::new(self, zip_op.into_par_iter()) 2161 } 2162 2163 /// The same as `Zip`, but requires that both iterators have the same length. 2164 /// 2165 /// # Panics 2166 /// Will panic if `self` and `zip_op` are not the same length. 2167 /// 2168 /// ```should_panic 2169 /// use rayon::prelude::*; 2170 /// 2171 /// let one = [1u8]; 2172 /// let two = [2u8, 2]; 2173 /// let one_iter = one.par_iter(); 2174 /// let two_iter = two.par_iter(); 2175 /// 2176 /// // this will panic 2177 /// let zipped: Vec<(&u8, &u8)> = one_iter.zip_eq(two_iter).collect(); 2178 /// 2179 /// // we should never get here 2180 /// assert_eq!(1, zipped.len()); 2181 /// ``` zip_eq<Z>(self, zip_op: Z) -> ZipEq<Self, Z::Iter> where Z: IntoParallelIterator, Z::Iter: IndexedParallelIterator,2182 fn zip_eq<Z>(self, zip_op: Z) -> ZipEq<Self, Z::Iter> 2183 where 2184 Z: IntoParallelIterator, 2185 Z::Iter: IndexedParallelIterator, 2186 { 2187 let zip_op_iter = zip_op.into_par_iter(); 2188 assert_eq!(self.len(), zip_op_iter.len()); 2189 ZipEq::new(self, zip_op_iter) 2190 } 2191 2192 /// Interleave elements of this iterator and the other given 2193 /// iterator. Alternately yields elements from this iterator and 2194 /// the given iterator, until both are exhausted. If one iterator 2195 /// is exhausted before the other, the last elements are provided 2196 /// from the other. 2197 /// 2198 /// # Examples 2199 /// 2200 /// ``` 2201 /// use rayon::prelude::*; 2202 /// let (x, y) = (vec![1, 2], vec![3, 4, 5, 6]); 2203 /// let r: Vec<i32> = x.into_par_iter().interleave(y).collect(); 2204 /// assert_eq!(r, vec![1, 3, 2, 4, 5, 6]); 2205 /// ``` interleave<I>(self, other: I) -> Interleave<Self, I::Iter> where I: IntoParallelIterator<Item = Self::Item>, I::Iter: IndexedParallelIterator<Item = Self::Item>,2206 fn interleave<I>(self, other: I) -> Interleave<Self, I::Iter> 2207 where 2208 I: IntoParallelIterator<Item = Self::Item>, 2209 I::Iter: IndexedParallelIterator<Item = Self::Item>, 2210 { 2211 Interleave::new(self, other.into_par_iter()) 2212 } 2213 2214 /// Interleave elements of this iterator and the other given 2215 /// iterator, until one is exhausted. 2216 /// 2217 /// # Examples 2218 /// 2219 /// ``` 2220 /// use rayon::prelude::*; 2221 /// let (x, y) = (vec![1, 2, 3, 4], vec![5, 6]); 2222 /// let r: Vec<i32> = x.into_par_iter().interleave_shortest(y).collect(); 2223 /// assert_eq!(r, vec![1, 5, 2, 6, 3]); 2224 /// ``` interleave_shortest<I>(self, other: I) -> InterleaveShortest<Self, I::Iter> where I: IntoParallelIterator<Item = Self::Item>, I::Iter: IndexedParallelIterator<Item = Self::Item>,2225 fn interleave_shortest<I>(self, other: I) -> InterleaveShortest<Self, I::Iter> 2226 where 2227 I: IntoParallelIterator<Item = Self::Item>, 2228 I::Iter: IndexedParallelIterator<Item = Self::Item>, 2229 { 2230 InterleaveShortest::new(self, other.into_par_iter()) 2231 } 2232 2233 /// Split an iterator up into fixed-size chunks. 2234 /// 2235 /// Returns an iterator that returns `Vec`s of the given number of elements. 2236 /// If the number of elements in the iterator is not divisible by `chunk_size`, 2237 /// the last chunk may be shorter than `chunk_size`. 2238 /// 2239 /// See also [`par_chunks()`] and [`par_chunks_mut()`] for similar behavior on 2240 /// slices, without having to allocate intermediate `Vec`s for the chunks. 2241 /// 2242 /// [`par_chunks()`]: ../slice/trait.ParallelSlice.html#method.par_chunks 2243 /// [`par_chunks_mut()`]: ../slice/trait.ParallelSliceMut.html#method.par_chunks_mut 2244 /// 2245 /// # Examples 2246 /// 2247 /// ``` 2248 /// use rayon::prelude::*; 2249 /// let a = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; 2250 /// let r: Vec<Vec<i32>> = a.into_par_iter().chunks(3).collect(); 2251 /// assert_eq!(r, vec![vec![1,2,3], vec![4,5,6], vec![7,8,9], vec![10]]); 2252 /// ``` chunks(self, chunk_size: usize) -> Chunks<Self>2253 fn chunks(self, chunk_size: usize) -> Chunks<Self> { 2254 assert!(chunk_size != 0, "chunk_size must not be zero"); 2255 Chunks::new(self, chunk_size) 2256 } 2257 2258 /// Lexicographically compares the elements of this `ParallelIterator` with those of 2259 /// another. 2260 /// 2261 /// # Examples 2262 /// 2263 /// ``` 2264 /// use rayon::prelude::*; 2265 /// use std::cmp::Ordering::*; 2266 /// 2267 /// let x = vec![1, 2, 3]; 2268 /// assert_eq!(x.par_iter().cmp(&vec![1, 3, 0]), Less); 2269 /// assert_eq!(x.par_iter().cmp(&vec![1, 2, 3]), Equal); 2270 /// assert_eq!(x.par_iter().cmp(&vec![1, 2]), Greater); 2271 /// ``` cmp<I>(self, other: I) -> Ordering where I: IntoParallelIterator<Item = Self::Item>, I::Iter: IndexedParallelIterator, Self::Item: Ord,2272 fn cmp<I>(self, other: I) -> Ordering 2273 where 2274 I: IntoParallelIterator<Item = Self::Item>, 2275 I::Iter: IndexedParallelIterator, 2276 Self::Item: Ord, 2277 { 2278 #[inline] 2279 fn ordering<T: Ord>((x, y): (T, T)) -> Ordering { 2280 Ord::cmp(&x, &y) 2281 } 2282 2283 #[inline] 2284 fn inequal(&ord: &Ordering) -> bool { 2285 ord != Ordering::Equal 2286 } 2287 2288 let other = other.into_par_iter(); 2289 let ord_len = self.len().cmp(&other.len()); 2290 self.zip(other) 2291 .map(ordering) 2292 .find_first(inequal) 2293 .unwrap_or(ord_len) 2294 } 2295 2296 /// Lexicographically compares the elements of this `ParallelIterator` with those of 2297 /// another. 2298 /// 2299 /// # Examples 2300 /// 2301 /// ``` 2302 /// use rayon::prelude::*; 2303 /// use std::cmp::Ordering::*; 2304 /// use std::f64::NAN; 2305 /// 2306 /// let x = vec![1.0, 2.0, 3.0]; 2307 /// assert_eq!(x.par_iter().partial_cmp(&vec![1.0, 3.0, 0.0]), Some(Less)); 2308 /// assert_eq!(x.par_iter().partial_cmp(&vec![1.0, 2.0, 3.0]), Some(Equal)); 2309 /// assert_eq!(x.par_iter().partial_cmp(&vec![1.0, 2.0]), Some(Greater)); 2310 /// assert_eq!(x.par_iter().partial_cmp(&vec![1.0, NAN]), None); 2311 /// ``` partial_cmp<I>(self, other: I) -> Option<Ordering> where I: IntoParallelIterator, I::Iter: IndexedParallelIterator, Self::Item: PartialOrd<I::Item>,2312 fn partial_cmp<I>(self, other: I) -> Option<Ordering> 2313 where 2314 I: IntoParallelIterator, 2315 I::Iter: IndexedParallelIterator, 2316 Self::Item: PartialOrd<I::Item>, 2317 { 2318 #[inline] 2319 fn ordering<T: PartialOrd<U>, U>((x, y): (T, U)) -> Option<Ordering> { 2320 PartialOrd::partial_cmp(&x, &y) 2321 } 2322 2323 #[inline] 2324 fn inequal(&ord: &Option<Ordering>) -> bool { 2325 ord != Some(Ordering::Equal) 2326 } 2327 2328 let other = other.into_par_iter(); 2329 let ord_len = self.len().cmp(&other.len()); 2330 self.zip(other) 2331 .map(ordering) 2332 .find_first(inequal) 2333 .unwrap_or(Some(ord_len)) 2334 } 2335 2336 /// Determines if the elements of this `ParallelIterator` 2337 /// are equal to those of another eq<I>(self, other: I) -> bool where I: IntoParallelIterator, I::Iter: IndexedParallelIterator, Self::Item: PartialEq<I::Item>,2338 fn eq<I>(self, other: I) -> bool 2339 where 2340 I: IntoParallelIterator, 2341 I::Iter: IndexedParallelIterator, 2342 Self::Item: PartialEq<I::Item>, 2343 { 2344 #[inline] 2345 fn eq<T: PartialEq<U>, U>((x, y): (T, U)) -> bool { 2346 PartialEq::eq(&x, &y) 2347 } 2348 2349 let other = other.into_par_iter(); 2350 self.len() == other.len() && self.zip(other).all(eq) 2351 } 2352 2353 /// Determines if the elements of this `ParallelIterator` 2354 /// are unequal to those of another ne<I>(self, other: I) -> bool where I: IntoParallelIterator, I::Iter: IndexedParallelIterator, Self::Item: PartialEq<I::Item>,2355 fn ne<I>(self, other: I) -> bool 2356 where 2357 I: IntoParallelIterator, 2358 I::Iter: IndexedParallelIterator, 2359 Self::Item: PartialEq<I::Item>, 2360 { 2361 !self.eq(other) 2362 } 2363 2364 /// Determines if the elements of this `ParallelIterator` 2365 /// are lexicographically less than those of another. lt<I>(self, other: I) -> bool where I: IntoParallelIterator, I::Iter: IndexedParallelIterator, Self::Item: PartialOrd<I::Item>,2366 fn lt<I>(self, other: I) -> bool 2367 where 2368 I: IntoParallelIterator, 2369 I::Iter: IndexedParallelIterator, 2370 Self::Item: PartialOrd<I::Item>, 2371 { 2372 self.partial_cmp(other) == Some(Ordering::Less) 2373 } 2374 2375 /// Determines if the elements of this `ParallelIterator` 2376 /// are less or equal to those of another. le<I>(self, other: I) -> bool where I: IntoParallelIterator, I::Iter: IndexedParallelIterator, Self::Item: PartialOrd<I::Item>,2377 fn le<I>(self, other: I) -> bool 2378 where 2379 I: IntoParallelIterator, 2380 I::Iter: IndexedParallelIterator, 2381 Self::Item: PartialOrd<I::Item>, 2382 { 2383 let ord = self.partial_cmp(other); 2384 ord == Some(Ordering::Equal) || ord == Some(Ordering::Less) 2385 } 2386 2387 /// Determines if the elements of this `ParallelIterator` 2388 /// are lexicographically greater than those of another. gt<I>(self, other: I) -> bool where I: IntoParallelIterator, I::Iter: IndexedParallelIterator, Self::Item: PartialOrd<I::Item>,2389 fn gt<I>(self, other: I) -> bool 2390 where 2391 I: IntoParallelIterator, 2392 I::Iter: IndexedParallelIterator, 2393 Self::Item: PartialOrd<I::Item>, 2394 { 2395 self.partial_cmp(other) == Some(Ordering::Greater) 2396 } 2397 2398 /// Determines if the elements of this `ParallelIterator` 2399 /// are less or equal to those of another. ge<I>(self, other: I) -> bool where I: IntoParallelIterator, I::Iter: IndexedParallelIterator, Self::Item: PartialOrd<I::Item>,2400 fn ge<I>(self, other: I) -> bool 2401 where 2402 I: IntoParallelIterator, 2403 I::Iter: IndexedParallelIterator, 2404 Self::Item: PartialOrd<I::Item>, 2405 { 2406 let ord = self.partial_cmp(other); 2407 ord == Some(Ordering::Equal) || ord == Some(Ordering::Greater) 2408 } 2409 2410 /// Yields an index along with each item. 2411 /// 2412 /// # Examples 2413 /// 2414 /// ``` 2415 /// use rayon::prelude::*; 2416 /// 2417 /// let chars = vec!['a', 'b', 'c']; 2418 /// let result: Vec<_> = chars 2419 /// .into_par_iter() 2420 /// .enumerate() 2421 /// .collect(); 2422 /// 2423 /// assert_eq!(result, [(0, 'a'), (1, 'b'), (2, 'c')]); 2424 /// ``` enumerate(self) -> Enumerate<Self>2425 fn enumerate(self) -> Enumerate<Self> { 2426 Enumerate::new(self) 2427 } 2428 2429 /// Creates an iterator that skips the first `n` elements. 2430 /// 2431 /// # Examples 2432 /// 2433 /// ``` 2434 /// use rayon::prelude::*; 2435 /// 2436 /// let result: Vec<_> = (0..100) 2437 /// .into_par_iter() 2438 /// .skip(95) 2439 /// .collect(); 2440 /// 2441 /// assert_eq!(result, [95, 96, 97, 98, 99]); 2442 /// ``` skip(self, n: usize) -> Skip<Self>2443 fn skip(self, n: usize) -> Skip<Self> { 2444 Skip::new(self, n) 2445 } 2446 2447 /// Creates an iterator that yields the first `n` elements. 2448 /// 2449 /// # Examples 2450 /// 2451 /// ``` 2452 /// use rayon::prelude::*; 2453 /// 2454 /// let result: Vec<_> = (0..100) 2455 /// .into_par_iter() 2456 /// .take(5) 2457 /// .collect(); 2458 /// 2459 /// assert_eq!(result, [0, 1, 2, 3, 4]); 2460 /// ``` take(self, n: usize) -> Take<Self>2461 fn take(self, n: usize) -> Take<Self> { 2462 Take::new(self, n) 2463 } 2464 2465 /// Searches for **some** item in the parallel iterator that 2466 /// matches the given predicate, and returns its index. Like 2467 /// `ParallelIterator::find_any`, the parallel search will not 2468 /// necessarily find the **first** match, and once a match is 2469 /// found we'll attempt to stop processing any more. 2470 /// 2471 /// # Examples 2472 /// 2473 /// ``` 2474 /// use rayon::prelude::*; 2475 /// 2476 /// let a = [1, 2, 3, 3]; 2477 /// 2478 /// let i = a.par_iter().position_any(|&x| x == 3).expect("found"); 2479 /// assert!(i == 2 || i == 3); 2480 /// 2481 /// assert_eq!(a.par_iter().position_any(|&x| x == 100), None); 2482 /// ``` position_any<P>(self, predicate: P) -> Option<usize> where P: Fn(Self::Item) -> bool + Sync + Send,2483 fn position_any<P>(self, predicate: P) -> Option<usize> 2484 where 2485 P: Fn(Self::Item) -> bool + Sync + Send, 2486 { 2487 #[inline] 2488 fn check(&(_, p): &(usize, bool)) -> bool { 2489 p 2490 } 2491 2492 let (i, _) = self.map(predicate).enumerate().find_any(check)?; 2493 Some(i) 2494 } 2495 2496 /// Searches for the sequentially **first** item in the parallel iterator 2497 /// that matches the given predicate, and returns its index. 2498 /// 2499 /// Like `ParallelIterator::find_first`, once a match is found, 2500 /// all attempts to the right of the match will be stopped, while 2501 /// attempts to the left must continue in case an earlier match 2502 /// is found. 2503 /// 2504 /// Note that not all parallel iterators have a useful order, much like 2505 /// sequential `HashMap` iteration, so "first" may be nebulous. If you 2506 /// just want the first match that discovered anywhere in the iterator, 2507 /// `position_any` is a better choice. 2508 /// 2509 /// # Examples 2510 /// 2511 /// ``` 2512 /// use rayon::prelude::*; 2513 /// 2514 /// let a = [1, 2, 3, 3]; 2515 /// 2516 /// assert_eq!(a.par_iter().position_first(|&x| x == 3), Some(2)); 2517 /// 2518 /// assert_eq!(a.par_iter().position_first(|&x| x == 100), None); 2519 /// ``` position_first<P>(self, predicate: P) -> Option<usize> where P: Fn(Self::Item) -> bool + Sync + Send,2520 fn position_first<P>(self, predicate: P) -> Option<usize> 2521 where 2522 P: Fn(Self::Item) -> bool + Sync + Send, 2523 { 2524 #[inline] 2525 fn check(&(_, p): &(usize, bool)) -> bool { 2526 p 2527 } 2528 2529 let (i, _) = self.map(predicate).enumerate().find_first(check)?; 2530 Some(i) 2531 } 2532 2533 /// Searches for the sequentially **last** item in the parallel iterator 2534 /// that matches the given predicate, and returns its index. 2535 /// 2536 /// Like `ParallelIterator::find_last`, once a match is found, 2537 /// all attempts to the left of the match will be stopped, while 2538 /// attempts to the right must continue in case a later match 2539 /// is found. 2540 /// 2541 /// Note that not all parallel iterators have a useful order, much like 2542 /// sequential `HashMap` iteration, so "last" may be nebulous. When the 2543 /// order doesn't actually matter to you, `position_any` is a better 2544 /// choice. 2545 /// 2546 /// # Examples 2547 /// 2548 /// ``` 2549 /// use rayon::prelude::*; 2550 /// 2551 /// let a = [1, 2, 3, 3]; 2552 /// 2553 /// assert_eq!(a.par_iter().position_last(|&x| x == 3), Some(3)); 2554 /// 2555 /// assert_eq!(a.par_iter().position_last(|&x| x == 100), None); 2556 /// ``` position_last<P>(self, predicate: P) -> Option<usize> where P: Fn(Self::Item) -> bool + Sync + Send,2557 fn position_last<P>(self, predicate: P) -> Option<usize> 2558 where 2559 P: Fn(Self::Item) -> bool + Sync + Send, 2560 { 2561 #[inline] 2562 fn check(&(_, p): &(usize, bool)) -> bool { 2563 p 2564 } 2565 2566 let (i, _) = self.map(predicate).enumerate().find_last(check)?; 2567 Some(i) 2568 } 2569 2570 #[doc(hidden)] 2571 #[deprecated( 2572 note = "parallel `position` does not search in order -- use `position_any`, \\ 2573 `position_first`, or `position_last`" 2574 )] position<P>(self, predicate: P) -> Option<usize> where P: Fn(Self::Item) -> bool + Sync + Send,2575 fn position<P>(self, predicate: P) -> Option<usize> 2576 where 2577 P: Fn(Self::Item) -> bool + Sync + Send, 2578 { 2579 self.position_any(predicate) 2580 } 2581 2582 /// Produces a new iterator with the elements of this iterator in 2583 /// reverse order. 2584 /// 2585 /// # Examples 2586 /// 2587 /// ``` 2588 /// use rayon::prelude::*; 2589 /// 2590 /// let result: Vec<_> = (0..5) 2591 /// .into_par_iter() 2592 /// .rev() 2593 /// .collect(); 2594 /// 2595 /// assert_eq!(result, [4, 3, 2, 1, 0]); 2596 /// ``` rev(self) -> Rev<Self>2597 fn rev(self) -> Rev<Self> { 2598 Rev::new(self) 2599 } 2600 2601 /// Sets the minimum length of iterators desired to process in each 2602 /// thread. Rayon will not split any smaller than this length, but 2603 /// of course an iterator could already be smaller to begin with. 2604 /// 2605 /// Producers like `zip` and `interleave` will use greater of the two 2606 /// minimums. 2607 /// Chained iterators and iterators inside `flat_map` may each use 2608 /// their own minimum length. 2609 /// 2610 /// # Examples 2611 /// 2612 /// ``` 2613 /// use rayon::prelude::*; 2614 /// 2615 /// let min = (0..1_000_000) 2616 /// .into_par_iter() 2617 /// .with_min_len(1234) 2618 /// .fold(|| 0, |acc, _| acc + 1) // count how many are in this segment 2619 /// .min().unwrap(); 2620 /// 2621 /// assert!(min >= 1234); 2622 /// ``` with_min_len(self, min: usize) -> MinLen<Self>2623 fn with_min_len(self, min: usize) -> MinLen<Self> { 2624 MinLen::new(self, min) 2625 } 2626 2627 /// Sets the maximum length of iterators desired to process in each 2628 /// thread. Rayon will try to split at least below this length, 2629 /// unless that would put it below the length from `with_min_len()`. 2630 /// For example, given min=10 and max=15, a length of 16 will not be 2631 /// split any further. 2632 /// 2633 /// Producers like `zip` and `interleave` will use lesser of the two 2634 /// maximums. 2635 /// Chained iterators and iterators inside `flat_map` may each use 2636 /// their own maximum length. 2637 /// 2638 /// # Examples 2639 /// 2640 /// ``` 2641 /// use rayon::prelude::*; 2642 /// 2643 /// let max = (0..1_000_000) 2644 /// .into_par_iter() 2645 /// .with_max_len(1234) 2646 /// .fold(|| 0, |acc, _| acc + 1) // count how many are in this segment 2647 /// .max().unwrap(); 2648 /// 2649 /// assert!(max <= 1234); 2650 /// ``` with_max_len(self, max: usize) -> MaxLen<Self>2651 fn with_max_len(self, max: usize) -> MaxLen<Self> { 2652 MaxLen::new(self, max) 2653 } 2654 2655 /// Produces an exact count of how many items this iterator will 2656 /// produce, presuming no panic occurs. 2657 /// 2658 /// # Examples 2659 /// 2660 /// ``` 2661 /// use rayon::prelude::*; 2662 /// 2663 /// let par_iter = (0..100).into_par_iter().zip(vec![0; 10]); 2664 /// assert_eq!(par_iter.len(), 10); 2665 /// 2666 /// let vec: Vec<_> = par_iter.collect(); 2667 /// assert_eq!(vec.len(), 10); 2668 /// ``` len(&self) -> usize2669 fn len(&self) -> usize; 2670 2671 /// Internal method used to define the behavior of this parallel 2672 /// iterator. You should not need to call this directly. 2673 /// 2674 /// This method causes the iterator `self` to start producing 2675 /// items and to feed them to the consumer `consumer` one by one. 2676 /// It may split the consumer before doing so to create the 2677 /// opportunity to produce in parallel. If a split does happen, it 2678 /// will inform the consumer of the index where the split should 2679 /// occur (unlike `ParallelIterator::drive_unindexed()`). 2680 /// 2681 /// See the [README] for more details on the internals of parallel 2682 /// iterators. 2683 /// 2684 /// [README]: README.md drive<C: Consumer<Self::Item>>(self, consumer: C) -> C::Result2685 fn drive<C: Consumer<Self::Item>>(self, consumer: C) -> C::Result; 2686 2687 /// Internal method used to define the behavior of this parallel 2688 /// iterator. You should not need to call this directly. 2689 /// 2690 /// This method converts the iterator into a producer P and then 2691 /// invokes `callback.callback()` with P. Note that the type of 2692 /// this producer is not defined as part of the API, since 2693 /// `callback` must be defined generically for all producers. This 2694 /// allows the producer type to contain references; it also means 2695 /// that parallel iterators can adjust that type without causing a 2696 /// breaking change. 2697 /// 2698 /// See the [README] for more details on the internals of parallel 2699 /// iterators. 2700 /// 2701 /// [README]: README.md with_producer<CB: ProducerCallback<Self::Item>>(self, callback: CB) -> CB::Output2702 fn with_producer<CB: ProducerCallback<Self::Item>>(self, callback: CB) -> CB::Output; 2703 } 2704 2705 /// `FromParallelIterator` implements the creation of a collection 2706 /// from a [`ParallelIterator`]. By implementing 2707 /// `FromParallelIterator` for a given type, you define how it will be 2708 /// created from an iterator. 2709 /// 2710 /// `FromParallelIterator` is used through [`ParallelIterator`]'s [`collect()`] method. 2711 /// 2712 /// [`ParallelIterator`]: trait.ParallelIterator.html 2713 /// [`collect()`]: trait.ParallelIterator.html#method.collect 2714 /// 2715 /// # Examples 2716 /// 2717 /// Implementing `FromParallelIterator` for your type: 2718 /// 2719 /// ``` 2720 /// use rayon::prelude::*; 2721 /// use std::mem; 2722 /// 2723 /// struct BlackHole { 2724 /// mass: usize, 2725 /// } 2726 /// 2727 /// impl<T: Send> FromParallelIterator<T> for BlackHole { 2728 /// fn from_par_iter<I>(par_iter: I) -> Self 2729 /// where I: IntoParallelIterator<Item = T> 2730 /// { 2731 /// let par_iter = par_iter.into_par_iter(); 2732 /// BlackHole { 2733 /// mass: par_iter.count() * mem::size_of::<T>(), 2734 /// } 2735 /// } 2736 /// } 2737 /// 2738 /// let bh: BlackHole = (0i32..1000).into_par_iter().collect(); 2739 /// assert_eq!(bh.mass, 4000); 2740 /// ``` 2741 pub trait FromParallelIterator<T> 2742 where 2743 T: Send, 2744 { 2745 /// Creates an instance of the collection from the parallel iterator `par_iter`. 2746 /// 2747 /// If your collection is not naturally parallel, the easiest (and 2748 /// fastest) way to do this is often to collect `par_iter` into a 2749 /// [`LinkedList`] or other intermediate data structure and then 2750 /// sequentially extend your collection. However, a more 'native' 2751 /// technique is to use the [`par_iter.fold`] or 2752 /// [`par_iter.fold_with`] methods to create the collection. 2753 /// Alternatively, if your collection is 'natively' parallel, you 2754 /// can use `par_iter.for_each` to process each element in turn. 2755 /// 2756 /// [`LinkedList`]: https://doc.rust-lang.org/std/collections/struct.LinkedList.html 2757 /// [`par_iter.fold`]: trait.ParallelIterator.html#method.fold 2758 /// [`par_iter.fold_with`]: trait.ParallelIterator.html#method.fold_with 2759 /// [`par_iter.for_each`]: trait.ParallelIterator.html#method.for_each from_par_iter<I>(par_iter: I) -> Self where I: IntoParallelIterator<Item = T>2760 fn from_par_iter<I>(par_iter: I) -> Self 2761 where 2762 I: IntoParallelIterator<Item = T>; 2763 } 2764 2765 /// `ParallelExtend` extends an existing collection with items from a [`ParallelIterator`]. 2766 /// 2767 /// [`ParallelIterator`]: trait.ParallelIterator.html 2768 /// 2769 /// # Examples 2770 /// 2771 /// Implementing `ParallelExtend` for your type: 2772 /// 2773 /// ``` 2774 /// use rayon::prelude::*; 2775 /// use std::mem; 2776 /// 2777 /// struct BlackHole { 2778 /// mass: usize, 2779 /// } 2780 /// 2781 /// impl<T: Send> ParallelExtend<T> for BlackHole { 2782 /// fn par_extend<I>(&mut self, par_iter: I) 2783 /// where I: IntoParallelIterator<Item = T> 2784 /// { 2785 /// let par_iter = par_iter.into_par_iter(); 2786 /// self.mass += par_iter.count() * mem::size_of::<T>(); 2787 /// } 2788 /// } 2789 /// 2790 /// let mut bh = BlackHole { mass: 0 }; 2791 /// bh.par_extend(0i32..1000); 2792 /// assert_eq!(bh.mass, 4000); 2793 /// bh.par_extend(0i64..10); 2794 /// assert_eq!(bh.mass, 4080); 2795 /// ``` 2796 pub trait ParallelExtend<T> 2797 where 2798 T: Send, 2799 { 2800 /// Extends an instance of the collection with the elements drawn 2801 /// from the parallel iterator `par_iter`. 2802 /// 2803 /// # Examples 2804 /// 2805 /// ``` 2806 /// use rayon::prelude::*; 2807 /// 2808 /// let mut vec = vec![]; 2809 /// vec.par_extend(0..5); 2810 /// vec.par_extend((0..5).into_par_iter().map(|i| i * i)); 2811 /// assert_eq!(vec, [0, 1, 2, 3, 4, 0, 1, 4, 9, 16]); 2812 /// ``` par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = T>2813 fn par_extend<I>(&mut self, par_iter: I) 2814 where 2815 I: IntoParallelIterator<Item = T>; 2816 } 2817 2818 /// We hide the `Try` trait in a private module, as it's only meant to be a 2819 /// stable clone of the standard library's `Try` trait, as yet unstable. 2820 mod private { 2821 /// Clone of `std::ops::Try`. 2822 /// 2823 /// Implementing this trait is not permitted outside of `rayon`. 2824 pub trait Try { 2825 private_decl! {} 2826 2827 type Ok; 2828 type Error; into_result(self) -> Result<Self::Ok, Self::Error>2829 fn into_result(self) -> Result<Self::Ok, Self::Error>; from_ok(v: Self::Ok) -> Self2830 fn from_ok(v: Self::Ok) -> Self; from_error(v: Self::Error) -> Self2831 fn from_error(v: Self::Error) -> Self; 2832 } 2833 2834 impl<T> Try for Option<T> { 2835 private_impl! {} 2836 2837 type Ok = T; 2838 type Error = (); 2839 into_result(self) -> Result<T, ()>2840 fn into_result(self) -> Result<T, ()> { 2841 self.ok_or(()) 2842 } from_ok(v: T) -> Self2843 fn from_ok(v: T) -> Self { 2844 Some(v) 2845 } from_error(_: ()) -> Self2846 fn from_error(_: ()) -> Self { 2847 None 2848 } 2849 } 2850 2851 impl<T, E> Try for Result<T, E> { 2852 private_impl! {} 2853 2854 type Ok = T; 2855 type Error = E; 2856 into_result(self) -> Result<T, E>2857 fn into_result(self) -> Result<T, E> { 2858 self 2859 } from_ok(v: T) -> Self2860 fn from_ok(v: T) -> Self { 2861 Ok(v) 2862 } from_error(v: E) -> Self2863 fn from_error(v: E) -> Self { 2864 Err(v) 2865 } 2866 } 2867 } 2868