diff options
52 files changed, 3263 insertions, 730 deletions
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json index ca20d51..e778cc0 100644 --- a/.cargo_vcs_info.json +++ b/.cargo_vcs_info.json @@ -1,5 +1,5 @@ { "git": { - "sha1": "b085c523681146151866ead66ae8a4b8967fd005" + "sha1": "4dac4c718895d8c0347d90be70f478673dd28193" } } diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml new file mode 100644 index 0000000..efc779f --- /dev/null +++ b/.github/workflows/ci.yml @@ -0,0 +1,51 @@ +name: CI + +on: + pull_request: + push: + branches: + - staging + - trying + +jobs: + msrv: + name: Rust MSRV + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@v2 + - uses: dtolnay/rust-toolchain@1.36.0 + - run: cargo check --no-default-features + - run: cargo check --no-default-features --features "use_alloc" + - run: cargo check + + stable: + name: Rust Stable + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@v2 + - uses: dtolnay/rust-toolchain@stable + - run: cargo check --no-default-features + - run: cargo check --no-default-features --features "use_alloc" + - run: cargo test + + # https://github.com/rust-lang/crater/blob/9ab6f9697c901c4a44025cf0a39b73ad5b37d198/.github/workflows/bors.yml#L125-L149 + end-success: + name: bors build finished + if: success() + runs-on: ubuntu-latest + needs: [msrv,stable] + + 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/.travis.yml b/.travis.yml deleted file mode 100644 index 8c4a598..0000000 --- a/.travis.yml +++ /dev/null @@ -1,20 +0,0 @@ -language: rust -sudo: false -matrix: - include: - - rust: 1.32.0 - - rust: stable - - rust: beta - - rust: nightly -branches: - only: - - master - # bors branches - - staging - - trying -script: - - | - cargo build --verbose --no-default-features && - cargo build --verbose --features "$FEATURES" && - cargo test --verbose --features "$FEATURES" && - cargo bench --verbose --features "$FEATURES" @@ -45,6 +45,7 @@ rust_library { edition: "2018", features: [ "default", + "use_alloc", "use_std", ], rustlibs: [ @@ -13,7 +13,7 @@ [package] edition = "2018" name = "itertools" -version = "0.9.0" +version = "0.10.0" authors = ["bluss"] exclude = ["/bors.toml"] description = "Extra iterator adaptors, iterator methods, free functions, and macros." @@ -54,11 +54,22 @@ harness = false [[bench]] name = "bench1" harness = false + +[[bench]] +name = "combinations" +harness = false + +[[bench]] +name = "powerset" +harness = false [dependencies.either] version = "1.0" default-features = false [dev-dependencies.criterion] -version = "=0.3.0" +version = "=0" + +[dev-dependencies.paste] +version = "1.0.0" [dev-dependencies.permutohedron] version = "0.2" @@ -72,4 +83,5 @@ version = "0.7" [features] default = ["use_std"] -use_std = [] +use_alloc = [] +use_std = ["use_alloc"] diff --git a/Cargo.toml.orig b/Cargo.toml.orig index 472a27a..46b2094 100644 --- a/Cargo.toml.orig +++ b/Cargo.toml.orig @@ -1,6 +1,6 @@ [package] name = "itertools" -version = "0.9.0" +version = "0.10.0" license = "MIT/Apache-2.0" repository = "https://github.com/bluss/rust-itertools" @@ -27,7 +27,8 @@ either = { version = "1.0", default-features = false } [dev-dependencies] rand = "0.7" -criterion = "=0.3.0" # TODO update criterion version once it becomes compatible with our minimum required Rust verision or bump minimum required rust version +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 [dev-dependencies.quickcheck] version = "0.9" @@ -38,7 +39,8 @@ version = "0.2" [features] default = ["use_std"] -use_std = [] +use_std = ["use_alloc"] +use_alloc = [] [profile] bench = { debug = true } @@ -66,3 +68,11 @@ harness = false [[bench]] name = "bench1" harness = false + +[[bench]] +name = "combinations" +harness = false + +[[bench]] +name = "powerset" +harness = false @@ -7,13 +7,13 @@ third_party { } url { type: ARCHIVE - value: "https://static.crates.io/crates/itertools/itertools-0.9.0.crate" + value: "https://static.crates.io/crates/itertools/itertools-0.10.0.crate" } - version: "0.9.0" + version: "0.10.0" license_type: NOTICE last_upgrade_date { - year: 2020 - month: 12 - day: 21 + year: 2021 + month: 4 + day: 1 } } @@ -21,7 +21,7 @@ How to use with cargo: .. code:: toml [dependencies] - itertools = "0.8" + itertools = "0.9" How to use in your crate: diff --git a/benches/combinations.rs b/benches/combinations.rs new file mode 100644 index 0000000..e7433a4 --- /dev/null +++ b/benches/combinations.rs @@ -0,0 +1,125 @@ +use criterion::{black_box, criterion_group, criterion_main, Criterion}; +use itertools::Itertools; + +// approximate 100_000 iterations for each combination +const N1: usize = 100_000; +const N2: usize = 448; +const N3: usize = 86; +const N4: usize = 41; +const N14: usize = 21; + +fn comb_for1(c: &mut Criterion) { + c.bench_function("comb for1", move |b| { + b.iter(|| { + for i in 0..N1 { + black_box(vec![i]); + } + }) + }); +} + +fn comb_for2(c: &mut Criterion) { + c.bench_function("comb for2", move |b| { + b.iter(|| { + for i in 0..N2 { + for j in (i + 1)..N2 { + black_box(vec![i, j]); + } + } + }) + }); +} + +fn comb_for3(c: &mut Criterion) { + c.bench_function("comb for3", move |b| { + b.iter(|| { + for i in 0..N3 { + for j in (i + 1)..N3 { + for k in (j + 1)..N3 { + black_box(vec![i, j, k]); + } + } + } + }) + }); +} + +fn comb_for4(c: &mut Criterion) { + c.bench_function("comb for4", move |b| { + b.iter(|| { + for i in 0..N4 { + for j in (i + 1)..N4 { + for k in (j + 1)..N4 { + for l in (k + 1)..N4 { + black_box(vec![i, j, k, l]); + } + } + } + } + }) + }); +} + +fn comb_c1(c: &mut Criterion) { + c.bench_function("comb c1", move |b| { + b.iter(|| { + for combo in (0..N1).combinations(1) { + black_box(combo); + } + }) + }); +} + +fn comb_c2(c: &mut Criterion) { + c.bench_function("comb c2", move |b| { + b.iter(|| { + for combo in (0..N2).combinations(2) { + black_box(combo); + } + }) + }); +} + +fn comb_c3(c: &mut Criterion) { + c.bench_function("comb c3", move |b| { + b.iter(|| { + for combo in (0..N3).combinations(3) { + black_box(combo); + } + }) + }); +} + +fn comb_c4(c: &mut Criterion) { + c.bench_function("comb c4", move |b| { + b.iter(|| { + for combo in (0..N4).combinations(4) { + black_box(combo); + } + }) + }); +} + +fn comb_c14(c: &mut Criterion) { + c.bench_function("comb c14", move |b| { + b.iter(|| { + for combo in (0..N14).combinations(14) { + black_box(combo); + } + }) + }); +} + +criterion_group!( + benches, + comb_for1, + comb_for2, + comb_for3, + comb_for4, + comb_c1, + comb_c2, + comb_c3, + comb_c4, + comb_c14, +); +criterion_main!(benches); diff --git a/benches/fold_specialization.rs b/benches/fold_specialization.rs index 53319a5..5de4671 100644 --- a/benches/fold_specialization.rs +++ b/benches/fold_specialization.rs @@ -9,7 +9,7 @@ where I: Iterator type Item = I::Item; #[inline(always)] - fn next(&mut self) -> Option<I::Item> { + fn next(&mut self) -> Option<Self::Item> { self.0.next() } diff --git a/benches/powerset.rs b/benches/powerset.rs new file mode 100644 index 0000000..074550b --- /dev/null +++ b/benches/powerset.rs @@ -0,0 +1,44 @@ +use criterion::{black_box, criterion_group, criterion_main, Criterion}; +use itertools::Itertools; + +// Keep aggregate generated elements the same, regardless of powerset length. +const TOTAL_ELEMENTS: usize = 1 << 12; +const fn calc_iters(n: usize) -> usize { + TOTAL_ELEMENTS / (1 << n) +} + +fn powerset_n(c: &mut Criterion, n: usize) { + let id = format!("powerset {}", n); + c.bench_function(id.as_str(), move |b| { + b.iter(|| { + for _ in 0..calc_iters(n) { + for elt in (0..n).powerset() { + black_box(elt); + } + } + }) + }); +} + +fn powerset_0(c: &mut Criterion) { powerset_n(c, 0); } + +fn powerset_1(c: &mut Criterion) { powerset_n(c, 1); } + +fn powerset_2(c: &mut Criterion) { powerset_n(c, 2); } + +fn powerset_4(c: &mut Criterion) { powerset_n(c, 4); } + +fn powerset_8(c: &mut Criterion) { powerset_n(c, 8); } + +fn powerset_12(c: &mut Criterion) { powerset_n(c, 12); } + +criterion_group!( + benches, + powerset_0, + powerset_1, + powerset_2, + powerset_4, + powerset_8, + powerset_12, +); +criterion_main!(benches);
\ No newline at end of file diff --git a/benches/tuple_combinations.rs b/benches/tuple_combinations.rs index 84411ef..4e26b28 100644 --- a/benches/tuple_combinations.rs +++ b/benches/tuple_combinations.rs @@ -7,8 +7,8 @@ const N2: usize = 448; const N3: usize = 86; const N4: usize = 41; -fn comb_for1(c: &mut Criterion) { - c.bench_function("comb for1", move |b| { +fn tuple_comb_for1(c: &mut Criterion) { + c.bench_function("tuple comb for1", move |b| { b.iter(|| { for i in 0..N1 { black_box(i); @@ -17,8 +17,8 @@ fn comb_for1(c: &mut Criterion) { }); } -fn comb_for2(c: &mut Criterion) { - c.bench_function("comb for2", move |b| { +fn tuple_comb_for2(c: &mut Criterion) { + c.bench_function("tuple comb for2", move |b| { b.iter(|| { for i in 0..N2 { for j in (i + 1)..N2 { @@ -29,8 +29,8 @@ fn comb_for2(c: &mut Criterion) { }); } -fn comb_for3(c: &mut Criterion) { - c.bench_function("comb for3", move |b| { +fn tuple_comb_for3(c: &mut Criterion) { + c.bench_function("tuple comb for3", move |b| { b.iter(|| { for i in 0..N3 { for j in (i + 1)..N3 { @@ -43,8 +43,8 @@ fn comb_for3(c: &mut Criterion) { }); } -fn comb_for4(c: &mut Criterion) { - c.bench_function("comb for4", move |b| { +fn tuple_comb_for4(c: &mut Criterion) { + c.bench_function("tuple comb for4", move |b| { b.iter(|| { for i in 0..N4 { for j in (i + 1)..N4 { @@ -59,8 +59,8 @@ fn comb_for4(c: &mut Criterion) { }); } -fn comb_c1(c: &mut Criterion) { - c.bench_function("comb c1", move |b| { +fn tuple_comb_c1(c: &mut Criterion) { + c.bench_function("tuple comb c1", move |b| { b.iter(|| { for (i,) in (0..N1).tuple_combinations() { black_box(i); @@ -69,8 +69,8 @@ fn comb_c1(c: &mut Criterion) { }); } -fn comb_c2(c: &mut Criterion) { - c.bench_function("comb c2", move |b| { +fn tuple_comb_c2(c: &mut Criterion) { + c.bench_function("tuple comb c2", move |b| { b.iter(|| { for (i, j) in (0..N2).tuple_combinations() { black_box(i + j); @@ -79,8 +79,8 @@ fn comb_c2(c: &mut Criterion) { }); } -fn comb_c3(c: &mut Criterion) { - c.bench_function("comb c3", move |b| { +fn tuple_comb_c3(c: &mut Criterion) { + c.bench_function("tuple comb c3", move |b| { b.iter(|| { for (i, j, k) in (0..N3).tuple_combinations() { black_box(i + j + k); @@ -89,8 +89,8 @@ fn comb_c3(c: &mut Criterion) { }); } -fn comb_c4(c: &mut Criterion) { - c.bench_function("comb c4", move |b| { +fn tuple_comb_c4(c: &mut Criterion) { + c.bench_function("tuple comb c4", move |b| { b.iter(|| { for (i, j, k, l) in (0..N4).tuple_combinations() { black_box(i + j + k + l); @@ -101,13 +101,13 @@ fn comb_c4(c: &mut Criterion) { criterion_group!( benches, - comb_for1, - comb_for2, - comb_for3, - comb_for4, - comb_c1, - comb_c2, - comb_c3, - comb_c4, + tuple_comb_for1, + tuple_comb_for2, + tuple_comb_for3, + tuple_comb_for4, + tuple_comb_c1, + tuple_comb_c2, + tuple_comb_c3, + tuple_comb_c4, ); criterion_main!(benches); diff --git a/examples/iris.rs b/examples/iris.rs index 25ab373..987d9e9 100644 --- a/examples/iris.rs +++ b/examples/iris.rs @@ -55,7 +55,7 @@ fn main() { // using Itertools::fold_results to create the result of parsing let irises = DATA.lines() .map(str::parse) - .fold_results(Vec::new(), |mut v, iris: Iris| { + .fold_ok(Vec::new(), |mut v, iris: Iris| { v.push(iris); v }); diff --git a/src/adaptors/coalesce.rs b/src/adaptors/coalesce.rs new file mode 100644 index 0000000..116f688 --- /dev/null +++ b/src/adaptors/coalesce.rs @@ -0,0 +1,232 @@ +use std::fmt; +use std::iter::FusedIterator; + +use crate::size_hint; + +pub struct CoalesceBy<I, F, T> +where + I: Iterator, +{ + iter: I, + last: Option<T>, + f: F, +} + +impl<I: Clone, F: Clone, T: Clone> Clone for CoalesceBy<I, F, T> +where + I: Iterator, +{ + clone_fields!(last, iter, f); +} + +impl<I, F, T> fmt::Debug for CoalesceBy<I, F, T> +where + I: Iterator + fmt::Debug, + T: fmt::Debug, +{ + debug_fmt_fields!(CoalesceBy, iter); +} + +pub trait CoalescePredicate<Item, T> { + fn coalesce_pair(&mut self, t: T, item: Item) -> Result<T, (T, T)>; +} + +impl<I, F, T> Iterator for CoalesceBy<I, F, T> +where + I: Iterator, + F: CoalescePredicate<I::Item, T>, +{ + type Item = T; + + 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) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + let (low, hi) = size_hint::add_scalar(self.iter.size_hint(), self.last.is_some() as usize); + ((low > 0) as usize, hi) + } + + fn fold<Acc, FnAcc>(self, acc: Acc, mut fn_acc: FnAcc) -> Acc + where + FnAcc: FnMut(Acc, Self::Item) -> Acc, + { + if let Some(last) = self.last { + let mut f = self.f; + let (last, acc) = self.iter.fold((last, acc), |(last, acc), elt| { + match f.coalesce_pair(last, elt) { + Ok(joined) => (joined, acc), + Err((last_, next_)) => (next_, fn_acc(acc, last_)), + } + }); + fn_acc(acc, last) + } else { + acc + } + } +} + +impl<I: Iterator, F: CoalescePredicate<I::Item, T>, T> FusedIterator for CoalesceBy<I, F, T> {} + +/// An iterator adaptor that may join together adjacent elements. +/// +/// See [`.coalesce()`](../trait.Itertools.html#method.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>; + +impl<F, Item, T> CoalescePredicate<Item, T> for F +where + F: FnMut(T, Item) -> Result<T, (T, T)>, +{ + fn coalesce_pair(&mut self, t: T, item: Item) -> Result<T, (T, T)> { + self(t, item) + } +} + +/// Create a new `Coalesce`. +pub fn coalesce<I, F>(mut iter: I, f: F) -> Coalesce<I, F> +where + I: Iterator, +{ + Coalesce { + last: iter.next(), + iter, + f, + } +} + +/// 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. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub type DedupBy<I, Pred> = CoalesceBy<I, DedupPred2CoalescePred<Pred>, <I as Iterator>::Item>; + +#[derive(Clone)] +pub struct DedupPred2CoalescePred<DP>(DP); + +pub trait DedupPredicate<T> { + // TODO replace by Fn(&T, &T)->bool once Rust supports it + fn dedup_pair(&mut self, a: &T, b: &T) -> bool; +} + +impl<DP, T> CoalescePredicate<T, T> for DedupPred2CoalescePred<DP> +where + DP: DedupPredicate<T>, +{ + fn coalesce_pair(&mut self, t: T, item: T) -> Result<T, (T, T)> { + if self.0.dedup_pair(&t, &item) { + Ok(t) + } else { + Err((t, item)) + } + } +} + +#[derive(Clone)] +pub struct DedupEq; + +impl<T: PartialEq> DedupPredicate<T> for DedupEq { + fn dedup_pair(&mut self, a: &T, b: &T) -> bool { + a == b + } +} + +impl<T, F: FnMut(&T, &T) -> bool> DedupPredicate<T> for F { + fn dedup_pair(&mut self, a: &T, b: &T) -> bool { + self(a, b) + } +} + +/// Create a new `DedupBy`. +pub fn dedup_by<I, Pred>(mut iter: I, dedup_pred: Pred) -> DedupBy<I, Pred> +where + I: Iterator, +{ + DedupBy { + last: iter.next(), + iter, + f: DedupPred2CoalescePred(dedup_pred), + } +} + +/// An iterator adaptor that removes repeated duplicates. +/// +/// See [`.dedup()`](../trait.Itertools.html#method.dedup) for more information. +pub type Dedup<I> = DedupBy<I, DedupEq>; + +/// Create a new `Dedup`. +pub fn dedup<I>(iter: I) -> Dedup<I> +where + I: Iterator, +{ + dedup_by(iter, DedupEq) +} + +/// 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. +#[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)>; + +#[derive(Clone)] +pub struct DedupPredWithCount2CoalescePred<DP>(DP); + +impl<DP, T> CoalescePredicate<T, (usize, T)> for DedupPredWithCount2CoalescePred<DP> +where + DP: DedupPredicate<T>, +{ + fn coalesce_pair( + &mut self, + (c, t): (usize, T), + item: T, + ) -> Result<(usize, T), ((usize, T), (usize, T))> { + if self.0.dedup_pair(&t, &item) { + Ok((c + 1, t)) + } else { + Err(((c, t), (1, item))) + } + } +} + +/// 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. +pub type DedupWithCount<I> = DedupByWithCount<I, DedupEq>; + +/// Create a new `DedupByWithCount`. +pub fn dedup_by_with_count<I, Pred>(mut iter: I, dedup_pred: Pred) -> DedupByWithCount<I, Pred> +where + I: Iterator, +{ + DedupByWithCount { + last: iter.next().map(|v| (1, v)), + iter, + f: DedupPredWithCount2CoalescePred(dedup_pred), + } +} + +/// Create a new `DedupWithCount`. +pub fn dedup_with_count<I>(iter: I) -> DedupWithCount<I> +where + I: Iterator, +{ + dedup_by_with_count(iter, DedupEq) +} diff --git a/src/adaptors/map.rs b/src/adaptors/map.rs new file mode 100644 index 0000000..ff377f7 --- /dev/null +++ b/src/adaptors/map.rs @@ -0,0 +1,120 @@ +use std::iter::FromIterator; +use std::marker::PhantomData; + +#[derive(Clone)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct MapSpecialCase<I, F> { + iter: I, + f: F, +} + +pub trait MapSpecialCaseFn<T> { + type Out; + fn call(&mut self, t: T) -> Self::Out; +} + +impl<I, R> Iterator for MapSpecialCase<I, R> +where + I: Iterator, + R: MapSpecialCaseFn<I::Item>, +{ + type Item = R::Out; + + fn next(&mut self) -> Option<Self::Item> { + self.iter.next().map(|i| self.f.call(i)) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } + + fn fold<Acc, Fold>(self, init: Acc, mut fold_f: Fold) -> Acc + where + Fold: FnMut(Acc, Self::Item) -> Acc, + { + let mut f = self.f; + self.iter.fold(init, move |acc, v| fold_f(acc, f.call(v))) + } + + fn collect<C>(self) -> C + where + C: FromIterator<Self::Item>, + { + let mut f = self.f; + self.iter.map(move |v| f.call(v)).collect() + } +} + +impl<I, R> DoubleEndedIterator for MapSpecialCase<I, R> +where + I: DoubleEndedIterator, + R: MapSpecialCaseFn<I::Item>, +{ + fn next_back(&mut self) -> Option<Self::Item> { + self.iter.next_back().map(|i| self.f.call(i)) + } +} + +impl<I, R> ExactSizeIterator for MapSpecialCase<I, R> +where + I: ExactSizeIterator, + R: MapSpecialCaseFn<I::Item>, +{ +} + +/// An iterator adapter to apply a transformation within a nested `Result::Ok`. +/// +/// See [`.map_ok()`](../trait.Itertools.html#method.map_ok) for more information. +pub type MapOk<I, F> = MapSpecialCase<I, MapSpecialCaseFnOk<F>>; + +/// See [`MapOk`](struct.MapOk.html). +#[deprecated(note = "Use MapOk instead", since = "0.10.0")] +pub type MapResults<I, F> = MapOk<I, F>; + +impl<F, T, U, E> MapSpecialCaseFn<Result<T, E>> for MapSpecialCaseFnOk<F> +where + F: FnMut(T) -> U, +{ + type Out = Result<U, E>; + fn call(&mut self, t: Result<T, E>) -> Self::Out { + t.map(|v| self.0(v)) + } +} + +#[derive(Clone)] +pub struct MapSpecialCaseFnOk<F>(F); + +/// Create a new `MapOk` iterator. +pub fn map_ok<I, F, T, U, E>(iter: I, f: F) -> MapOk<I, F> +where + I: Iterator<Item = Result<T, E>>, + F: FnMut(T) -> U, +{ + MapSpecialCase { + iter, + f: MapSpecialCaseFnOk(f), + } +} + +/// An iterator adapter to apply `Into` conversion to each element. +/// +/// See [`.map_into()`](../trait.Itertools.html#method.map_into) for more information. +pub type MapInto<I, R> = MapSpecialCase<I, MapSpecialCaseFnInto<R>>; + +impl<T: Into<U>, U> MapSpecialCaseFn<T> for MapSpecialCaseFnInto<U> { + type Out = U; + fn call(&mut self, t: T) -> Self::Out { + t.into() + } +} + +#[derive(Clone)] +pub struct MapSpecialCaseFnInto<U>(PhantomData<U>); + +/// Create a new [`MapInto`](struct.MapInto.html) iterator. +pub fn map_into<I, R>(iter: I) -> MapInto<I, R> { + MapSpecialCase { + iter, + f: MapSpecialCaseFnInto(PhantomData), + } +} diff --git a/src/adaptors/mod.rs b/src/adaptors/mod.rs index 7d61f11..8a8697b 100644 --- a/src/adaptors/mod.rs +++ b/src/adaptors/mod.rs @@ -4,12 +4,17 @@ //! option. This file may not be copied, modified, or distributed //! except according to those terms. +mod coalesce; +mod map; mod multi_product; -#[cfg(feature = "use_std")] +pub use self::coalesce::*; +pub use self::map::{map_into, map_ok, MapInto, MapOk}; +#[allow(deprecated)] +pub use self::map::MapResults; +#[cfg(feature = "use_alloc")] pub use self::multi_product::*; use std::fmt; -use std::mem::replace; use std::iter::{Fuse, Peekable, FromIterator}; use std::marker::PhantomData; use crate::size_hint; @@ -32,13 +37,7 @@ pub struct Interleave<I, J> { /// /// `IntoIterator` enabled version of `i.interleave(j)`. /// -/// ``` -/// use itertools::interleave; -/// -/// for elt in interleave(&[1, 2, 3], &[2, 3, 4]) { -/// /* loop body */ -/// } -/// ``` +/// See [`.interleave()`](trait.Itertools.html#method.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> @@ -56,7 +55,7 @@ impl<I, J> Iterator for Interleave<I, J> { type Item = I::Item; #[inline] - fn next(&mut self) -> Option<I::Item> { + fn next(&mut self) -> Option<Self::Item> { self.flag = !self.flag; if self.flag { match self.a.next() { @@ -113,23 +112,12 @@ impl<I, J> Iterator for InterleaveShortest<I, J> type Item = I::Item; #[inline] - fn next(&mut self) -> Option<I::Item> { - match self.phase { - false => match self.it0.next() { - None => None, - e => { - self.phase = true; - e - } - }, - true => match self.it1.next() { - None => None, - e => { - self.phase = false; - e - } - }, + fn next(&mut self) -> Option<Self::Item> { + let e = if self.phase { self.it1.next() } else { self.it0.next() }; + if e.is_some() { + self.phase = !self.phase; } + e } #[inline] @@ -221,7 +209,7 @@ impl<I> Iterator for PutBack<I> { type Item = I::Item; #[inline] - fn next(&mut self) -> Option<I::Item> { + fn next(&mut self) -> Option<Self::Item> { match self.top { None => self.iter.next(), ref mut some => some.take(), @@ -310,14 +298,14 @@ pub fn cartesian_product<I, J>(mut i: I, j: J) -> Product<I, J> } } - impl<I, J> Iterator for Product<I, J> where I: Iterator, J: Clone + Iterator, I::Item: Clone { type Item = (I::Item, J::Item); - fn next(&mut self) -> Option<(I::Item, J::Item)> { + + fn next(&mut self) -> Option<Self::Item> { let elt_b = match self.b.next() { None => { self.b = self.b_orig.clone(); @@ -401,15 +389,9 @@ impl<B, F, I> Iterator for Batching<I, F> { type Item = B; #[inline] - fn next(&mut self) -> Option<B> { + fn next(&mut self) -> Option<Self::Item> { (self.f)(&mut self.iter) } - - #[inline] - fn size_hint(&self) -> (usize, Option<usize>) { - // No information about closue behavior - (0, None) - } } /// An iterator adaptor that steps a number elements in the base iterator @@ -419,7 +401,7 @@ impl<B, F, I> Iterator for Batching<I, F> /// then skipping forward *n-1* elements. /// /// See [`.step()`](../trait.Itertools.html#method.step) for more information. -#[deprecated(note="Use std .step_by() instead", since="0.8")] +#[deprecated(note="Use std .step_by() instead", since="0.8.0")] #[allow(deprecated)] #[derive(Clone, Debug)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] @@ -448,7 +430,7 @@ impl<I> Iterator for Step<I> { type Item = I::Item; #[inline] - fn next(&mut self) -> Option<I::Item> { + fn next(&mut self) -> Option<Self::Item> { let elt = self.iter.next(); if self.skip > 0 { self.iter.nth(self.skip - 1); @@ -577,7 +559,7 @@ impl<I, J, F> Iterator for MergeBy<I, J, F> { type Item = I::Item; - fn next(&mut self) -> Option<I::Item> { + fn next(&mut self) -> Option<Self::Item> { let less_than = match self.fused { Some(lt) => lt, None => match (self.a.peek(), self.b.peek()) { @@ -606,203 +588,6 @@ impl<I, J, F> Iterator for MergeBy<I, J, F> } } -#[derive(Clone, Debug)] -pub struct CoalesceCore<I> - where I: Iterator -{ - iter: I, - last: Option<I::Item>, -} - -impl<I> CoalesceCore<I> - where I: Iterator -{ - fn next_with<F>(&mut self, mut f: F) -> Option<I::Item> - where F: FnMut(I::Item, I::Item) -> Result<I::Item, (I::Item, I::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 f(last, next) { - Ok(joined) => last = joined, - Err((last_, next_)) => { - self.last = Some(next_); - return Some(last_); - } - } - } - - Some(last) - } - - fn size_hint(&self) -> (usize, Option<usize>) { - let (low, hi) = size_hint::add_scalar(self.iter.size_hint(), - self.last.is_some() as usize); - ((low > 0) as usize, hi) - } -} - -/// An iterator adaptor that may join together adjacent elements. -/// -/// See [`.coalesce()`](../trait.Itertools.html#method.coalesce) for more information. -#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] -pub struct Coalesce<I, F> - where I: Iterator -{ - iter: CoalesceCore<I>, - f: F, -} - -impl<I: Clone, F: Clone> Clone for Coalesce<I, F> - where I: Iterator, - I::Item: Clone -{ - clone_fields!(iter, f); -} - -impl<I, F> fmt::Debug for Coalesce<I, F> - where I: Iterator + fmt::Debug, - I::Item: fmt::Debug, -{ - debug_fmt_fields!(Coalesce, iter); -} - -/// Create a new `Coalesce`. -pub fn coalesce<I, F>(mut iter: I, f: F) -> Coalesce<I, F> - where I: Iterator -{ - Coalesce { - iter: CoalesceCore { - last: iter.next(), - iter, - }, - f, - } -} - -impl<I, F> Iterator for Coalesce<I, F> - where I: Iterator, - F: FnMut(I::Item, I::Item) -> Result<I::Item, (I::Item, I::Item)> -{ - type Item = I::Item; - - fn next(&mut self) -> Option<I::Item> { - self.iter.next_with(&mut self.f) - } - - fn size_hint(&self) -> (usize, Option<usize>) { - self.iter.size_hint() - } -} - -/// 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. -#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] -pub struct DedupBy<I, Pred> - where I: Iterator -{ - iter: CoalesceCore<I>, - dedup_pred: Pred, -} - -pub trait DedupPredicate<T> { // TODO replace by Fn(&T, &T)->bool once Rust supports it - fn dedup_pair(&mut self, a: &T, b: &T) -> bool; -} - -#[derive(Clone)] -pub struct DedupEq; - -impl<T: PartialEq> DedupPredicate<T> for DedupEq { - fn dedup_pair(&mut self, a: &T, b: &T) -> bool { - a==b - } -} - -impl<T, F: FnMut(&T, &T)->bool> DedupPredicate<T> for F { - fn dedup_pair(&mut self, a: &T, b: &T) -> bool { - self(a, b) - } -} - -/// An iterator adaptor that removes repeated duplicates. -/// -/// See [`.dedup()`](../trait.Itertools.html#method.dedup) for more information. -pub type Dedup<I>=DedupBy<I, DedupEq>; - -impl<I: Clone, Pred: Clone> Clone for DedupBy<I, Pred> - where I: Iterator, - I::Item: Clone, -{ - clone_fields!(iter, dedup_pred); -} - -/// Create a new `DedupBy`. -pub fn dedup_by<I, Pred>(mut iter: I, dedup_pred: Pred) -> DedupBy<I, Pred> - where I: Iterator, -{ - DedupBy { - iter: CoalesceCore { - last: iter.next(), - iter, - }, - dedup_pred, - } -} - -/// Create a new `Dedup`. -pub fn dedup<I>(iter: I) -> Dedup<I> - where I: Iterator -{ - dedup_by(iter, DedupEq) -} - -impl<I, Pred> fmt::Debug for DedupBy<I, Pred> - where I: Iterator + fmt::Debug, - I::Item: fmt::Debug, -{ - debug_fmt_fields!(Dedup, iter); -} - -impl<I, Pred> Iterator for DedupBy<I, Pred> - where I: Iterator, - Pred: DedupPredicate<I::Item>, -{ - type Item = I::Item; - - fn next(&mut self) -> Option<I::Item> { - let ref mut dedup_pred = self.dedup_pred; - self.iter.next_with(|x, y| { - if dedup_pred.dedup_pair(&x, &y) { Ok(x) } else { Err((x, y)) } - }) - } - - fn size_hint(&self) -> (usize, Option<usize>) { - self.iter.size_hint() - } - - fn fold<Acc, G>(self, mut accum: Acc, mut f: G) -> Acc - where G: FnMut(Acc, Self::Item) -> Acc, - { - if let Some(mut last) = self.iter.last { - let mut dedup_pred = self.dedup_pred; - accum = self.iter.iter.fold(accum, |acc, elt| { - if dedup_pred.dedup_pair(&elt, &last) { - acc - } else { - f(acc, replace(&mut last, elt)) - } - }); - f(accum, last) - } else { - accum - } - } -} - /// An iterator adaptor that borrows from a `Clone`-able iterator /// to only pick off elements while the predicate returns `true`. /// @@ -832,7 +617,7 @@ impl<'a, I, F> Iterator for TakeWhileRef<'a, I, F> { type Item = I::Item; - fn next(&mut self) -> Option<I::Item> { + fn next(&mut self) -> Option<Self::Item> { let old = self.iter.clone(); match self.iter.next() { None => None, @@ -848,8 +633,7 @@ impl<'a, I, F> Iterator for TakeWhileRef<'a, I, F> } fn size_hint(&self) -> (usize, Option<usize>) { - let (_, hi) = self.iter.size_hint(); - (0, hi) + (0, self.iter.size_hint().1) } } @@ -873,7 +657,7 @@ impl<I, A> Iterator for WhileSome<I> { type Item = A; - fn next(&mut self) -> Option<A> { + fn next(&mut self) -> Option<Self::Item> { match self.iter.next() { None | Some(None) => None, Some(elt) => elt, @@ -881,8 +665,7 @@ impl<I, A> Iterator for WhileSome<I> } fn size_hint(&self) -> (usize, Option<usize>) { - let sh = self.iter.size_hint(); - (0, sh.1) + (0, self.iter.size_hint().1) } } @@ -1012,115 +795,163 @@ macro_rules! impl_tuple_combination { ) } -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); - -/// An iterator adapter to apply `Into` conversion to each element. +// This snippet generates the twelve `impl_tuple_combination!` invocations: +// use core::iter; +// use itertools::Itertools; +// +// for i in 2..=12 { +// println!("impl_tuple_combination!(Tuple{arity}Combination Tuple{prev}Combination; {tys}; {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); + +/// An iterator adapter to filter values within a nested `Result::Ok`. /// -/// See [`.map_into()`](../trait.Itertools.html#method.map_into) for more information. +/// See [`.filter_ok()`](../trait.Itertools.html#method.filter_ok) for more information. #[derive(Clone)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] -pub struct MapInto<I, R> { +pub struct FilterOk<I, F> { iter: I, - _res: PhantomData<fn() -> R>, + f: F } -/// Create a new [`MapInto`](struct.MapInto.html) iterator. -pub fn map_into<I, R>(iter: I) -> MapInto<I, R> { - MapInto { +/// Create a new `FilterOk` iterator. +pub fn filter_ok<I, F, T, E>(iter: I, f: F) -> FilterOk<I, F> + where I: Iterator<Item = Result<T, E>>, + F: FnMut(&T) -> bool, +{ + FilterOk { iter, - _res: PhantomData, + f, } } -impl<I, R> Iterator for MapInto<I, R> - where I: Iterator, - I::Item: Into<R>, +impl<I, F, T, E> Iterator for FilterOk<I, F> + where I: Iterator<Item = Result<T, E>>, + F: FnMut(&T) -> bool, { - type Item = R; + type Item = Result<T, E>; - fn next(&mut self) -> Option<R> { - self.iter - .next() - .map(|i| i.into()) + fn next(&mut self) -> Option<Self::Item> { + loop { + match self.iter.next() { + Some(Ok(v)) => { + if (self.f)(&v) { + return Some(Ok(v)); + } + }, + Some(Err(e)) => return Some(Err(e)), + None => return None, + } + } } fn size_hint(&self) -> (usize, Option<usize>) { - self.iter.size_hint() + (0, self.iter.size_hint().1) } - fn fold<Acc, Fold>(self, init: Acc, mut fold_f: Fold) -> Acc + fn fold<Acc, Fold>(self, init: Acc, fold_f: Fold) -> Acc where Fold: FnMut(Acc, Self::Item) -> Acc, { - self.iter.fold(init, move |acc, v| fold_f(acc, v.into())) + let mut f = self.f; + self.iter.filter(|v| { + v.as_ref().map(&mut f).unwrap_or(true) + }).fold(init, fold_f) } -} -impl<I, R> DoubleEndedIterator for MapInto<I, R> - where I: DoubleEndedIterator, - I::Item: Into<R>, -{ - fn next_back(&mut self) -> Option<Self::Item> { - self.iter - .next_back() - .map(|i| i.into()) + fn collect<C>(self) -> C + where C: FromIterator<Self::Item> + { + let mut f = self.f; + self.iter.filter(|v| { + v.as_ref().map(&mut f).unwrap_or(true) + }).collect() } } -impl<I, R> ExactSizeIterator for MapInto<I, R> -where - I: ExactSizeIterator, - I::Item: Into<R>, -{} - -/// An iterator adapter to apply a transformation within a nested `Result`. +/// An iterator adapter to filter and apply a transformation on values within a nested `Result::Ok`. /// -/// See [`.map_results()`](../trait.Itertools.html#method.map_results) for more information. -#[derive(Clone)] +/// See [`.filter_map_ok()`](../trait.Itertools.html#method.filter_map_ok) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] -pub struct MapResults<I, F> { +pub struct FilterMapOk<I, F> { iter: I, f: F } -/// Create a new `MapResults` iterator. -pub fn map_results<I, F, T, U, E>(iter: I, f: F) -> MapResults<I, F> +fn transpose_result<T, E>(result: Result<Option<T>, E>) -> Option<Result<T, E>> { + match result { + Ok(Some(v)) => Some(Ok(v)), + Ok(None) => None, + Err(e) => Some(Err(e)), + } +} + +/// Create a new `FilterOk` iterator. +pub fn filter_map_ok<I, F, T, U, E>(iter: I, f: F) -> FilterMapOk<I, F> where I: Iterator<Item = Result<T, E>>, - F: FnMut(T) -> U, + F: FnMut(T) -> Option<U>, { - MapResults { + FilterMapOk { iter, f, } } -impl<I, F, T, U, E> Iterator for MapResults<I, F> +impl<I, F, T, U, E> Iterator for FilterMapOk<I, F> where I: Iterator<Item = Result<T, E>>, - F: FnMut(T) -> U, + F: FnMut(T) -> Option<U>, { type Item = Result<U, E>; fn next(&mut self) -> Option<Self::Item> { - self.iter.next().map(|v| v.map(&mut self.f)) + loop { + match self.iter.next() { + Some(Ok(v)) => { + if let Some(v) = (self.f)(v) { + return Some(Ok(v)); + } + }, + Some(Err(e)) => return Some(Err(e)), + None => return None, + } + } } fn size_hint(&self) -> (usize, Option<usize>) { - self.iter.size_hint() + (0, self.iter.size_hint().1) } - fn fold<Acc, Fold>(self, init: Acc, mut fold_f: Fold) -> Acc + fn fold<Acc, Fold>(self, init: Acc, fold_f: Fold) -> Acc where Fold: FnMut(Acc, Self::Item) -> Acc, { let mut f = self.f; - self.iter.fold(init, move |acc, v| fold_f(acc, v.map(&mut f))) + self.iter.filter_map(|v| { + transpose_result(v.map(&mut f)) + }).fold(init, fold_f) } fn collect<C>(self) -> C where C: FromIterator<Self::Item> { let mut f = self.f; - self.iter.map(move |v| v.map(&mut f)).collect() + self.iter.filter_map(|v| { + transpose_result(v.map(&mut f)) + }).collect() } } diff --git a/src/adaptors/multi_product.rs b/src/adaptors/multi_product.rs index 4a31713..6938014 100644 --- a/src/adaptors/multi_product.rs +++ b/src/adaptors/multi_product.rs @@ -1,8 +1,10 @@ -#![cfg(feature = "use_std")] +#![cfg(feature = "use_alloc")] use crate::size_hint; use crate::Itertools; +use alloc::vec::Vec; + #[derive(Clone)] /// An iterator adaptor that iterates over the cartesian product of /// multiple iterators of type `I`. @@ -161,7 +163,7 @@ impl<I> Iterator for MultiProduct<I> } fn count(self) -> usize { - if self.0.len() == 0 { + if self.0.is_empty() { return 0; } @@ -183,7 +185,7 @@ impl<I> Iterator for MultiProduct<I> fn size_hint(&self) -> (usize, Option<usize>) { // Not ExactSizeIterator because size may be larger than usize - if self.0.len() == 0 { + if self.0.is_empty() { return (0, Some(0)); } diff --git a/src/combinations.rs b/src/combinations.rs index 8759518..e6ba4ac 100644 --- a/src/combinations.rs +++ b/src/combinations.rs @@ -1,6 +1,7 @@ use std::fmt; use super::lazy_buffer::LazyBuffer; +use alloc::vec::Vec; /// An iterator to iterate through all the `k`-length combinations in an iterator. /// @@ -30,13 +31,8 @@ impl<I> fmt::Debug for Combinations<I> pub fn combinations<I>(iter: I, k: usize) -> Combinations<I> where I: Iterator { - let mut pool: LazyBuffer<I> = LazyBuffer::new(iter); - - for _ in 0..k { - if !pool.get_next() { - break; - } - } + let mut pool = LazyBuffer::new(iter); + pool.prefill(k); Combinations { indices: (0..k).collect(), @@ -45,6 +41,45 @@ pub fn combinations<I>(iter: I, k: usize) -> Combinations<I> } } +impl<I: Iterator> Combinations<I> { + /// Returns the length of a combination produced by this iterator. + #[inline] + 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 + #[inline] + pub fn n(&self) -> usize { self.pool.len() } + + /// Returns a reference to the source iterator. + #[inline] + pub(crate) fn src(&self) -> &I { &self.pool.it } + + /// Resets this `Combinations` back to an initial state for combinations of length + /// `k` over the same pool data source. If `k` is larger than the current length + /// of the data pool an attempt is made to prefill the pool so that it holds `k` + /// elements. + pub(crate) fn reset(&mut self, k: usize) { + self.first = true; + + if k < self.indices.len() { + self.indices.truncate(k); + for i in 0..k { + self.indices[i] = i; + } + + } else { + for i in 0..self.indices.len() { + self.indices[i] = i; + } + self.indices.extend(self.indices.len()..k); + self.pool.prefill(k); + } + } +} + impl<I> Iterator for Combinations<I> where I: Iterator, I::Item: Clone @@ -52,11 +87,11 @@ impl<I> Iterator for Combinations<I> type Item = Vec<I::Item>; fn next(&mut self) -> Option<Self::Item> { if self.first { - if self.pool.is_done() { + if self.k() > self.n() { return None; } self.first = false; - } else if self.indices.len() == 0 { + } else if self.indices.is_empty() { return None; } else { // Scan from the end, looking for an index to increment diff --git a/src/combinations_with_replacement.rs b/src/combinations_with_replacement.rs index d511545..7e7a802 100644 --- a/src/combinations_with_replacement.rs +++ b/src/combinations_with_replacement.rs @@ -1,3 +1,4 @@ +use alloc::vec::Vec; use std::fmt; use super::lazy_buffer::LazyBuffer; @@ -11,10 +12,7 @@ where I: Iterator, I::Item: Clone, { - k: usize, indices: Vec<usize>, - // The current known max index value. This increases as pool grows. - max_index: usize, pool: LazyBuffer<I>, first: bool, } @@ -24,7 +22,7 @@ where I: Iterator + fmt::Debug, I::Item: fmt::Debug + Clone, { - debug_fmt_fields!(Combinations, k, indices, max_index, pool, first); + debug_fmt_fields!(Combinations, indices, pool, first); } impl<I> CombinationsWithReplacement<I> @@ -44,13 +42,11 @@ where I: Iterator, I::Item: Clone, { - let indices: Vec<usize> = vec![0; k]; + let indices: Vec<usize> = alloc::vec![0; k]; let pool: LazyBuffer<I> = LazyBuffer::new(iter); CombinationsWithReplacement { - k, indices, - max_index: 0, pool, first: true, } @@ -66,7 +62,7 @@ where // If this is the first iteration, return early if self.first { // In empty edge cases, stop iterating immediately - return if self.k != 0 && !self.pool.get_next() { + return if self.indices.len() != 0 && !self.pool.get_next() { None // Otherwise, yield the initial state } else { @@ -77,14 +73,12 @@ where // Check if we need to consume more from the iterator // This will run while we increment our first index digit - if self.pool.get_next() { - self.max_index = self.pool.len() - 1; - } + self.pool.get_next(); // Work out where we need to update our indices let mut increment: Option<(usize, usize)> = None; for (i, indices_int) in self.indices.iter().enumerate().rev() { - if indices_int < &self.max_index { + if *indices_int < self.pool.len()-1 { increment = Some((i, indices_int + 1)); break; } diff --git a/src/concat_impl.rs b/src/concat_impl.rs index 6048d18..0233d01 100644 --- a/src/concat_impl.rs +++ b/src/concat_impl.rs @@ -18,5 +18,5 @@ pub fn concat<I>(iterable: I) -> I::Item where I: IntoIterator, I::Item: Extend<<<I as IntoIterator>::Item as IntoIterator>::Item> + IntoIterator + Default { - iterable.into_iter().fold1(|mut a, b| { a.extend(b); a }).unwrap_or_else(|| <_>::default()) + iterable.into_iter().fold1(|mut a, b| { a.extend(b); a }).unwrap_or_else(<_>::default) } diff --git a/src/cons_tuples_impl.rs b/src/cons_tuples_impl.rs index 3cdfe0d..ae0f48f 100644 --- a/src/cons_tuples_impl.rs +++ b/src/cons_tuples_impl.rs @@ -35,7 +35,7 @@ macro_rules! impl_cons_iter( ); ); -impl_cons_iter!(A, B, C, D, E, F, G, H,); +impl_cons_iter!(A, B, C, D, E, F, G, H, I, J, K, L,); /// An iterator that maps an iterator of tuples like /// `((A, B), C)` to an iterator of `(A, B, C)`. @@ -57,8 +57,8 @@ impl<I, J> Clone for ConsTuples<I, J> /// Create an iterator that maps for example iterators of /// `((A, B), C)` to `(A, B, C)`. -pub fn cons_tuples<I, J>(iterable: I) -> ConsTuples<I, J> - where I: Iterator<Item=J> +pub fn cons_tuples<I, J>(iterable: I) -> ConsTuples<I::IntoIter, J> + where I: IntoIterator<Item=J> { ConsTuples { iter: iterable.into_iter() } } diff --git a/src/exactly_one_err.rs b/src/exactly_one_err.rs index e4925ff..63485c9 100644 --- a/src/exactly_one_err.rs +++ b/src/exactly_one_err.rs @@ -1,5 +1,11 @@ +#[cfg(feature = "use_std")] +use std::error::Error; +use std::fmt::{Debug, Display, Formatter, Result as FmtResult}; + use std::iter::ExactSizeIterator; +use either::Either; + use crate::size_hint; /// Iterator returned for the error case of `IterTools::exactly_one()` @@ -10,12 +16,12 @@ use crate::size_hint; /// /// This is very similar to PutBackN except this iterator only supports 0-2 elements and does not /// use a `Vec`. -#[derive(Debug, Clone)] +#[derive(Clone)] pub struct ExactlyOneError<I> where I: Iterator, { - first_two: (Option<I::Item>, Option<I::Item>), + first_two: Option<Either<[I::Item; 2], I::Item>>, inner: I, } @@ -24,9 +30,17 @@ where I: Iterator, { /// Creates a new `ExactlyOneErr` iterator. - pub(crate) fn new(first_two: (Option<I::Item>, Option<I::Item>), inner: I) -> Self { + pub(crate) fn new(first_two: Option<Either<[I::Item; 2], I::Item>>, inner: I) -> Self { Self { first_two, inner } } + + fn additional_len(&self) -> usize { + match self.first_two { + Some(Either::Left(_)) => 2, + Some(Either::Right(_)) => 1, + None => 0, + } + } } impl<I> Iterator for ExactlyOneError<I> @@ -36,23 +50,61 @@ where type Item = I::Item; fn next(&mut self) -> Option<Self::Item> { - self.first_two - .0 - .take() - .or_else(|| self.first_two.1.take()) - .or_else(|| self.inner.next()) + match self.first_two.take() { + Some(Either::Left([first, second])) => { + self.first_two = Some(Either::Right(second)); + Some(first) + }, + Some(Either::Right(second)) => { + Some(second) + } + None => { + self.inner.next() + } + } } fn size_hint(&self) -> (usize, Option<usize>) { - let mut additional_len = 0; - if self.first_two.0.is_some() { - additional_len += 1; + size_hint::add_scalar(self.inner.size_hint(), self.additional_len()) + } +} + + +impl<I> ExactSizeIterator for ExactlyOneError<I> where I: ExactSizeIterator {} + +impl<I> Display for ExactlyOneError<I> + where I: Iterator, +{ + fn fmt(&self, f: &mut Formatter) -> FmtResult { + let additional = self.additional_len(); + if additional > 0 { + write!(f, "got at least 2 elements when exactly one was expected") + } else { + write!(f, "got zero elements when exactly one was expected") } - if self.first_two.1.is_some() { - additional_len += 1; + } +} + +impl<I> Debug for ExactlyOneError<I> + where I: Iterator + Debug, + I::Item: Debug, +{ + fn fmt(&self, f: &mut Formatter) -> FmtResult { + match &self.first_two { + Some(Either::Left([first, second])) => { + write!(f, "ExactlyOneError[First: {:?}, Second: {:?}, RemainingIter: {:?}]", first, second, self.inner) + }, + Some(Either::Right(second)) => { + write!(f, "ExactlyOneError[Second: {:?}, RemainingIter: {:?}]", second, self.inner) + } + None => { + write!(f, "ExactlyOneError[RemainingIter: {:?}]", self.inner) + } } - size_hint::add_scalar(self.inner.size_hint(), additional_len) } } -impl<I> ExactSizeIterator for ExactlyOneError<I> where I: ExactSizeIterator {} +#[cfg(feature = "use_std")] +impl<I> Error for ExactlyOneError<I> where I: Iterator + Debug, I::Item: Debug, {} + + diff --git a/src/format.rs b/src/format.rs index f72ed39..ec2dc7a 100644 --- a/src/format.rs +++ b/src/format.rs @@ -28,7 +28,7 @@ pub struct Format<'a, I> { inner: RefCell<Option<I>>, } -pub fn new_format<'a, I, F>(iter: I, separator: &'a str, f: F) -> FormatWith<'a, I, F> +pub fn new_format<I, F>(iter: I, separator: &str, f: F) -> FormatWith<'_, I, F> where I: Iterator, F: FnMut(I::Item, &mut dyn FnMut(&dyn fmt::Display) -> fmt::Result) -> fmt::Result { @@ -38,7 +38,7 @@ pub fn new_format<'a, I, F>(iter: I, separator: &'a str, f: F) -> FormatWith<'a, } } -pub fn new_format_default<'a, I>(iter: I, separator: &'a str) -> Format<'a, I> +pub fn new_format_default<I>(iter: I, separator: &str) -> Format<'_, I> where I: Iterator, { Format { @@ -59,13 +59,12 @@ impl<'a, I, F> fmt::Display for FormatWith<'a, I, F> if let Some(fst) = iter.next() { format(fst, &mut |disp: &dyn fmt::Display| disp.fmt(f))?; - for elt in iter { - if self.sep.len() > 0 { - + iter.try_for_each(|elt| { + if !self.sep.is_empty() { f.write_str(self.sep)?; } - format(elt, &mut |disp: &dyn fmt::Display| disp.fmt(f))?; - } + format(elt, &mut |disp: &dyn fmt::Display| disp.fmt(f)) + })?; } Ok(()) } @@ -84,12 +83,12 @@ impl<'a, I> Format<'a, I> if let Some(fst) = iter.next() { cb(&fst, f)?; - for elt in iter { - if self.sep.len() > 0 { + iter.try_for_each(|elt| { + if !self.sep.is_empty() { f.write_str(self.sep)?; } - cb(&elt, f)?; - } + cb(&elt, f) + })?; } Ok(()) } diff --git a/src/free.rs b/src/free.rs index a6bc1bd..bfc5ab4 100644 --- a/src/free.rs +++ b/src/free.rs @@ -3,13 +3,18 @@ //! 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_std")] +#[cfg(feature = "use_alloc")] use std::fmt::Display; use std::iter::{self, Zip}; -#[cfg(feature = "use_std")] -type VecIntoIter<T> = ::std::vec::IntoIter<T>; +#[cfg(feature = "use_alloc")] +type VecIntoIter<T> = alloc::vec::IntoIter<T>; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] +use alloc::{ + string::String, +}; + +#[cfg(feature = "use_alloc")] use crate::Itertools; pub use crate::adaptors::{ @@ -17,15 +22,17 @@ pub use crate::adaptors::{ merge, put_back, }; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] pub use crate::put_back_n_impl::put_back_n; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] pub use crate::multipeek_impl::multipeek; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] +pub use crate::peek_nth::peek_nth; +#[cfg(feature = "use_alloc")] pub use crate::kmerge_impl::kmerge; pub use crate::zip_eq_impl::zip_eq; pub use crate::merge_join::merge_join_by; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] pub use crate::rciter_impl::rciter; /// Iterate `iterable` with a running index. @@ -206,7 +213,7 @@ pub fn min<I>(iterable: I) -> Option<I::Item> /// /// assert_eq!(join(&[1, 2, 3], ", "), "1, 2, 3"); /// ``` -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] pub fn join<I>(iterable: I, sep: &str) -> String where I: IntoIterator, I::Item: Display @@ -226,7 +233,7 @@ pub fn join<I>(iterable: I, sep: &str) -> String /// /// assert_equal(sorted("rust".chars()), "rstu".chars()); /// ``` -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] pub fn sorted<I>(iterable: I) -> VecIntoIter<I::Item> where I: IntoIterator, I::Item: Ord diff --git a/src/group_map.rs b/src/group_map.rs index be9f842..4231de0 100644 --- a/src/group_map.rs +++ b/src/group_map.rs @@ -14,9 +14,19 @@ pub fn into_group_map<I, K, V>(iter: I) -> HashMap<K, Vec<V>> { let mut lookup = HashMap::new(); - for (key, val) in iter { - lookup.entry(key).or_insert(Vec::new()).push(val); - } + iter.for_each(|(key, val)| { + lookup.entry(key).or_insert_with(Vec::new).push(val); + }); lookup -}
\ No newline at end of file +} + +pub fn into_group_map_by<I, K, V>(iter: I, f: impl Fn(&V) -> K) -> HashMap<K, Vec<V>> + where + I: Iterator<Item=V>, + K: Hash + Eq, +{ + into_group_map( + iter.map(|v| (f(&v), v)) + ) +} diff --git a/src/groupbylazy.rs b/src/groupbylazy.rs index bf6e3c7..5d4a0c9 100644 --- a/src/groupbylazy.rs +++ b/src/groupbylazy.rs @@ -1,5 +1,5 @@ use std::cell::{Cell, RefCell}; -use std::vec; +use alloc::vec::{self, Vec}; /// A trait to unify FnMut for GroupBy with the chunk key in IntoChunks trait KeyFunction<A> { diff --git a/src/grouping_map.rs b/src/grouping_map.rs new file mode 100644 index 0000000..5232f5d --- /dev/null +++ b/src/grouping_map.rs @@ -0,0 +1,536 @@ +#![cfg(feature = "use_std")] + +use crate::MinMaxResult; +use std::collections::HashMap; +use std::cmp::Ordering; +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) +#[derive(Clone, Debug)] +pub struct MapForGrouping<I, F>(I, F); + +impl<I, F> MapForGrouping<I, F> { + pub(crate) fn new(iter: I, key_mapper: F) -> Self { + Self(iter, key_mapper) + } +} + +impl<K, V, I, F> Iterator for MapForGrouping<I, F> + where I: Iterator<Item = V>, + K: Hash + Eq, + F: FnMut(&V) -> K, +{ + type Item = (K, V); + fn next(&mut self) -> Option<Self::Item> { + self.0.next().map(|val| ((self.1)(&val), val)) + } +} + +/// Creates a new `GroupingMap` from `iter` +pub fn new<I, K, V>(iter: I) -> GroupingMap<I> + where I: Iterator<Item = (K, V)>, + K: Hash + Eq, +{ + GroupingMap { iter } +} + +/// `GroupingMapBy` is an intermediate struct for efficient group-and-fold operations. +/// +/// See [`GroupingMap`](./struct.GroupingMap.html) for more informations. +#[must_use = "GroupingMapBy is lazy and do nothing unless consumed"] +pub type GroupingMapBy<I, F> = GroupingMap<MapForGrouping<I, F>>; + +/// `GroupingMap` is an intermediate struct for efficient group-and-fold operations. +/// It groups elements by their key and at the same time fold each group +/// using some aggregating operation. +/// +/// No method on this struct performs temporary allocations. +#[derive(Clone, Debug)] +#[must_use = "GroupingMap is lazy and do nothing unless consumed"] +pub struct GroupingMap<I> { + iter: I, +} + +impl<I, K, V> GroupingMap<I> + where I: Iterator<Item = (K, V)>, + K: Hash + Eq, +{ + /// This is the generic way to perform any operation on a `GroupingMap`. + /// It's suggested to use this method only to implement custom operations + /// when the already provided ones are not enough. + /// + /// Groups elements from the `GroupingMap` source by key and applies `operation` to the elements + /// of each group sequentially, passing the previously accumulated value, a reference to the key + /// and the current element as arguments, and stores the results in an `HashMap`. + /// + /// The `operation` function is invoked on each element with the following parameters: + /// - the current value of the accumulator of the group if there is currently one; + /// - a reference to the key of the group this element belongs to; + /// - the element from the source being aggregated; + /// + /// If `operation` returns `Some(element)` then the accumulator is updated with `element`, + /// otherwise the previous accumulation is discarded. + /// + /// Return a `HashMap` associating the key of each group with the result of aggregation of + /// that group's elements. If the aggregation of the last element of a group discards the + /// accumulator then there won't be an entry associated to that group's key. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let data = vec![2, 8, 5, 7, 9, 0, 4, 10]; + /// let lookup = data.into_iter() + /// .into_grouping_map_by(|&n| n % 4) + /// .aggregate(|acc, _key, val| { + /// if val == 0 || val == 10 { + /// None + /// } else { + /// Some(acc.unwrap_or(0) + val) + /// } + /// }); + /// + /// assert_eq!(lookup[&0], 4); // 0 resets the accumulator so only 4 is summed + /// assert_eq!(lookup[&1], 5 + 9); + /// assert_eq!(lookup.get(&2), None); // 10 resets the accumulator and nothing is summed afterward + /// assert_eq!(lookup[&3], 7); + /// assert_eq!(lookup.len(), 3); // The final keys are only 0, 1 and 2 + /// ``` + pub fn aggregate<FO, R>(self, mut operation: FO) -> HashMap<K, R> + where FO: FnMut(Option<R>, &K, V) -> Option<R>, + { + let mut destination_map = HashMap::new(); + + for (key, val) in self.iter { + let acc = destination_map.remove(&key); + if let Some(op_res) = operation(acc, &key, val) { + destination_map.insert(key, op_res); + } + } + + destination_map + } + + /// Groups elements from the `GroupingMap` source by key and applies `operation` to the elements + /// of each group sequentially, passing the previously accumulated value, a reference to the key + /// and the current element as arguments, and stores the results in a new map. + /// + /// `init` is the value from which will be cloned the initial value of each accumulator. + /// + /// `operation` is a function that is invoked on each element with the following parameters: + /// - the current value of the accumulator of the group; + /// - a reference to the key of the group this element belongs to; + /// - the element from the source being accumulated. + /// + /// Return a `HashMap` associating the key of each group with the result of folding that group's elements. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let lookup = (1..=7) + /// .into_grouping_map_by(|&n| n % 3) + /// .fold(0, |acc, _key, val| acc + val); + /// + /// assert_eq!(lookup[&0], 3 + 6); + /// assert_eq!(lookup[&1], 1 + 4 + 7); + /// assert_eq!(lookup[&2], 2 + 5); + /// assert_eq!(lookup.len(), 3); + /// ``` + pub fn fold<FO, R>(self, init: R, mut operation: FO) -> HashMap<K, R> + where R: Clone, + FO: FnMut(R, &K, V) -> R, + { + self.aggregate(|acc, key, val| { + let acc = acc.unwrap_or_else(|| init.clone()); + Some(operation(acc, key, val)) + }) + } + + /// Groups elements from the `GroupingMap` source by key and applies `operation` to the elements + /// of each group sequentially, passing the previously accumulated value, a reference to the key + /// and the current element as arguments, and stores the results in a new map. + /// + /// This is similar to [`fold`] but the initial value of the accumulator is the first element of the group. + /// + /// `operation` is a function that is invoked on each element with the following parameters: + /// - the current value of the accumulator of the group; + /// - a reference to the key of the group this element belongs to; + /// - the element from the source being accumulated. + /// + /// Return a `HashMap` associating the key of each group with the result of folding that group's elements. + /// + /// [`fold`]: #tymethod.fold + /// + /// ``` + /// use itertools::Itertools; + /// + /// let lookup = (1..=7) + /// .into_grouping_map_by(|&n| n % 3) + /// .fold_first(|acc, _key, val| acc + val); + /// + /// assert_eq!(lookup[&0], 3 + 6); + /// assert_eq!(lookup[&1], 1 + 4 + 7); + /// assert_eq!(lookup[&2], 2 + 5); + /// assert_eq!(lookup.len(), 3); + /// ``` + pub fn fold_first<FO>(self, mut operation: FO) -> HashMap<K, V> + where FO: FnMut(V, &K, V) -> V, + { + self.aggregate(|acc, key, val| { + Some(match acc { + Some(acc) => operation(acc, key, val), + None => val, + }) + }) + } + + /// Groups elements from the `GroupingMap` source by key and collects the elements of each group in + /// an instance of `C`. The iteration order is preserved when inserting elements. + /// + /// Return a `HashMap` associating the key of each group with the collection containing that group's elements. + /// + /// ``` + /// use itertools::Itertools; + /// use std::collections::HashSet; + /// + /// let lookup = vec![0, 1, 2, 3, 4, 5, 6, 2, 3, 6].into_iter() + /// .into_grouping_map_by(|&n| n % 3) + /// .collect::<HashSet<_>>(); + /// + /// assert_eq!(lookup[&0], vec![0, 3, 6].into_iter().collect::<HashSet<_>>()); + /// assert_eq!(lookup[&1], vec![1, 4].into_iter().collect::<HashSet<_>>()); + /// assert_eq!(lookup[&2], vec![2, 5].into_iter().collect::<HashSet<_>>()); + /// assert_eq!(lookup.len(), 3); + /// ``` + pub fn collect<C>(self) -> HashMap<K, C> + where C: Default + Extend<V>, + { + let mut destination_map = HashMap::new(); + + for (key, val) in self.iter { + destination_map.entry(key).or_insert_with(C::default).extend(Some(val)); + } + + destination_map + } + + /// Groups elements from the `GroupingMap` source by key and finds the maximum of each group. + /// + /// If several elements are equally maximum, the last element is picked. + /// + /// Returns a `HashMap` associating the key of each group with the maximum of that group's elements. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter() + /// .into_grouping_map_by(|&n| n % 3) + /// .max(); + /// + /// assert_eq!(lookup[&0], 12); + /// assert_eq!(lookup[&1], 7); + /// assert_eq!(lookup[&2], 8); + /// assert_eq!(lookup.len(), 3); + /// ``` + pub fn max(self) -> HashMap<K, V> + where V: Ord, + { + self.max_by(|_, v1, v2| V::cmp(v1, v2)) + } + + /// Groups elements from the `GroupingMap` source by key and finds the maximum of each group + /// with respect to the specified comparison function. + /// + /// If several elements are equally maximum, the last element is picked. + /// + /// Returns a `HashMap` associating the key of each group with the maximum of that group's elements. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter() + /// .into_grouping_map_by(|&n| n % 3) + /// .max_by(|_key, x, y| y.cmp(x)); + /// + /// assert_eq!(lookup[&0], 3); + /// assert_eq!(lookup[&1], 1); + /// assert_eq!(lookup[&2], 5); + /// assert_eq!(lookup.len(), 3); + /// ``` + pub fn max_by<F>(self, mut compare: F) -> HashMap<K, V> + where F: FnMut(&K, &V, &V) -> Ordering, + { + self.fold_first(|acc, key, val| match compare(key, &acc, &val) { + Ordering::Less | Ordering::Equal => val, + Ordering::Greater => acc + }) + } + + /// Groups elements from the `GroupingMap` source by key and finds the element of each group + /// that gives the maximum from the specified function. + /// + /// If several elements are equally maximum, the last element is picked. + /// + /// Returns a `HashMap` associating the key of each group with the maximum of that group's elements. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter() + /// .into_grouping_map_by(|&n| n % 3) + /// .max_by_key(|_key, &val| val % 4); + /// + /// assert_eq!(lookup[&0], 3); + /// assert_eq!(lookup[&1], 7); + /// assert_eq!(lookup[&2], 5); + /// assert_eq!(lookup.len(), 3); + /// ``` + pub fn max_by_key<F, CK>(self, mut f: F) -> HashMap<K, V> + where F: FnMut(&K, &V) -> CK, + CK: Ord, + { + self.max_by(|key, v1, v2| f(key, &v1).cmp(&f(key, &v2))) + } + + /// Groups elements from the `GroupingMap` source by key and finds the minimum of each group. + /// + /// If several elements are equally minimum, the first element is picked. + /// + /// Returns a `HashMap` associating the key of each group with the minimum of that group's elements. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter() + /// .into_grouping_map_by(|&n| n % 3) + /// .min(); + /// + /// assert_eq!(lookup[&0], 3); + /// assert_eq!(lookup[&1], 1); + /// assert_eq!(lookup[&2], 5); + /// assert_eq!(lookup.len(), 3); + /// ``` + pub fn min(self) -> HashMap<K, V> + where V: Ord, + { + self.min_by(|_, v1, v2| V::cmp(v1, v2)) + } + + /// Groups elements from the `GroupingMap` source by key and finds the minimum of each group + /// with respect to the specified comparison function. + /// + /// If several elements are equally minimum, the first element is picked. + /// + /// Returns a `HashMap` associating the key of each group with the minimum of that group's elements. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter() + /// .into_grouping_map_by(|&n| n % 3) + /// .min_by(|_key, x, y| y.cmp(x)); + /// + /// assert_eq!(lookup[&0], 12); + /// assert_eq!(lookup[&1], 7); + /// assert_eq!(lookup[&2], 8); + /// assert_eq!(lookup.len(), 3); + /// ``` + pub fn min_by<F>(self, mut compare: F) -> HashMap<K, V> + where F: FnMut(&K, &V, &V) -> Ordering, + { + self.fold_first(|acc, key, val| match compare(key, &acc, &val) { + Ordering::Less | Ordering::Equal => acc, + Ordering::Greater => val + }) + } + + /// Groups elements from the `GroupingMap` source by key and finds the element of each group + /// that gives the minimum from the specified function. + /// + /// If several elements are equally minimum, the first element is picked. + /// + /// Returns a `HashMap` associating the key of each group with the minimum of that group's elements. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter() + /// .into_grouping_map_by(|&n| n % 3) + /// .min_by_key(|_key, &val| val % 4); + /// + /// assert_eq!(lookup[&0], 12); + /// assert_eq!(lookup[&1], 4); + /// assert_eq!(lookup[&2], 8); + /// assert_eq!(lookup.len(), 3); + /// ``` + pub fn min_by_key<F, CK>(self, mut f: F) -> HashMap<K, V> + where F: FnMut(&K, &V) -> CK, + CK: Ord, + { + self.min_by(|key, v1, v2| f(key, &v1).cmp(&f(key, &v2))) + } + + /// Groups elements from the `GroupingMap` source by key and find the maximum and minimum of + /// each group. + /// + /// 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. + /// + /// Differences from the non grouping version: + /// - It never produces a `MinMaxResult::NoElements` + /// - It doesn't have any speedup + /// + /// Returns a `HashMap` associating the key of each group with the minimum and maximum of that group's elements. + /// + /// ``` + /// use itertools::Itertools; + /// use itertools::MinMaxResult::{OneElement, MinMax}; + /// + /// let lookup = vec![1, 3, 4, 5, 7, 9, 12].into_iter() + /// .into_grouping_map_by(|&n| n % 3) + /// .minmax(); + /// + /// assert_eq!(lookup[&0], MinMax(3, 12)); + /// assert_eq!(lookup[&1], MinMax(1, 7)); + /// assert_eq!(lookup[&2], OneElement(5)); + /// assert_eq!(lookup.len(), 3); + /// ``` + pub fn minmax(self) -> HashMap<K, MinMaxResult<V>> + where V: Ord, + { + self.minmax_by(|_, v1, v2| V::cmp(v1, v2)) + } + + /// Groups elements from the `GroupingMap` source by key and find the maximum and minimum of + /// each group with respect to the specified comparison function. + /// + /// If several elements are equally maximum, the last element is picked. + /// If several elements are equally minimum, the first element is picked. + /// + /// It has the same differences from the non-grouping version as `minmax`. + /// + /// Returns a `HashMap` associating the key of each group with the minimum and maximum of that group's elements. + /// + /// ``` + /// use itertools::Itertools; + /// use itertools::MinMaxResult::{OneElement, MinMax}; + /// + /// let lookup = vec![1, 3, 4, 5, 7, 9, 12].into_iter() + /// .into_grouping_map_by(|&n| n % 3) + /// .minmax_by(|_key, x, y| y.cmp(x)); + /// + /// assert_eq!(lookup[&0], MinMax(12, 3)); + /// assert_eq!(lookup[&1], MinMax(7, 1)); + /// assert_eq!(lookup[&2], OneElement(5)); + /// assert_eq!(lookup.len(), 3); + /// ``` + pub fn minmax_by<F>(self, mut compare: F) -> HashMap<K, MinMaxResult<V>> + where F: FnMut(&K, &V, &V) -> Ordering, + { + self.aggregate(|acc, key, val| { + Some(match acc { + Some(MinMaxResult::OneElement(e)) => { + if compare(key, &val, &e) == Ordering::Less { + MinMaxResult::MinMax(val, e) + } else { + MinMaxResult::MinMax(e, val) + } + } + Some(MinMaxResult::MinMax(min, max)) => { + if compare(key, &val, &min) == Ordering::Less { + MinMaxResult::MinMax(val, max) + } else if compare(key, &val, &max) != Ordering::Less { + MinMaxResult::MinMax(min, val) + } else { + MinMaxResult::MinMax(min, max) + } + } + None => MinMaxResult::OneElement(val), + Some(MinMaxResult::NoElements) => unreachable!(), + }) + }) + } + + /// Groups elements from the `GroupingMap` source by key and find the elements of each group + /// that gives the minimum and maximum from the specified function. + /// + /// If several elements are equally maximum, the last element is picked. + /// If several elements are equally minimum, the first element is picked. + /// + /// It has the same differences from the non-grouping version as `minmax`. + /// + /// Returns a `HashMap` associating the key of each group with the minimum and maximum of that group's elements. + /// + /// ``` + /// use itertools::Itertools; + /// use itertools::MinMaxResult::{OneElement, MinMax}; + /// + /// let lookup = vec![1, 3, 4, 5, 7, 9, 12].into_iter() + /// .into_grouping_map_by(|&n| n % 3) + /// .minmax_by_key(|_key, &val| val % 4); + /// + /// assert_eq!(lookup[&0], MinMax(12, 3)); + /// assert_eq!(lookup[&1], MinMax(4, 7)); + /// assert_eq!(lookup[&2], OneElement(5)); + /// assert_eq!(lookup.len(), 3); + /// ``` + pub fn minmax_by_key<F, CK>(self, mut f: F) -> HashMap<K, MinMaxResult<V>> + where F: FnMut(&K, &V) -> CK, + CK: Ord, + { + self.minmax_by(|key, v1, v2| f(key, &v1).cmp(&f(key, &v2))) + } + + /// Groups elements from the `GroupingMap` source by key and sums them. + /// + /// This is just a shorthand for `self.fold_first(|acc, _, val| acc + val)`. + /// It is more limited than `Iterator::sum` since it doesn't use the `Sum` trait. + /// + /// Returns a `HashMap` associating the key of each group with the sum of that group's elements. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter() + /// .into_grouping_map_by(|&n| n % 3) + /// .sum(); + /// + /// assert_eq!(lookup[&0], 3 + 9 + 12); + /// assert_eq!(lookup[&1], 1 + 4 + 7); + /// assert_eq!(lookup[&2], 5 + 8); + /// assert_eq!(lookup.len(), 3); + /// ``` + pub fn sum(self) -> HashMap<K, V> + where V: Add<V, Output = V> + { + self.fold_first(|acc, _, val| acc + val) + } + + /// Groups elements from the `GroupingMap` source by key and multiply them. + /// + /// This is just a shorthand for `self.fold_first(|acc, _, val| acc * val)`. + /// It is more limited than `Iterator::product` since it doesn't use the `Product` trait. + /// + /// Returns a `HashMap` associating the key of each group with the product of that group's elements. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter() + /// .into_grouping_map_by(|&n| n % 3) + /// .product(); + /// + /// assert_eq!(lookup[&0], 3 * 9 * 12); + /// assert_eq!(lookup[&1], 1 * 4 * 7); + /// assert_eq!(lookup[&2], 5 * 8); + /// assert_eq!(lookup.len(), 3); + /// ``` + pub fn product(self) -> HashMap<K, V> + where V: Mul<V, Output = V>, + { + self.fold_first(|acc, _, val| acc * val) + } +} diff --git a/src/intersperse.rs b/src/intersperse.rs index 0579299..a0d79b0 100644 --- a/src/intersperse.rs +++ b/src/intersperse.rs @@ -1,7 +1,19 @@ use std::iter::Fuse; use super::size_hint; -#[derive(Clone)] +pub trait IntersperseElement<Item> { + fn generate(&mut self) -> Item; +} + +#[derive(Debug, Clone)] +pub struct IntersperseElementSimple<Item>(Item); + +impl<Item: Clone> IntersperseElement<Item> for IntersperseElementSimple<Item> { + fn generate(&mut self) -> Item { + self.0.clone() + } +} + /// An iterator adaptor to insert a particular value /// between each element of the adapted iterator. /// @@ -10,41 +22,64 @@ use super::size_hint; /// This iterator is *fused*. /// /// See [`.intersperse()`](../trait.Itertools.html#method.intersperse) for more information. +pub type Intersperse<I> = IntersperseWith<I, IntersperseElementSimple<<I as Iterator>::Item>>; + +/// Create a new Intersperse iterator +pub fn intersperse<I>(iter: I, elt: I::Item) -> Intersperse<I> + where I: Iterator, +{ + intersperse_with(iter, IntersperseElementSimple(elt)) +} + +impl<Item, F: FnMut()->Item> IntersperseElement<Item> for F { + fn generate(&mut self) -> Item { + self() + } +} + +/// An iterator adaptor to insert a particular value created by a function +/// between each element of the adapted iterator. +/// +/// Iterator element type is `I::Item` +/// +/// This iterator is *fused*. +/// +/// See [`.intersperse_with()`](../trait.Itertools.html#method.intersperse_with) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] -#[derive(Debug)] -pub struct Intersperse<I> - where I: Iterator +#[derive(Clone, Debug)] +pub struct IntersperseWith<I, ElemF> + where I: Iterator, { - element: I::Item, + element: ElemF, iter: Fuse<I>, peek: Option<I::Item>, } -/// Create a new Intersperse iterator -pub fn intersperse<I>(iter: I, elt: I::Item) -> Intersperse<I> - where I: Iterator +/// Create a new IntersperseWith iterator +pub fn intersperse_with<I, ElemF>(iter: I, elt: ElemF) -> IntersperseWith<I, ElemF> + where I: Iterator, { let mut iter = iter.fuse(); - Intersperse { + IntersperseWith { peek: iter.next(), iter, element: elt, } } -impl<I> Iterator for Intersperse<I> +impl<I, ElemF> Iterator for IntersperseWith<I, ElemF> where I: Iterator, - I::Item: Clone + ElemF: IntersperseElement<I::Item> { type Item = I::Item; #[inline] - fn next(&mut self) -> Option<I::Item> { + fn next(&mut self) -> Option<Self::Item> { if self.peek.is_some() { self.peek.take() } else { self.peek = self.iter.next(); if self.peek.is_some() { - Some(self.element.clone()) + Some(self.element.generate()) } else { None } @@ -62,16 +97,16 @@ impl<I> Iterator for Intersperse<I> Self: Sized, F: FnMut(B, Self::Item) -> B, { let mut accum = init; - + if let Some(x) = self.peek.take() { accum = f(accum, x); } - let element = &self.element; + let element = &mut self.element; self.iter.fold(accum, |accum, x| { - let accum = f(accum, element.clone()); + let accum = f(accum, element.generate()); let accum = f(accum, x); accum }) diff --git a/src/k_smallest.rs b/src/k_smallest.rs new file mode 100644 index 0000000..d58ec70 --- /dev/null +++ b/src/k_smallest.rs @@ -0,0 +1,20 @@ +use alloc::collections::BinaryHeap; +use core::cmp::Ord; + +pub(crate) fn k_smallest<T: Ord, I: Iterator<Item = T>>(mut iter: I, k: usize) -> BinaryHeap<T> { + if k == 0 { return BinaryHeap::new(); } + + let mut heap = iter.by_ref().take(k).collect::<BinaryHeap<_>>(); + + for i in iter { + 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 + // `PeekMut` sifts-down unconditionally on Rust 1.46.0 and prior. + if *heap.peek().unwrap() > i { + *heap.peek_mut().unwrap() = i; + } + } + + heap +} diff --git a/src/kmerge_impl.rs b/src/kmerge_impl.rs index 8f68aeb..a1b3d8e 100644 --- a/src/kmerge_impl.rs +++ b/src/kmerge_impl.rs @@ -1,6 +1,7 @@ use crate::size_hint; use crate::Itertools; +use alloc::vec::Vec; use std::mem::replace; use std::fmt; diff --git a/src/lazy_buffer.rs b/src/lazy_buffer.rs index 01123d4..fa514ec 100644 --- a/src/lazy_buffer.rs +++ b/src/lazy_buffer.rs @@ -1,4 +1,5 @@ use std::ops::Index; +use alloc::vec::Vec; #[derive(Debug, Clone)] pub struct LazyBuffer<I: Iterator> { @@ -23,10 +24,6 @@ where self.buffer.len() } - pub fn is_done(&self) -> bool { - self.done - } - pub fn get_next(&mut self) -> bool { if self.done { return false; @@ -43,6 +40,17 @@ where } } } + + pub fn prefill(&mut self, len: usize) { + let buffer_len = self.buffer.len(); + + if !self.done && len > buffer_len { + let delta = len - buffer_len; + + self.buffer.extend(self.it.by_ref().take(delta)); + self.done = self.buffer.len() < len; + } + } } impl<I, J> Index<J> for LazyBuffer<I> @@ -50,6 +50,15 @@ #[cfg(not(feature = "use_std"))] extern crate core as std; +#[cfg(feature = "use_alloc")] +extern crate alloc; + +#[cfg(feature = "use_alloc")] +use alloc::{ + string::String, + vec::Vec, +}; + pub use either::Either; #[cfg(feature = "use_std")] @@ -59,11 +68,11 @@ use std::cmp::Ordering; use std::fmt; #[cfg(feature = "use_std")] use std::hash::Hash; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] use std::fmt::Write; -#[cfg(feature = "use_std")] -type VecIntoIter<T> = ::std::vec::IntoIter<T>; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] +type VecIntoIter<T> = alloc::vec::IntoIter<T>; +#[cfg(feature = "use_alloc")] use std::iter::FromIterator; #[macro_use] @@ -78,13 +87,17 @@ pub mod structs { pub use crate::adaptors::{ Dedup, DedupBy, + DedupWithCount, + DedupByWithCount, Interleave, InterleaveShortest, + FilterMapOk, + FilterOk, Product, PutBack, Batching, MapInto, - MapResults, + MapOk, Merge, MergeBy, TakeWhileRef, @@ -95,39 +108,45 @@ pub mod structs { Update, }; #[allow(deprecated)] - pub use crate::adaptors::Step; - #[cfg(feature = "use_std")] + pub use crate::adaptors::{MapResults, Step}; + #[cfg(feature = "use_alloc")] pub use crate::adaptors::MultiProduct; - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] pub use crate::combinations::Combinations; - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] pub use crate::combinations_with_replacement::CombinationsWithReplacement; pub use crate::cons_tuples_impl::ConsTuples; pub use crate::exactly_one_err::ExactlyOneError; pub use crate::format::{Format, FormatWith}; #[cfg(feature = "use_std")] + pub use crate::grouping_map::{GroupingMap, GroupingMapBy}; + #[cfg(feature = "use_alloc")] pub use crate::groupbylazy::{IntoChunks, Chunk, Chunks, GroupBy, Group, Groups}; - pub use crate::intersperse::Intersperse; - #[cfg(feature = "use_std")] + pub use crate::intersperse::{Intersperse, IntersperseWith}; + #[cfg(feature = "use_alloc")] pub use crate::kmerge_impl::{KMerge, KMergeBy}; pub use crate::merge_join::MergeJoinBy; - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] pub use crate::multipeek_impl::MultiPeek; + #[cfg(feature = "use_alloc")] + pub use crate::peek_nth::PeekNth; pub use crate::pad_tail::PadUsing; pub use crate::peeking_take_while::PeekingTakeWhile; - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] pub use crate::permutations::Permutations; pub use crate::process_results_impl::ProcessResults; - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] + pub use crate::powerset::Powerset; + #[cfg(feature = "use_alloc")] pub use crate::put_back_n_impl::PutBackN; - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] pub use crate::rciter_impl::RcIter; pub use crate::repeatn::RepeatN; #[allow(deprecated)] pub use crate::sources::{RepeatCall, Unfold, Iterate}; - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] pub use crate::tee::Tee; - pub use crate::tuple_impl::{TupleBuffer, TupleWindows, Tuples}; + pub use crate::tuple_impl::{TupleBuffer, TupleWindows, CircularTupleWindows, Tuples}; #[cfg(feature = "use_std")] pub use crate::unique_impl::{Unique, UniqueBy}; pub use crate::with_position::WithPosition; @@ -147,7 +166,7 @@ pub use crate::concat_impl::concat; pub use crate::cons_tuples_impl::cons_tuples; pub use crate::diff::diff_with; pub use crate::diff::Diff; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] pub use crate::kmerge_impl::{kmerge_by}; pub use crate::minmax::MinMaxResult; pub use crate::peeking_take_while::PeekingNext; @@ -166,39 +185,47 @@ pub mod free; pub use crate::free::*; mod concat_impl; mod cons_tuples_impl; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] mod combinations; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] mod combinations_with_replacement; mod exactly_one_err; mod diff; mod format; #[cfg(feature = "use_std")] +mod grouping_map; +#[cfg(feature = "use_alloc")] mod group_map; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] mod groupbylazy; mod intersperse; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] +mod k_smallest; +#[cfg(feature = "use_alloc")] mod kmerge_impl; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] mod lazy_buffer; mod merge_join; mod minmax; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] mod multipeek_impl; mod pad_tail; +#[cfg(feature = "use_alloc")] +mod peek_nth; mod peeking_take_while; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] mod permutations; +#[cfg(feature = "use_alloc")] +mod powerset; mod process_results_impl; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] mod put_back_n_impl; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] mod rciter_impl; mod repeatn; mod size_hint; mod sources; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] mod tee; mod tuple_impl; #[cfg(feature = "use_std")] @@ -230,16 +257,16 @@ macro_rules! iproduct { $I ); (@flatten $I:expr, $J:expr, $($K:expr,)*) => ( - iproduct!(@flatten $crate::cons_tuples(iproduct!($I, $J)), $($K,)*) + $crate::iproduct!(@flatten $crate::cons_tuples($crate::iproduct!($I, $J)), $($K,)*) ); ($I:expr) => ( $crate::__std_iter::IntoIterator::into_iter($I) ); ($I:expr, $J:expr) => ( - $crate::Itertools::cartesian_product(iproduct!($I), iproduct!($J)) + $crate::Itertools::cartesian_product($crate::iproduct!($I), $crate::iproduct!($J)) ); ($I:expr, $J:expr, $($K:expr),+) => ( - iproduct!(@flatten iproduct!($I, $J), $($K,)+) + $crate::iproduct!(@flatten $crate::iproduct!($I, $J), $($K,)+) ); } @@ -290,7 +317,7 @@ macro_rules! izip { // The "b" identifier is a different identifier on each recursion level thanks to hygiene. ( @closure $p:pat => ( $($tup:tt)* ) , $_iter:expr $( , $tail:expr )* ) => { - izip!(@closure ($p, b) => ( $($tup)*, b ) $( , $tail )*) + $crate::izip!(@closure ($p, b) => ( $($tup)*, b ) $( , $tail )*) }; // unary @@ -300,18 +327,18 @@ macro_rules! izip { // binary ($first:expr, $second:expr $(,)*) => { - izip!($first) + $crate::izip!($first) .zip($second) }; // n-ary where n > 2 ( $first:expr $( , $rest:expr )* $(,)* ) => { - izip!($first) + $crate::izip!($first) $( .zip($rest) )* .map( - izip!(@closure a => (a) $( , $rest )*) + $crate::izip!(@closure a => (a) $( , $rest )*) ) }; } @@ -390,6 +417,27 @@ pub trait Itertools : Iterator { intersperse::intersperse(self, element) } + /// An iterator adaptor to insert a particular value created by a function + /// between each element of the adapted iterator. + /// + /// Iterator element type is `Self::Item`. + /// + /// This iterator is *fused*. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let mut i = 10; + /// itertools::assert_equal((0..3).intersperse_with(|| { i -= 1; i }), vec![0, 9, 1, 8, 2]); + /// assert_eq!(i, 8); + /// ``` + fn intersperse_with<F>(self, element: F) -> IntersperseWith<Self, F> + where Self: Sized, + F: FnMut() -> Self::Item + { + intersperse::intersperse_with(self, element) + } + /// Create an iterator which iterates over both this and the specified /// iterator simultaneously, yielding pairs of two optional elements. /// @@ -501,7 +549,7 @@ pub trait Itertools : Iterator { /// } /// assert_eq!(data_grouped, vec![(true, vec![1, 3]), (false, vec![-2, -2]), (true, vec![1, 0, 1, 2])]); /// ``` - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn group_by<K, F>(self, key: F) -> GroupBy<K, Self, F> where Self: Sized, F: FnMut(&Self::Item) -> K, @@ -537,7 +585,7 @@ pub trait Itertools : Iterator { /// assert_eq!(4, chunk.sum()); /// } /// ``` - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn chunks(self, size: usize) -> IntoChunks<Self> where Self: Sized, { @@ -555,6 +603,8 @@ pub trait Itertools : Iterator { /// ``` /// use itertools::Itertools; /// let mut v = Vec::new(); + /// + /// // pairwise iteration /// for (a, b) in (1..5).tuple_windows() { /// v.push((a, b)); /// } @@ -584,6 +634,40 @@ pub trait Itertools : Iterator { tuple_impl::tuple_windows(self) } + /// Return 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 (up to 4). + /// + /// `circular_tuple_windows` clones the iterator elements so that they can be + /// part of successive windows, this makes it most suited for iterators + /// of references and other values that are cheap to copy. + /// + /// ``` + /// use itertools::Itertools; + /// let mut v = Vec::new(); + /// for (a, b) in (1..5).circular_tuple_windows() { + /// v.push((a, b)); + /// } + /// assert_eq!(v, vec![(1, 2), (2, 3), (3, 4), (4, 1)]); + /// + /// let mut it = (1..5).circular_tuple_windows(); + /// assert_eq!(Some((1, 2, 3)), it.next()); + /// assert_eq!(Some((2, 3, 4)), it.next()); + /// assert_eq!(Some((3, 4, 1)), it.next()); + /// assert_eq!(Some((4, 1, 2)), it.next()); + /// assert_eq!(None, it.next()); + /// + /// // this requires a type hint + /// let it = (1..5).circular_tuple_windows::<(_, _, _)>(); + /// itertools::assert_equal(it, vec![(1, 2, 3), (2, 3, 4), (3, 4, 1), (4, 1, 2)]); + /// ``` + fn circular_tuple_windows<T>(self) -> CircularTupleWindows<Self, T> + where Self: Sized + Clone + Iterator<Item = T::Item> + ExactSizeIterator, + T: tuple_impl::TupleCollect + Clone, + T::Item: Clone + { + tuple_impl::circular_tuple_windows(self) + } /// Return an iterator that groups the items in tuples of a specific size /// (up to 4). /// @@ -639,7 +723,7 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(t2, 0..4); /// itertools::assert_equal(t1, 1..4); /// ``` - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn tee(self) -> (Tee<Self>, Tee<Self>) where Self: Sized, Self::Item: Clone @@ -663,7 +747,7 @@ pub trait Itertools : Iterator { /// let it = (0..8).step(3); /// itertools::assert_equal(it, vec![0, 3, 6]); /// ``` - #[deprecated(note="Use std .step_by() instead", since="0.8")] + #[deprecated(note="Use std .step_by() instead", since="0.8.0")] #[allow(deprecated)] fn step(self, n: usize) -> Step<Self> where Self: Sized @@ -685,6 +769,15 @@ pub trait Itertools : Iterator { adaptors::map_into(self) } + /// See [`.map_ok()`](#method.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, + F: FnMut(T) -> U, + { + self.map_ok(f) + } + /// Return an iterator adaptor that applies the provided closure /// to every `Result::Ok` value. `Result::Err` values are /// unchanged. @@ -693,14 +786,50 @@ pub trait Itertools : Iterator { /// use itertools::Itertools; /// /// let input = vec![Ok(41), Err(false), Ok(11)]; - /// let it = input.into_iter().map_results(|i| i + 1); + /// let it = input.into_iter().map_ok(|i| i + 1); /// itertools::assert_equal(it, vec![Ok(42), Err(false), Ok(12)]); /// ``` - fn map_results<F, T, U, E>(self, f: F) -> MapResults<Self, F> + fn map_ok<F, T, U, E>(self, f: F) -> MapOk<Self, F> where Self: Iterator<Item = Result<T, E>> + Sized, F: FnMut(T) -> U, { - adaptors::map_results(self, f) + adaptors::map_ok(self, f) + } + + /// Return an iterator adaptor that filters every `Result::Ok` + /// value with the provided closure. `Result::Err` values are + /// unchanged. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let input = vec![Ok(22), Err(false), Ok(11)]; + /// let it = input.into_iter().filter_ok(|&i| i > 20); + /// itertools::assert_equal(it, vec![Ok(22), Err(false)]); + /// ``` + fn filter_ok<F, T, E>(self, f: F) -> FilterOk<Self, F> + where Self: Iterator<Item = Result<T, E>> + Sized, + F: FnMut(&T) -> bool, + { + adaptors::filter_ok(self, f) + } + + /// Return an iterator adaptor that filters and transforms every + /// `Result::Ok` value with the provided closure. `Result::Err` + /// values are unchanged. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let input = vec![Ok(22), Err(false), Ok(11)]; + /// let it = input.into_iter().filter_map_ok(|i| if i > 20 { Some(i * 2) } else { None }); + /// itertools::assert_equal(it, vec![Ok(44), Err(false)]); + /// ``` + fn filter_map_ok<F, T, U, E>(self, f: F) -> FilterMapOk<Self, F> + where Self: Iterator<Item = Result<T, E>> + Sized, + F: FnMut(T) -> Option<U>, + { + adaptors::filter_map_ok(self, f) } /// Return an iterator adaptor that merges the two base iterators in @@ -768,17 +897,13 @@ pub trait Itertools : Iterator { /// use itertools::Itertools; /// use itertools::EitherOrBoth::{Left, Right, Both}; /// - /// let ki = (0..10).step(3); - /// let ku = (0..10).step(5); - /// let ki_ku = ki.merge_join_by(ku, |i, j| i.cmp(j)).map(|either| { - /// match either { - /// Left(_) => "Ki", - /// Right(_) => "Ku", - /// Both(_, _) => "KiKu" - /// } - /// }); + /// let multiples_of_2 = (0..10).step(2); + /// let multiples_of_3 = (0..10).step(3); /// - /// itertools::assert_equal(ki_ku, vec!["KiKu", "Ki", "Ku", "Ki", "Ki"]); + /// itertools::assert_equal( + /// multiples_of_2.merge_join_by(multiples_of_3, |i, j| i.cmp(j)), + /// vec![Both(0, 0), Left(2), Right(3), Left(4), Both(6, 6), Left(8), Right(9)] + /// ); /// ``` #[inline] fn merge_join_by<J, F>(self, other: J, cmp_fn: F) -> MergeJoinBy<Self, J::IntoIter, F> @@ -789,7 +914,6 @@ pub trait Itertools : Iterator { merge_join_by(self, other, cmp_fn) } - /// Return an iterator adaptor that flattens an iterator of iterators by /// merging them in ascending order. /// @@ -806,7 +930,7 @@ pub trait Itertools : Iterator { /// let it = vec![a, b, c].into_iter().kmerge(); /// itertools::assert_equal(it, vec![0, 1, 2, 3, 4, 5]); /// ``` - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn kmerge(self) -> KMerge<<Self::Item as IntoIterator>::IntoIter> where Self: Sized, Self::Item: IntoIterator, @@ -835,7 +959,7 @@ pub trait Itertools : Iterator { /// assert_eq!(it.next(), Some(0.)); /// assert_eq!(it.last(), Some(-7.)); /// ``` - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn kmerge_by<F>(self, first: F) -> KMergeBy<<Self::Item as IntoIterator>::IntoIter, F> where Self: Sized, @@ -891,7 +1015,7 @@ pub trait Itertools : Iterator { /// assert_eq!(multi_prod.next(), Some(vec![1, 3, 5])); /// assert_eq!(multi_prod.next(), None); /// ``` - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn multi_cartesian_product(self) -> MultiProduct<<Self::Item as IntoIterator>::IntoIter> where Self: Iterator + Sized, Self::Item: IntoIterator, @@ -970,7 +1094,7 @@ pub trait Itertools : Iterator { /// use itertools::Itertools; /// /// let data = vec![(0, 1.), (1, 1.), (0, 2.), (0, 3.), (1, 3.), (1, 2.), (2, 2.)]; - /// itertools::assert_equal(data.into_iter().dedup_by(|x, y| x.1==y.1), + /// itertools::assert_equal(data.into_iter().dedup_by(|x, y| x.1 == y.1), /// vec![(0, 1.), (0, 2.), (0, 3.), (1, 2.)]); /// ``` fn dedup_by<Cmp>(self, cmp: Cmp) -> DedupBy<Self, Cmp> @@ -980,6 +1104,50 @@ pub trait Itertools : Iterator { adaptors::dedup_by(self, cmp) } + /// Remove duplicates from sections of consecutive identical elements, while keeping a count of + /// how many repeated elements were present. + /// If the iterator is sorted, all elements will be unique. + /// + /// Iterator element type is `(usize, Self::Item)`. + /// + /// This iterator is *fused*. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let data = vec![1., 1., 2., 3., 3., 2., 2.]; + /// itertools::assert_equal(data.into_iter().dedup_with_count(), + /// vec![(2, 1.), (1, 2.), (2, 3.), (2, 2.)]); + /// ``` + fn dedup_with_count(self) -> DedupWithCount<Self> + where Self: Sized, + { + adaptors::dedup_with_count(self) + } + + /// Remove duplicates from sections of consecutive identical elements, while keeping a count of + /// how many repeated elements were present. + /// This will determine equality using a comparison function. + /// If the iterator is sorted, all elements will be unique. + /// + /// Iterator element type is `(usize, Self::Item)`. + /// + /// This iterator is *fused*. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let data = vec![(0, 1.), (1, 1.), (0, 2.), (0, 3.), (1, 3.), (1, 2.), (2, 2.)]; + /// 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.))]); + /// ``` + fn dedup_by_with_count<Cmp>(self, cmp: Cmp) -> DedupByWithCount<Self, Cmp> + where Self: Sized, + Cmp: FnMut(&Self::Item, &Self::Item) -> bool, + { + adaptors::dedup_by_with_count(self, cmp) + } + /// Return an iterator adaptor that filters out elements that have /// already been produced once during the iteration. Duplicates /// are detected using hash and equality. @@ -987,6 +1155,10 @@ pub trait Itertools : Iterator { /// Clones of visited elements are stored in a hash set in the /// iterator. /// + /// The iterator is stable, returning the non-duplicate items in the order + /// in which they occur in the adapted iterator. In a set of duplicate + /// items, the first item encountered is the item retained. + /// /// ``` /// use itertools::Itertools; /// @@ -1009,6 +1181,10 @@ pub trait Itertools : Iterator { /// with the keying function `f` by hash and equality. /// The keys are stored in a hash set in the iterator. /// + /// The iterator is stable, returning the non-duplicate items in the order + /// in which they occur in the adapted iterator. In a set of duplicate + /// items, the first item encountered is the item retained. + /// /// ``` /// use itertools::Itertools; /// @@ -1093,7 +1269,7 @@ pub trait Itertools : Iterator { /// elements from an iterator. /// /// Iterator element can be any homogeneous tuple of type `Self::Item` with - /// size up to 4. + /// size up to 12. /// /// ``` /// use itertools::Itertools; @@ -1159,7 +1335,7 @@ pub trait Itertools : Iterator { /// vec![2, 2], /// ]); /// ``` - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn combinations(self, k: usize) -> Combinations<Self> where Self: Sized, Self::Item: Clone @@ -1186,7 +1362,7 @@ pub trait Itertools : Iterator { /// vec![3, 3], /// ]); /// ``` - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn combinations_with_replacement(self, k: usize) -> CombinationsWithReplacement<Self> where Self: Sized, @@ -1232,7 +1408,7 @@ pub trait Itertools : Iterator { /// /// Note: The source iterator is collected lazily, and will not be /// re-iterated if the permutations adaptor is completed and re-iterated. - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn permutations(self, k: usize) -> Permutations<Self> where Self: Sized, Self::Item: Clone @@ -1240,6 +1416,42 @@ pub trait Itertools : Iterator { permutations::permutations(self, k) } + /// Return an iterator that iterates through the powerset of the elements from an + /// iterator. + /// + /// Iterator element type is `Vec<Self::Item>`. The iterator produces a new `Vec` + /// per iteration, and clones the iterator elements. + /// + /// The powerset of a set contains all subsets including the empty set and the full + /// input set. A powerset has length _2^n_ where _n_ is the length of the input + /// set. + /// + /// Each `Vec` produced by this iterator represents a subset of the elements + /// produced by the source iterator. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let sets = (1..4).powerset().collect::<Vec<_>>(); + /// itertools::assert_equal(sets, vec![ + /// vec![], + /// vec![1], + /// vec![2], + /// vec![3], + /// vec![1, 2], + /// vec![1, 3], + /// vec![2, 3], + /// vec![1, 2, 3], + /// ]); + /// ``` + #[cfg(feature = "use_alloc")] + fn powerset(self) -> Powerset<Self> + where Self: Sized, + Self::Item: Clone, + { + powerset::powerset(self) + } + /// Return an iterator adaptor that pads the sequence to a minimum length of /// `min` by filling missing elements using a closure `f`. /// @@ -1328,7 +1540,7 @@ pub trait Itertools : Iterator { // non-adaptor methods /// Advances the iterator and returns the next items grouped in a tuple of - /// a specific size (up to 4). + /// a specific size (up to 12). /// /// If there are enough elements to be grouped in a tuple, then the tuple is /// returned inside `Some`, otherwise `None` is returned. @@ -1348,7 +1560,7 @@ pub trait Itertools : Iterator { } /// Collects all items from the iterator into a tuple of a specific size - /// (up to 4). + /// (up to 12). /// /// If the number of elements inside the iterator is **exactly** equal to /// the tuple size, then the tuple is returned inside `Some`, otherwise @@ -1494,7 +1706,7 @@ pub trait Itertools : Iterator { /// /// itertools::assert_equal(rx.iter(), vec![1, 3, 5, 7, 9]); /// ``` - #[deprecated(note="Use .for_each() instead", since="0.8")] + #[deprecated(note="Use .for_each() instead", since="0.8.0")] fn foreach<F>(self, f: F) where F: FnMut(Self::Item), Self: Sized, @@ -1524,7 +1736,7 @@ pub trait Itertools : Iterator { /// `.collect_vec()` is simply a type specialization of `.collect()`, /// for convenience. - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn collect_vec(self) -> Vec<Self::Item> where Self: Sized { @@ -1551,7 +1763,7 @@ pub trait Itertools : Iterator { /// Ok(()) /// } /// ``` - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn try_collect<T, U, E>(self) -> Result<U, E> where Self: Sized + Iterator<Item = Result<T, E>>, @@ -1601,7 +1813,7 @@ pub trait Itertools : Iterator { /// assert_eq!(["a", "b", "c"].iter().join(", "), "a, b, c"); /// assert_eq!([1, 2, 3].iter().join(", "), "1, 2, 3"); /// ``` - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn join(&mut self, sep: &str) -> String where Self::Item: std::fmt::Display { @@ -1612,10 +1824,10 @@ pub trait Itertools : Iterator { let (lower, _) = self.size_hint(); let mut result = String::with_capacity(sep.len() * lower); write!(&mut result, "{}", first_elt).unwrap(); - for elt in self { + self.for_each(|elt| { result.push_str(sep); write!(&mut result, "{}", elt).unwrap(); - } + }); result } } @@ -1681,6 +1893,15 @@ pub trait Itertools : Iterator { format::new_format(self, sep, format) } + /// See [`.fold_ok()`](#method.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>>, + F: FnMut(B, A) -> B + { + self.fold_ok(start, f) + } + /// Fold `Result` values from an iterator. /// /// Only `Ok` values are folded. If no error is encountered, the folded @@ -1713,17 +1934,17 @@ pub trait Itertools : Iterator { /// assert_eq!( /// values.iter() /// .map(Ok::<_, ()>) - /// .fold_results(0, Add::add), + /// .fold_ok(0, Add::add), /// Ok(3) /// ); /// assert!( /// values.iter() /// .map(|&x| if x >= 0 { Ok(x) } else { Err("Negative number") }) - /// .fold_results(0, Add::add) + /// .fold_ok(0, Add::add) /// .is_err() /// ); /// ``` - fn fold_results<A, E, B, F>(&mut self, mut start: B, mut f: F) -> Result<B, E> + fn fold_ok<A, E, B, F>(&mut self, mut start: B, mut f: F) -> Result<B, E> where Self: Iterator<Item = Result<A, E>>, F: FnMut(B, A) -> B { @@ -1742,7 +1963,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_results`. + /// This is the `Option` equivalent to `fold_ok`. /// /// ``` /// use std::ops::Add; @@ -1933,19 +2154,26 @@ pub trait Itertools : Iterator { /// The big difference between the computations of `result2` and `result3` is that while /// `fold()` called the provided closure for every item of the callee iterator, /// `fold_while()` actually stopped iterating as soon as it encountered `Fold::Done(_)`. - #[deprecated(note="Use .try_fold() instead", since="0.8")] fn fold_while<B, F>(&mut self, init: B, mut f: F) -> FoldWhile<B> where Self: Sized, F: FnMut(B, Self::Item) -> FoldWhile<B> { - let mut acc = init; - while let Some(item) = self.next() { - match f(acc, item) { - FoldWhile::Continue(res) => acc = res, - res @ FoldWhile::Done(_) => return res, + use Result::{ + Ok as Continue, + Err as Break, + }; + + let result = self.try_fold(init, #[inline(always)] |acc, v| + match f(acc, v) { + FoldWhile::Continue(acc) => Continue(acc), + FoldWhile::Done(acc) => Break(acc), } + ); + + match result { + Continue(acc) => FoldWhile::Continue(acc), + Break(acc) => FoldWhile::Done(acc), } - FoldWhile::Continue(acc) } /// Iterate over the entire iterator and add all the elements. @@ -2005,6 +2233,101 @@ pub trait Itertools : Iterator { .map(|first| once(first).chain(self).product()) } + /// 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 + /// iterator that owns its elements. + /// + /// The sorted iterator, if directly collected to a `Vec`, is converted + /// without any extra copying or allocation cost. + /// + /// ``` + /// use itertools::Itertools; + /// + /// // sort the letters of the text in ascending order + /// let text = "bdacfe"; + /// itertools::assert_equal(text.chars().sorted_unstable(), + /// "abcdef".chars()); + /// ``` + #[cfg(feature = "use_alloc")] + fn sorted_unstable(self) -> VecIntoIter<Self::Item> + where Self: Sized, + Self::Item: Ord + { + // Use .sort_unstable() directly since it is not quite identical with + // .sort_by(Ord::cmp) + let mut v = Vec::from_iter(self); + v.sort_unstable(); + v.into_iter() + } + + /// 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 + /// iterator that owns its elements. + /// + /// The sorted iterator, if directly collected to a `Vec`, is converted + /// without any extra copying or allocation cost. + /// + /// ``` + /// use itertools::Itertools; + /// + /// // sort people in descending order by age + /// let people = vec![("Jane", 20), ("John", 18), ("Jill", 30), ("Jack", 27)]; + /// + /// let oldest_people_first = people + /// .into_iter() + /// .sorted_unstable_by(|a, b| Ord::cmp(&b.1, &a.1)) + /// .map(|(person, _age)| person); + /// + /// itertools::assert_equal(oldest_people_first, + /// vec!["Jill", "Jack", "Jane", "John"]); + /// ``` + #[cfg(feature = "use_alloc")] + fn sorted_unstable_by<F>(self, cmp: F) -> VecIntoIter<Self::Item> + where Self: Sized, + F: FnMut(&Self::Item, &Self::Item) -> Ordering, + { + let mut v = Vec::from_iter(self); + v.sort_unstable_by(cmp); + v.into_iter() + } + + /// 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 + /// iterator that owns its elements. + /// + /// The sorted iterator, if directly collected to a `Vec`, is converted + /// without any extra copying or allocation cost. + /// + /// ``` + /// use itertools::Itertools; + /// + /// // sort people in descending order by age + /// let people = vec![("Jane", 20), ("John", 18), ("Jill", 30), ("Jack", 27)]; + /// + /// let oldest_people_first = people + /// .into_iter() + /// .sorted_unstable_by_key(|x| -x.1) + /// .map(|(person, _age)| person); + /// + /// itertools::assert_equal(oldest_people_first, + /// vec!["Jill", "Jack", "Jane", "John"]); + /// ``` + #[cfg(feature = "use_alloc")] + fn sorted_unstable_by_key<K, F>(self, f: F) -> VecIntoIter<Self::Item> + where Self: Sized, + K: Ord, + F: FnMut(&Self::Item) -> K, + { + let mut v = Vec::from_iter(self); + v.sort_unstable_by_key(f); + v.into_iter() + } /// Sort all iterator elements into a new iterator in ascending order. /// @@ -2023,7 +2346,7 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(text.chars().sorted(), /// "abcdef".chars()); /// ``` - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn sorted(self) -> VecIntoIter<Self::Item> where Self: Sized, Self::Item: Ord @@ -2058,7 +2381,7 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(oldest_people_first, /// vec!["Jill", "Jack", "Jane", "John"]); /// ``` - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn sorted_by<F>(self, cmp: F) -> VecIntoIter<Self::Item> where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering, @@ -2091,7 +2414,7 @@ pub trait Itertools : Iterator { /// itertools::assert_equal(oldest_people_first, /// vec!["Jill", "Jack", "Jane", "John"]); /// ``` - #[cfg(feature = "use_std")] + #[cfg(feature = "use_alloc")] fn sorted_by_key<K, F>(self, f: F) -> VecIntoIter<Self::Item> where Self: Sized, K: Ord, @@ -2102,6 +2425,43 @@ pub trait Itertools : Iterator { v.into_iter() } + /// Sort the k smallest elements into a new iterator, in ascending order. + /// + /// **Note:** This consumes the entire iterator, and returns the result + /// as a new iterator that owns its elements. If the input contains + /// less than k elements, the result is equivalent to `self.sorted()`. + /// + /// This is guaranteed to use `k * sizeof(Self::Item) + O(1)` memory + /// and `O(n log k)` time, with `n` the number of elements in the input. + /// + /// The sorted iterator, if directly collected to a `Vec`, is converted + /// without any extra copying or allocation cost. + /// + /// **Note:** This is functionally-equivalent to `self.sorted().take(k)` + /// but much more efficient. + /// + /// ``` + /// use itertools::Itertools; + /// + /// // A random permutation of 0..15 + /// let numbers = vec![6, 9, 1, 14, 0, 4, 8, 7, 11, 2, 10, 3, 13, 12, 5]; + /// + /// let five_smallest = numbers + /// .into_iter() + /// .k_smallest(5); + /// + /// itertools::assert_equal(five_smallest, 0..5); + /// ``` + #[cfg(feature = "use_alloc")] + fn k_smallest(self, k: usize) -> VecIntoIter<Self::Item> + where Self: Sized, + Self::Item: Ord + { + crate::k_smallest::k_smallest(self, k) + .into_sorted_vec() + .into_iter() + } + /// Collect all iterator elements into one of two /// partitions. Unlike `Iterator::partition`, each partition may /// have a distinct type. @@ -2162,6 +2522,75 @@ 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 + /// 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. + /// + /// ``` + /// 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); + /// + /// assert_eq!(lookup[&0], vec![(0,10),(0,20)]); + /// assert_eq!(lookup.get(&1), None); + /// assert_eq!(lookup[&2], vec![(2,12), (2,42)]); + /// assert_eq!(lookup[&3], vec![(3,13), (3,33)]); + /// + /// 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) + /// ``` + #[cfg(feature = "use_std")] + fn into_group_map_by<K, V, F>(self, f: F) -> HashMap<K, Vec<V>> + where + Self: Iterator<Item=V> + Sized, + K: Hash + Eq, + F: Fn(&V) -> K, + { + group_map::into_group_map_by(self, f) + } + + /// Constructs a `GroupingMap` to be used later with one of the efficient + /// group-and-fold operations it allows to perform. + /// + /// The input iterator must yield item in the form of `(K, V)` where the + /// 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 + /// on what operations are available. + #[cfg(feature = "use_std")] + fn into_grouping_map<K, V>(self) -> GroupingMap<Self> + where Self: Iterator<Item=(K, V)> + Sized, + K: Hash + Eq, + { + grouping_map::new(self) + } + + /// Constructs a `GroupingMap` to be used later with one of the efficient + /// group-and-fold operations it allows to perform. + /// + /// 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 + /// on what operations are available. + #[cfg(feature = "use_std")] + fn into_grouping_map_by<K, V, F>(self, key_mapper: F) -> GroupingMapBy<Self, F> + where Self: Iterator<Item=V> + Sized, + K: Hash + Eq, + F: FnMut(&V) -> K + { + grouping_map::new(grouping_map::MapForGrouping::new(self, key_mapper)) + } + /// Return the minimum and maximum elements in the iterator. /// /// The return type `MinMaxResult` is an enum of three variants: @@ -2573,16 +3002,62 @@ pub trait Itertools : Iterator { Some(first) => { match self.next() { Some(second) => { - Err(ExactlyOneError::new((Some(first), Some(second)), self)) + Err(ExactlyOneError::new(Some(Either::Left([first, second])), self)) } None => { Ok(first) } } } - None => Err(ExactlyOneError::new((None, None), self)), + None => Err(ExactlyOneError::new(None, self)), } } + + /// An iterator adaptor that allows the user to peek at multiple `.next()` + /// values without advancing the base iterator. + /// + /// # Examples + /// ``` + /// use itertools::Itertools; + /// + /// let mut iter = (0..10).multipeek(); + /// assert_eq!(iter.peek(), Some(&0)); + /// assert_eq!(iter.peek(), Some(&1)); + /// assert_eq!(iter.peek(), Some(&2)); + /// assert_eq!(iter.next(), Some(0)); + /// assert_eq!(iter.peek(), Some(&1)); + /// ``` + #[cfg(feature = "use_alloc")] + fn multipeek(self) -> MultiPeek<Self> + where + Self: Sized, + { + multipeek_impl::multipeek(self) + } + + /// 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. + /// + /// # Examples + /// ``` + /// # use itertools::Itertools; + /// let counts = [1, 1, 1, 3, 3, 5].into_iter().counts(); + /// assert_eq!(counts[&1], 3); + /// assert_eq!(counts[&3], 2); + /// assert_eq!(counts[&5], 1); + /// assert_eq!(counts.get(&0), None); + /// ``` + #[cfg(feature = "use_std")] + fn counts(self) -> HashMap<Self::Item, usize> + where + Self: Sized, + Self::Item: Eq + Hash, + { + let mut counts = HashMap::new(); + self.for_each(|item| *counts.entry(item).or_default() += 1); + counts + } } impl<T: ?Sized> Itertools for T where T: Iterator { } diff --git a/src/multipeek_impl.rs b/src/multipeek_impl.rs index 0b64e1d..986e5b4 100644 --- a/src/multipeek_impl.rs +++ b/src/multipeek_impl.rs @@ -1,5 +1,5 @@ use std::iter::Fuse; -use std::collections::VecDeque; +use alloc::collections::VecDeque; use crate::size_hint; use crate::PeekingNext; @@ -80,13 +80,9 @@ impl<I> Iterator for MultiPeek<I> { type Item = I::Item; - fn next(&mut self) -> Option<I::Item> { + fn next(&mut self) -> Option<Self::Item> { self.index = 0; - if self.buf.is_empty() { - self.iter.next() - } else { - self.buf.pop_front() - } + self.buf.pop_front().or_else(|| self.iter.next()) } fn size_hint(&self) -> (usize, Option<usize>) { diff --git a/src/pad_tail.rs b/src/pad_tail.rs index 8d9d5ff..4ed83c3 100644 --- a/src/pad_tail.rs +++ b/src/pad_tail.rs @@ -36,7 +36,7 @@ impl<I, F> Iterator for PadUsing<I, F> type Item = I::Item; #[inline] - fn next(&mut self) -> Option<I::Item> { + fn next(&mut self) -> Option<Self::Item> { match self.iter.next() { None => { if self.pos < self.min { @@ -64,7 +64,7 @@ impl<I, F> DoubleEndedIterator for PadUsing<I, F> where I: DoubleEndedIterator + ExactSizeIterator, F: FnMut(usize) -> I::Item { - fn next_back(&mut self) -> Option<I::Item> { + fn next_back(&mut self) -> Option<Self::Item> { if self.min == 0 { self.iter.next_back() } else if self.iter.len() >= self.min { diff --git a/src/peek_nth.rs b/src/peek_nth.rs new file mode 100644 index 0000000..d22258b --- /dev/null +++ b/src/peek_nth.rs @@ -0,0 +1,102 @@ +use crate::size_hint; +use crate::PeekingNext; +use alloc::collections::VecDeque; +use std::iter::Fuse; + +/// See [`peek_nth()`](../fn.peek_nth.html) for more information. +#[derive(Clone, Debug)] +pub struct PeekNth<I> +where + I: Iterator, +{ + iter: Fuse<I>, + buf: VecDeque<I::Item>, +} + +/// 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. +/// +/// This differs from `multipeek` in that subsequent calls to `peek` or +/// `peek_nth` will always return the same value until `next` is called +/// (making `reset_peek` unnecessary). +pub fn peek_nth<I>(iterable: I) -> PeekNth<I::IntoIter> +where + I: IntoIterator, +{ + PeekNth { + iter: iterable.into_iter().fuse(), + buf: VecDeque::new(), + } +} + +impl<I> PeekNth<I> +where + I: Iterator, +{ + /// Works exactly like the `peek` method in `std::iter::Peekable` + pub fn peek(&mut self) -> Option<&I::Item> { + self.peek_nth(0) + } + + /// Returns a reference to the `nth` value without advancing the iterator. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ```rust + /// use itertools::peek_nth; + /// + /// let xs = vec![1,2,3]; + /// let mut iter = peek_nth(xs.iter()); + /// + /// assert_eq!(iter.peek_nth(0), Some(&&1)); + /// assert_eq!(iter.next(), Some(&1)); + /// + /// // The iterator does not advance even if we call `peek_nth` multiple times + /// assert_eq!(iter.peek_nth(0), Some(&&2)); + /// assert_eq!(iter.peek_nth(1), Some(&&3)); + /// assert_eq!(iter.next(), Some(&2)); + /// + /// // Calling `peek_nth` past the end of the iterator will return `None` + /// assert_eq!(iter.peek_nth(1), None); + /// ``` + pub fn peek_nth(&mut self, n: usize) -> Option<&I::Item> { + let unbuffered_items = (n + 1).saturating_sub(self.buf.len()); + + self.buf.extend(self.iter.by_ref().take(unbuffered_items)); + + self.buf.get(n) + } +} + +impl<I> Iterator for PeekNth<I> +where + I: Iterator, +{ + type Item = I::Item; + + fn next(&mut self) -> Option<Self::Item> { + self.buf.pop_front().or_else(|| self.iter.next()) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + size_hint::add_scalar(self.iter.size_hint(), self.buf.len()) + } +} + +impl<I> ExactSizeIterator for PeekNth<I> where I: ExactSizeIterator {} + +impl<I> PeekingNext for PeekNth<I> +where + I: Iterator, +{ + fn peeking_next<F>(&mut self, accept: F) -> Option<Self::Item> + where + F: FnOnce(&Self::Item) -> bool, + { + self.peek().filter(|item| accept(item))?; + self.next() + } +} diff --git a/src/peeking_take_while.rs b/src/peeking_take_while.rs index b404904..70ef988 100644 --- a/src/peeking_take_while.rs +++ b/src/peeking_take_while.rs @@ -1,6 +1,6 @@ use std::iter::Peekable; use crate::PutBack; -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] use crate::PutBackN; /// An iterator that allows peeking at an element before deciding to accept it. @@ -52,7 +52,7 @@ impl<I> PeekingNext for PutBack<I> } } -#[cfg(feature = "use_std")] +#[cfg(feature = "use_alloc")] impl<I> PeekingNext for PutBackN<I> where I: Iterator, { @@ -104,8 +104,7 @@ impl<'a, I, F> Iterator for PeekingTakeWhile<'a, I, F> } fn size_hint(&self) -> (usize, Option<usize>) { - let (_, hi) = self.iter.size_hint(); - (0, hi) + (0, self.iter.size_hint().1) } } @@ -138,10 +137,10 @@ peeking_next_by_clone! { ['a] ::std::str::Bytes<'a> } peeking_next_by_clone! { ['a, T] ::std::option::Iter<'a, T> } peeking_next_by_clone! { ['a, T] ::std::result::Iter<'a, T> } peeking_next_by_clone! { [T] ::std::iter::Empty<T> } -#[cfg(feature = "use_std")] -peeking_next_by_clone! { ['a, T] ::std::collections::linked_list::Iter<'a, T> } -#[cfg(feature = "use_std")] -peeking_next_by_clone! { ['a, T] ::std::collections::vec_deque::Iter<'a, T> } +#[cfg(feature = "use_alloc")] +peeking_next_by_clone! { ['a, T] alloc::collections::linked_list::Iter<'a, T> } +#[cfg(feature = "use_alloc")] +peeking_next_by_clone! { ['a, T] alloc::collections::vec_deque::Iter<'a, T> } // cloning a Rev has no extra overhead; peekable and put backs are never DEI. peeking_next_by_clone! { [I: Clone + PeekingNext + DoubleEndedIterator] diff --git a/src/permutations.rs b/src/permutations.rs index fb4dd50..d96bbac 100644 --- a/src/permutations.rs +++ b/src/permutations.rs @@ -1,3 +1,4 @@ +use alloc::vec::Vec; use std::fmt; use std::iter::once; @@ -104,21 +105,21 @@ where let &mut Permutations { ref vals, ref state } = self; - match state { - &PermutationState::StartUnknownLen { .. } => panic!("unexpected iterator state"), - &PermutationState::OngoingUnknownLen { k, min_n } => { + match *state { + PermutationState::StartUnknownLen { .. } => panic!("unexpected iterator state"), + PermutationState::OngoingUnknownLen { k, min_n } => { let latest_idx = min_n - 1; let indices = (0..(k - 1)).chain(once(latest_idx)); Some(indices.map(|i| vals[i].clone()).collect()) } - &PermutationState::Complete(CompleteState::Start { .. }) => None, - &PermutationState::Complete(CompleteState::Ongoing { ref indices, ref cycles }) => { + PermutationState::Complete(CompleteState::Start { .. }) => None, + PermutationState::Complete(CompleteState::Ongoing { ref indices, ref cycles }) => { let k = cycles.len(); Some(indices[0..k].iter().map(|&i| vals[i].clone()).collect()) }, - &PermutationState::Empty => None + PermutationState::Empty => None } } @@ -174,11 +175,11 @@ where fn advance(&mut self) { let &mut Permutations { ref mut vals, ref mut state } = self; - *state = match state { - &mut PermutationState::StartUnknownLen { k } => { + *state = match *state { + PermutationState::StartUnknownLen { k } => { PermutationState::OngoingUnknownLen { k, min_n: k } } - &mut PermutationState::OngoingUnknownLen { k, min_n } => { + PermutationState::OngoingUnknownLen { k, min_n } => { if vals.get_next() { PermutationState::OngoingUnknownLen { k, min_n: min_n + 1 } } else { @@ -194,20 +195,20 @@ where PermutationState::Complete(complete_state) } } - &mut PermutationState::Complete(ref mut state) => { + PermutationState::Complete(ref mut state) => { state.advance(); return; } - &mut PermutationState::Empty => { return; } + PermutationState::Empty => { return; } }; } } impl CompleteState { fn advance(&mut self) { - *self = match self { - &mut CompleteState::Start { n, k } => { + *self = match *self { + CompleteState::Start { n, k } => { let indices = (0..n).collect(); let cycles = ((n - k)..n).rev().collect(); @@ -216,7 +217,7 @@ impl CompleteState { indices } }, - &mut CompleteState::Ongoing { ref mut indices, ref mut cycles } => { + CompleteState::Ongoing { ref mut indices, ref mut cycles } => { let n = indices.len(); let k = cycles.len(); @@ -243,8 +244,8 @@ impl CompleteState { fn remaining(&self) -> CompleteStateRemaining { use self::CompleteStateRemaining::{Known, Overflow}; - match self { - &CompleteState::Start { n, k } => { + match *self { + CompleteState::Start { n, k } => { if n < k { return Known(0); } @@ -258,7 +259,7 @@ impl CompleteState { None => Overflow } } - &CompleteState::Ongoing { ref indices, ref cycles } => { + CompleteState::Ongoing { ref indices, ref cycles } => { let mut count: usize = 0; for (i, &c) in cycles.iter().enumerate() { diff --git a/src/powerset.rs b/src/powerset.rs new file mode 100644 index 0000000..ef17752 --- /dev/null +++ b/src/powerset.rs @@ -0,0 +1,83 @@ +use std::fmt; +use std::usize; +use alloc::vec::Vec; + +use super::combinations::{Combinations, combinations}; +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 +/// information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct Powerset<I: Iterator> { + combs: Combinations<I>, + // Iterator `position` (equal to count of yielded elements). + pos: usize, +} + +impl<I> Clone for Powerset<I> + where I: Clone + Iterator, + I::Item: Clone, +{ + clone_fields!(combs, pos); +} + +impl<I> fmt::Debug for Powerset<I> + where I: Iterator + fmt::Debug, + I::Item: fmt::Debug, +{ + debug_fmt_fields!(Powerset, combs, pos); +} + +/// Create a new `Powerset` from a clonable iterator. +pub fn powerset<I>(src: I) -> Powerset<I> + where I: Iterator, + I::Item: Clone, +{ + Powerset { + combs: combinations(src, 0), + pos: 0, + } +} + +impl<I> Iterator for Powerset<I> + where + I: Iterator, + I::Item: Clone, +{ + type Item = Vec<I::Item>; + + fn next(&mut self) -> Option<Self::Item> { + if let Some(elt) = self.combs.next() { + self.pos = self.pos.saturating_add(1); + Some(elt) + } else if self.combs.k() < self.combs.n() + || self.combs.k() == 0 + { + self.combs.reset(self.combs.k() + 1); + self.combs.next().map(|elt| { + self.pos = self.pos.saturating_add(1); + elt + }) + } else { + None + } + } + + fn size_hint(&self) -> (usize, Option<usize>) { + // Total bounds for source iterator. + let src_total = size_hint::add_scalar(self.combs.src().size_hint(), self.combs.n()); + + // Total bounds for self ( length(powerset(set) == 2 ^ length(set) ) + let self_total = size_hint::pow_scalar_base(2, src_total); + + if self.pos < usize::MAX { + // Subtract count of elements already yielded from total. + size_hint::sub_scalar(self_total, self.pos) + } else { + // Fallback: self.pos is saturated and no longer reliable. + (0, self_total.1) + } + } +} diff --git a/src/process_results_impl.rs b/src/process_results_impl.rs index c819f50..d74925a 100644 --- a/src/process_results_impl.rs +++ b/src/process_results_impl.rs @@ -28,8 +28,7 @@ impl<'a, I, T, E> Iterator for ProcessResults<'a, I, E> } fn size_hint(&self) -> (usize, Option<usize>) { - let (_, hi) = self.iter.size_hint(); - (0, hi) + (0, self.iter.size_hint().1) } } diff --git a/src/put_back_n_impl.rs b/src/put_back_n_impl.rs index dcb2894..60ea8e6 100644 --- a/src/put_back_n_impl.rs +++ b/src/put_back_n_impl.rs @@ -1,3 +1,5 @@ +use alloc::vec::Vec; + use crate::size_hint; /// An iterator adaptor that allows putting multiple @@ -47,12 +49,8 @@ impl<I: Iterator> PutBackN<I> { impl<I: Iterator> Iterator for PutBackN<I> { type Item = I::Item; #[inline] - fn next(&mut self) -> Option<I::Item> { - if self.top.is_empty() { - self.iter.next() - } else { - self.top.pop() - } + fn next(&mut self) -> Option<Self::Item> { + self.top.pop().or_else(|| self.iter.next()) } #[inline] diff --git a/src/rciter_impl.rs b/src/rciter_impl.rs index 6ee90ad..9122dad 100644 --- a/src/rciter_impl.rs +++ b/src/rciter_impl.rs @@ -1,6 +1,6 @@ use std::iter::IntoIterator; -use std::rc::Rc; +use alloc::rc::Rc; use std::cell::RefCell; /// A wrapper for `Rc<RefCell<I>>`, that implements the `Iterator` trait. @@ -60,7 +60,7 @@ impl<A, I> Iterator for RcIter<I> { type Item = A; #[inline] - fn next(&mut self) -> Option<A> { + fn next(&mut self) -> Option<Self::Item> { self.rciter.borrow_mut().next() } @@ -69,8 +69,7 @@ impl<A, I> Iterator for RcIter<I> // To work sanely with other API that assume they own an iterator, // so it can't change in other places, we can't guarantee as much // in our size_hint. Other clones may drain values under our feet. - let (_, hi) = self.rciter.borrow().size_hint(); - (0, hi) + (0, self.rciter.borrow().size_hint().1) } } @@ -78,7 +77,7 @@ impl<I> DoubleEndedIterator for RcIter<I> where I: DoubleEndedIterator { #[inline] - fn next_back(&mut self) -> Option<I::Item> { + fn next_back(&mut self) -> Option<Self::Item> { self.rciter.borrow_mut().next_back() } } diff --git a/src/size_hint.rs b/src/size_hint.rs index be54443..1168eca 100644 --- a/src/size_hint.rs +++ b/src/size_hint.rs @@ -3,6 +3,7 @@ use std::usize; use std::cmp; +use std::u32; /// **SizeHint** is the return type of **Iterator::size_hint()**. pub type SizeHint = (usize, Option<usize>); @@ -10,7 +11,7 @@ pub type SizeHint = (usize, Option<usize>); /// Add **SizeHint** correctly. #[inline] pub fn add(a: SizeHint, b: SizeHint) -> SizeHint { - let min = a.0.checked_add(b.0).unwrap_or(usize::MAX); + let min = a.0.saturating_add(b.0); let max = match (a.1, b.1) { (Some(x), Some(y)) => x.checked_add(y), _ => None, @@ -56,7 +57,7 @@ pub fn sub_scalar(sh: SizeHint, x: usize) -> SizeHint { /// ``` #[inline] pub fn mul(a: SizeHint, b: SizeHint) -> SizeHint { - let low = a.0.checked_mul(b.0).unwrap_or(usize::MAX); + let low = a.0.saturating_mul(b.0); let hi = match (a.1, b.1) { (Some(x), Some(y)) => x.checked_mul(y), (Some(0), None) | (None, Some(0)) => Some(0), @@ -74,6 +75,20 @@ pub fn mul_scalar(sh: SizeHint, x: usize) -> SizeHint { (low, hi) } +/// Raise `base` correctly by a **`SizeHint`** exponent. +#[inline] +pub fn pow_scalar_base(base: usize, exp: SizeHint) -> SizeHint { + let exp_low = cmp::min(exp.0, u32::MAX as usize) as u32; + let low = base.saturating_pow(exp_low); + + let hi = exp.1.and_then(|exp| { + let exp_hi = cmp::min(exp, u32::MAX as usize) as u32; + base.checked_pow(exp_hi) + }); + + (low, hi) +} + /// Return the maximum #[inline] pub fn max(a: SizeHint, b: SizeHint) -> SizeHint { diff --git a/src/sources.rs b/src/sources.rs index 17d9ff9..5bb6afe 100644 --- a/src/sources.rs +++ b/src/sources.rs @@ -7,7 +7,7 @@ use std::mem; /// See [`repeat_call`](../fn.repeat_call.html) for more information. #[derive(Clone)] -#[deprecated(note="Use std repeat_with() instead", since="0.8")] +#[deprecated(note="Use std repeat_with() instead", since="0.8.0")] pub struct RepeatCall<F> { f: F, } @@ -39,7 +39,7 @@ impl<F> fmt::Debug for RepeatCall<F> /// vec![1, 1, 1, 1, 1] /// ); /// ``` -#[deprecated(note="Use std repeat_with() instead", since="0.8")] +#[deprecated(note="Use std repeat_with() instead", since="0.8.0")] pub fn repeat_call<F, A>(function: F) -> RepeatCall<F> where F: FnMut() -> A { @@ -52,7 +52,7 @@ impl<A, F> Iterator for RepeatCall<F> type Item = A; #[inline] - fn next(&mut self) -> Option<A> { + fn next(&mut self) -> Option<Self::Item> { Some((self.f)()) } @@ -76,22 +76,21 @@ impl<A, F> Iterator for RepeatCall<F> /// /// use itertools::unfold; /// -/// let (mut x1, mut x2) = (1u32, 1u32); -/// let mut fibonacci = unfold((), move |_| { +/// let mut fibonacci = unfold((1u32, 1u32), |(x1, x2)| { /// // Attempt to get the next Fibonacci number -/// let next = x1.saturating_add(x2); +/// let next = x1.saturating_add(*x2); /// /// // Shift left: ret <- x1 <- x2 <- next -/// let ret = x1; -/// x1 = x2; -/// x2 = next; +/// let ret = *x1; +/// *x1 = *x2; +/// *x2 = next; /// /// // If addition has saturated at the maximum, we are finished -/// if ret == x1 && ret > 1 { -/// return None; +/// if ret == *x1 && ret > 1 { +/// None +/// } else { +/// Some(ret) /// } -/// -/// Some(ret) /// }); /// /// itertools::assert_equal(fibonacci.by_ref().take(8), @@ -128,15 +127,9 @@ impl<A, St, F> Iterator for Unfold<St, F> type Item = A; #[inline] - fn next(&mut self) -> Option<A> { + fn next(&mut self) -> Option<Self::Item> { (self.f)(&mut self.state) } - - #[inline] - fn size_hint(&self) -> (usize, Option<usize>) { - // no possible known bounds at this point - (0, None) - } } /// An iterator that infinitely applies function to value and yields results. @@ -1,8 +1,8 @@ use super::size_hint; use std::cell::RefCell; -use std::collections::VecDeque; -use std::rc::Rc; +use alloc::collections::VecDeque; +use alloc::rc::Rc; /// Common buffer object for the two tee halves #[derive(Debug)] @@ -39,7 +39,7 @@ impl<I> Iterator for Tee<I> I::Item: Clone { type Item = I::Item; - fn next(&mut self) -> Option<I::Item> { + fn next(&mut self) -> Option<Self::Item> { // .borrow_mut may fail here -- but only if the user has tied some kind of weird // knot where the iterator refers back to itself. let mut buffer = self.rcbuffer.borrow_mut(); diff --git a/src/tuple_impl.rs b/src/tuple_impl.rs index f205f01..1d24b0b 100644 --- a/src/tuple_impl.rs +++ b/src/tuple_impl.rs @@ -1,6 +1,9 @@ //! Some iterator that produces tuples use std::iter::Fuse; +use std::iter::Take; +use std::iter::Cycle; +use std::marker::PhantomData; // `HomogeneousTuple` is a public facade for `TupleCollect`, allowing // tuple-related methods to be used by clients in generic contexts, while @@ -54,12 +57,12 @@ impl<T> Iterator for TupleBuffer<T> fn size_hint(&self) -> (usize, Option<usize>) { let buffer = &self.buf.as_ref()[self.cur..]; - let len = if buffer.len() == 0 { + let len = if buffer.is_empty() { 0 } else { buffer.iter() .position(|x| x.is_none()) - .unwrap_or(buffer.len()) + .unwrap_or_else(|| buffer.len()) }; (len, Some(len)) } @@ -100,7 +103,7 @@ impl<I, T> Iterator for Tuples<I, T> { type Item = T; - fn next(&mut self) -> Option<T> { + fn next(&mut self) -> Option<Self::Item> { T::collect_from_iter(&mut self.iter, &mut self.buf) } } @@ -170,7 +173,7 @@ impl<I, T> Iterator for TupleWindows<I, T> { type Item = T; - fn next(&mut self) -> Option<T> { + fn next(&mut self) -> Option<Self::Item> { if T::num_items() == 1 { return T::collect_from_iter_no_buf(&mut self.iter) } @@ -184,6 +187,48 @@ impl<I, T> Iterator for TupleWindows<I, T> } } +/// 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 +/// information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +#[derive(Debug)] +pub struct CircularTupleWindows<I, T: Clone> + where I: Iterator<Item = T::Item> + Clone, + T: TupleCollect + Clone +{ + iter: Take<TupleWindows<Cycle<I>, T>>, + phantom_data: PhantomData<T> +} + +pub fn circular_tuple_windows<I, T>(iter: I) -> CircularTupleWindows<I, T> + where I: Iterator<Item = T::Item> + Clone + ExactSizeIterator, + T: TupleCollect + Clone, + T::Item: Clone +{ + let len = iter.len(); + let iter = tuple_windows(iter.cycle()).take(len); + + CircularTupleWindows { + iter, + phantom_data: PhantomData{} + } +} + +impl<I, T> Iterator for CircularTupleWindows<I, T> + where I: Iterator<Item = T::Item> + Clone, + T: TupleCollect + Clone, + T::Item: Clone +{ + type Item = T; + + fn next(&mut self) -> Option<Self::Item> { + self.iter.next() + } +} + pub trait TupleCollect: Sized { type Item; type Buffer: Default + AsRef<[Option<Self::Item>]> + AsMut<[Option<Self::Item>]>; @@ -199,16 +244,32 @@ pub trait TupleCollect: Sized { fn left_shift_push(&mut self, item: Self::Item); } +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,)*) => { + rev_for_each_ident!($m, $($i,)*); + $m!($i0); + }; +} + macro_rules! impl_tuple_collect { - () => (); - ($N:expr; $A:ident ; $($X:ident),* ; $($Y:ident),* ; $($Y_rev:ident),*) => ( - impl<$A> TupleCollect for ($($X),*,) { - type Item = $A; - type Buffer = [Option<$A>; $N - 1]; + ($dummy:ident,) => {}; // stop + ($dummy:ident, $($Y:ident,)*) => ( + impl_tuple_collect!($($Y,)*); + impl<A> TupleCollect for ($(ignore_ident!($Y, A),)*) { + type Item = A; + type Buffer = [Option<A>; count_ident!($($Y,)*) - 1]; #[allow(unused_assignments, unused_mut)] fn collect_from_iter<I>(iter: I, buf: &mut Self::Buffer) -> Option<Self> - where I: IntoIterator<Item = $A> + where I: IntoIterator<Item = A> { let mut iter = iter.into_iter(); $( @@ -236,44 +297,31 @@ macro_rules! impl_tuple_collect { return None; } - #[allow(unused_assignments)] fn collect_from_iter_no_buf<I>(iter: I) -> Option<Self> - where I: IntoIterator<Item = $A> + where I: IntoIterator<Item = A> { let mut iter = iter.into_iter(); - loop { - $( - let $Y = if let Some($Y) = iter.next() { - $Y - } else { - break; - }; - )* - return Some(($($Y),*,)) - } - return None; + Some(($( + { let $Y = iter.next()?; $Y }, + )*)) } fn num_items() -> usize { - $N + count_ident!($($Y,)*) } - fn left_shift_push(&mut self, item: $A) { + fn left_shift_push(&mut self, mut item: A) { use std::mem::replace; let &mut ($(ref mut $Y),*,) = self; - let tmp = item; - $( - let tmp = replace($Y_rev, tmp); - )* - drop(tmp); + macro_rules! replace_item{($i:ident) => { + item = replace($i, item); + }}; + rev_for_each_ident!(replace_item, $($Y,)*); + drop(item); } } ) } - -impl_tuple_collect!(1; A; A; a; a); -impl_tuple_collect!(2; A; A, A; a, b; b, a); -impl_tuple_collect!(3; A; A, A, A; a, b, c; c, b, a); -impl_tuple_collect!(4; A; A, A, A, A; a, b, c, d; d, c, b, a); +impl_tuple_collect!(dummy, a, b, c, d, e, f, g, h, i, j, k, l,); diff --git a/src/unique_impl.rs b/src/unique_impl.rs index cf8675c..14c14fc 100644 --- a/src/unique_impl.rs +++ b/src/unique_impl.rs @@ -54,7 +54,7 @@ impl<I, V, F> Iterator for UniqueBy<I, V, F> { type Item = I::Item; - fn next(&mut self) -> Option<I::Item> { + fn next(&mut self) -> Option<Self::Item> { while let Some(v) = self.iter.next() { let key = (self.f)(&v); if self.used.insert(key, ()).is_none() { @@ -76,13 +76,29 @@ impl<I, V, F> Iterator for UniqueBy<I, V, F> } } +impl<I, V, F> DoubleEndedIterator for UniqueBy<I, V, F> + where I: DoubleEndedIterator, + V: Eq + Hash, + F: FnMut(&I::Item) -> V +{ + fn next_back(&mut self) -> Option<Self::Item> { + while let Some(v) = self.iter.next_back() { + let key = (self.f)(&v); + if self.used.insert(key, ()).is_none() { + return Some(v); + } + } + None + } +} + impl<I> Iterator for Unique<I> where I: Iterator, I::Item: Eq + Hash + Clone { type Item = I::Item; - fn next(&mut self) -> Option<I::Item> { + fn next(&mut self) -> Option<Self::Item> { while let Some(v) = self.iter.iter.next() { if let Entry::Vacant(entry) = self.iter.used.entry(v) { let elt = entry.key().clone(); @@ -104,6 +120,22 @@ impl<I> Iterator for Unique<I> } } +impl<I> DoubleEndedIterator for Unique<I> + where I: DoubleEndedIterator, + I::Item: Eq + Hash + Clone +{ + fn next_back(&mut self) -> Option<Self::Item> { + while let Some(v) = self.iter.iter.next_back() { + if let Entry::Vacant(entry) = self.iter.used.entry(v) { + let elt = entry.key().clone(); + entry.insert(()); + return Some(elt); + } + } + None + } +} + /// An iterator adapter to filter out duplicate elements. /// /// See [`.unique()`](../trait.Itertools.html#method.unique) for more information. diff --git a/src/ziptuple.rs b/src/ziptuple.rs index 2dc3ea5..8f40193 100644 --- a/src/ziptuple.rs +++ b/src/ziptuple.rs @@ -98,6 +98,30 @@ macro_rules! impl_zip_iter { $B: ExactSizeIterator, )* { } + + #[allow(non_snake_case)] + impl<$($B),*> DoubleEndedIterator for Zip<($($B,)*)> where + $( + $B: DoubleEndedIterator + ExactSizeIterator, + )* + { + #[inline] + fn next_back(&mut self) -> Option<Self::Item> { + let ($(ref mut $B,)*) = self.t; + let size = *[$( $B.len(), )*].iter().min().unwrap(); + + $( + if $B.len() != size { + for _ in 0..$B.len() - size { $B.next_back(); } + } + )* + + match ($($B.next_back(),)*) { + ($(Some($B),)*) => Some(($($B,)*)), + _ => None, + } + } + } ); } @@ -109,3 +133,7 @@ impl_zip_iter!(A, B, C, D, E); impl_zip_iter!(A, B, C, D, E, F); impl_zip_iter!(A, B, C, D, E, F, G); impl_zip_iter!(A, B, C, D, E, F, G, H); +impl_zip_iter!(A, B, C, D, E, F, G, H, I); +impl_zip_iter!(A, B, C, D, E, F, G, H, I, J); +impl_zip_iter!(A, B, C, D, E, F, G, H, I, J, K); +impl_zip_iter!(A, B, C, D, E, F, G, H, I, J, K, L); diff --git a/tests/macros_hygiene.rs b/tests/macros_hygiene.rs new file mode 100644 index 0000000..d111124 --- /dev/null +++ b/tests/macros_hygiene.rs @@ -0,0 +1,13 @@ +#[test] +fn iproduct_hygiene() { + let _ = itertools::iproduct!(0..6); + let _ = itertools::iproduct!(0..6, 0..9); + let _ = itertools::iproduct!(0..6, 0..9, 0..12); +} + +#[test] +fn izip_hygiene() { + let _ = itertools::izip!(0..6); + let _ = itertools::izip!(0..6, 0..9); + let _ = itertools::izip!(0..6, 0..9, 0..12); +} diff --git a/tests/quick.rs b/tests/quick.rs index 683ba7a..e5bee17 100644 --- a/tests/quick.rs +++ b/tests/quick.rs @@ -5,9 +5,10 @@ use quickcheck as qc; use std::default::Default; +use std::num::Wrapping; use std::ops::Range; use std::cmp::{max, min, Ordering}; -use std::collections::HashSet; +use std::collections::{HashMap, HashSet}; use itertools::Itertools; use itertools::{ multizip, @@ -19,6 +20,7 @@ use itertools::free::{ cloned, enumerate, multipeek, + peek_nth, put_back, put_back_n, rciter, @@ -487,6 +489,15 @@ quickcheck! { exact_size(it) } + fn size_peek_nth(a: Iter<u16, Exact>, s: u8) -> bool { + let mut it = peek_nth(a); + // peek a few times + for n in 0..s { + it.peek_nth(n as usize); + } + exact_size(it) + } + fn equal_merge(a: Vec<i16>, b: Vec<i16>) -> bool { let mut sa = a.clone(); let mut sb = b.clone(); @@ -744,6 +755,29 @@ quickcheck! { } quickcheck! { + fn dedup_via_coalesce(a: Vec<i32>) -> bool { + let mut b = a.clone(); + b.dedup(); + itertools::equal( + &b, + a + .iter() + .coalesce(|x, y| { + if x==y { + Ok(x) + } else { + Err((x, y)) + } + }) + .fold(vec![], |mut v, n| { + v.push(n); + v + }) + ) + } +} + +quickcheck! { fn equal_dedup(a: Vec<i32>) -> bool { let mut b = a.clone(); b.dedup(); @@ -875,6 +909,13 @@ quickcheck! { } quickcheck! { + fn size_powerset(it: Iter<u8, Exact>) -> bool { + // Powerset cardinality gets large very quickly, limit input to keep test fast. + correct_size_hint(it.take(12).powerset()) + } +} + +quickcheck! { fn size_unique(it: Iter<i8>) -> bool { correct_size_hint(it.unique()) } @@ -1155,3 +1196,388 @@ quickcheck! { } } } + +quickcheck! { + fn consistent_grouping_map_with_by(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0` + + let lookup_grouping_map = a.iter().copied().map(|i| (i % modulo, i)).into_grouping_map().collect::<Vec<_>>(); + let lookup_grouping_map_by = a.iter().copied().into_grouping_map_by(|i| i % modulo).collect::<Vec<_>>(); + + assert_eq!(lookup_grouping_map, lookup_grouping_map_by); + } + + fn correct_grouping_map_by_aggregate_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo < 2 { 2 } else { modulo } as u64; // Avoid `% 0` + let lookup = a.iter() + .map(|&b| b as u64) // Avoid overflows + .into_grouping_map_by(|i| i % modulo) + .aggregate(|acc, &key, val| { + assert!(val % modulo == key); + if val % (modulo - 1) == 0 { + None + } else { + Some(acc.unwrap_or(0) + val) + } + }); + + let group_map_lookup = a.iter() + .map(|&b| b as u64) + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .filter_map(|(key, vals)| { + vals.into_iter().fold(None, |acc, val| { + if val % (modulo - 1) == 0 { + None + } else { + Some(acc.unwrap_or(0) + val) + } + }).map(|new_val| (key, new_val)) + }) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for m in 0..modulo { + assert_eq!( + lookup.get(&m).copied(), + a.iter() + .map(|&b| b as u64) + .filter(|&val| val % modulo == m) + .fold(None, |acc, val| { + if val % (modulo - 1) == 0 { + None + } else { + Some(acc.unwrap_or(0) + val) + } + }) + ); + } + } + + fn correct_grouping_map_by_fold_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo == 0 { 1 } else { modulo } as u64; // Avoid `% 0` + let lookup = a.iter().map(|&b| b as u64) // Avoid overflows + .into_grouping_map_by(|i| i % modulo) + .fold(0u64, |acc, &key, val| { + assert!(val % modulo == key); + acc + val + }); + + let group_map_lookup = a.iter() + .map(|&b| b as u64) + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().fold(0u64, |acc, val| acc + val))) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &sum) in lookup.iter() { + assert_eq!(sum, a.iter().map(|&b| b as u64).filter(|&val| val % modulo == key).sum::<u64>()); + } + } + + fn correct_grouping_map_by_fold_first_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo == 0 { 1 } else { modulo } as u64; // Avoid `% 0` + let lookup = a.iter().map(|&b| b as u64) // Avoid overflows + .into_grouping_map_by(|i| i % modulo) + .fold_first(|acc, &key, val| { + assert!(val % modulo == key); + acc + val + }); + + // TODO: Swap `fold1` with stdlib's `fold_first` when it's stabilized + let group_map_lookup = a.iter() + .map(|&b| b as u64) + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().fold1(|acc, val| acc + val).unwrap())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &sum) in lookup.iter() { + assert_eq!(sum, a.iter().map(|&b| b as u64).filter(|&val| val % modulo == key).sum::<u64>()); + } + } + + fn correct_grouping_map_by_collect_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0` + let lookup_grouping_map = a.iter().copied().into_grouping_map_by(|i| i % modulo).collect::<Vec<_>>(); + let lookup_group_map = a.iter().copied().map(|i| (i % modulo, i)).into_group_map(); + + assert_eq!(lookup_grouping_map, lookup_group_map); + } + + fn correct_grouping_map_by_max_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0` + let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).max(); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().max().unwrap())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &max) in lookup.iter() { + assert_eq!(Some(max), a.iter().copied().filter(|&val| val % modulo == key).max()); + } + } + + fn correct_grouping_map_by_max_by_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0` + let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).max_by(|_, v1, v2| v1.cmp(v2)); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().max_by(|v1, v2| v1.cmp(v2)).unwrap())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &max) in lookup.iter() { + assert_eq!(Some(max), a.iter().copied().filter(|&val| val % modulo == key).max_by(|v1, v2| v1.cmp(v2))); + } + } + + fn correct_grouping_map_by_max_by_key_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0` + let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).max_by_key(|_, &val| val); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().max_by_key(|&val| val).unwrap())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &max) in lookup.iter() { + assert_eq!(Some(max), a.iter().copied().filter(|&val| val % modulo == key).max_by_key(|&val| val)); + } + } + + fn correct_grouping_map_by_min_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0` + let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).min(); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().min().unwrap())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &min) in lookup.iter() { + assert_eq!(Some(min), a.iter().copied().filter(|&val| val % modulo == key).min()); + } + } + + fn correct_grouping_map_by_min_by_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0` + let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).min_by(|_, v1, v2| v1.cmp(v2)); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().min_by(|v1, v2| v1.cmp(v2)).unwrap())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &min) in lookup.iter() { + assert_eq!(Some(min), a.iter().copied().filter(|&val| val % modulo == key).min_by(|v1, v2| v1.cmp(v2))); + } + } + + fn correct_grouping_map_by_min_by_key_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0` + let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).min_by_key(|_, &val| val); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().min_by_key(|&val| val).unwrap())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &min) in lookup.iter() { + assert_eq!(Some(min), a.iter().copied().filter(|&val| val % modulo == key).min_by_key(|&val| val)); + } + } + + fn correct_grouping_map_by_minmax_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0` + let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).minmax(); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().minmax())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &minmax) in lookup.iter() { + assert_eq!(minmax, a.iter().copied().filter(|&val| val % modulo == key).minmax()); + } + } + + fn correct_grouping_map_by_minmax_by_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0` + let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).minmax_by(|_, v1, v2| v1.cmp(v2)); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().minmax_by(|v1, v2| v1.cmp(v2)))) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &minmax) in lookup.iter() { + assert_eq!(minmax, a.iter().copied().filter(|&val| val % modulo == key).minmax_by(|v1, v2| v1.cmp(v2))); + } + } + + fn correct_grouping_map_by_minmax_by_key_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0` + let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).minmax_by_key(|_, &val| val); + + let group_map_lookup = a.iter().copied() + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().minmax_by_key(|&val| val))) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &minmax) in lookup.iter() { + assert_eq!(minmax, a.iter().copied().filter(|&val| val % modulo == key).minmax_by_key(|&val| val)); + } + } + + fn correct_grouping_map_by_sum_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = if modulo == 0 { 1 } else { modulo } as u64; // Avoid `% 0` + let lookup = a.iter().map(|&b| b as u64) // Avoid overflows + .into_grouping_map_by(|i| i % modulo) + .sum(); + + let group_map_lookup = a.iter().map(|&b| b as u64) + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().sum())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &sum) in lookup.iter() { + assert_eq!(sum, a.iter().map(|&b| b as u64).filter(|&val| val % modulo == key).sum::<u64>()); + } + } + + fn correct_grouping_map_by_product_modulo_key(a: Vec<u8>, modulo: u8) -> () { + let modulo = Wrapping(if modulo == 0 { 1 } else { modulo } as u64); // Avoid `% 0` + let lookup = a.iter().map(|&b| Wrapping(b as u64)) // Avoid overflows + .into_grouping_map_by(|i| i % modulo) + .product(); + + let group_map_lookup = a.iter().map(|&b| Wrapping(b as u64)) + .map(|i| (i % modulo, i)) + .into_group_map() + .into_iter() + .map(|(key, vals)| (key, vals.into_iter().product::<Wrapping<u64>>())) + .collect::<HashMap<_,_>>(); + assert_eq!(lookup, group_map_lookup); + + for (&key, &prod) in lookup.iter() { + assert_eq!( + prod, + a.iter() + .map(|&b| Wrapping(b as u64)) + .filter(|&val| val % modulo == key) + .product::<Wrapping<u64>>() + ); + } + } + + // This should check that if multiple elements are equally minimum or maximum + // then `max`, `min` and `minmax` pick the first minimum and the last maximum. + // This is to be consistent with `std::iter::max` and `std::iter::min`. + fn correct_grouping_map_by_min_max_minmax_order_modulo_key() -> () { + use itertools::MinMaxResult; + + let lookup = (0..=10) + .into_grouping_map_by(|_| 0) + .max_by(|_, _, _| Ordering::Equal); + + assert_eq!(lookup[&0], 10); + + let lookup = (0..=10) + .into_grouping_map_by(|_| 0) + .min_by(|_, _, _| Ordering::Equal); + + assert_eq!(lookup[&0], 0); + + let lookup = (0..=10) + .into_grouping_map_by(|_| 0) + .minmax_by(|_, _, _| Ordering::Equal); + + assert_eq!(lookup[&0], MinMaxResult::MinMax(0, 10)); + } +} + +quickcheck! { + #[test] + fn counts(nums: Vec<isize>) -> TestResult { + let counts = nums.iter().counts(); + for (&item, &count) in counts.iter() { + if count <= 0 { + return TestResult::failed(); + } + if count != nums.iter().filter(|&x| x == item).count() { + return TestResult::failed(); + } + } + for item in nums.iter() { + if !counts.contains_key(item) { + return TestResult::failed(); + } + } + TestResult::passed() + } +} + +quickcheck! { + fn test_double_ended_zip_2(a: Vec<u8>, b: Vec<u8>) -> TestResult { + let mut x = + multizip((a.clone().into_iter(), b.clone().into_iter())) + .collect_vec(); + x.reverse(); + + let y = + multizip((a.into_iter(), b.into_iter())) + .rfold(Vec::new(), |mut vec, e| { vec.push(e); vec }); + + TestResult::from_bool(itertools::equal(x, y)) + } + + fn test_double_ended_zip_3(a: Vec<u8>, b: Vec<u8>, c: Vec<u8>) -> TestResult { + let mut x = + multizip((a.clone().into_iter(), b.clone().into_iter(), c.clone().into_iter())) + .collect_vec(); + x.reverse(); + + let y = + multizip((a.into_iter(), b.into_iter(), c.into_iter())) + .rfold(Vec::new(), |mut vec, e| { vec.push(e); vec }); + + TestResult::from_bool(itertools::equal(x, y)) + } +} diff --git a/tests/specializations.rs b/tests/specializations.rs index ef51bbe..bc337c2 100644 --- a/tests/specializations.rs +++ b/tests/specializations.rs @@ -1,6 +1,5 @@ -use itertools::{EitherOrBoth, Itertools}; +use itertools::Itertools; use std::fmt::Debug; -use std::ops::BitXor; use quickcheck::quickcheck; struct Unspecialized<I>(I); @@ -11,20 +10,14 @@ where type Item = I::Item; #[inline(always)] - fn next(&mut self) -> Option<I::Item> { + fn next(&mut self) -> Option<Self::Item> { self.0.next() } - - #[inline(always)] - fn size_hint(&self) -> (usize, Option<usize>) { - self.0.size_hint() - } } fn check_specialized<'a, V, IterItem, Iter, F>(iterator: &Iter, mapper: F) where V: Eq + Debug, - IterItem: 'a, Iter: Iterator<Item = IterItem> + Clone + 'a, F: Fn(Box<dyn Iterator<Item = IterItem> + 'a>) -> V, { @@ -34,27 +27,43 @@ where ) } -fn check_specialized_count_last_nth_sizeh<'a, IterItem, Iter>( +fn test_specializations<IterItem, Iter>( it: &Iter, - known_expected_size: Option<usize>, ) where - IterItem: 'a + Eq + Debug, - Iter: Iterator<Item = IterItem> + Clone + 'a, + IterItem: Eq + Debug + Clone, + Iter: Iterator<Item = IterItem> + Clone, { - let size = it.clone().count(); - if let Some(expected_size) = known_expected_size { - assert_eq!(size, expected_size); - } check_specialized(it, |i| i.count()); check_specialized(it, |i| i.last()); + check_specialized(it, |i| i.collect::<Vec<_>>()); + check_specialized(it, |i| { + let mut parameters_from_fold = vec![]; + let fold_result = i.fold(vec![], |mut acc, v: IterItem| { + parameters_from_fold.push((acc.clone(), v.clone())); + acc.push(v); + acc + }); + (parameters_from_fold, fold_result) + }); + check_specialized(it, |mut i| { + let mut parameters_from_all = vec![]; + let first = i.next(); + let all_result = i.all(|x| { + parameters_from_all.push(x.clone()); + Some(x)==first + }); + (parameters_from_all, all_result) + }); + let size = it.clone().count(); for n in 0..size + 2 { check_specialized(it, |mut i| i.nth(n)); } + // size_hint is a bit harder to check let mut it_sh = it.clone(); for n in 0..size + 2 { let len = it_sh.clone().count(); let (min, max) = it_sh.size_hint(); - assert_eq!((size - n.min(size)), len); + assert_eq!(size - n.min(size), len); assert!(min <= len); if let Some(max) = max { assert!(len <= max); @@ -63,87 +72,29 @@ fn check_specialized_count_last_nth_sizeh<'a, IterItem, Iter>( } } -fn check_specialized_fold_xor<'a, IterItem, Iter>(it: &Iter) -where - IterItem: 'a - + BitXor - + Eq - + Debug - + BitXor<<IterItem as BitXor>::Output, Output = <IterItem as BitXor>::Output> - + Clone, - <IterItem as BitXor>::Output: - BitXor<Output = <IterItem as BitXor>::Output> + Eq + Debug + Clone, - Iter: Iterator<Item = IterItem> + Clone + 'a, -{ - check_specialized(it, |mut i| { - let first = i.next().map(|f| f.clone() ^ (f.clone() ^ f)); - i.fold(first, |acc, v: IterItem| acc.map(move |a| v ^ a)) - }); -} - -fn put_back_test(test_vec: Vec<i32>, known_expected_size: Option<usize>) { - { - // Lexical lifetimes support - let pb = itertools::put_back(test_vec.iter()); - check_specialized_count_last_nth_sizeh(&pb, known_expected_size); - check_specialized_fold_xor(&pb); - } - - let mut pb = itertools::put_back(test_vec.into_iter()); - pb.put_back(1); - check_specialized_count_last_nth_sizeh(&pb, known_expected_size.map(|x| x + 1)); - check_specialized_fold_xor(&pb) -} - -#[test] -fn put_back() { - put_back_test(vec![7, 4, 1], Some(3)); -} - quickcheck! { fn put_back_qc(test_vec: Vec<i32>) -> () { - put_back_test(test_vec, None) + test_specializations(&itertools::put_back(test_vec.iter())); + let mut pb = itertools::put_back(test_vec.into_iter()); + pb.put_back(1); + test_specializations(&pb); } } -fn merge_join_by_test(i1: Vec<usize>, i2: Vec<usize>, known_expected_size: Option<usize>) { - let i1 = i1.into_iter(); - let i2 = i2.into_iter(); - let mjb = i1.clone().merge_join_by(i2.clone(), std::cmp::Ord::cmp); - check_specialized_count_last_nth_sizeh(&mjb, known_expected_size); - // Rust 1.24 compatibility: - fn eob_left_z(eob: EitherOrBoth<usize, usize>) -> usize { - eob.left().unwrap_or(0) - } - fn eob_right_z(eob: EitherOrBoth<usize, usize>) -> usize { - eob.left().unwrap_or(0) - } - fn eob_both_z(eob: EitherOrBoth<usize, usize>) -> usize { - let (a, b) = eob.both().unwrap_or((0, 0)); - assert_eq!(a, b); - a +quickcheck! { + fn merge_join_by_qc(i1: Vec<usize>, i2: Vec<usize>) -> () { + test_specializations(&i1.into_iter().merge_join_by(i2.into_iter(), std::cmp::Ord::cmp)); } - check_specialized_fold_xor(&mjb.clone().map(eob_left_z)); - check_specialized_fold_xor(&mjb.clone().map(eob_right_z)); - check_specialized_fold_xor(&mjb.clone().map(eob_both_z)); - - // And the other way around - let mjb = i2.merge_join_by(i1, std::cmp::Ord::cmp); - check_specialized_count_last_nth_sizeh(&mjb, known_expected_size); - check_specialized_fold_xor(&mjb.clone().map(eob_left_z)); - check_specialized_fold_xor(&mjb.clone().map(eob_right_z)); - check_specialized_fold_xor(&mjb.clone().map(eob_both_z)); } -#[test] -fn merge_join_by() { - let i1 = vec![1, 3, 5, 7, 8, 9]; - let i2 = vec![0, 3, 4, 5]; - merge_join_by_test(i1, i2, Some(8)); +quickcheck! { + fn map_into(v: Vec<u8>) -> () { + test_specializations(&v.into_iter().map_into::<u32>()); + } } quickcheck! { - fn merge_join_by_qc(i1: Vec<usize>, i2: Vec<usize>) -> () { - merge_join_by_test(i1, i2, None) + fn map_ok(v: Vec<Result<u8, char>>) -> () { + test_specializations(&v.into_iter().map_ok(|u| u.checked_add(1))); } } diff --git a/tests/test_std.rs b/tests/test_std.rs index ba07784..d1ff815 100644 --- a/tests/test_std.rs +++ b/tests/test_std.rs @@ -1,8 +1,15 @@ +use paste; use permutohedron; +use quickcheck as qc; +use rand::{distributions::{Distribution, Standard}, Rng, SeedableRng, rngs::StdRng}; +use rand::{seq::SliceRandom, thread_rng}; +use std::{cmp::min, fmt::Debug, marker::PhantomData}; use itertools as it; use crate::it::Itertools; +use crate::it::ExactlyOneError; use crate::it::multizip; use crate::it::multipeek; +use crate::it::peek_nth; use crate::it::free::rciter; use crate::it::free::put_back_n; use crate::it::FoldWhile; @@ -58,6 +65,9 @@ fn unique_by() { let xs = ["aaa", "bbbbb", "aa", "ccc", "bbbb", "aaaaa", "cccc"]; let ys = ["aaa", "bbbbb", "ccc"]; it::assert_equal(ys.iter(), xs.iter().unique_by(|x| x[..2].to_string())); + it::assert_equal(ys.iter(), xs.iter().rev().unique_by(|x| x[..2].to_string()).rev()); + let ys_rev = ["cccc", "aaaaa", "bbbb"]; + it::assert_equal(ys_rev.iter(), xs.iter().unique_by(|x| x[..2].to_string()).rev()); } #[test] @@ -65,9 +75,16 @@ fn unique() { let xs = [0, 1, 2, 3, 2, 1, 3]; let ys = [0, 1, 2, 3]; it::assert_equal(ys.iter(), xs.iter().unique()); + it::assert_equal(ys.iter(), xs.iter().rev().unique().rev()); + let ys_rev = [3, 1, 2, 0]; + it::assert_equal(ys_rev.iter(), xs.iter().unique().rev()); + let xs = [0, 1]; let ys = [0, 1]; it::assert_equal(ys.iter(), xs.iter().unique()); + it::assert_equal(ys.iter(), xs.iter().rev().unique().rev()); + let ys_rev = [1, 0]; + it::assert_equal(ys_rev.iter(), xs.iter().unique().rev()); } #[test] @@ -99,6 +116,26 @@ fn dedup() { } #[test] +fn coalesce() { + let data = vec![-1., -2., -3., 3., 1., 0., -1.]; + let it = data.iter().cloned().coalesce(|x, y| + if (x >= 0.) == (y >= 0.) { + Ok(x + y) + } else { + Err((x, y)) + } + ); + itertools::assert_equal(it.clone(), vec![-6., 4., -1.]); + assert_eq!( + it.fold(vec![], |mut v, n| { + v.push(n); + v + }), + vec![-6., 4., -1.] + ); +} + +#[test] fn dedup_by() { let xs = [(0, 0), (0, 1), (1, 1), (2, 1), (0, 2), (3, 1), (0, 3), (1, 3)]; let ys = [(0, 0), (0, 1), (0, 2), (3, 1), (0, 3)]; @@ -115,6 +152,33 @@ fn dedup_by() { } #[test] +fn dedup_with_count() { + let xs: [i32; 8] = [0, 1, 1, 1, 2, 1, 3, 3]; + let ys: [(usize, &i32); 5] = [(1, &0), (3, &1), (1, &2), (1, &1), (2, &3)]; + + it::assert_equal(ys.iter().cloned(), xs.iter().dedup_with_count()); + + let xs: [i32; 5] = [0, 0, 0, 0, 0]; + let ys: [(usize, &i32); 1] = [(5, &0)]; + + it::assert_equal(ys.iter().cloned(), xs.iter().dedup_with_count()); +} + + +#[test] +fn dedup_by_with_count() { + let xs = [(0, 0), (0, 1), (1, 1), (2, 1), (0, 2), (3, 1), (0, 3), (1, 3)]; + let ys = [(1, &(0, 0)), (3, &(0, 1)), (1, &(0, 2)), (1, &(3, 1)), (2, &(0, 3))]; + + it::assert_equal(ys.iter().cloned(), xs.iter().dedup_by_with_count(|x, y| x.1==y.1)); + + let xs = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]; + let ys = [( 5, &(0, 1))]; + + it::assert_equal(ys.iter().cloned(), xs.iter().dedup_by_with_count(|x, y| x.0==y.0)); +} + +#[test] fn all_equal() { assert!("".chars().all_equal()); assert!("A".chars().all_equal()); @@ -192,7 +256,7 @@ fn trait_pointers() { I: 'r + Iterator<Item=X> { type Item = X; - fn next(&mut self) -> Option<X> + fn next(&mut self) -> Option<Self::Item> { self.0.next() } @@ -285,6 +349,26 @@ fn join() { } #[test] +fn sorted_unstable_by() { + let sc = [3, 4, 1, 2].iter().cloned().sorted_by(|&a, &b| { + a.cmp(&b) + }); + it::assert_equal(sc, vec![1, 2, 3, 4]); + + let v = (0..5).sorted_unstable_by(|&a, &b| a.cmp(&b).reverse()); + it::assert_equal(v, vec![4, 3, 2, 1, 0]); +} + +#[test] +fn sorted_unstable_by_key() { + let sc = [3, 4, 1, 2].iter().cloned().sorted_unstable_by_key(|&x| x); + it::assert_equal(sc, vec![1, 2, 3, 4]); + + let v = (0..5).sorted_unstable_by_key(|&x| -x); + it::assert_equal(v, vec![4, 3, 2, 1, 0]); +} + +#[test] fn sorted_by() { let sc = [3, 4, 1, 2].iter().cloned().sorted_by(|&a, &b| { a.cmp(&b) @@ -295,6 +379,88 @@ fn sorted_by() { it::assert_equal(v, vec![4, 3, 2, 1, 0]); } +qc::quickcheck! { + fn k_smallest_range(n: u64, m: u16, k: u16) -> () { + // u16 is used to constrain k and m to 0..2¹⁶, + // otherwise the test could use too much memory. + let (k, m) = (k as u64, m as u64); + + // Generate a random permutation of n..n+m + let i = { + let mut v: Vec<u64> = (n..n.saturating_add(m)).collect(); + v.shuffle(&mut thread_rng()); + v.into_iter() + }; + + // Check that taking the k smallest elements yields n..n+min(k, m) + it::assert_equal( + i.k_smallest(k as usize), + n..n.saturating_add(min(k, m)) + ); + } +} + +#[derive(Clone, Debug)] +struct RandIter<T: 'static + Clone + Send, R: 'static + Clone + Rng + SeedableRng + Send = StdRng> { + idx: usize, + len: usize, + rng: R, + _t: PhantomData<T> +} + +impl<T: Clone + Send, R: Clone + Rng + SeedableRng + Send> Iterator for RandIter<T, R> +where Standard: Distribution<T> { + type Item = T; + fn next(&mut self) -> Option<T> { + if self.idx == self.len { + None + } else { + self.idx += 1; + Some(self.rng.gen()) + } + } +} + +impl<T: Clone + Send, R: Clone + Rng + SeedableRng + Send> qc::Arbitrary for RandIter<T, R> { + fn arbitrary<G: qc::Gen>(g: &mut G) -> Self { + RandIter { + idx: 0, + len: g.size(), + rng: R::seed_from_u64(g.next_u64()), + _t : PhantomData{}, + } + } +} + +// Check that taking the k smallest is the same as +// sorting then taking the k first elements +fn k_smallest_sort<I>(i: I, k: u16) -> () +where + I: Iterator + Clone, + I::Item: Ord + Debug, +{ + let j = i.clone(); + let k = k as usize; + it::assert_equal( + i.k_smallest(k), + j.sorted().take(k) + ) +} + +macro_rules! generic_test { + ($f:ident, $($t:ty),+) => { + $(paste::item! { + qc::quickcheck! { + fn [< $f _ $t >](i: RandIter<$t>, k: u16) -> () { + $f(i, k) + } + } + })+ + }; +} + +generic_test!(k_smallest_sort, u8, u16, u32, u64, i8, i16, i32, i64); + #[test] fn sorted_by_key() { let sc = [3, 4, 1, 2].iter().cloned().sorted_by_key(|&x| x); @@ -328,7 +494,6 @@ fn test_multipeek() { assert_eq!(mp.next(), Some(5)); assert_eq!(mp.next(), None); assert_eq!(mp.peek(), None); - } #[test] @@ -372,6 +537,70 @@ fn test_multipeek_peeking_next() { } #[test] +fn test_peek_nth() { + let nums = vec![1u8,2,3,4,5]; + + let iter = peek_nth(nums.iter().map(|&x| x)); + assert_eq!(nums, iter.collect::<Vec<_>>()); + + let mut iter = peek_nth(nums.iter().map(|&x| x)); + + assert_eq!(iter.peek_nth(0), Some(&1)); + assert_eq!(iter.peek_nth(0), Some(&1)); + assert_eq!(iter.next(), Some(1)); + + assert_eq!(iter.peek_nth(0), Some(&2)); + assert_eq!(iter.peek_nth(1), Some(&3)); + assert_eq!(iter.next(), Some(2)); + + assert_eq!(iter.peek_nth(0), Some(&3)); + assert_eq!(iter.peek_nth(1), Some(&4)); + assert_eq!(iter.peek_nth(2), Some(&5)); + assert_eq!(iter.peek_nth(3), None); + + assert_eq!(iter.next(), Some(3)); + assert_eq!(iter.next(), Some(4)); + + assert_eq!(iter.peek_nth(0), Some(&5)); + assert_eq!(iter.peek_nth(1), None); + assert_eq!(iter.next(), Some(5)); + assert_eq!(iter.next(), None); + + assert_eq!(iter.peek_nth(0), None); + assert_eq!(iter.peek_nth(1), None); +} + +#[test] +fn test_peek_nth_peeking_next() { + use it::PeekingNext; + let nums = vec![1u8,2,3,4,5,6,7]; + let mut iter = peek_nth(nums.iter().map(|&x| x)); + + assert_eq!(iter.peeking_next(|&x| x != 0), Some(1)); + assert_eq!(iter.next(), Some(2)); + + assert_eq!(iter.peek_nth(0), Some(&3)); + assert_eq!(iter.peek_nth(1), Some(&4)); + assert_eq!(iter.peeking_next(|&x| x == 3), Some(3)); + assert_eq!(iter.peek(), Some(&4)); + + assert_eq!(iter.peeking_next(|&x| x != 4), None); + assert_eq!(iter.peeking_next(|&x| x == 4), Some(4)); + assert_eq!(iter.peek_nth(0), Some(&5)); + assert_eq!(iter.peek_nth(1), Some(&6)); + + assert_eq!(iter.peeking_next(|&x| x != 5), None); + assert_eq!(iter.peek(), Some(&5)); + + assert_eq!(iter.peeking_next(|&x| x == 5), Some(5)); + assert_eq!(iter.peeking_next(|&x| x == 6), Some(6)); + assert_eq!(iter.peek_nth(0), Some(&7)); + assert_eq!(iter.peek_nth(1), None); + assert_eq!(iter.next(), Some(7)); + assert_eq!(iter.peek(), None); +} + +#[test] fn pad_using() { it::assert_equal((0..0).pad_using(1, |_| 1), 1..2); @@ -642,6 +871,23 @@ fn combinations_with_replacement() { } #[test] +fn powerset() { + it::assert_equal((0..0).powerset(), vec![vec![]]); + it::assert_equal((0..1).powerset(), vec![vec![], vec![0]]); + it::assert_equal((0..2).powerset(), vec![vec![], vec![0], vec![1], vec![0, 1]]); + it::assert_equal((0..3).powerset(), vec![ + vec![], + vec![0], vec![1], vec![2], + vec![0, 1], vec![0, 2], vec![1, 2], + vec![0, 1, 2] + ]); + + assert_eq!((0..4).powerset().count(), 1 << 4); + assert_eq!((0..8).powerset().count(), 1 << 8); + assert_eq!((0..16).powerset().count(), 1 << 16); +} + +#[test] fn diff_mismatch() { let a = vec![1, 2, 3, 4]; let b = vec![1.0, 5.0, 3.0, 4.0]; @@ -791,3 +1037,13 @@ fn tree_fold1() { assert_eq!(actual, expected); } } + +#[test] +fn exactly_one_question_mark_syntax_works() { + exactly_one_question_mark_return().unwrap_err(); +} + +fn exactly_one_question_mark_return() -> Result<(), ExactlyOneError<std::slice::Iter<'static, ()>>> { + [].iter().exactly_one()?; + Ok(()) +} diff --git a/tests/zip.rs b/tests/zip.rs index b1af52c..5801b42 100644 --- a/tests/zip.rs +++ b/tests/zip.rs @@ -1,6 +1,7 @@ use itertools::Itertools; use itertools::EitherOrBoth::{Both, Left, Right}; use itertools::free::zip_eq; +use itertools::multizip; #[test] fn zip_longest_fused() { @@ -40,6 +41,20 @@ fn test_double_ended_zip_longest() { assert_eq!(it.next(), None); } +#[test] +fn test_double_ended_zip() { + let xs = [1, 2, 3, 4, 5, 6]; + let ys = [1, 2, 3, 7]; + let a = xs.iter().map(|&x| x); + let b = ys.iter().map(|&x| x); + let mut it = multizip((a, b)); + assert_eq!(it.next_back(), Some((4, 7))); + assert_eq!(it.next_back(), Some((3, 3))); + assert_eq!(it.next_back(), Some((2, 2))); + assert_eq!(it.next_back(), Some((1, 1))); + assert_eq!(it.next_back(), None); +} + #[should_panic] #[test] @@ -60,4 +75,3 @@ fn zip_eq_panic2() zip_eq(&a, &b).count(); } - |