diff options
52 files changed, 1422 insertions, 282 deletions
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json index e778cc0..b29a8ee 100644 --- a/.cargo_vcs_info.json +++ b/.cargo_vcs_info.json @@ -1,5 +1,5 @@ { "git": { - "sha1": "4dac4c718895d8c0347d90be70f478673dd28193" + "sha1": "20c09bd4fed037fa3df6f2a6a1e717b01be89f11" } } diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml index efc779f..143ac2b 100644 --- a/.github/workflows/ci.yml +++ b/.github/workflows/ci.yml @@ -38,14 +38,3 @@ jobs: steps: - name: Mark the job as successful run: exit 0 - - end-failure: - name: bors build finished - if: "!success()" - runs-on: ubuntu-latest - needs: [msrv,stable] - - steps: - - name: Mark the job as a failure - run: exit 1 - diff --git a/CHANGELOG.md b/CHANGELOG.md index 67633ab..41c4ab0 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -1,5 +1,48 @@ # Changelog +## 0.10.1 + - Add `Itertools::contains` (#514) + - Add `Itertools::counts_by` (#515) + - Add `Itertools::partition_result` (#511) + - Add `Itertools::all_unique` (#241) + - Add `Itertools::duplicates` and `Itertools::duplicates_by` (#502) + - Add `chain!` (#525) + - Add `Itertools::at_most_one` (#523) + - Add `Itertools::flatten_ok` (#527) + - Add `EitherOrBoth::or_default` (#583) + - Add `Itertools::find_or_last` and `Itertools::find_or_first` (#535) + - Implement `FusedIterator` for `FilterOk`, `FilterMapOk`, `InterleaveShortest`, `KMergeBy`, `MergeBy`, `PadUsing`, `Positions`, `Product` , `RcIter`, `TupleWindows`, `Unique`, `UniqueBy`, `Update`, `WhileSome`, `Combinations`, `CombinationsWithReplacement`, `Powerset`, `RepeatN`, and `WithPosition` (#550) + - Implement `FusedIterator` for `Interleave`, `IntersperseWith`, and `ZipLongest` (#548) + +## 0.10.0 + - **Increase minimum supported Rust version to 1.32.0** + - Improve macro hygiene (#507) + - Add `Itertools::powerset` (#335) + - Add `Itertools::sorted_unstable`, `Itertools::sorted_unstable_by`, and `Itertools::sorted_unstable_by_key` (#494) + - Implement `Error` for `ExactlyOneError` (#484) + - Undeprecate `Itertools::fold_while` (#476) + - Tuple-related adapters work for tuples of arity up to 12 (#475) + - `use_alloc` feature for users who have `alloc`, but not `std` (#474) + - Add `Itertools::k_smallest` (#473) + - Add `Itertools::into_grouping_map` and `GroupingMap` (#465) + - Add `Itertools::into_grouping_map_by` and `GroupingMapBy` (#465) + - Add `Itertools::counts` (#468) + - Add implementation of `DoubleEndedIterator` for `Unique` (#442) + - Add implementation of `DoubleEndedIterator` for `UniqueBy` (#442) + - Add implementation of `DoubleEndedIterator` for `Zip` (#346) + - Add `Itertools::multipeek` (#435) + - Add `Itertools::dedup_with_count` and `DedupWithCount` (#423) + - Add `Itertools::dedup_by_with_count` and `DedupByWithCount` (#423) + - Add `Itertools::intersperse_with` and `IntersperseWith` (#381) + - Add `Itertools::filter_ok` and `FilterOk` (#377) + - Add `Itertools::filter_map_ok` and `FilterMapOk` (#377) + - Deprecate `Itertools::fold_results`, use `Itertools::fold_ok` instead (#377) + - Deprecate `Itertools::map_results`, use `Itertools::map_ok` instead (#377) + - Deprecate `FoldResults`, use `FoldOk` instead (#377) + - Deprecate `MapResults`, use `MapOk` instead (#377) + - Add `Itertools::circular_tuple_windows` and `CircularTupleWindows` (#350) + - Add `peek_nth` and `PeekNth` (#303) + ## 0.9.0 - Fix potential overflow in `MergeJoinBy::size_hint` (#385) - Add `derive(Clone)` where possible (#382) @@ -163,7 +206,7 @@ ## 0.5.1 - Workaround module/function name clash that made racer crash on completing itertools. Only internal changes needed. ## 0.5.0 - - [Release announcement](http://bluss.github.io/rust/2016/09/26/itertools-0.5.0/) + - [Release announcement](https://bluss.github.io/rust/2016/09/26/itertools-0.5.0/) - Renamed: - `combinations` is now `tuple_combinations` - `combinations_n` to `combinations` @@ -217,7 +260,7 @@ ## 0.4.15 - Fixup on top of the workaround in 0.4.14. A function in `itertools::free` was removed by mistake and now it is added back again. ## 0.4.14 - - Workaround an upstream regression in a rust nightly build that broke compilation of of `itertools::free::{interleave, merge}` + - Workaround an upstream regression in a Rust nightly build that broke compilation of of `itertools::free::{interleave, merge}` ## 0.4.13 - Add `.minmax()` and `.minmax_by_key()`, iterator methods for finding both minimum and maximum in one scan. - Add `.format_default()`, a simpler version of `.format()` (lazy formatting for iterators). @@ -283,9 +326,9 @@ ## 0.3.19 - Added `.group_by_lazy()`, a possibly nonallocating group by - Added `.format()`, a nonallocating formatting helper for iterators - - Remove uses of `RandomAccessIterator` since it has been deprecated in rust. + - Remove uses of `RandomAccessIterator` since it has been deprecated in Rust. ## 0.3.17 - - Added (adopted) `Unfold` from rust + - Added (adopted) `Unfold` from Rust ## 0.3.16 - Added adaptors `.unique()`, `.unique_by()` ## 0.3.15 @@ -13,7 +13,7 @@ [package] edition = "2018" name = "itertools" -version = "0.10.0" +version = "0.10.1" authors = ["bluss"] exclude = ["/bors.toml"] description = "Extra iterator adaptors, iterator methods, free functions, and macros." @@ -21,7 +21,7 @@ documentation = "https://docs.rs/itertools/" keywords = ["iterator", "data-structure", "zip", "product", "group-by"] categories = ["algorithms", "rust-patterns"] license = "MIT/Apache-2.0" -repository = "https://github.com/bluss/rust-itertools" +repository = "https://github.com/rust-itertools/itertools" [package.metadata.release] no-dev-version = true [profile.bench] diff --git a/Cargo.toml.orig b/Cargo.toml.orig index 46b2094..d7f6b23 100644 --- a/Cargo.toml.orig +++ b/Cargo.toml.orig @@ -1,9 +1,9 @@ [package] name = "itertools" -version = "0.10.0" +version = "0.10.1" license = "MIT/Apache-2.0" -repository = "https://github.com/bluss/rust-itertools" +repository = "https://github.com/rust-itertools/itertools" documentation = "https://docs.rs/itertools/" authors = ["bluss"] @@ -27,8 +27,8 @@ either = { version = "1.0", default-features = false } [dev-dependencies] rand = "0.7" -criterion = "=0" # TODO how could this work with our minimum supported rust version? -paste = "1.0.0" # Used in test_std to instanciate generic tests +criterion = "=0" # TODO how could this work with our minimum supported Rust version? +paste = "1.0.0" # Used in test_std to instantiate generic tests [dev-dependencies.quickcheck] version = "0.9" @@ -7,13 +7,13 @@ third_party { } url { type: ARCHIVE - value: "https://static.crates.io/crates/itertools/itertools-0.10.0.crate" + value: "https://static.crates.io/crates/itertools/itertools-0.10.1.crate" } - version: "0.10.0" + version: "0.10.1" license_type: NOTICE last_upgrade_date { year: 2021 - month: 4 - day: 1 + month: 6 + day: 21 } } @@ -13,7 +13,7 @@ __ https://docs.rs/itertools/ .. |build_status| image:: https://travis-ci.org/rust-itertools/itertools.svg?branch=master .. _build_status: https://travis-ci.org/rust-itertools/itertools -.. |crates| image:: http://meritbadge.herokuapp.com/itertools +.. |crates| image:: https://meritbadge.herokuapp.com/itertools .. _crates: https://crates.io/crates/itertools How to use with cargo: @@ -21,7 +21,7 @@ How to use with cargo: .. code:: toml [dependencies] - itertools = "0.9" + itertools = "0.10.0" How to use in your crate: @@ -36,7 +36,7 @@ How to contribute - Include tests for your new feature, preferably a quickcheck test - Make a Pull Request -For new features, please first consider filing a PR to `rust-lang/rust <https://github.com/rust-lang/rust/>`_, +For new features, please first consider filing a PR to `rust-lang/rust <https://github.com/rust-lang/rust>`_, adding your new feature to the `Iterator` trait of the standard library, if you believe it is reasonable. If it isn't accepted there, proposing it for inclusion in ``itertools`` is a good idea. The reason for doing is this is so that we avoid future breakage as with ``.flatten()``. @@ -49,7 +49,7 @@ License Dual-licensed to be compatible with the Rust project. Licensed under the Apache License, Version 2.0 -http://www.apache.org/licenses/LICENSE-2.0 or the MIT license -http://opensource.org/licenses/MIT, at your +https://www.apache.org/licenses/LICENSE-2.0 or the MIT license +https://opensource.org/licenses/MIT, at your option. This file may not be copied, modified, or distributed except according to those terms. diff --git a/TEST_MAPPING b/TEST_MAPPING new file mode 100644 index 0000000..19817ee --- /dev/null +++ b/TEST_MAPPING @@ -0,0 +1,11 @@ +// Generated by update_crate_tests.py for tests that depend on this crate. +{ + "presubmit": [ + { + "name": "unicode-xid_device_test_src_lib" + }, + { + "name": "unicode-xid_device_test_tests_exhaustive_tests" + } + ] +} diff --git a/src/adaptors/coalesce.rs b/src/adaptors/coalesce.rs index 116f688..1afbee5 100644 --- a/src/adaptors/coalesce.rs +++ b/src/adaptors/coalesce.rs @@ -40,20 +40,21 @@ where fn next(&mut self) -> Option<Self::Item> { // this fuses the iterator - let mut last = match self.last.take() { - None => return None, - Some(x) => x, - }; - for next in &mut self.iter { - match self.f.coalesce_pair(last, next) { - Ok(joined) => last = joined, - Err((last_, next_)) => { - self.last = Some(next_); - return Some(last_); - } - } - } - Some(last) + let last = self.last.take()?; + + let self_last = &mut self.last; + let self_f = &mut self.f; + Some( + self.iter + .try_fold(last, |last, next| match self_f.coalesce_pair(last, next) { + Ok(joined) => Ok(joined), + Err((last_, next_)) => { + *self_last = Some(next_); + Err(last_) + } + }) + .unwrap_or_else(|x| x), + ) } fn size_hint(&self) -> (usize, Option<usize>) { @@ -84,7 +85,7 @@ impl<I: Iterator, F: CoalescePredicate<I::Item, T>, T> FusedIterator for Coalesc /// An iterator adaptor that may join together adjacent elements. /// -/// See [`.coalesce()`](../trait.Itertools.html#method.coalesce) for more information. +/// See [`.coalesce()`](crate::Itertools::coalesce) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub type Coalesce<I, F> = CoalesceBy<I, F, <I as Iterator>::Item>; @@ -111,7 +112,7 @@ where /// An iterator adaptor that removes repeated duplicates, determining equality using a comparison function. /// -/// See [`.dedup_by()`](../trait.Itertools.html#method.dedup_by) or [`.dedup()`](../trait.Itertools.html#method.dedup) for more information. +/// See [`.dedup_by()`](crate::Itertools::dedup_by) or [`.dedup()`](crate::Itertools::dedup) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub type DedupBy<I, Pred> = CoalesceBy<I, DedupPred2CoalescePred<Pred>, <I as Iterator>::Item>; @@ -165,7 +166,7 @@ where /// An iterator adaptor that removes repeated duplicates. /// -/// See [`.dedup()`](../trait.Itertools.html#method.dedup) for more information. +/// See [`.dedup()`](crate::Itertools::dedup) for more information. pub type Dedup<I> = DedupBy<I, DedupEq>; /// Create a new `Dedup`. @@ -179,8 +180,8 @@ where /// An iterator adaptor that removes repeated duplicates, while keeping a count of how many /// repeated elements were present. This will determine equality using a comparison function. /// -/// See [`.dedup_by_with_count()`](../trait.Itertools.html#method.dedup_by_with_count) or -/// [`.dedup_with_count()`](../trait.Itertools.html#method.dedup_with_count) for more information. +/// See [`.dedup_by_with_count()`](crate::Itertools::dedup_by_with_count) or +/// [`.dedup_with_count()`](crate::Itertools::dedup_with_count) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub type DedupByWithCount<I, Pred> = CoalesceBy<I, DedupPredWithCount2CoalescePred<Pred>, (usize, <I as Iterator>::Item)>; @@ -208,7 +209,7 @@ where /// An iterator adaptor that removes repeated duplicates, while keeping a count of how many /// repeated elements were present. /// -/// See [`.dedup_with_count()`](../trait.Itertools.html#method.dedup_with_count) for more information. +/// See [`.dedup_with_count()`](crate::Itertools::dedup_with_count) for more information. pub type DedupWithCount<I> = DedupByWithCount<I, DedupEq>; /// Create a new `DedupByWithCount`. diff --git a/src/adaptors/map.rs b/src/adaptors/map.rs index ff377f7..eee5cc3 100644 --- a/src/adaptors/map.rs +++ b/src/adaptors/map.rs @@ -64,10 +64,10 @@ where /// An iterator adapter to apply a transformation within a nested `Result::Ok`. /// -/// See [`.map_ok()`](../trait.Itertools.html#method.map_ok) for more information. +/// See [`.map_ok()`](crate::Itertools::map_ok) for more information. pub type MapOk<I, F> = MapSpecialCase<I, MapSpecialCaseFnOk<F>>; -/// See [`MapOk`](struct.MapOk.html). +/// See [`MapOk`]. #[deprecated(note = "Use MapOk instead", since = "0.10.0")] pub type MapResults<I, F> = MapOk<I, F>; @@ -98,7 +98,7 @@ where /// An iterator adapter to apply `Into` conversion to each element. /// -/// See [`.map_into()`](../trait.Itertools.html#method.map_into) for more information. +/// See [`.map_into()`](crate::Itertools::map_into) for more information. pub type MapInto<I, R> = MapSpecialCase<I, MapSpecialCaseFnInto<R>>; impl<T: Into<U>, U> MapSpecialCaseFn<T> for MapSpecialCaseFnInto<U> { @@ -111,7 +111,7 @@ impl<T: Into<U>, U> MapSpecialCaseFn<T> for MapSpecialCaseFnInto<U> { #[derive(Clone)] pub struct MapSpecialCaseFnInto<U>(PhantomData<U>); -/// Create a new [`MapInto`](struct.MapInto.html) iterator. +/// Create a new [`MapInto`] iterator. pub fn map_into<I, R>(iter: I) -> MapInto<I, R> { MapSpecialCase { iter, diff --git a/src/adaptors/mod.rs b/src/adaptors/mod.rs index 8a8697b..bd0d93a 100644 --- a/src/adaptors/mod.rs +++ b/src/adaptors/mod.rs @@ -1,6 +1,6 @@ //! Licensed under the Apache License, Version 2.0 -//! http://www.apache.org/licenses/LICENSE-2.0 or the MIT license -//! http://opensource.org/licenses/MIT, at your +//! <https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +//! <https://opensource.org/licenses/MIT>, at your //! option. This file may not be copied, modified, or distributed //! except according to those terms. @@ -15,7 +15,7 @@ pub use self::map::MapResults; pub use self::multi_product::*; use std::fmt; -use std::iter::{Fuse, Peekable, FromIterator}; +use std::iter::{Fuse, Peekable, FromIterator, FusedIterator}; use std::marker::PhantomData; use crate::size_hint; @@ -24,7 +24,7 @@ use crate::size_hint; /// /// This iterator is *fused*. /// -/// See [`.interleave()`](../trait.Itertools.html#method.interleave) for more information. +/// See [`.interleave()`](crate::Itertools::interleave) for more information. #[derive(Clone, Debug)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Interleave<I, J> { @@ -35,9 +35,9 @@ pub struct Interleave<I, J> { /// Create an iterator that interleaves elements in `i` and `j`. /// -/// `IntoIterator` enabled version of `i.interleave(j)`. +/// [`IntoIterator`] enabled version of `i.interleave(j)`. /// -/// See [`.interleave()`](trait.Itertools.html#method.interleave) for more information. +/// See [`.interleave()`](crate::Itertools::interleave) for more information. pub fn interleave<I, J>(i: I, j: J) -> Interleave<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter> where I: IntoIterator, J: IntoIterator<Item = I::Item> @@ -75,12 +75,17 @@ impl<I, J> Iterator for Interleave<I, J> } } +impl<I, J> FusedIterator for Interleave<I, J> + where I: Iterator, + J: Iterator<Item = I::Item> +{} + /// An iterator adaptor that alternates elements from the two iterators until /// one of them runs out. /// /// This iterator is *fused*. /// -/// See [`.interleave_shortest()`](../trait.Itertools.html#method.interleave_shortest) +/// See [`.interleave_shortest()`](crate::Itertools::interleave_shortest) /// for more information. #[derive(Clone, Debug)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] @@ -157,6 +162,11 @@ impl<I, J> Iterator for InterleaveShortest<I, J> } } +impl<I, J> FusedIterator for InterleaveShortest<I, J> + where I: FusedIterator, + J: FusedIterator<Item = I::Item> +{} + #[derive(Clone, Debug)] /// An iterator adaptor that allows putting back a single /// item to the front of the iterator. @@ -271,7 +281,7 @@ impl<I> Iterator for PutBack<I> /// /// Iterator element type is `(I::Item, J::Item)`. /// -/// See [`.cartesian_product()`](../trait.Itertools.html#method.cartesian_product) for more information. +/// See [`.cartesian_product()`](crate::Itertools::cartesian_product) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Product<I, J> where I: Iterator @@ -361,12 +371,18 @@ impl<I, J> Iterator for Product<I, J> } } +impl<I, J> FusedIterator for Product<I, J> + where I: FusedIterator, + J: Clone + FusedIterator, + I::Item: Clone +{} + /// A “meta iterator adaptor”. Its closure receives a reference to the iterator /// and may pick off as many elements as it likes, to produce the next iterator element. /// /// Iterator element type is *X*, if the return type of `F` is *Option\<X\>*. /// -/// See [`.batching()`](../trait.Itertools.html#method.batching) for more information. +/// See [`.batching()`](crate::Itertools::batching) for more information. #[derive(Clone)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Batching<I, F> { @@ -400,7 +416,7 @@ impl<B, F, I> Iterator for Batching<I, F> /// The iterator steps by yielding the next element from the base iterator, /// then skipping forward *n-1* elements. /// -/// See [`.step()`](../trait.Itertools.html#method.step) for more information. +/// See [`.step()`](crate::Itertools::step) for more information. #[deprecated(note="Use std .step_by() instead", since="0.8.0")] #[allow(deprecated)] #[derive(Clone, Debug)] @@ -475,13 +491,13 @@ impl<T: PartialOrd> MergePredicate<T> for MergeLte { /// /// Iterator element type is `I::Item`. /// -/// See [`.merge()`](../trait.Itertools.html#method.merge_by) for more information. +/// See [`.merge()`](crate::Itertools::merge_by) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub type Merge<I, J> = MergeBy<I, J, MergeLte>; /// Create an iterator that merges elements in `i` and `j`. /// -/// `IntoIterator` enabled version of `i.merge(j)`. +/// [`IntoIterator`] enabled version of [`Itertools::merge`](crate::Itertools::merge). /// /// ``` /// use itertools::merge; @@ -503,7 +519,7 @@ pub fn merge<I, J>(i: I, j: J) -> Merge<<I as IntoIterator>::IntoIter, <J as Int /// /// Iterator element type is `I::Item`. /// -/// See [`.merge_by()`](../trait.Itertools.html#method.merge_by) for more information. +/// See [`.merge_by()`](crate::Itertools::merge_by) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct MergeBy<I, J, F> where I: Iterator, @@ -588,10 +604,16 @@ impl<I, J, F> Iterator for MergeBy<I, J, F> } } +impl<I, J, F> FusedIterator for MergeBy<I, J, F> + where I: FusedIterator, + J: FusedIterator<Item = I::Item>, + F: MergePredicate<I::Item> +{} + /// An iterator adaptor that borrows from a `Clone`-able iterator /// to only pick off elements while the predicate returns `true`. /// -/// See [`.take_while_ref()`](../trait.Itertools.html#method.take_while_ref) for more information. +/// See [`.take_while_ref()`](crate::Itertools::take_while_ref) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct TakeWhileRef<'a, I: 'a, F> { iter: &'a mut I, @@ -640,7 +662,7 @@ impl<'a, I, F> Iterator for TakeWhileRef<'a, I, F> /// An iterator adaptor that filters `Option<A>` iterator elements /// and produces `A`. Stops on the first `None` encountered. /// -/// See [`.while_some()`](../trait.Itertools.html#method.while_some) for more information. +/// See [`.while_some()`](crate::Itertools::while_some) for more information. #[derive(Clone, Debug)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct WhileSome<I> { @@ -672,7 +694,7 @@ impl<I, A> Iterator for WhileSome<I> /// An iterator to iterate through all combinations in a `Clone`-able iterator that produces tuples /// of a specific size. /// -/// See [`.tuple_combinations()`](../trait.Itertools.html#method.tuple_combinations) for more +/// See [`.tuple_combinations()`](crate::Itertools::tuple_combinations) for more /// information. #[derive(Clone, Debug)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] @@ -682,7 +704,6 @@ pub struct TupleCombinations<I, T> { iter: T::Combination, _mi: PhantomData<I>, - _mt: PhantomData<T> } pub trait HasCombination<I>: Sized { @@ -698,7 +719,6 @@ pub fn tuple_combinations<T, I>(iter: I) -> TupleCombinations<I, T> TupleCombinations { iter: T::Combination::from(iter), _mi: PhantomData, - _mt: PhantomData, } } @@ -713,6 +733,11 @@ impl<I, T> Iterator for TupleCombinations<I, T> } } +impl<I, T> FusedIterator for TupleCombinations<I, T> + where I: FusedIterator, + T: HasCombination<I>, +{} + #[derive(Clone, Debug)] pub struct Tuple1Combination<I> { iter: I, @@ -737,7 +762,7 @@ impl<I: Iterator> HasCombination<I> for (I::Item,) { } macro_rules! impl_tuple_combination { - ($C:ident $P:ident ; $A:ident, $($I:ident),* ; $($X:ident)*) => ( + ($C:ident $P:ident ; $($X:ident)*) => ( #[derive(Clone, Debug)] pub struct $C<I: Iterator> { item: Option<I::Item>, @@ -747,30 +772,25 @@ macro_rules! impl_tuple_combination { impl<I: Iterator + Clone> From<I> for $C<I> { fn from(mut iter: I) -> Self { - $C { + Self { item: iter.next(), iter: iter.clone(), - c: $P::from(iter), + c: iter.into(), } } } impl<I: Iterator + Clone> From<I> for $C<Fuse<I>> { fn from(iter: I) -> Self { - let mut iter = iter.fuse(); - $C { - item: iter.next(), - iter: iter.clone(), - c: $P::from(iter), - } + Self::from(iter.fuse()) } } - impl<I, $A> Iterator for $C<I> - where I: Iterator<Item = $A> + Clone, + impl<I, A> Iterator for $C<I> + where I: Iterator<Item = A> + Clone, I::Item: Clone { - type Item = ($($I),*); + type Item = (A, $(ignore_ident!($X, A)),*); fn next(&mut self) -> Option<Self::Item> { if let Some(($($X),*,)) = self.c.next() { @@ -779,15 +799,15 @@ macro_rules! impl_tuple_combination { } else { self.item = self.iter.next(); self.item.clone().and_then(|z| { - self.c = $P::from(self.iter.clone()); + self.c = self.iter.clone().into(); self.c.next().map(|($($X),*,)| (z, $($X),*)) }) } } } - impl<I, $A> HasCombination<I> for ($($I),*) - where I: Iterator<Item = $A> + Clone, + impl<I, A> HasCombination<I> for (A, $(ignore_ident!($X, A)),*) + where I: Iterator<Item = A> + Clone, I::Item: Clone { type Combination = $C<Fuse<I>>; @@ -800,29 +820,28 @@ macro_rules! impl_tuple_combination { // use itertools::Itertools; // // for i in 2..=12 { -// println!("impl_tuple_combination!(Tuple{arity}Combination Tuple{prev}Combination; {tys}; {idents});", +// println!("impl_tuple_combination!(Tuple{arity}Combination Tuple{prev}Combination; {idents});", // arity = i, // prev = i - 1, -// tys = iter::repeat("A").take(i + 1).join(", "), // idents = ('a'..'z').take(i - 1).join(" "), // ); // } // It could probably be replaced by a bit more macro cleverness. -impl_tuple_combination!(Tuple2Combination Tuple1Combination; A, A, A; a); -impl_tuple_combination!(Tuple3Combination Tuple2Combination; A, A, A, A; a b); -impl_tuple_combination!(Tuple4Combination Tuple3Combination; A, A, A, A, A; a b c); -impl_tuple_combination!(Tuple5Combination Tuple4Combination; A, A, A, A, A, A; a b c d); -impl_tuple_combination!(Tuple6Combination Tuple5Combination; A, A, A, A, A, A, A; a b c d e); -impl_tuple_combination!(Tuple7Combination Tuple6Combination; A, A, A, A, A, A, A, A; a b c d e f); -impl_tuple_combination!(Tuple8Combination Tuple7Combination; A, A, A, A, A, A, A, A, A; a b c d e f g); -impl_tuple_combination!(Tuple9Combination Tuple8Combination; A, A, A, A, A, A, A, A, A, A; a b c d e f g h); -impl_tuple_combination!(Tuple10Combination Tuple9Combination; A, A, A, A, A, A, A, A, A, A, A; a b c d e f g h i); -impl_tuple_combination!(Tuple11Combination Tuple10Combination; A, A, A, A, A, A, A, A, A, A, A, A; a b c d e f g h i j); -impl_tuple_combination!(Tuple12Combination Tuple11Combination; A, A, A, A, A, A, A, A, A, A, A, A, A; a b c d e f g h i j k); +impl_tuple_combination!(Tuple2Combination Tuple1Combination; a); +impl_tuple_combination!(Tuple3Combination Tuple2Combination; a b); +impl_tuple_combination!(Tuple4Combination Tuple3Combination; a b c); +impl_tuple_combination!(Tuple5Combination Tuple4Combination; a b c d); +impl_tuple_combination!(Tuple6Combination Tuple5Combination; a b c d e); +impl_tuple_combination!(Tuple7Combination Tuple6Combination; a b c d e f); +impl_tuple_combination!(Tuple8Combination Tuple7Combination; a b c d e f g); +impl_tuple_combination!(Tuple9Combination Tuple8Combination; a b c d e f g h); +impl_tuple_combination!(Tuple10Combination Tuple9Combination; a b c d e f g h i); +impl_tuple_combination!(Tuple11Combination Tuple10Combination; a b c d e f g h i j); +impl_tuple_combination!(Tuple12Combination Tuple11Combination; a b c d e f g h i j k); /// An iterator adapter to filter values within a nested `Result::Ok`. /// -/// See [`.filter_ok()`](../trait.Itertools.html#method.filter_ok) for more information. +/// See [`.filter_ok()`](crate::Itertools::filter_ok) for more information. #[derive(Clone)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct FilterOk<I, F> { @@ -884,9 +903,14 @@ impl<I, F, T, E> Iterator for FilterOk<I, F> } } +impl<I, F, T, E> FusedIterator for FilterOk<I, F> + where I: FusedIterator<Item = Result<T, E>>, + F: FnMut(&T) -> bool, +{} + /// An iterator adapter to filter and apply a transformation on values within a nested `Result::Ok`. /// -/// See [`.filter_map_ok()`](../trait.Itertools.html#method.filter_map_ok) for more information. +/// See [`.filter_map_ok()`](crate::Itertools::filter_map_ok) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct FilterMapOk<I, F> { iter: I, @@ -955,9 +979,14 @@ impl<I, F, T, U, E> Iterator for FilterMapOk<I, F> } } +impl<I, F, T, U, E> FusedIterator for FilterMapOk<I, F> + where I: FusedIterator<Item = Result<T, E>>, + F: FnMut(T) -> Option<U>, +{} + /// An iterator adapter to get the positions of each element that matches a predicate. /// -/// See [`.positions()`](../trait.Itertools.html#method.positions) for more information. +/// See [`.positions()`](crate::Itertools::positions) for more information. #[derive(Clone)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Positions<I, F> { @@ -1014,9 +1043,14 @@ impl<I, F> DoubleEndedIterator for Positions<I, F> } } +impl<I, F> FusedIterator for Positions<I, F> + where I: FusedIterator, + F: FnMut(I::Item) -> bool, +{} + /// An iterator adapter to apply a mutating function to each element before yielding it. /// -/// See [`.update()`](../trait.Itertools.html#method.update) for more information. +/// See [`.update()`](crate::Itertools::update) for more information. #[derive(Clone)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Update<I, F> { @@ -1089,3 +1123,9 @@ where } } } + +impl<I, F> FusedIterator for Update<I, F> +where + I: FusedIterator, + F: FnMut(&mut I::Item), +{} diff --git a/src/adaptors/multi_product.rs b/src/adaptors/multi_product.rs index 6938014..9708ef4 100644 --- a/src/adaptors/multi_product.rs +++ b/src/adaptors/multi_product.rs @@ -11,7 +11,7 @@ use alloc::vec::Vec; /// /// An iterator element type is `Vec<I>`. /// -/// See [`.multi_cartesian_product()`](../trait.Itertools.html#method.multi_cartesian_product) +/// See [`.multi_cartesian_product()`](crate::Itertools::multi_cartesian_product) /// for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct MultiProduct<I>(Vec<MultiProductIter<I>>) diff --git a/src/combinations.rs b/src/combinations.rs index e6ba4ac..68a59c5 100644 --- a/src/combinations.rs +++ b/src/combinations.rs @@ -1,11 +1,12 @@ use std::fmt; +use std::iter::FusedIterator; use super::lazy_buffer::LazyBuffer; use alloc::vec::Vec; /// An iterator to iterate through all the `k`-length combinations in an iterator. /// -/// See [`.combinations()`](../trait.Itertools.html#method.combinations) for more information. +/// See [`.combinations()`](crate::Itertools::combinations) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Combinations<I: Iterator> { indices: Vec<usize>, @@ -47,9 +48,7 @@ impl<I: Iterator> Combinations<I> { pub fn k(&self) -> usize { self.indices.len() } /// Returns the (current) length of the pool from which combination elements are - /// selected. This value can change between invocations of [`next`]. - /// - /// [`next`]: #method.next + /// selected. This value can change between invocations of [`next`](Combinations::next). #[inline] pub fn n(&self) -> usize { self.pool.len() } @@ -122,3 +121,8 @@ impl<I> Iterator for Combinations<I> Some(self.indices.iter().map(|i| self.pool[*i].clone()).collect()) } } + +impl<I> FusedIterator for Combinations<I> + where I: Iterator, + I::Item: Clone +{} diff --git a/src/combinations_with_replacement.rs b/src/combinations_with_replacement.rs index 7e7a802..81b13f1 100644 --- a/src/combinations_with_replacement.rs +++ b/src/combinations_with_replacement.rs @@ -1,11 +1,13 @@ use alloc::vec::Vec; use std::fmt; +use std::iter::FusedIterator; use super::lazy_buffer::LazyBuffer; /// An iterator to iterate through all the `n`-length combinations in an iterator, with replacement. /// -/// See [`.combinations_with_replacement()`](../trait.Itertools.html#method.combinations_with_replacement) for more information. +/// See [`.combinations_with_replacement()`](crate::Itertools::combinations_with_replacement) +/// for more information. #[derive(Clone)] pub struct CombinationsWithReplacement<I> where @@ -99,3 +101,9 @@ where } } } + +impl<I> FusedIterator for CombinationsWithReplacement<I> +where + I: Iterator, + I::Item: Clone, +{} diff --git a/src/concat_impl.rs b/src/concat_impl.rs index 0233d01..450f7fc 100644 --- a/src/concat_impl.rs +++ b/src/concat_impl.rs @@ -1,8 +1,8 @@ use crate::Itertools; -/// Combine all an iterator's elements into one element by using `Extend`. +/// Combine all an iterator's elements into one element by using [`Extend`]. /// -/// `IntoIterator`-enabled version of `.concat()` +/// [`IntoIterator`]-enabled version of [`Itertools::concat`]. /// /// This combinator will extend the first item with each of the rest of the /// items of the iterator. If the iterator is empty, the default value of diff --git a/src/diff.rs b/src/diff.rs index c196d8d..1731f06 100644 --- a/src/diff.rs +++ b/src/diff.rs @@ -1,14 +1,14 @@ //! "Diff"ing iterators for caching elements to sequential collections without requiring the new //! elements' iterator to be `Clone`. //! -//! - [**Diff**](./enum.Diff.html) (produced by the [**diff_with**](./fn.diff_with.html) function) +//! - [`Diff`] (produced by the [`diff_with`] function) //! describes the difference between two non-`Clone` iterators `I` and `J` after breaking ASAP from //! a lock-step comparison. use crate::free::put_back; use crate::structs::PutBack; -/// A type returned by the [`diff_with`](./fn.diff_with.html) function. +/// A type returned by the [`diff_with`] function. /// /// `Diff` represents the way in which the elements yielded by the iterator `I` differ to some /// iterator `J`. @@ -26,7 +26,7 @@ pub enum Diff<I, J> } /// Compares every element yielded by both `i` and `j` with the given function in lock-step and -/// returns a `Diff` which describes how `j` differs from `i`. +/// returns a [`Diff`] which describes how `j` differs from `i`. /// /// If the number of elements yielded by `j` is less than the number of elements yielded by `i`, /// the number of `j` elements yielded will be returned along with `i`'s remaining elements as diff --git a/src/duplicates_impl.rs b/src/duplicates_impl.rs new file mode 100644 index 0000000..42049df --- /dev/null +++ b/src/duplicates_impl.rs @@ -0,0 +1,206 @@ +use std::hash::Hash; + +mod private { + use std::collections::HashMap; + use std::hash::Hash; + use std::fmt; + + #[derive(Clone)] + #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] + pub struct DuplicatesBy<I: Iterator, Key, F> { + pub(crate) iter: I, + pub(crate) meta: Meta<Key, F>, + } + + impl<I, V, F> fmt::Debug for DuplicatesBy<I, V, F> + where + I: Iterator + fmt::Debug, + V: fmt::Debug + Hash + Eq, + { + debug_fmt_fields!(DuplicatesBy, iter, meta.used); + } + + impl<I: Iterator, Key: Eq + Hash, F> DuplicatesBy<I, Key, F> { + pub(crate) fn new(iter: I, key_method: F) -> Self { + DuplicatesBy { + iter, + meta: Meta { + used: HashMap::new(), + pending: 0, + key_method, + }, + } + } + } + + #[derive(Clone)] + pub struct Meta<Key, F> { + used: HashMap<Key, bool>, + pending: usize, + key_method: F, + } + + impl<Key, F> Meta<Key, F> + where + Key: Eq + Hash, + { + /// Takes an item and returns it back to the caller if it's the second time we see it. + /// Otherwise the item is consumed and None is returned + #[inline(always)] + fn filter<I>(&mut self, item: I) -> Option<I> + where + F: KeyMethod<Key, I>, + { + let kv = self.key_method.make(item); + match self.used.get_mut(kv.key_ref()) { + None => { + self.used.insert(kv.key(), false); + self.pending += 1; + None + } + Some(true) => None, + Some(produced) => { + *produced = true; + self.pending -= 1; + Some(kv.value()) + } + } + } + } + + impl<I, Key, F> Iterator for DuplicatesBy<I, Key, F> + where + I: Iterator, + Key: Eq + Hash, + F: KeyMethod<Key, I::Item>, + { + type Item = I::Item; + + fn next(&mut self) -> Option<Self::Item> { + let DuplicatesBy { iter, meta } = self; + iter.find_map(|v| meta.filter(v)) + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + let (_, hi) = self.iter.size_hint(); + // There are `hi` number of items left in the base iterator. In the best case scenario, + // these items are exactly the same as the ones pending (i.e items seen exactly once so + // far), plus (hi - pending) / 2 pairs of never seen before items. + let hi = hi.map(|hi| { + let max_pending = std::cmp::min(self.meta.pending, hi); + let max_new = std::cmp::max(hi - self.meta.pending, 0) / 2; + max_pending + max_new + }); + // The lower bound is always 0 since we might only get unique items from now on + (0, hi) + } + } + + impl<I, Key, F> DoubleEndedIterator for DuplicatesBy<I, Key, F> + where + I: DoubleEndedIterator, + Key: Eq + Hash, + F: KeyMethod<Key, I::Item>, + { + fn next_back(&mut self) -> Option<Self::Item> { + let DuplicatesBy { iter, meta } = self; + iter.rev().find_map(|v| meta.filter(v)) + } + } + + /// A keying method for use with `DuplicatesBy` + pub trait KeyMethod<K, V> { + type Container: KeyXorValue<K, V>; + + fn make(&mut self, value: V) -> Self::Container; + } + + /// Apply the identity function to elements before checking them for equality. + pub struct ById; + impl<V> KeyMethod<V, V> for ById { + type Container = JustValue<V>; + + fn make(&mut self, v: V) -> Self::Container { + JustValue(v) + } + } + + /// Apply a user-supplied function to elements before checking them for equality. + pub struct ByFn<F>(pub(crate) F); + impl<K, V, F> KeyMethod<K, V> for ByFn<F> + where + F: FnMut(&V) -> K, + { + type Container = KeyValue<K, V>; + + fn make(&mut self, v: V) -> Self::Container { + KeyValue((self.0)(&v), v) + } + } + + // Implementors of this trait can hold onto a key and a value but only give access to one of them + // at a time. This allows the key and the value to be the same value internally + pub trait KeyXorValue<K, V> { + fn key_ref(&self) -> &K; + fn key(self) -> K; + fn value(self) -> V; + } + + pub struct KeyValue<K, V>(K, V); + impl<K, V> KeyXorValue<K, V> for KeyValue<K, V> { + fn key_ref(&self) -> &K { + &self.0 + } + fn key(self) -> K { + self.0 + } + fn value(self) -> V { + self.1 + } + } + + pub struct JustValue<V>(V); + impl<V> KeyXorValue<V, V> for JustValue<V> { + fn key_ref(&self) -> &V { + &self.0 + } + fn key(self) -> V { + self.0 + } + fn value(self) -> V { + self.0 + } + } +} + +/// An iterator adapter to filter for duplicate elements. +/// +/// See [`.duplicates_by()`](crate::Itertools::duplicates_by) for more information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub type DuplicatesBy<I, V, F> = private::DuplicatesBy<I, V, private::ByFn<F>>; + +/// Create a new `DuplicatesBy` iterator. +pub fn duplicates_by<I, Key, F>(iter: I, f: F) -> DuplicatesBy<I, Key, F> +where + Key: Eq + Hash, + F: FnMut(&I::Item) -> Key, + I: Iterator, +{ + DuplicatesBy::new(iter, private::ByFn(f)) +} + +/// An iterator adapter to filter out duplicate elements. +/// +/// See [`.duplicates()`](crate::Itertools::duplicates) for more information. +pub type Duplicates<I> = private::DuplicatesBy<I, <I as Iterator>::Item, private::ById>; + +/// Create a new `Duplicates` iterator. +pub fn duplicates<I>(iter: I) -> Duplicates<I> +where + I: Iterator, + I::Item: Eq + Hash, +{ + Duplicates::new(iter, private::ById) +} + diff --git a/src/either_or_both.rs b/src/either_or_both.rs index a03a4f1..28d1df7 100644 --- a/src/either_or_both.rs +++ b/src/either_or_both.rs @@ -25,7 +25,7 @@ impl<A, B> EitherOrBoth<A, B> { } /// If Left, return true otherwise, return false. - /// Exclusive version of [`has_left`]. + /// Exclusive version of [`has_left`](EitherOrBoth::has_left). pub fn is_left(&self) -> bool { match *self { Left(_) => true, @@ -34,7 +34,7 @@ impl<A, B> EitherOrBoth<A, B> { } /// If Right, return true otherwise, return false. - /// Exclusive version of [`has_right`]. + /// Exclusive version of [`has_right`](EitherOrBoth::has_right). pub fn is_right(&self) -> bool { match *self { Right(_) => true, @@ -140,7 +140,7 @@ impl<A, B> EitherOrBoth<A, B> { } } - /// Apply the function `f` on the value `b` in `Right(b)` or `Both(a, _)` variants if it is + /// Apply the function `f` on the value `a` in `Left(a)` or `Both(a, _)` variants if it is /// present. pub fn left_and_then<F, L>(self, f: F) -> EitherOrBoth<L, B> where @@ -152,8 +152,8 @@ impl<A, B> EitherOrBoth<A, B> { } } - /// Apply the function `f` on the value `a` - /// in `Left(a)` or `Both(a, _)` variants if it is present. + /// Apply the function `f` on the value `b` + /// in `Right(b)` or `Both(_, b)` variants if it is present. pub fn right_and_then<F, R>(self, f: F) -> EitherOrBoth<A, R> where F: FnOnce(B) -> EitherOrBoth<A, R>, @@ -163,6 +163,21 @@ impl<A, B> EitherOrBoth<A, B> { Right(b) | Both(_, b) => f(b), } } + + /// Returns a tuple consisting of the `l` and `r` in `Both(l, r)`, if present. + /// Otherwise, returns the wrapped value for the present element, and the [`default`](Default::default) + /// for the other. + pub fn or_default(self) -> (A, B) + where + A: Default, + B: Default, + { + match self { + EitherOrBoth::Left(l) => (l, B::default()), + EitherOrBoth::Right(r) => (A::default(), r), + EitherOrBoth::Both(l, r) => (l, r), + } + } } impl<T> EitherOrBoth<T, T> { diff --git a/src/flatten_ok.rs b/src/flatten_ok.rs new file mode 100644 index 0000000..d46bbde --- /dev/null +++ b/src/flatten_ok.rs @@ -0,0 +1,166 @@ +use crate::size_hint; +use std::{ + fmt, + iter::{DoubleEndedIterator, FusedIterator}, +}; + +pub fn flatten_ok<I, T, E>(iter: I) -> FlattenOk<I, T, E> +where + I: Iterator<Item = Result<T, E>>, + T: IntoIterator, +{ + FlattenOk { + iter, + inner_front: None, + inner_back: None, + } +} + +/// An iterator adaptor that flattens `Result::Ok` values and +/// allows `Result::Err` values through unchanged. +/// +/// See [`.flatten_ok()`](crate::Itertools::flatten_ok) for more information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct FlattenOk<I, T, E> +where + I: Iterator<Item = Result<T, E>>, + T: IntoIterator, +{ + iter: I, + inner_front: Option<T::IntoIter>, + inner_back: Option<T::IntoIter>, +} + +impl<I, T, E> Iterator for FlattenOk<I, T, E> +where + I: Iterator<Item = Result<T, E>>, + T: IntoIterator, +{ + type Item = Result<T::Item, E>; + + fn next(&mut self) -> Option<Self::Item> { + loop { + // Handle the front inner iterator. + if let Some(inner) = &mut self.inner_front { + if let Some(item) = inner.next() { + return Some(Ok(item)); + } else { + // This is necessary for the iterator to implement `FusedIterator` + // with only the orginal iterator being fused. + self.inner_front = None; + } + } + + match self.iter.next() { + Some(Ok(ok)) => self.inner_front = Some(ok.into_iter()), + Some(Err(e)) => return Some(Err(e)), + None => { + // Handle the back inner iterator. + if let Some(inner) = &mut self.inner_back { + if let Some(item) = inner.next() { + return Some(Ok(item)); + } else { + // This is necessary for the iterator to implement `FusedIterator` + // with only the orginal iterator being fused. + self.inner_back = None; + } + } else { + return None; + } + } + } + } + } + + fn size_hint(&self) -> (usize, Option<usize>) { + let inner_hint = |inner: &Option<T::IntoIter>| { + inner + .as_ref() + .map(Iterator::size_hint) + .unwrap_or((0, Some(0))) + }; + let inner_front = inner_hint(&self.inner_front); + let inner_back = inner_hint(&self.inner_back); + // The outer iterator `Ok` case could be (0, None) as we don't know its size_hint yet. + let outer = match self.iter.size_hint() { + (0, Some(0)) => (0, Some(0)), + _ => (0, None), + }; + + size_hint::add(size_hint::add(inner_front, inner_back), outer) + } +} + +impl<I, T, E> DoubleEndedIterator for FlattenOk<I, T, E> +where + I: DoubleEndedIterator<Item = Result<T, E>>, + T: IntoIterator, + T::IntoIter: DoubleEndedIterator, +{ + fn next_back(&mut self) -> Option<Self::Item> { + loop { + // Handle the back inner iterator. + if let Some(inner) = &mut self.inner_back { + if let Some(item) = inner.next_back() { + return Some(Ok(item)); + } else { + // This is necessary for the iterator to implement `FusedIterator` + // with only the orginal iterator being fused. + self.inner_back = None; + } + } + + match self.iter.next_back() { + Some(Ok(ok)) => self.inner_back = Some(ok.into_iter()), + Some(Err(e)) => return Some(Err(e)), + None => { + // Handle the front inner iterator. + if let Some(inner) = &mut self.inner_front { + if let Some(item) = inner.next_back() { + return Some(Ok(item)); + } else { + // This is necessary for the iterator to implement `FusedIterator` + // with only the orginal iterator being fused. + self.inner_front = None; + } + } else { + return None; + } + } + } + } + } +} + +impl<I, T, E> Clone for FlattenOk<I, T, E> +where + I: Iterator<Item = Result<T, E>> + Clone, + T: IntoIterator, + T::IntoIter: Clone, +{ + #[inline] + clone_fields!(iter, inner_front, inner_back); +} + +impl<I, T, E> fmt::Debug for FlattenOk<I, T, E> +where + I: Iterator<Item = Result<T, E>> + fmt::Debug, + T: IntoIterator, + T::IntoIter: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("FlattenOk") + .field("iter", &self.iter) + .field("inner_front", &self.inner_front) + .field("inner_back", &self.inner_back) + .finish() + } +} + +/// Only the iterator being flattened needs to implement [`FusedIterator`]. +impl<I, T, E> FusedIterator for FlattenOk<I, T, E> +where + I: FusedIterator<Item = Result<T, E>>, + T: IntoIterator, +{ +} diff --git a/src/format.rs b/src/format.rs index ec2dc7a..d87cee9 100644 --- a/src/format.rs +++ b/src/format.rs @@ -6,7 +6,7 @@ use std::cell::RefCell; /// The format value can only be formatted once, after that the iterator is /// exhausted. /// -/// See [`.format_with()`](../trait.Itertools.html#method.format_with) for more information. +/// See [`.format_with()`](crate::Itertools::format_with) for more information. #[derive(Clone)] pub struct FormatWith<'a, I, F> { sep: &'a str, @@ -19,7 +19,7 @@ pub struct FormatWith<'a, I, F> { /// The format value can only be formatted once, after that the iterator is /// exhausted. /// -/// See [`.format()`](../trait.Itertools.html#method.format) +/// See [`.format()`](crate::Itertools::format) /// for more information. #[derive(Clone)] pub struct Format<'a, I> { diff --git a/src/free.rs b/src/free.rs index bfc5ab4..c78dc1d 100644 --- a/src/free.rs +++ b/src/free.rs @@ -1,6 +1,6 @@ //! Free functions that create iterator adaptors or call iterator methods. //! -//! The benefit of free functions is that they accept any `IntoIterator` as +//! The benefit of free functions is that they accept any [`IntoIterator`] as //! argument, so the resulting code may be easier to read. #[cfg(feature = "use_alloc")] @@ -37,7 +37,7 @@ pub use crate::rciter_impl::rciter; /// Iterate `iterable` with a running index. /// -/// `IntoIterator` enabled version of `.enumerate()`. +/// [`IntoIterator`] enabled version of [`Iterator::enumerate`]. /// /// ``` /// use itertools::enumerate; @@ -54,7 +54,7 @@ pub fn enumerate<I>(iterable: I) -> iter::Enumerate<I::IntoIter> /// Iterate `iterable` in reverse. /// -/// `IntoIterator` enabled version of `.rev()`. +/// [`IntoIterator`] enabled version of [`Iterator::rev`]. /// /// ``` /// use itertools::rev; @@ -72,7 +72,7 @@ pub fn rev<I>(iterable: I) -> iter::Rev<I::IntoIter> /// Iterate `i` and `j` in lock step. /// -/// `IntoIterator` enabled version of `i.zip(j)`. +/// [`IntoIterator`] enabled version of [`Iterator::zip`]. /// /// ``` /// use itertools::zip; @@ -91,7 +91,7 @@ pub fn zip<I, J>(i: I, j: J) -> Zip<I::IntoIter, J::IntoIter> /// Create an iterator that first iterates `i` and then `j`. /// -/// `IntoIterator` enabled version of `i.chain(j)`. +/// [`IntoIterator`] enabled version of [`Iterator::chain`]. /// /// ``` /// use itertools::chain; @@ -109,7 +109,7 @@ pub fn chain<I, J>(i: I, j: J) -> iter::Chain<<I as IntoIterator>::IntoIter, <J /// Create an iterator that clones each element from &T to T /// -/// `IntoIterator` enabled version of `i.cloned()`. +/// [`IntoIterator`] enabled version of [`Iterator::cloned`]. /// /// ``` /// use itertools::cloned; @@ -125,7 +125,7 @@ pub fn cloned<'a, I, T: 'a>(iterable: I) -> iter::Cloned<I::IntoIter> /// Perform a fold operation over the iterable. /// -/// `IntoIterator` enabled version of `i.fold(init, f)` +/// [`IntoIterator`] enabled version of [`Iterator::fold`]. /// /// ``` /// use itertools::fold; @@ -141,7 +141,7 @@ pub fn fold<I, B, F>(iterable: I, init: B, f: F) -> B /// Test whether the predicate holds for all elements in the iterable. /// -/// `IntoIterator` enabled version of `i.all(f)` +/// [`IntoIterator`] enabled version of [`Iterator::all`]. /// /// ``` /// use itertools::all; @@ -157,7 +157,7 @@ pub fn all<I, F>(iterable: I, f: F) -> bool /// Test whether the predicate holds for any elements in the iterable. /// -/// `IntoIterator` enabled version of `i.any(f)` +/// [`IntoIterator`] enabled version of [`Iterator::any`]. /// /// ``` /// use itertools::any; @@ -173,7 +173,7 @@ pub fn any<I, F>(iterable: I, f: F) -> bool /// Return the maximum value of the iterable. /// -/// `IntoIterator` enabled version of `i.max()`. +/// [`IntoIterator`] enabled version of [`Iterator::max`]. /// /// ``` /// use itertools::max; @@ -189,7 +189,7 @@ pub fn max<I>(iterable: I) -> Option<I::Item> /// Return the minimum value of the iterable. /// -/// `IntoIterator` enabled version of `i.min()`. +/// [`IntoIterator`] enabled version of [`Iterator::min`]. /// /// ``` /// use itertools::min; @@ -206,7 +206,7 @@ pub fn min<I>(iterable: I) -> Option<I::Item> /// Combine all iterator elements into one String, seperated by `sep`. /// -/// `IntoIterator` enabled version of `iterable.join(sep)`. +/// [`IntoIterator`] enabled version of [`Itertools::join`]. /// /// ``` /// use itertools::join; @@ -223,9 +223,7 @@ pub fn join<I>(iterable: I, sep: &str) -> String /// Sort all iterator elements into a new iterator in ascending order. /// -/// `IntoIterator` enabled version of [`iterable.sorted()`][1]. -/// -/// [1]: trait.Itertools.html#method.sorted +/// [`IntoIterator`] enabled version of [`Itertools::sorted`]. /// /// ``` /// use itertools::sorted; diff --git a/src/group_map.rs b/src/group_map.rs index 4231de0..a2d0ebb 100644 --- a/src/group_map.rs +++ b/src/group_map.rs @@ -6,7 +6,7 @@ use std::iter::Iterator; /// Return a `HashMap` of keys mapped to a list of their corresponding values. /// -/// See [`.into_group_map()`](../trait.Itertools.html#method.into_group_map) +/// See [`.into_group_map()`](crate::Itertools::into_group_map) /// for more information. pub fn into_group_map<I, K, V>(iter: I) -> HashMap<K, Vec<V>> where I: Iterator<Item=(K, V)>, diff --git a/src/groupbylazy.rs b/src/groupbylazy.rs index 5d4a0c9..91c52ea 100644 --- a/src/groupbylazy.rs +++ b/src/groupbylazy.rs @@ -279,12 +279,12 @@ impl<K, I, F> GroupInner<K, I, F> /// no allocations. It needs allocations only if several group iterators /// are alive at the same time. /// -/// This type implements `IntoIterator` (it is **not** an iterator +/// This type implements [`IntoIterator`] (it is **not** an iterator /// itself), because the group iterators need to borrow from this /// value. It should be stored in a local variable or temporary and /// iterated. /// -/// See [`.group_by()`](../trait.Itertools.html#method.group_by) for more information. +/// See [`.group_by()`](crate::Itertools::group_by) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct GroupBy<K, I, F> where I: Iterator, @@ -354,7 +354,7 @@ impl<'a, K, I, F> IntoIterator for &'a GroupBy<K, I, F> /// Iterator element type is `(K, Group)`: /// the group's key `K` and the group's iterator. /// -/// See [`.group_by()`](../trait.Itertools.html#method.group_by) for more information. +/// See [`.group_by()`](crate::Itertools::group_by) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Groups<'a, K: 'a, I: 'a, F: 'a> where I: Iterator, @@ -453,14 +453,14 @@ pub fn new_chunks<J>(iter: J, size: usize) -> IntoChunks<J::IntoIter> /// `IntoChunks` behaves just like `GroupBy`: it is iterable, and /// it only buffers if several chunk iterators are alive at the same time. /// -/// This type implements `IntoIterator` (it is **not** an iterator +/// This type implements [`IntoIterator`] (it is **not** an iterator /// itself), because the chunk iterators need to borrow from this /// value. It should be stored in a local variable or temporary and /// iterated. /// /// Iterator element type is `Chunk`, each chunk's iterator. /// -/// See [`.chunks()`](../trait.Itertools.html#method.chunks) for more information. +/// See [`.chunks()`](crate::Itertools::chunks) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct IntoChunks<I> where I: Iterator, @@ -505,7 +505,7 @@ impl<'a, I> IntoIterator for &'a IntoChunks<I> /// /// Iterator element type is `Chunk`. /// -/// See [`.chunks()`](../trait.Itertools.html#method.chunks) for more information. +/// See [`.chunks()`](crate::Itertools::chunks) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Chunks<'a, I: 'a> where I: Iterator, diff --git a/src/grouping_map.rs b/src/grouping_map.rs index 5232f5d..be22ec8 100644 --- a/src/grouping_map.rs +++ b/src/grouping_map.rs @@ -7,7 +7,7 @@ use std::hash::Hash; use std::iter::Iterator; use std::ops::{Add, Mul}; -/// A wrapper to allow for an easy [`into_grouping_map_by`](../trait.Itertools.html#method.into_grouping_map_by) +/// A wrapper to allow for an easy [`into_grouping_map_by`](crate::Itertools::into_grouping_map_by) #[derive(Clone, Debug)] pub struct MapForGrouping<I, F>(I, F); @@ -38,7 +38,7 @@ pub fn new<I, K, V>(iter: I) -> GroupingMap<I> /// `GroupingMapBy` is an intermediate struct for efficient group-and-fold operations. /// -/// See [`GroupingMap`](./struct.GroupingMap.html) for more informations. +/// See [`GroupingMap`] for more informations. #[must_use = "GroupingMapBy is lazy and do nothing unless consumed"] pub type GroupingMapBy<I, F> = GroupingMap<MapForGrouping<I, F>>; @@ -102,12 +102,12 @@ impl<I, K, V> GroupingMap<I> { let mut destination_map = HashMap::new(); - for (key, val) in self.iter { + self.iter.for_each(|(key, val)| { let acc = destination_map.remove(&key); if let Some(op_res) = operation(acc, &key, val) { destination_map.insert(key, op_res); } - } + }); destination_map } @@ -160,7 +160,7 @@ impl<I, K, V> GroupingMap<I> /// /// Return a `HashMap` associating the key of each group with the result of folding that group's elements. /// - /// [`fold`]: #tymethod.fold + /// [`fold`]: GroupingMap::fold /// /// ``` /// use itertools::Itertools; @@ -208,9 +208,9 @@ impl<I, K, V> GroupingMap<I> { let mut destination_map = HashMap::new(); - for (key, val) in self.iter { + self.iter.for_each(|(key, val)| { destination_map.entry(key).or_insert_with(C::default).extend(Some(val)); - } + }); destination_map } @@ -377,7 +377,7 @@ impl<I, K, V> GroupingMap<I> /// If several elements are equally maximum, the last element is picked. /// If several elements are equally minimum, the first element is picked. /// - /// See [.minmax()](../trait.Itertools.html#method.minmax) for the non-grouping version. + /// See [.minmax()](crate::Itertools::minmax) for the non-grouping version. /// /// Differences from the non grouping version: /// - It never produces a `MinMaxResult::NoElements` diff --git a/src/impl_macros.rs b/src/impl_macros.rs index 04ab8e1..3da8c63 100644 --- a/src/impl_macros.rs +++ b/src/impl_macros.rs @@ -22,3 +22,7 @@ macro_rules! clone_fields { } } } + +macro_rules! ignore_ident{ + ($id:ident, $($t:tt)*) => {$($t)*}; +} diff --git a/src/intersperse.rs b/src/intersperse.rs index a0d79b0..2c660d4 100644 --- a/src/intersperse.rs +++ b/src/intersperse.rs @@ -1,4 +1,4 @@ -use std::iter::Fuse; +use std::iter::{Fuse, FusedIterator}; use super::size_hint; pub trait IntersperseElement<Item> { @@ -21,7 +21,7 @@ impl<Item: Clone> IntersperseElement<Item> for IntersperseElementSimple<Item> { /// /// This iterator is *fused*. /// -/// See [`.intersperse()`](../trait.Itertools.html#method.intersperse) for more information. +/// See [`.intersperse()`](crate::Itertools::intersperse) for more information. pub type Intersperse<I> = IntersperseWith<I, IntersperseElementSimple<<I as Iterator>::Item>>; /// Create a new Intersperse iterator @@ -44,7 +44,7 @@ impl<Item, F: FnMut()->Item> IntersperseElement<Item> for F { /// /// This iterator is *fused*. /// -/// See [`.intersperse_with()`](../trait.Itertools.html#method.intersperse_with) for more information. +/// See [`.intersperse_with()`](crate::Itertools::intersperse_with) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] #[derive(Clone, Debug)] pub struct IntersperseWith<I, ElemF> @@ -112,3 +112,8 @@ impl<I, ElemF> Iterator for IntersperseWith<I, ElemF> }) } } + +impl<I, ElemF> FusedIterator for IntersperseWith<I, ElemF> + where I: Iterator, + ElemF: IntersperseElement<I::Item> +{} diff --git a/src/k_smallest.rs b/src/k_smallest.rs index d58ec70..acaea59 100644 --- a/src/k_smallest.rs +++ b/src/k_smallest.rs @@ -6,7 +6,7 @@ pub(crate) fn k_smallest<T: Ord, I: Iterator<Item = T>>(mut iter: I, k: usize) - let mut heap = iter.by_ref().take(k).collect::<BinaryHeap<_>>(); - for i in iter { + iter.for_each(|i| { debug_assert_eq!(heap.len(), k); // Equivalent to heap.push(min(i, heap.pop())) but more efficient. // This should be done with a single `.peek_mut().unwrap()` but @@ -14,7 +14,7 @@ pub(crate) fn k_smallest<T: Ord, I: Iterator<Item = T>>(mut iter: I, k: usize) - if *heap.peek().unwrap() > i { *heap.peek_mut().unwrap() = i; } - } + }); heap } diff --git a/src/kmerge_impl.rs b/src/kmerge_impl.rs index a1b3d8e..dce5b78 100644 --- a/src/kmerge_impl.rs +++ b/src/kmerge_impl.rs @@ -2,6 +2,7 @@ use crate::size_hint; use crate::Itertools; use alloc::vec::Vec; +use std::iter::FusedIterator; use std::mem::replace; use std::fmt; @@ -74,14 +75,13 @@ fn sift_down<T, S>(heap: &mut [T], index: usize, mut less_than: S) debug_assert!(index <= heap.len()); let mut pos = index; let mut child = 2 * pos + 1; - // the `pos` conditional is to avoid a bounds check - while pos < heap.len() && child < heap.len() { - let right = child + 1; - + // Require the right child to be present + // This allows to find the index of the smallest child without a branch + // that wouldn't be predicted if present + while child + 1 < heap.len() { // pick the smaller of the two children - if right < heap.len() && less_than(&heap[right], &heap[child]) { - child = right; - } + // use aritmethic to avoid an unpredictable branch + child += less_than(&heap[child+1], &heap[child]) as usize; // sift down is done if we are already in order if !less_than(&heap[child], &heap[pos]) { @@ -91,6 +91,11 @@ fn sift_down<T, S>(heap: &mut [T], index: usize, mut less_than: S) pos = child; child = 2 * pos + 1; } + // Check if the last (left) child was an only child + // if it is then it has to be compared with the parent + if child + 1 == heap.len() && less_than(&heap[child], &heap[pos]) { + heap.swap(pos, child); + } } /// An iterator adaptor that merges an abitrary number of base iterators in ascending order. @@ -98,7 +103,7 @@ fn sift_down<T, S>(heap: &mut [T], index: usize, mut less_than: S) /// /// Iterator element type is `I::Item`. /// -/// See [`.kmerge()`](../trait.Itertools.html#method.kmerge) for more information. +/// See [`.kmerge()`](crate::Itertools::kmerge) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub type KMerge<I> = KMergeBy<I, KMergeByLt>; @@ -146,7 +151,7 @@ pub fn kmerge<I>(iterable: I) -> KMerge<<I::Item as IntoIterator>::IntoIter> /// /// Iterator element type is `I::Item`. /// -/// See [`.kmerge_by()`](../trait.Itertools.html#method.kmerge_by) for more +/// See [`.kmerge_by()`](crate::Itertools::kmerge_by) for more /// information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct KMergeBy<I, F> @@ -215,3 +220,8 @@ impl<I, F> Iterator for KMergeBy<I, F> .unwrap_or((0, Some(0))) } } + +impl<I, F> FusedIterator for KMergeBy<I, F> + where I: Iterator, + F: KMergePredicate<I::Item> +{} @@ -5,13 +5,13 @@ //! Extra iterator adaptors, functions and macros. //! //! To extend [`Iterator`] with methods in this crate, import -//! the [`Itertools` trait](./trait.Itertools.html): +//! the [`Itertools`] trait: //! //! ``` //! use itertools::Itertools; //! ``` //! -//! Now, new methods like [`interleave`](./trait.Itertools.html#method.interleave) +//! Now, new methods like [`interleave`](Itertools::interleave) //! are available on all iterators: //! //! ``` @@ -43,8 +43,6 @@ //! ## Rust Version //! //! This version of itertools requires Rust 1.32 or later. -//! -//! [`Iterator`]: https://doc.rust-lang.org/std/iter/trait.Iterator.html #![doc(html_root_url="https://docs.rs/itertools/0.8/")] #[cfg(not(feature = "use_std"))] @@ -61,12 +59,15 @@ use alloc::{ pub use either::Either; +use core::borrow::Borrow; #[cfg(feature = "use_std")] use std::collections::HashMap; use std::iter::{IntoIterator, once}; use std::cmp::Ordering; use std::fmt; #[cfg(feature = "use_std")] +use std::collections::HashSet; +#[cfg(feature = "use_std")] use std::hash::Hash; #[cfg(feature = "use_alloc")] use std::fmt::Write; @@ -118,6 +119,7 @@ pub mod structs { pub use crate::cons_tuples_impl::ConsTuples; pub use crate::exactly_one_err::ExactlyOneError; pub use crate::format::{Format, FormatWith}; + pub use crate::flatten_ok::FlattenOk; #[cfg(feature = "use_std")] pub use crate::grouping_map::{GroupingMap, GroupingMapBy}; #[cfg(feature = "use_alloc")] @@ -148,6 +150,8 @@ pub mod structs { pub use crate::tee::Tee; pub use crate::tuple_impl::{TupleBuffer, TupleWindows, CircularTupleWindows, Tuples}; #[cfg(feature = "use_std")] + pub use crate::duplicates_impl::{Duplicates, DuplicatesBy}; + #[cfg(feature = "use_std")] pub use crate::unique_impl::{Unique, UniqueBy}; pub use crate::with_position::WithPosition; pub use crate::zip_eq_impl::ZipEq; @@ -191,6 +195,7 @@ mod combinations; mod combinations_with_replacement; mod exactly_one_err; mod diff; +mod flatten_ok; mod format; #[cfg(feature = "use_std")] mod grouping_map; @@ -229,6 +234,8 @@ mod sources; mod tee; mod tuple_impl; #[cfg(feature = "use_std")] +mod duplicates_impl; +#[cfg(feature = "use_std")] mod unique_impl; mod with_position; mod zip_eq_impl; @@ -289,8 +296,6 @@ macro_rules! iproduct { /// Prefer this macro `izip!()` over [`multizip`] for the performance benefits /// of using the standard library `.zip()`. /// -/// [`multizip`]: fn.multizip.html -/// /// ``` /// # use itertools::izip; /// # @@ -343,6 +348,69 @@ macro_rules! izip { }; } +#[macro_export] +/// [Chain][`chain`] zero or more iterators together into one sequence. +/// +/// The comma-separated arguments must implement [`IntoIterator`]. +/// The final argument may be followed by a trailing comma. +/// +/// [`chain`]: Iterator::chain +/// +/// # Examples +/// +/// Empty invocations of `chain!` expand to an invocation of [`std::iter::empty`]: +/// ``` +/// use std::iter; +/// use itertools::chain; +/// +/// let _: iter::Empty<()> = chain!(); +/// let _: iter::Empty<i8> = chain!(); +/// ``` +/// +/// Invocations of `chain!` with one argument expand to [`arg.into_iter()`](IntoIterator): +/// ``` +/// use std::{ops::Range, slice}; +/// use itertools::chain; +/// let _: <Range<_> as IntoIterator>::IntoIter = chain!((2..6),); // trailing comma optional! +/// let _: <&[_] as IntoIterator>::IntoIter = chain!(&[2, 3, 4]); +/// ``` +/// +/// Invocations of `chain!` with multiple arguments [`.into_iter()`](IntoIterator) each +/// argument, and then [`chain`] them together: +/// ``` +/// use std::{iter::*, ops::Range, slice}; +/// use itertools::{assert_equal, chain}; +/// +/// // e.g., this: +/// let with_macro: Chain<Chain<Once<_>, Take<Repeat<_>>>, slice::Iter<_>> = +/// chain![once(&0), repeat(&1).take(2), &[2, 3, 5],]; +/// +/// // ...is equivalant to this: +/// let with_method: Chain<Chain<Once<_>, Take<Repeat<_>>>, slice::Iter<_>> = +/// once(&0) +/// .chain(repeat(&1).take(2)) +/// .chain(&[2, 3, 5]); +/// +/// assert_equal(with_macro, with_method); +/// ``` +macro_rules! chain { + () => { + core::iter::empty() + }; + ($first:expr $(, $rest:expr )* $(,)?) => { + { + let iter = core::iter::IntoIterator::into_iter($first); + $( + let iter = + core::iter::Iterator::chain( + iter, + core::iter::IntoIterator::into_iter($rest)); + )* + iter + } + }; +} + /// An [`Iterator`] blanket implementation that provides extra adaptors and /// methods. /// @@ -350,14 +418,12 @@ macro_rules! izip { /// /// * *Adaptors* take an iterator and parameter as input, and return /// a new iterator value. These are listed first in the trait. An example -/// of an adaptor is [`.interleave()`](#method.interleave) +/// of an adaptor is [`.interleave()`](Itertools::interleave) /// /// * *Regular methods* are those that don't return iterators and instead /// return a regular value of some other kind. -/// [`.next_tuple()`](#method.next_tuple) is an example and the first regular +/// [`.next_tuple()`](Itertools::next_tuple) is an example and the first regular /// method in the list. -/// -/// [`Iterator`]: https://doc.rust-lang.org/std/iter/trait.Iterator.html pub trait Itertools : Iterator { // adaptors @@ -456,7 +522,7 @@ pub trait Itertools : Iterator { /// will return `None`. /// /// Iterator element type is - /// [`EitherOrBoth<Self::Item, J::Item>`](enum.EitherOrBoth.html). + /// [`EitherOrBoth<Self::Item, J::Item>`](EitherOrBoth). /// /// ```rust /// use itertools::EitherOrBoth::{Both, Right}; @@ -526,7 +592,7 @@ pub trait Itertools : Iterator { /// allocations. It needs allocations only if several group iterators /// are alive at the same time. /// - /// This type implements `IntoIterator` (it is **not** an iterator + /// This type implements [`IntoIterator`] (it is **not** an iterator /// itself), because the group iterators need to borrow from this /// value. It should be stored in a local variable or temporary and /// iterated. @@ -671,7 +737,7 @@ pub trait Itertools : Iterator { /// Return an iterator that groups the items in tuples of a specific size /// (up to 4). /// - /// See also the method [`.next_tuple()`](#method.next_tuple). + /// See also the method [`.next_tuple()`](Itertools::next_tuple). /// /// ``` /// use itertools::Itertools; @@ -698,7 +764,7 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(it, vec![(1, 2, 3), (4, 5, 6)]); /// ``` /// - /// See also [`Tuples::into_buffer`](structs/struct.Tuples.html#method.into_buffer). + /// See also [`Tuples::into_buffer`]. fn tuples<T>(self) -> Tuples<Self, T> where Self: Sized + Iterator<Item = T::Item>, T: traits::HomogeneousTuple @@ -755,7 +821,7 @@ pub trait Itertools : Iterator { adaptors::step(self, n) } - /// Convert each item of the iterator using the `Into` trait. + /// Convert each item of the iterator using the [`Into`] trait. /// /// ```rust /// use itertools::Itertools; @@ -769,7 +835,7 @@ pub trait Itertools : Iterator { adaptors::map_into(self) } - /// See [`.map_ok()`](#method.map_ok). + /// See [`.map_ok()`](Itertools::map_ok). #[deprecated(note="Use .map_ok() instead", since="0.10.0")] fn map_results<F, T, U, E>(self, f: F) -> MapOk<Self, F> where Self: Iterator<Item = Result<T, E>> + Sized, @@ -832,6 +898,30 @@ pub trait Itertools : Iterator { adaptors::filter_map_ok(self, f) } + /// Return an iterator adaptor that flattens every `Result::Ok` value into + /// a series of `Result::Ok` values. `Result::Err` values are unchanged. + /// + /// This is useful when you have some common error type for your crate and + /// need to propogate it upwards, but the `Result::Ok` case needs to be flattened. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let input = vec![Ok(0..2), Err(false), Ok(2..4)]; + /// let it = input.iter().cloned().flatten_ok(); + /// itertools::assert_equal(it.clone(), vec![Ok(0), Ok(1), Err(false), Ok(2), Ok(3)]); + /// + /// // This can also be used to propogate errors when collecting. + /// let output_result: Result<Vec<i32>, bool> = it.collect(); + /// assert_eq!(output_result, Err(false)); + /// ``` + fn flatten_ok<T, E>(self) -> FlattenOk<Self, T, E> + where Self: Iterator<Item = Result<T, E>> + Sized, + T: IntoIterator + { + flatten_ok::flatten_ok(self) + } + /// Return an iterator adaptor that merges the two base iterators in /// ascending order. If both base iterators are sorted (ascending), the /// result is sorted. @@ -855,7 +945,7 @@ pub trait Itertools : Iterator { } /// Return an iterator adaptor that merges the two base iterators in order. - /// This is much like `.merge()` but allows for a custom ordering. + /// This is much like [`.merge()`](Itertools::merge) but allows for a custom ordering. /// /// This can be especially useful for sequences of tuples. /// @@ -995,7 +1085,7 @@ pub trait Itertools : Iterator { /// /// All provided iterators must yield the same `Item` type. To generate /// the product of iterators yielding multiple types, use the - /// [`iproduct`](macro.iproduct.html) macro instead. + /// [`iproduct`] macro instead. /// /// /// The iterator element type is `Vec<T>`, where `T` is the iterator element @@ -1115,12 +1205,13 @@ pub trait Itertools : Iterator { /// ``` /// use itertools::Itertools; /// - /// let data = vec![1., 1., 2., 3., 3., 2., 2.]; + /// let data = vec!['a', 'a', 'b', 'c', 'c', 'b', 'b']; /// itertools::assert_equal(data.into_iter().dedup_with_count(), - /// vec![(2, 1.), (1, 2.), (2, 3.), (2, 2.)]); + /// vec![(2, 'a'), (1, 'b'), (2, 'c'), (2, 'b')]); /// ``` fn dedup_with_count(self) -> DedupWithCount<Self> - where Self: Sized, + where + Self: Sized, { adaptors::dedup_with_count(self) } @@ -1137,17 +1228,66 @@ pub trait Itertools : Iterator { /// ``` /// use itertools::Itertools; /// - /// let data = vec![(0, 1.), (1, 1.), (0, 2.), (0, 3.), (1, 3.), (1, 2.), (2, 2.)]; + /// let data = vec![(0, 'a'), (1, 'a'), (0, 'b'), (0, 'c'), (1, 'c'), (1, 'b'), (2, 'b')]; /// itertools::assert_equal(data.into_iter().dedup_by_with_count(|x, y| x.1 == y.1), - /// vec![(2, (0, 1.)), (1, (0, 2.)), (2, (0, 3.)), (2, (1, 2.))]); + /// vec![(2, (0, 'a')), (1, (0, 'b')), (2, (0, 'c')), (2, (1, 'b'))]); /// ``` fn dedup_by_with_count<Cmp>(self, cmp: Cmp) -> DedupByWithCount<Self, Cmp> - where Self: Sized, - Cmp: FnMut(&Self::Item, &Self::Item) -> bool, + where + Self: Sized, + Cmp: FnMut(&Self::Item, &Self::Item) -> bool, { adaptors::dedup_by_with_count(self, cmp) } + /// Return an iterator adaptor that produces elements that appear more than once during the + /// iteration. Duplicates are detected using hash and equality. + /// + /// The iterator is stable, returning the duplicate items in the order in which they occur in + /// the adapted iterator. Each duplicate item is returned exactly once. If an item appears more + /// than twice, the second item is the item retained and the rest are discarded. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let data = vec![10, 20, 30, 20, 40, 10, 50]; + /// itertools::assert_equal(data.into_iter().duplicates(), + /// vec![20, 10]); + /// ``` + #[cfg(feature = "use_std")] + fn duplicates(self) -> Duplicates<Self> + where Self: Sized, + Self::Item: Eq + Hash + { + duplicates_impl::duplicates(self) + } + + /// Return an iterator adaptor that produces elements that appear more than once during the + /// iteration. Duplicates are detected using hash and equality. + /// + /// Duplicates are detected by comparing the key they map to with the keying function `f` by + /// hash and equality. The keys are stored in a hash map in the iterator. + /// + /// The iterator is stable, returning the duplicate items in the order in which they occur in + /// the adapted iterator. Each duplicate item is returned exactly once. If an item appears more + /// than twice, the second item is the item retained and the rest are discarded. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let data = vec!["a", "bb", "aa", "c", "ccc"]; + /// itertools::assert_equal(data.into_iter().duplicates_by(|s| s.len()), + /// vec!["aa", "c"]); + /// ``` + #[cfg(feature = "use_std")] + fn duplicates_by<V, F>(self, f: F) -> DuplicatesBy<Self, V, F> + where Self: Sized, + V: Eq + Hash, + F: FnMut(&Self::Item) -> V + { + duplicates_impl::duplicates_by(self, f) + } + /// Return an iterator adaptor that filters out elements that have /// already been produced once during the iteration. Duplicates /// are detected using hash and equality. @@ -1211,7 +1351,7 @@ pub trait Itertools : Iterator { /// `peeking_take_while` is done. /// /// - /// See also [`.take_while_ref()`](#method.take_while_ref) + /// See also [`.take_while_ref()`](Itertools::take_while_ref) /// which is a similar adaptor. fn peeking_take_while<F>(&mut self, accept: F) -> PeekingTakeWhile<Self, F> where Self: Sized + PeekingNext, @@ -1480,7 +1620,7 @@ pub trait Itertools : Iterator { /// ease special-case handling of the first or last elements. /// /// Iterator element type is - /// [`Position<Self::Item>`](enum.Position.html) + /// [`Position<Self::Item>`](Position) /// /// ``` /// use itertools::{Itertools, Position}; @@ -1613,6 +1753,82 @@ pub trait Itertools : Iterator { } None } + /// Find the value of the first element satisfying a predicate or return the last element, if any. + /// + /// The iterator is not advanced past the first element found. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let numbers = [1, 2, 3, 4]; + /// assert_eq!(numbers.iter().find_or_last(|&&x| x > 5), Some(&4)); + /// assert_eq!(numbers.iter().find_or_last(|&&x| x > 2), Some(&3)); + /// assert_eq!(std::iter::empty::<i32>().find_or_last(|&x| x > 5), None); + /// ``` + fn find_or_last<P>(mut self, mut predicate: P) -> Option<Self::Item> + where Self: Sized, + P: FnMut(&Self::Item) -> bool, + { + let mut prev = None; + self.find_map(|x| if predicate(&x) { Some(x) } else { prev = Some(x); None }) + .or(prev) + } + /// Find the value of the first element satisfying a predicate or return the first element, if any. + /// + /// The iterator is not advanced past the first element found. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let numbers = [1, 2, 3, 4]; + /// assert_eq!(numbers.iter().find_or_first(|&&x| x > 5), Some(&1)); + /// assert_eq!(numbers.iter().find_or_first(|&&x| x > 2), Some(&3)); + /// assert_eq!(std::iter::empty::<i32>().find_or_first(|&x| x > 5), None); + /// ``` + fn find_or_first<P>(mut self, mut predicate: P) -> Option<Self::Item> + where Self: Sized, + P: FnMut(&Self::Item) -> bool, + { + let first = self.next()?; + Some(if predicate(&first) { + first + } else { + self.find(|x| predicate(&x)).unwrap_or(first) + }) + } + /// Returns `true` if the given item is present in this iterator. + /// + /// This method is short-circuiting. If the given item is present in this + /// iterator, this method will consume the iterator up-to-and-including + /// the item. If the given item is not present in this iterator, the + /// iterator will be exhausted. + /// + /// ``` + /// use itertools::Itertools; + /// + /// #[derive(PartialEq, Debug)] + /// enum Enum { A, B, C, D, E, } + /// + /// let mut iter = vec![Enum::A, Enum::B, Enum::C, Enum::D].into_iter(); + /// + /// // search `iter` for `B` + /// assert_eq!(iter.contains(&Enum::B), true); + /// // `B` was found, so the iterator now rests at the item after `B` (i.e, `C`). + /// assert_eq!(iter.next(), Some(Enum::C)); + /// + /// // search `iter` for `E` + /// assert_eq!(iter.contains(&Enum::E), false); + /// // `E` wasn't found, so `iter` is now exhausted + /// assert_eq!(iter.next(), None); + /// ``` + fn contains<Q>(&mut self, query: &Q) -> bool + where + Self: Sized, + Self::Item: Borrow<Q>, + Q: PartialEq, + { + self.any(|x| x.borrow() == query) + } /// Check whether all elements compare equal. /// @@ -1640,6 +1856,30 @@ pub trait Itertools : Iterator { } } + /// Check whether all elements are unique (non equal). + /// + /// Empty iterators are considered to have unique elements: + /// + /// ``` + /// use itertools::Itertools; + /// + /// let data = vec![1, 2, 3, 4, 1, 5]; + /// assert!(!data.iter().all_unique()); + /// assert!(data[0..4].iter().all_unique()); + /// assert!(data[1..6].iter().all_unique()); + /// + /// let data : Option<usize> = None; + /// assert!(data.into_iter().all_unique()); + /// ``` + #[cfg(feature = "use_std")] + fn all_unique(&mut self) -> bool + where Self: Sized, + Self::Item: Eq + Hash + { + let mut used = HashSet::new(); + self.all(move |elt| used.insert(elt)) + } + /// Consume the first `n` elements from the iterator eagerly, /// and return the same iterator again. /// @@ -1714,7 +1954,7 @@ pub trait Itertools : Iterator { self.for_each(f) } - /// Combine all an iterator's elements into one element by using `Extend`. + /// Combine all an iterator's elements into one element by using [`Extend`]. /// /// This combinator will extend the first item with each of the rest of the /// items of the iterator. If the iterator is empty, the default value of @@ -1734,7 +1974,7 @@ pub trait Itertools : Iterator { concat(self) } - /// `.collect_vec()` is simply a type specialization of `.collect()`, + /// `.collect_vec()` is simply a type specialization of [`Iterator::collect`], /// for convenience. #[cfg(feature = "use_alloc")] fn collect_vec(self) -> Vec<Self::Item> @@ -1856,7 +2096,7 @@ pub trait Itertools : Iterator { /// Format all iterator elements, separated by `sep`. /// - /// This is a customizable version of `.format()`. + /// This is a customizable version of [`.format()`](Itertools::format). /// /// The supplied closure `format` is called once per iterator element, /// with two arguments: the element and a callback that takes a @@ -1893,7 +2133,7 @@ pub trait Itertools : Iterator { format::new_format(self, sep, format) } - /// See [`.fold_ok()`](#method.fold_ok). + /// See [`.fold_ok()`](Itertools::fold_ok). #[deprecated(note="Use .fold_ok() instead", since="0.10.0")] fn fold_results<A, E, B, F>(&mut self, start: B, f: F) -> Result<B, E> where Self: Iterator<Item = Result<A, E>>, @@ -1963,7 +2203,7 @@ pub trait Itertools : Iterator { /// value is returned inside `Some`. Otherwise, the operation terminates /// and returns `None`. No iterator elements are consumed after the `None`. /// - /// This is the `Option` equivalent to `fold_ok`. + /// This is the `Option` equivalent to [`fold_ok`](Itertools::fold_ok). /// /// ``` /// use std::ops::Add; @@ -2117,7 +2357,7 @@ pub trait Itertools : Iterator { /// An iterator method that applies a function, producing a single, final value. /// - /// `fold_while()` is basically equivalent to `fold()` but with additional support for + /// `fold_while()` is basically equivalent to [`Iterator::fold`] but with additional support for /// early exit via short-circuiting. /// /// ``` @@ -2236,7 +2476,7 @@ pub trait Itertools : Iterator { /// Sort all iterator elements into a new iterator in ascending order. /// /// **Note:** This consumes the entire iterator, uses the - /// `slice::sort_unstable()` method and returns the result as a new + /// [`slice::sort_unstable`] method and returns the result as a new /// iterator that owns its elements. /// /// The sorted iterator, if directly collected to a `Vec`, is converted @@ -2265,7 +2505,7 @@ pub trait Itertools : Iterator { /// Sort all iterator elements into a new iterator in ascending order. /// /// **Note:** This consumes the entire iterator, uses the - /// `slice::sort_unstable_by()` method and returns the result as a new + /// [`slice::sort_unstable_by`] method and returns the result as a new /// iterator that owns its elements. /// /// The sorted iterator, if directly collected to a `Vec`, is converted @@ -2298,7 +2538,7 @@ pub trait Itertools : Iterator { /// Sort all iterator elements into a new iterator in ascending order. /// /// **Note:** This consumes the entire iterator, uses the - /// `slice::sort_unstable_by_key()` method and returns the result as a new + /// [`slice::sort_unstable_by_key`] method and returns the result as a new /// iterator that owns its elements. /// /// The sorted iterator, if directly collected to a `Vec`, is converted @@ -2332,7 +2572,7 @@ pub trait Itertools : Iterator { /// Sort all iterator elements into a new iterator in ascending order. /// /// **Note:** This consumes the entire iterator, uses the - /// `slice::sort()` method and returns the result as a new + /// [`slice::sort`] method and returns the result as a new /// iterator that owns its elements. /// /// The sorted iterator, if directly collected to a `Vec`, is converted @@ -2361,7 +2601,7 @@ pub trait Itertools : Iterator { /// Sort all iterator elements into a new iterator in ascending order. /// /// **Note:** This consumes the entire iterator, uses the - /// `slice::sort_by()` method and returns the result as a new + /// [`slice::sort_by`] method and returns the result as a new /// iterator that owns its elements. /// /// The sorted iterator, if directly collected to a `Vec`, is converted @@ -2394,7 +2634,7 @@ pub trait Itertools : Iterator { /// Sort all iterator elements into a new iterator in ascending order. /// /// **Note:** This consumes the entire iterator, uses the - /// `slice::sort_by_key()` method and returns the result as a new + /// [`slice::sort_by_key`] method and returns the result as a new /// iterator that owns its elements. /// /// The sorted iterator, if directly collected to a `Vec`, is converted @@ -2463,7 +2703,7 @@ pub trait Itertools : Iterator { } /// Collect all iterator elements into one of two - /// partitions. Unlike `Iterator::partition`, each partition may + /// partitions. Unlike [`Iterator::partition`], each partition may /// have a distinct type. /// /// ``` @@ -2500,6 +2740,33 @@ pub trait Itertools : Iterator { (left, right) } + /// Partition a sequence of `Result`s into one list of all the `Ok` elements + /// and another list of all the `Err` elements. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let successes_and_failures = vec![Ok(1), Err(false), Err(true), Ok(2)]; + /// + /// let (successes, failures): (Vec<_>, Vec<_>) = successes_and_failures + /// .into_iter() + /// .partition_result(); + /// + /// assert_eq!(successes, [1, 2]); + /// assert_eq!(failures, [false, true]); + /// ``` + fn partition_result<A, B, T, E>(self) -> (A, B) + where + Self: Iterator<Item = Result<T, E>> + Sized, + A: Default + Extend<T>, + B: Default + Extend<E>, + { + self.partition_map(|r| match r { + Ok(v) => Either::Left(v), + Err(v) => Either::Right(v), + }) + } + /// Return a `HashMap` of keys mapped to `Vec`s of values. Keys and values /// are taken from `(Key, Value)` tuple pairs yielded by the input iterator. /// @@ -2522,18 +2789,18 @@ pub trait Itertools : Iterator { group_map::into_group_map(self) } - /// Return an `Iterator` on a HahMap. Keys mapped to `Vec`s of values. The key is specified in + /// Return an `Iterator` on a `HashMap`. Keys mapped to `Vec`s of values. The key is specified /// in the closure. - /// Different of into_group_map_by because the key is still present. It is also more general. - /// you can also fold the group_map. + /// Different to `into_group_map_by` because the key is still present. It is also more general. + /// You can also fold the `group_map`. /// /// ``` /// use itertools::Itertools; /// use std::collections::HashMap; /// /// let data = vec![(0, 10), (2, 12), (3, 13), (0, 20), (3, 33), (2, 42)]; - /// let lookup: HashMap<u32,Vec<(u32, u32)>> = data.clone().into_iter().into_group_map_by(|a| - /// a.0); + /// let lookup: HashMap<u32,Vec<(u32, u32)>> = + /// data.clone().into_iter().into_group_map_by(|a| a.0); /// /// assert_eq!(lookup[&0], vec![(0,10),(0,20)]); /// assert_eq!(lookup.get(&1), None); @@ -2542,10 +2809,12 @@ pub trait Itertools : Iterator { /// /// assert_eq!( /// data.into_iter() - /// .into_group_map_by(|x| x.0) - /// .into_iter() - /// .map(|(key, values)| (key, values.into_iter().fold(0,|acc, (_,v)| acc + v ))) - /// .collect::<HashMap<u32,u32>>()[&0], 30) + /// .into_group_map_by(|x| x.0) + /// .into_iter() + /// .map(|(key, values)| (key, values.into_iter().fold(0,|acc, (_,v)| acc + v ))) + /// .collect::<HashMap<u32,u32>>()[&0], + /// 30, + /// ); /// ``` #[cfg(feature = "use_std")] fn into_group_map_by<K, V, F>(self, f: F) -> HashMap<K, Vec<V>> @@ -2564,7 +2833,7 @@ pub trait Itertools : Iterator { /// value of type `K` will be used as key to identify the groups and the /// value of type `V` as value for the folding operation. /// - /// See [`GroupingMap`](./structs/struct.GroupingMap.html) for more informations + /// See [`GroupingMap`] for more informations /// on what operations are available. #[cfg(feature = "use_std")] fn into_grouping_map<K, V>(self) -> GroupingMap<Self> @@ -2580,7 +2849,7 @@ pub trait Itertools : Iterator { /// The values from this iterator will be used as values for the folding operation /// while the keys will be obtained from the values by calling `key_mapper`. /// - /// See [`GroupingMap`](./structs/struct.GroupingMap.html) for more informations + /// See [`GroupingMap`] for more informations /// on what operations are available. #[cfg(feature = "use_std")] fn into_grouping_map_by<K, V, F>(self, key_mapper: F) -> GroupingMapBy<Self, F> @@ -2635,11 +2904,11 @@ pub trait Itertools : Iterator { /// Return the minimum and maximum element of an iterator, as determined by /// the specified function. /// - /// The return value is a variant of `MinMaxResult` like for `minmax()`. + /// The return value is a variant of [`MinMaxResult`] like for [`.minmax()`](Itertools::minmax). /// /// For the minimum, the first minimal element is returned. For the maximum, /// the last maximal element wins. This matches the behavior of the standard - /// `Iterator::min()` and `Iterator::max()` methods. + /// [`Iterator::min`] and [`Iterator::max`] methods. /// /// The keys can be floats but no particular result is guaranteed /// if a key is NaN. @@ -2652,11 +2921,11 @@ pub trait Itertools : Iterator { /// Return the minimum and maximum element of an iterator, as determined by /// the specified comparison function. /// - /// The return value is a variant of `MinMaxResult` like for `minmax()`. + /// The return value is a variant of [`MinMaxResult`] like for [`.minmax()`](Itertools::minmax). /// /// For the minimum, the first minimal element is returned. For the maximum, /// the last maximal element wins. This matches the behavior of the standard - /// `Iterator::min()` and `Iterator::max()` methods. + /// [`Iterator::min`] and [`Iterator::max`] methods. fn minmax_by<F>(self, mut compare: F) -> MinMaxResult<Self::Item> where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering { @@ -2875,8 +3144,6 @@ pub trait Itertools : Iterator { /// let a = [1, 1, -1, -1]; /// assert_eq!(a.iter().position_minmax(), MinMax(2, 1)); /// ``` - /// - /// [`MinMaxResult`]: enum.MinMaxResult.html fn position_minmax(self) -> MinMaxResult<usize> where Self: Sized, Self::Item: PartialOrd { @@ -2921,8 +3188,7 @@ pub trait Itertools : Iterator { /// assert_eq!(a.iter().position_minmax_by_key(|x| x.abs()), MinMax(0, 3)); /// ``` /// - /// [`MinMaxResult`]: enum.MinMaxResult.html - /// [`position_minmax`]: #method.position_minmax + /// [`position_minmax`]: Self::position_minmax fn position_minmax_by_key<K, F>(self, mut key: F) -> MinMaxResult<usize> where Self: Sized, K: PartialOrd, F: FnMut(&Self::Item) -> K { @@ -2964,8 +3230,7 @@ pub trait Itertools : Iterator { /// assert_eq!(a.iter().position_minmax_by(|x, y| x.cmp(y)), MinMax(2, 1)); /// ``` /// - /// [`MinMaxResult`]: enum.MinMaxResult.html - /// [`position_minmax`]: #method.position_minmax + /// [`position_minmax`]: Self::position_minmax fn position_minmax_by<F>(self, mut compare: F) -> MinMaxResult<usize> where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering { @@ -3013,6 +3278,42 @@ pub trait Itertools : Iterator { } } + /// If the iterator yields no elements, Ok(None) will be returned. If the iterator yields + /// exactly one element, that element will be returned, otherwise an error will be returned + /// containing an iterator that has the same output as the input iterator. + /// + /// This provides an additional layer of validation over just calling `Iterator::next()`. + /// If your assumption that there should be at most one element yielded is false this provides + /// the opportunity to detect and handle that, preventing errors at a distance. + /// + /// # Examples + /// ``` + /// use itertools::Itertools; + /// + /// assert_eq!((0..10).filter(|&x| x == 2).at_most_one().unwrap(), Some(2)); + /// assert!((0..10).filter(|&x| x > 1 && x < 4).at_most_one().unwrap_err().eq(2..4)); + /// assert!((0..10).filter(|&x| x > 1 && x < 5).at_most_one().unwrap_err().eq(2..5)); + /// assert_eq!((0..10).filter(|&_| false).at_most_one().unwrap(), None); + /// ``` + fn at_most_one(mut self) -> Result<Option<Self::Item>, ExactlyOneError<Self>> + where + Self: Sized, + { + match self.next() { + Some(first) => { + match self.next() { + Some(second) => { + Err(ExactlyOneError::new(Some(Either::Left([first, second])), self)) + } + None => { + Ok(Some(first)) + } + } + } + None => Ok(None), + } + } + /// An iterator adaptor that allows the user to peek at multiple `.next()` /// values without advancing the base iterator. /// @@ -3058,6 +3359,48 @@ pub trait Itertools : Iterator { self.for_each(|item| *counts.entry(item).or_default() += 1); counts } + + /// Collect the items in this iterator and return a `HashMap` which + /// contains each item that appears in the iterator and the number + /// of times it appears, + /// determining identity using a keying function. + /// + /// ``` + /// # use itertools::Itertools; + /// struct Character { + /// first_name: &'static str, + /// last_name: &'static str, + /// } + /// + /// let characters = + /// vec![ + /// Character { first_name: "Amy", last_name: "Pond" }, + /// Character { first_name: "Amy", last_name: "Wong" }, + /// Character { first_name: "Amy", last_name: "Santiago" }, + /// Character { first_name: "James", last_name: "Bond" }, + /// Character { first_name: "James", last_name: "Sullivan" }, + /// Character { first_name: "James", last_name: "Norington" }, + /// Character { first_name: "James", last_name: "Kirk" }, + /// ]; + /// + /// let first_name_frequency = + /// characters + /// .into_iter() + /// .counts_by(|c| c.first_name); + /// + /// assert_eq!(first_name_frequency["Amy"], 3); + /// assert_eq!(first_name_frequency["James"], 4); + /// assert_eq!(first_name_frequency.contains_key("Asha"), false); + /// ``` + #[cfg(feature = "use_std")] + fn counts_by<K, F>(self, f: F) -> HashMap<K, usize> + where + Self: Sized, + K: Eq + Hash, + F: FnMut(Self::Item) -> K, + { + self.map(f).counts() + } } impl<T: ?Sized> Itertools for T where T: Iterator { } @@ -3066,8 +3409,8 @@ impl<T: ?Sized> Itertools for T where T: Iterator { } /// (elements pairwise equal and sequences of the same length), /// `false` otherwise. /// -/// This is an `IntoIterator` enabled function that is similar to the standard -/// library method `Iterator::eq`. +/// This is an [`IntoIterator`] enabled function that is similar to the standard +/// library method [`Iterator::eq`]. /// /// ``` /// assert!(itertools::equal(vec![1, 2, 3], 1..4)); @@ -3092,7 +3435,7 @@ pub fn equal<I, J>(a: I, b: J) -> bool } /// Assert that two iterables produce equal sequences, with the same -/// semantics as *equal(a, b)*. +/// semantics as [`equal(a, b)`](equal). /// /// **Panics** on assertion failure with a message that shows the /// two iteration elements. @@ -3167,9 +3510,9 @@ pub fn partition<'a, A: 'a, I, F>(iter: I, mut pred: F) -> usize split_index } -/// An enum used for controlling the execution of `.fold_while()`. +/// An enum used for controlling the execution of `fold_while`. /// -/// See [`.fold_while()`](trait.Itertools.html#method.fold_while) for more information. +/// See [`.fold_while()`](Itertools::fold_while) for more information. #[derive(Copy, Clone, Debug, Eq, PartialEq)] pub enum FoldWhile<T> { /// Continue folding with this value diff --git a/src/merge_join.rs b/src/merge_join.rs index 0f87ae4..4c0048f 100644 --- a/src/merge_join.rs +++ b/src/merge_join.rs @@ -7,7 +7,7 @@ use crate::either_or_both::EitherOrBoth; /// Return an iterator adaptor that merge-joins items from the two base iterators in ascending order. /// -/// See [`.merge_join_by()`](trait.Itertools.html#method.merge_join_by) for more information. +/// See [`.merge_join_by()`](crate::Itertools::merge_join_by) for more information. pub fn merge_join_by<I, J, F>(left: I, right: J, cmp_fn: F) -> MergeJoinBy<I::IntoIter, J::IntoIter, F> where I: IntoIterator, @@ -23,7 +23,7 @@ pub fn merge_join_by<I, J, F>(left: I, right: J, cmp_fn: F) /// An iterator adaptor that merge-joins items from the two base iterators in ascending order. /// -/// See [`.merge_join_by()`](../trait.Itertools.html#method.merge_join_by) for more information. +/// See [`.merge_join_by()`](crate::Itertools::merge_join_by) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct MergeJoinBy<I: Iterator, J: Iterator, F> { left: PutBack<Fuse<I>>, diff --git a/src/minmax.rs b/src/minmax.rs index 38180ef..52b2f11 100644 --- a/src/minmax.rs +++ b/src/minmax.rs @@ -1,6 +1,7 @@ -/// `MinMaxResult` is an enum returned by `minmax`. See `Itertools::minmax()` for -/// more detail. +/// `MinMaxResult` is an enum returned by `minmax`. +/// +/// See [`.minmax()`](crate::Itertools::minmax) for more detail. #[derive(Copy, Clone, PartialEq, Debug)] pub enum MinMaxResult<T> { /// Empty iterator diff --git a/src/multipeek_impl.rs b/src/multipeek_impl.rs index 986e5b4..93b0227 100644 --- a/src/multipeek_impl.rs +++ b/src/multipeek_impl.rs @@ -3,7 +3,7 @@ use alloc::collections::VecDeque; use crate::size_hint; use crate::PeekingNext; -/// See [`multipeek()`](../fn.multipeek.html) for more information. +/// See [`multipeek()`] for more information. #[derive(Clone, Debug)] pub struct MultiPeek<I> where I: Iterator diff --git a/src/pad_tail.rs b/src/pad_tail.rs index 4ed83c3..03867cb 100644 --- a/src/pad_tail.rs +++ b/src/pad_tail.rs @@ -1,4 +1,4 @@ -use std::iter::Fuse; +use std::iter::{Fuse, FusedIterator}; use crate::size_hint; /// An iterator adaptor that pads a sequence to a minimum length by filling @@ -6,7 +6,7 @@ use crate::size_hint; /// /// Iterator element type is `I::Item`. /// -/// See [`.pad_using()`](../trait.Itertools.html#method.pad_using) for more information. +/// See [`.pad_using()`](crate::Itertools::pad_using) for more information. #[derive(Clone)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct PadUsing<I, F> { @@ -81,3 +81,9 @@ impl<I, F> ExactSizeIterator for PadUsing<I, F> where I: ExactSizeIterator, F: FnMut(usize) -> I::Item {} + + +impl<I, F> FusedIterator for PadUsing<I, F> + where I: FusedIterator, + F: FnMut(usize) -> I::Item +{} diff --git a/src/peek_nth.rs b/src/peek_nth.rs index d22258b..bcca458 100644 --- a/src/peek_nth.rs +++ b/src/peek_nth.rs @@ -3,7 +3,7 @@ use crate::PeekingNext; use alloc::collections::VecDeque; use std::iter::Fuse; -/// See [`peek_nth()`](../fn.peek_nth.html) for more information. +/// See [`peek_nth()`] for more information. #[derive(Clone, Debug)] pub struct PeekNth<I> where @@ -13,7 +13,7 @@ where buf: VecDeque<I::Item>, } -/// A drop-in replacement for `std::iter::Peekable` which adds a `peek_nth` +/// A drop-in replacement for [`std::iter::Peekable`] which adds a `peek_nth` /// method allowing the user to `peek` at a value several iterations forward /// without advancing the base iterator. /// diff --git a/src/peeking_take_while.rs b/src/peeking_take_while.rs index 70ef988..f9f2134 100644 --- a/src/peeking_take_while.rs +++ b/src/peeking_take_while.rs @@ -5,7 +5,7 @@ use crate::PutBackN; /// An iterator that allows peeking at an element before deciding to accept it. /// -/// See [`.peeking_take_while()`](trait.Itertools.html#method.peeking_take_while) +/// See [`.peeking_take_while()`](crate::Itertools::peeking_take_while) /// for more information. /// /// This is implemented by peeking adaptors like peekable and put back, @@ -73,7 +73,7 @@ impl<I> PeekingNext for PutBackN<I> /// An iterator adaptor that takes items while a closure returns `true`. /// -/// See [`.peeking_take_while()`](../trait.Itertools.html#method.peeking_take_while) +/// See [`.peeking_take_while()`](crate::Itertools::peeking_take_while) /// for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct PeekingTakeWhile<'a, I: 'a, F> diff --git a/src/permutations.rs b/src/permutations.rs index d96bbac..3080f9d 100644 --- a/src/permutations.rs +++ b/src/permutations.rs @@ -7,7 +7,7 @@ use super::lazy_buffer::LazyBuffer; /// An iterator adaptor that iterates through all the `k`-permutations of the /// elements from an iterator. /// -/// See [`.permutations()`](../trait.Itertools.html#method.permutations) for +/// See [`.permutations()`](crate::Itertools::permutations) for /// more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Permutations<I: Iterator> { diff --git a/src/powerset.rs b/src/powerset.rs index ef17752..4d7685b 100644 --- a/src/powerset.rs +++ b/src/powerset.rs @@ -1,4 +1,5 @@ use std::fmt; +use std::iter::FusedIterator; use std::usize; use alloc::vec::Vec; @@ -7,7 +8,7 @@ use super::size_hint; /// An iterator to iterate through the powerset of the elements from an iterator. /// -/// See [`.powerset()`](../trait.Itertools.html#method.powerset) for more +/// See [`.powerset()`](crate::Itertools::powerset) for more /// information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Powerset<I: Iterator> { @@ -81,3 +82,9 @@ impl<I> Iterator for Powerset<I> } } } + +impl<I> FusedIterator for Powerset<I> + where + I: Iterator, + I::Item: Clone, +{} diff --git a/src/process_results_impl.rs b/src/process_results_impl.rs index d74925a..9da108b 100644 --- a/src/process_results_impl.rs +++ b/src/process_results_impl.rs @@ -2,7 +2,7 @@ /// An iterator that produces only the `T` values as long as the /// inner iterator produces `Ok(T)`. /// -/// Used by [`process_results`](../fn.process_results.html), see its docs +/// Used by [`process_results`](crate::process_results), see its docs /// for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] #[derive(Debug)] diff --git a/src/rciter_impl.rs b/src/rciter_impl.rs index 9122dad..782908e 100644 --- a/src/rciter_impl.rs +++ b/src/rciter_impl.rs @@ -1,5 +1,5 @@ -use std::iter::IntoIterator; +use std::iter::{FusedIterator, IntoIterator}; use alloc::rc::Rc; use std::cell::RefCell; @@ -93,3 +93,8 @@ impl<'a, I> IntoIterator for &'a RcIter<I> self.clone() } } + + +impl<A, I> FusedIterator for RcIter<I> + where I: FusedIterator<Item = A> +{} diff --git a/src/repeatn.rs b/src/repeatn.rs index 8bc4850..e025f6f 100644 --- a/src/repeatn.rs +++ b/src/repeatn.rs @@ -1,7 +1,8 @@ +use std::iter::FusedIterator; /// An iterator that produces *n* repetitions of an element. /// -/// See [`repeat_n()`](../fn.repeat_n.html) for more information. +/// See [`repeat_n()`](crate::repeat_n) for more information. #[must_use = "iterators are lazy and do nothing unless consumed"] #[derive(Clone, Debug)] pub struct RepeatN<A> { @@ -52,3 +53,7 @@ impl<A> DoubleEndedIterator for RepeatN<A> impl<A> ExactSizeIterator for RepeatN<A> where A: Clone {} + +impl<A> FusedIterator for RepeatN<A> + where A: Clone +{} diff --git a/src/sources.rs b/src/sources.rs index 5bb6afe..3877ce3 100644 --- a/src/sources.rs +++ b/src/sources.rs @@ -5,7 +5,7 @@ use std::fmt; use std::mem; -/// See [`repeat_call`](../fn.repeat_call.html) for more information. +/// See [`repeat_call`](crate::repeat_call) for more information. #[derive(Clone)] #[deprecated(note="Use std repeat_with() instead", since="0.8.0")] pub struct RepeatCall<F> { @@ -67,7 +67,7 @@ impl<A, F> Iterator for RepeatCall<F> /// `unfold` is a general iterator builder: it has a mutable state value, /// and a closure with access to the state that produces the next value. /// -/// This more or less equivalent to a regular struct with an `Iterator` +/// This more or less equivalent to a regular struct with an [`Iterator`] /// implementation, and is useful for one-off iterators. /// /// ``` @@ -112,7 +112,7 @@ impl<St, F> fmt::Debug for Unfold<St, F> debug_fmt_fields!(Unfold, state); } -/// See [`unfold`](../fn.unfold.html) for more information. +/// See [`unfold`](crate::unfold) for more information. #[derive(Clone)] #[must_use = "iterators are lazy and do nothing unless consumed"] pub struct Unfold<St, F> { @@ -134,9 +134,8 @@ impl<A, St, F> Iterator for Unfold<St, F> /// An iterator that infinitely applies function to value and yields results. /// -/// This `struct` is created by the [`iterate()`] function. See its documentation for more. -/// -/// [`iterate()`]: ../fn.iterate.html +/// This `struct` is created by the [`iterate()`](crate::iterate) function. +/// See its documentation for more. #[derive(Clone)] #[must_use = "iterators are lazy and do nothing unless consumed"] pub struct Iterate<St, F> { @@ -15,7 +15,7 @@ struct TeeBuffer<A, I> { /// One half of an iterator pair where both return the same elements. /// -/// See [`.tee()`](../trait.Itertools.html#method.tee) for more information. +/// See [`.tee()`](crate::Itertools::tee) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] #[derive(Debug)] pub struct Tee<I> diff --git a/src/tuple_impl.rs b/src/tuple_impl.rs index 1d24b0b..ca8b97c 100644 --- a/src/tuple_impl.rs +++ b/src/tuple_impl.rs @@ -1,6 +1,7 @@ //! Some iterator that produces tuples use std::iter::Fuse; +use std::iter::FusedIterator; use std::iter::Take; use std::iter::Cycle; use std::marker::PhantomData; @@ -19,8 +20,8 @@ impl<T: TupleCollect> HomogeneousTuple for T {} /// An iterator over a incomplete tuple. /// -/// See [`.tuples()`](../trait.Itertools.html#method.tuples) and -/// [`Tuples::into_buffer()`](struct.Tuples.html#method.into_buffer). +/// See [`.tuples()`](crate::Itertools::tuples) and +/// [`Tuples::into_buffer()`]. #[derive(Clone, Debug)] pub struct TupleBuffer<T> where T: HomogeneousTuple @@ -75,7 +76,7 @@ impl<T> ExactSizeIterator for TupleBuffer<T> /// An iterator that groups the items in tuples of a specific size. /// -/// See [`.tuples()`](../trait.Itertools.html#method.tuples) for more information. +/// See [`.tuples()`](crate::Itertools::tuples) for more information. #[derive(Clone)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Tuples<I, T> @@ -130,7 +131,7 @@ impl<I, T> Tuples<I, T> /// An iterator over all contiguous windows that produces tuples of a specific size. /// -/// See [`.tuple_windows()`](../trait.Itertools.html#method.tuple_windows) for more +/// See [`.tuple_windows()`](crate::Itertools::tuple_windows) for more /// information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] #[derive(Clone, Debug)] @@ -187,11 +188,17 @@ impl<I, T> Iterator for TupleWindows<I, T> } } +impl<I, T> FusedIterator for TupleWindows<I, T> + where I: FusedIterator<Item = T::Item>, + T: HomogeneousTuple + Clone, + T::Item: Clone +{} + /// An iterator over all windows,wrapping back to the first elements when the /// window would otherwise exceed the length of the iterator, producing tuples /// of a specific size. /// -/// See [`.circular_tuple_windows()`](../trait.Itertools.html#method.circular_tuple_windows) for more +/// See [`.circular_tuple_windows()`](crate::Itertools::circular_tuple_windows) for more /// information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] #[derive(Debug)] @@ -248,9 +255,6 @@ macro_rules! count_ident{ () => {0}; ($i0:ident, $($i:ident,)*) => {1 + count_ident!($($i,)*)}; } -macro_rules! ignore_ident{ - ($id:ident, $($t:tt)*) => {$($t)*}; -} macro_rules! rev_for_each_ident{ ($m:ident, ) => {}; ($m:ident, $i0:ident, $($i:ident,)*) => { @@ -317,7 +321,7 @@ macro_rules! impl_tuple_collect { let &mut ($(ref mut $Y),*,) = self; macro_rules! replace_item{($i:ident) => { item = replace($i, item); - }}; + }} rev_for_each_ident!(replace_item, $($Y,)*); drop(item); } diff --git a/src/unique_impl.rs b/src/unique_impl.rs index 14c14fc..2240f36 100644 --- a/src/unique_impl.rs +++ b/src/unique_impl.rs @@ -3,10 +3,11 @@ use std::collections::HashMap; use std::collections::hash_map::{Entry}; use std::hash::Hash; use std::fmt; +use std::iter::FusedIterator; /// An iterator adapter to filter out duplicate elements. /// -/// See [`.unique_by()`](../trait.Itertools.html#method.unique) for more information. +/// See [`.unique_by()`](crate::Itertools::unique) for more information. #[derive(Clone)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct UniqueBy<I: Iterator, V, F> { @@ -92,6 +93,12 @@ impl<I, V, F> DoubleEndedIterator for UniqueBy<I, V, F> } } +impl<I, V, F> FusedIterator for UniqueBy<I, V, F> + where I: FusedIterator, + V: Eq + Hash, + F: FnMut(&I::Item) -> V +{} + impl<I> Iterator for Unique<I> where I: Iterator, I::Item: Eq + Hash + Clone @@ -136,9 +143,14 @@ impl<I> DoubleEndedIterator for Unique<I> } } +impl<I> FusedIterator for Unique<I> + where I: FusedIterator, + I::Item: Eq + Hash + Clone +{} + /// An iterator adapter to filter out duplicate elements. /// -/// See [`.unique()`](../trait.Itertools.html#method.unique) for more information. +/// See [`.unique()`](crate::Itertools::unique) for more information. #[derive(Clone)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Unique<I: Iterator> { diff --git a/src/with_position.rs b/src/with_position.rs index 1440fb6..1388503 100644 --- a/src/with_position.rs +++ b/src/with_position.rs @@ -1,10 +1,10 @@ -use std::iter::{Fuse,Peekable}; +use std::iter::{Fuse,Peekable, FusedIterator}; -/// An iterator adaptor that wraps each element in an [`Position`](../enum.Position.html). +/// An iterator adaptor that wraps each element in an [`Position`]. /// /// Iterator element type is `Position<I::Item>`. /// -/// See [`.with_position()`](../trait.Itertools.html#method.with_position) for more information. +/// See [`.with_position()`](crate::Itertools::with_position) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct WithPosition<I> where I: Iterator, @@ -33,7 +33,7 @@ pub fn with_position<I>(iter: I) -> WithPosition<I> /// A value yielded by `WithPosition`. /// Indicates the position of this element in the iterator results. /// -/// See [`.with_position()`](trait.Itertools.html#method.with_position) for more information. +/// See [`.with_position()`](crate::Itertools::with_position) for more information. #[derive(Copy, Clone, Debug, PartialEq)] pub enum Position<T> { /// This is the first element. @@ -95,3 +95,6 @@ impl<I: Iterator> Iterator for WithPosition<I> { impl<I> ExactSizeIterator for WithPosition<I> where I: ExactSizeIterator, { } + +impl<I: Iterator> FusedIterator for WithPosition<I> +{} diff --git a/src/zip_eq_impl.rs b/src/zip_eq_impl.rs index 857465d..a079b32 100644 --- a/src/zip_eq_impl.rs +++ b/src/zip_eq_impl.rs @@ -2,7 +2,7 @@ use super::size_hint; /// An iterator which iterates two other iterators simultaneously /// -/// See [`.zip_eq()`](../trait.Itertools.html#method.zip_eq) for more information. +/// See [`.zip_eq()`](crate::Itertools::zip_eq) for more information. #[derive(Clone, Debug)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct ZipEq<I, J> { @@ -14,7 +14,7 @@ pub struct ZipEq<I, J> { /// /// **Panics** if the iterators are not of the same length. /// -/// `IntoIterator` enabled version of `i.zip_eq(j)`. +/// [`IntoIterator`] enabled version of [`Itertools::zip_eq`](crate::Itertools::zip_eq). /// /// ``` /// use itertools::zip_eq; diff --git a/src/zip_longest.rs b/src/zip_longest.rs index 1395c84..cb9a7ba 100644 --- a/src/zip_longest.rs +++ b/src/zip_longest.rs @@ -1,6 +1,6 @@ use std::cmp::Ordering::{Equal, Greater, Less}; use super::size_hint; -use std::iter::Fuse; +use std::iter::{Fuse, FusedIterator}; use crate::either_or_both::EitherOrBoth; @@ -11,7 +11,7 @@ use crate::either_or_both::EitherOrBoth; /// /// This iterator is *fused*. /// -/// See [`.zip_longest()`](../trait.Itertools.html#method.zip_longest) for more information. +/// See [`.zip_longest()`](crate::Itertools::zip_longest) for more information. #[derive(Clone, Debug)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct ZipLongest<T, U> { @@ -20,7 +20,7 @@ pub struct ZipLongest<T, U> { } /// Create a new `ZipLongest` iterator. -pub fn zip_longest<T, U>(a: T, b: U) -> ZipLongest<T, U> +pub fn zip_longest<T, U>(a: T, b: U) -> ZipLongest<T, U> where T: Iterator, U: Iterator { @@ -76,3 +76,8 @@ impl<T, U> ExactSizeIterator for ZipLongest<T, U> where T: ExactSizeIterator, U: ExactSizeIterator {} + +impl<T, U> FusedIterator for ZipLongest<T, U> + where T: Iterator, + U: Iterator +{} diff --git a/src/ziptuple.rs b/src/ziptuple.rs index 8f40193..b7902ae 100644 --- a/src/ziptuple.rs +++ b/src/ziptuple.rs @@ -1,6 +1,6 @@ use super::size_hint; -/// See [`multizip`](../fn.multizip.html) for more information. +/// See [`multizip`] for more information. #[derive(Clone, Debug)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Zip<T> { @@ -10,7 +10,7 @@ pub struct Zip<T> { /// An iterator that generalizes *.zip()* and allows running multiple iterators in lockstep. /// /// The iterator `Zip<(I, J, ..., M)>` is formed from a tuple of iterators (or values that -/// implement `IntoIterator`) and yields elements +/// implement [`IntoIterator`]) and yields elements /// until any of the subiterators yields `None`. /// /// The iterator element type is a tuple like like `(A, B, ..., E)` where `A` to `E` are the @@ -23,8 +23,6 @@ pub struct Zip<T> { /// Prefer [`izip!()`] over `multizip` for the performance benefits of using the /// standard library `.zip()`. Prefer `multizip` if a nameable type is needed. /// -/// [`izip!()`]: macro.izip.html -/// /// ``` /// use itertools::multizip; /// diff --git a/tests/flatten_ok.rs b/tests/flatten_ok.rs new file mode 100644 index 0000000..bf835b5 --- /dev/null +++ b/tests/flatten_ok.rs @@ -0,0 +1,76 @@ +use itertools::{assert_equal, Itertools}; +use std::{ops::Range, vec::IntoIter}; + +fn mix_data() -> IntoIter<Result<Range<i32>, bool>> { + vec![Ok(0..2), Err(false), Ok(2..4), Err(true), Ok(4..6)].into_iter() +} + +fn ok_data() -> IntoIter<Result<Range<i32>, bool>> { + vec![Ok(0..2), Ok(2..4), Ok(4..6)].into_iter() +} + +#[test] +fn flatten_ok_mixed_expected_forward() { + assert_equal( + mix_data().flatten_ok(), + vec![ + Ok(0), + Ok(1), + Err(false), + Ok(2), + Ok(3), + Err(true), + Ok(4), + Ok(5), + ], + ); +} + +#[test] +fn flatten_ok_mixed_expected_reverse() { + assert_equal( + mix_data().flatten_ok().rev(), + vec![ + Ok(5), + Ok(4), + Err(true), + Ok(3), + Ok(2), + Err(false), + Ok(1), + Ok(0), + ], + ); +} + +#[test] +fn flatten_ok_collect_mixed_forward() { + assert_eq!( + mix_data().flatten_ok().collect::<Result<Vec<_>, _>>(), + Err(false) + ); +} + +#[test] +fn flatten_ok_collect_mixed_reverse() { + assert_eq!( + mix_data().flatten_ok().rev().collect::<Result<Vec<_>, _>>(), + Err(true) + ); +} + +#[test] +fn flatten_ok_collect_ok_forward() { + assert_eq!( + ok_data().flatten_ok().collect::<Result<Vec<_>, _>>(), + Ok((0..6).collect()) + ); +} + +#[test] +fn flatten_ok_collect_ok_reverse() { + assert_eq!( + ok_data().flatten_ok().rev().collect::<Result<Vec<_>, _>>(), + Ok((0..6).rev().collect()) + ); +} diff --git a/tests/quick.rs b/tests/quick.rs index e5bee17..7e222a6 100644 --- a/tests/quick.rs +++ b/tests/quick.rs @@ -916,6 +916,12 @@ quickcheck! { } quickcheck! { + fn size_duplicates(it: Iter<i8>) -> bool { + correct_size_hint(it.duplicates()) + } +} + +quickcheck! { fn size_unique(it: Iter<i8>) -> bool { correct_size_hint(it.unique()) } @@ -1198,6 +1204,17 @@ quickcheck! { } quickcheck! { + fn at_most_one_i32(a: Vec<i32>) -> TestResult { + let ret = a.iter().cloned().at_most_one(); + match a.len() { + 0 => TestResult::from_bool(ret.unwrap() == None), + 1 => TestResult::from_bool(ret.unwrap() == Some(a[0])), + _ => TestResult::from_bool(ret.unwrap_err().eq(a.iter().cloned())), + } + } +} + +quickcheck! { fn consistent_grouping_map_with_by(a: Vec<u8>, modulo: u8) -> () { let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0` @@ -1581,3 +1598,98 @@ quickcheck! { TestResult::from_bool(itertools::equal(x, y)) } } + + +fn is_fused<I: Iterator>(mut it: I) -> bool +{ + while let Some(_) = it.next() {} + for _ in 0..10{ + if it.next().is_some(){ + return false; + } + } + true +} + +quickcheck! { + fn fused_combination(a: Iter<i16>) -> bool + { + is_fused(a.clone().combinations(1)) && + is_fused(a.combinations(3)) + } + + fn fused_combination_with_replacement(a: Iter<i16>) -> bool + { + is_fused(a.clone().combinations_with_replacement(1)) && + is_fused(a.combinations_with_replacement(3)) + } + + fn fused_tuple_combination(a: Iter<i16>) -> bool + { + is_fused(a.clone().fuse().tuple_combinations::<(_,)>()) && + is_fused(a.fuse().tuple_combinations::<(_,_,_)>()) + } + + fn fused_unique(a: Iter<i16>) -> bool + { + is_fused(a.fuse().unique()) + } + + fn fused_unique_by(a: Iter<i16>) -> bool + { + is_fused(a.fuse().unique_by(|x| x % 100)) + } + + fn fused_interleave_shortest(a: Iter<i16>, b: Iter<i16>) -> bool + { + !is_fused(a.clone().interleave_shortest(b.clone())) && + is_fused(a.fuse().interleave_shortest(b.fuse())) + } + + fn fused_product(a: Iter<i16>, b: Iter<i16>) -> bool + { + is_fused(a.fuse().cartesian_product(b.fuse())) + } + + fn fused_merge(a: Iter<i16>, b: Iter<i16>) -> bool + { + is_fused(a.fuse().merge(b.fuse())) + } + + fn fused_filter_ok(a: Iter<i16>) -> bool + { + is_fused(a.map(|x| if x % 2 == 0 {Ok(x)} else {Err(x)} ) + .filter_ok(|x| x % 3 == 0) + .fuse()) + } + + fn fused_filter_map_ok(a: Iter<i16>) -> bool + { + is_fused(a.map(|x| if x % 2 == 0 {Ok(x)} else {Err(x)} ) + .filter_map_ok(|x| if x % 3 == 0 {Some(x / 3)} else {None}) + .fuse()) + } + + fn fused_positions(a: Iter<i16>) -> bool + { + !is_fused(a.clone().positions(|x|x%2==0)) && + is_fused(a.fuse().positions(|x|x%2==0)) + } + + fn fused_update(a: Iter<i16>) -> bool + { + !is_fused(a.clone().update(|x|*x+=1)) && + is_fused(a.fuse().update(|x|*x+=1)) + } + + fn fused_tuple_windows(a: Iter<i16>) -> bool + { + is_fused(a.fuse().tuple_windows::<(_,_)>()) + } + + fn fused_pad_using(a: Iter<i16>) -> bool + { + is_fused(a.fuse().pad_using(100,|_|0)) + } +} + diff --git a/tests/test_core.rs b/tests/test_core.rs index 5861653..bcdca0e 100644 --- a/tests/test_core.rs +++ b/tests/test_core.rs @@ -1,6 +1,6 @@ //! Licensed under the Apache License, Version 2.0 -//! http://www.apache.org/licenses/LICENSE-2.0 or the MIT license -//! http://opensource.org/licenses/MIT, at your +//! https://www.apache.org/licenses/LICENSE-2.0 or the MIT license +//! https://opensource.org/licenses/MIT, at your //! option. This file may not be copied, modified, or distributed //! except according to those terms. #![no_std] @@ -13,6 +13,7 @@ use crate::it::multizip; use crate::it::free::put_back; use crate::it::iproduct; use crate::it::izip; +use crate::it::chain; #[test] fn product2() { @@ -88,6 +89,28 @@ fn multizip3() { } #[test] +fn chain_macro() { + let mut chain = chain!(2..3); + assert!(chain.next() == Some(2)); + assert!(chain.next().is_none()); + + let mut chain = chain!(0..2, 2..3, 3..5i8); + for i in 0..5i8 { + assert_eq!(Some(i), chain.next()); + } + assert!(chain.next().is_none()); + + let mut chain = chain!(); + assert_eq!(chain.next(), Option::<()>::None); +} + +#[test] +fn chain2() { + let _ = chain!(1.., 2..); + let _ = chain!(1.., 2.., ); +} + +#[test] fn write_to() { let xs = [7, 9, 8]; let mut ys = [0; 5]; @@ -254,6 +277,14 @@ fn exactly_one() { } #[test] +fn at_most_one() { + assert_eq!((0..10).filter(|&x| x == 2).at_most_one().unwrap(), Some(2)); + assert!((0..10).filter(|&x| x > 1 && x < 4).at_most_one().unwrap_err().eq(2..4)); + assert!((0..10).filter(|&x| x > 1 && x < 5).at_most_one().unwrap_err().eq(2..5)); + assert_eq!((0..10).filter(|&_| false).at_most_one().unwrap(), None); +} + +#[test] fn sum1() { let v: &[i32] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; assert_eq!(v[..0].iter().cloned().sum1::<i32>(), None); diff --git a/tests/test_std.rs b/tests/test_std.rs index d1ff815..7cda9b5 100644 --- a/tests/test_std.rs +++ b/tests/test_std.rs @@ -59,6 +59,32 @@ fn interleave_shortest() { assert_eq!(it.size_hint(), (6, Some(6))); } +#[test] +fn duplicates_by() { + let xs = ["aaa", "bbbbb", "aa", "ccc", "bbbb", "aaaaa", "cccc"]; + let ys = ["aa", "bbbb", "cccc"]; + it::assert_equal(ys.iter(), xs.iter().duplicates_by(|x| x[..2].to_string())); + it::assert_equal(ys.iter(), xs.iter().rev().duplicates_by(|x| x[..2].to_string()).rev()); + let ys_rev = ["ccc", "aa", "bbbbb"]; + it::assert_equal(ys_rev.iter(), xs.iter().duplicates_by(|x| x[..2].to_string()).rev()); +} + +#[test] +fn duplicates() { + let xs = [0, 1, 2, 3, 2, 1, 3]; + let ys = [2, 1, 3]; + it::assert_equal(ys.iter(), xs.iter().duplicates()); + it::assert_equal(ys.iter(), xs.iter().rev().duplicates().rev()); + let ys_rev = [3, 2, 1]; + it::assert_equal(ys_rev.iter(), xs.iter().duplicates().rev()); + + let xs = [0, 1, 0, 1]; + let ys = [0, 1]; + it::assert_equal(ys.iter(), xs.iter().duplicates()); + it::assert_equal(ys.iter(), xs.iter().rev().duplicates().rev()); + let ys_rev = [1, 0]; + it::assert_equal(ys_rev.iter(), xs.iter().duplicates().rev()); +} #[test] fn unique_by() { @@ -190,6 +216,13 @@ fn all_equal() { } #[test] +fn all_unique() { + assert!("ABCDEFGH".chars().all_unique()); + assert!(!"ABCDEFGA".chars().all_unique()); + assert!(::std::iter::empty::<usize>().all_unique()); +} + +#[test] fn test_put_back_n() { let xs = [0, 1, 1, 1, 2, 1, 3, 3]; let mut pb = put_back_n(xs.iter().cloned()); |