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