]>
Commit | Line | Data |
---|---|---|
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 |
82 | use self::plumbing::*; |
83 | use self::private::Try; | |
2c00a5a8 XL |
84 | pub use either::Either; |
85 | use std::cmp::{self, Ordering}; | |
532ac7d7 | 86 | use std::iter::{Product, Sum}; |
923072b8 FG |
87 | use std::ops::{Fn, RangeBounds}; |
88 | ||
89 | pub mod plumbing; | |
90 | ||
91 | #[cfg(test)] | |
92 | mod 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 | 105 | mod chain; |
2c00a5a8 | 106 | mod chunks; |
923072b8 | 107 | mod cloned; |
2c00a5a8 | 108 | mod collect; |
923072b8 FG |
109 | mod copied; |
110 | mod empty; | |
2c00a5a8 | 111 | mod enumerate; |
923072b8 | 112 | mod extend; |
2c00a5a8 | 113 | mod filter; |
2c00a5a8 | 114 | mod filter_map; |
923072b8 FG |
115 | mod find; |
116 | mod find_first_last; | |
2c00a5a8 | 117 | mod flat_map; |
923072b8 | 118 | mod flat_map_iter; |
2c00a5a8 | 119 | mod flatten; |
923072b8 | 120 | mod flatten_iter; |
532ac7d7 XL |
121 | mod fold; |
122 | mod for_each; | |
2c00a5a8 | 123 | mod from_par_iter; |
923072b8 | 124 | mod inspect; |
2c00a5a8 | 125 | mod interleave; |
2c00a5a8 | 126 | mod interleave_shortest; |
2c00a5a8 | 127 | mod intersperse; |
2c00a5a8 | 128 | mod len; |
923072b8 FG |
129 | mod map; |
130 | mod map_with; | |
131 | mod multizip; | |
132 | mod noop; | |
133 | mod once; | |
e74abb32 | 134 | mod panic_fuse; |
923072b8 FG |
135 | mod par_bridge; |
136 | mod positions; | |
137 | mod product; | |
138 | mod reduce; | |
2c00a5a8 | 139 | mod repeat; |
923072b8 FG |
140 | mod rev; |
141 | mod skip; | |
142 | mod splitter; | |
143 | mod sum; | |
144 | mod take; | |
145 | mod try_fold; | |
146 | mod try_reduce; | |
147 | mod try_reduce_with; | |
532ac7d7 | 148 | mod unzip; |
923072b8 FG |
149 | mod update; |
150 | mod while_some; | |
151 | mod zip; | |
152 | mod zip_eq; | |
2c00a5a8 | 153 | |
923072b8 FG |
154 | pub 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 | ||
192 | mod step_by; | |
193 | #[cfg(has_step_by_rev)] | |
194 | pub 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 | |
204 | pub 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 | |
249 | pub 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 | ||
275 | impl<'data, I: 'data + ?Sized> IntoParallelRefIterator<'data> for I | |
532ac7d7 XL |
276 | where |
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 | |
300 | pub 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 | ||
322 | impl<'data, I: 'data + ?Sized> IntoParallelRefMutIterator<'data> for I | |
532ac7d7 XL |
323 | where |
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 | |
348 | pub 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 | ||
2230 | impl<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 |
2244 | pub 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 | /// ``` | |
2950 | pub trait FromParallelIterator<T> | |
532ac7d7 XL |
2951 | where |
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 | /// ``` | |
3005 | pub trait ParallelExtend<T> | |
532ac7d7 XL |
3006 | where |
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 | |
3034 | pub 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 | |
3076 | pub 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. | |
3147 | mod 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 | } |