Snap for 7263361 from 16514b8f2782005df002eb2e0e0cb0e957b6e694 to sc-v2-release
Change-Id: I020bc8b648415be695968aa71f766d21d1ee87f0
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"
diff --git a/Android.bp b/Android.bp
index cc98d26..963b929 100644
--- a/Android.bp
+++ b/Android.bp
@@ -45,6 +45,7 @@
edition: "2018",
features: [
"default",
+ "use_alloc",
"use_std",
],
rustlibs: [
diff --git a/Cargo.toml b/Cargo.toml
index d8a9b8c..ffe2f37 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -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 @@
[[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 @@
[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 @@
[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 @@
[features]
default = ["use_std"]
-use_std = []
+use_std = ["use_alloc"]
+use_alloc = []
[profile]
bench = { debug = true }
@@ -66,3 +68,11 @@
[[bench]]
name = "bench1"
harness = false
+
+[[bench]]
+name = "combinations"
+harness = false
+
+[[bench]]
+name = "powerset"
+harness = false
diff --git a/METADATA b/METADATA
index a2c5dd7..b617903 100644
--- a/METADATA
+++ b/METADATA
@@ -7,13 +7,13 @@
}
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
}
}
diff --git a/README.rst b/README.rst
index 24c99d3..4e37007 100644
--- a/README.rst
+++ b/README.rst
@@ -21,7 +21,7 @@
.. 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 @@
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 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_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_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_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_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_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_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_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 @@
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 @@
// 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 @@
///
/// `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 @@
{
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 @@
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 @@
{
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 @@
}
}
-
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 @@
{
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 @@
/// 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 @@
{
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 @@
{
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 @@
}
}
-#[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 @@
{
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 @@
}
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 @@
{
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 @@
}
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 @@
)
}
-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);
+// 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 apply `Into` conversion to each element.
+/// 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> {
- iter: I,
- _res: PhantomData<fn() -> R>,
-}
-
-/// Create a new [`MapInto`](struct.MapInto.html) iterator.
-pub fn map_into<I, R>(iter: I) -> MapInto<I, R> {
- MapInto {
- iter,
- _res: PhantomData,
- }
-}
-
-impl<I, R> Iterator for MapInto<I, R>
- where I: Iterator,
- I::Item: Into<R>,
-{
- type Item = R;
-
- fn next(&mut self) -> Option<R> {
- self.iter
- .next()
- .map(|i| i.into())
- }
-
- 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,
- {
- self.iter.fold(init, move |acc, v| fold_f(acc, v.into()))
- }
-}
-
-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())
- }
-}
-
-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`.
-///
-/// See [`.map_results()`](../trait.Itertools.html#method.map_results) for more information.
-#[derive(Clone)]
-#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
-pub struct MapResults<I, F> {
+pub struct FilterOk<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>
+/// 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) -> U,
+ F: FnMut(&T) -> bool,
{
- MapResults {
+ FilterOk {
iter,
f,
}
}
-impl<I, F, T, U, E> Iterator for MapResults<I, F>
+impl<I, F, T, E> Iterator for FilterOk<I, F>
where I: Iterator<Item = Result<T, E>>,
- F: FnMut(T) -> U,
+ F: FnMut(&T) -> bool,
{
- type Item = Result<U, E>;
+ type Item = Result<T, 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 (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(|v| {
+ v.as_ref().map(&mut f).unwrap_or(true)
+ }).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(|v| {
+ v.as_ref().map(&mut f).unwrap_or(true)
+ }).collect()
+ }
+}
+
+/// An iterator adapter to filter and apply a transformation on values within a nested `Result::Ok`.
+///
+/// See [`.filter_map_ok()`](../trait.Itertools.html#method.filter_map_ok) for more information.
+#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
+pub struct FilterMapOk<I, F> {
+ iter: I,
+ f: 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) -> Option<U>,
+{
+ FilterMapOk {
+ iter,
+ f,
+ }
+}
+
+impl<I, F, T, U, E> Iterator for FilterMapOk<I, F>
+ where I: Iterator<Item = Result<T, E>>,
+ F: FnMut(T) -> Option<U>,
+{
+ type Item = Result<U, E>;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ 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>) {
+ (0, self.iter.size_hint().1)
+ }
+
+ 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.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.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 @@
}
fn count(self) -> usize {
- if self.0.len() == 0 {
+ if self.0.is_empty() {
return 0;
}
@@ -183,7 +185,7 @@
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 @@
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 @@
}
}
+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 @@
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 @@
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 @@
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 @@
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 @@
// 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 @@
// 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 @@
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 @@
);
);
-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 @@
/// 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 @@
///
/// 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 @@
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 @@
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;
- }
- if self.first_two.1.is_some() {
- additional_len += 1;
- }
- size_hint::add_scalar(self.inner.size_hint(), additional_len)
+ 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")
+ }
+ }
+}
+
+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)
+ }
+ }
+ }
+}
+
+#[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 @@
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_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 @@
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 @@
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 @@
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 @@
///
/// 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 @@
///
/// 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 @@
{
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 @@
/// This iterator is *fused*.
///
/// See [`.intersperse()`](../trait.Itertools.html#method.intersperse) for more information.
-#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
-#[derive(Debug)]
-pub struct Intersperse<I>
- where I: Iterator
+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,
{
- element: I::Item,
+ 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(Clone, Debug)]
+pub struct IntersperseWith<I, ElemF>
+ where I: Iterator,
+{
+ 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 @@
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 @@
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 @@
}
}
}
+
+ 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>
diff --git a/src/lib.rs b/src/lib.rs
index b8daefd..2ef7bd9 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -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::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 use crate::adaptors::{
Dedup,
DedupBy,
+ DedupWithCount,
+ DedupByWithCount,
Interleave,
InterleaveShortest,
+ FilterMapOk,
+ FilterOk,
Product,
PutBack,
Batching,
MapInto,
- MapResults,
+ MapOk,
Merge,
MergeBy,
TakeWhileRef,
@@ -95,39 +108,45 @@
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::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 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 @@
$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 @@
// 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 @@
// 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 @@
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 @@
/// }
/// 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 @@
/// 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 @@
/// ```
/// 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 @@
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 @@
/// 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 @@
/// 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 @@
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 @@
/// 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 @@
/// 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 @@
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 @@
/// 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 @@
/// 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 @@
/// 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 @@
/// 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 @@
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 @@
/// 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 @@
/// 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 @@
/// 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 @@
/// 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 @@
/// 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 @@
///
/// 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 @@
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 @@
// 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 @@
}
/// 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 @@
///
/// 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 @@
/// `.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 @@
/// 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 @@
/// 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 @@
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 @@
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 @@
/// 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 @@
/// 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 @@
/// 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 @@
.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 @@
/// 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 @@
/// 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 @@
/// 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 @@
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 @@
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 @@
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 @@
{
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 @@
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 @@
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 @@
}
}
-#[cfg(feature = "use_std")]
+#[cfg(feature = "use_alloc")]
impl<I> PeekingNext for PutBackN<I>
where I: Iterator,
{
@@ -104,8 +104,7 @@
}
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, 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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
}
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> 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 @@
{
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 @@
// 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 @@
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 @@
/// 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 @@
/// ```
#[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 @@
(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 @@
/// 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 @@
/// 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 @@
type Item = A;
#[inline]
- fn next(&mut self) -> Option<A> {
+ fn next(&mut self) -> Option<Self::Item> {
Some((self.f)())
}
@@ -76,22 +76,21 @@
///
/// 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 @@
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.
diff --git a/src/tee.rs b/src/tee.rs
index aa4be41..0b00302 100644
--- a/src/tee.rs
+++ b/src/tee.rs
@@ -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 @@
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 @@
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 @@
{
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 @@
{
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 @@
}
}
+/// 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 @@
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 @@
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 @@
{
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> 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> 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 @@
$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, 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 @@
cloned,
enumerate,
multipeek,
+ peek_nth,
put_back,
put_back_n,
rciter,
@@ -487,6 +489,15 @@
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! {
+ 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! {
+ 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! {
+ 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 @@
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 @@
)
}
-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_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
- }
- 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 merge_join_by_qc(i1: Vec<usize>, i2: Vec<usize>) -> () {
- merge_join_by_test(i1, i2, None)
+ test_specializations(&i1.into_iter().merge_join_by(i2.into_iter(), std::cmp::Ord::cmp));
+ }
+}
+
+quickcheck! {
+ fn map_into(v: Vec<u8>) -> () {
+ test_specializations(&v.into_iter().map_into::<u32>());
+ }
+}
+
+quickcheck! {
+ 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 @@
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 @@
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 @@
}
#[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 @@
}
#[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 @@
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 @@
}
#[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 @@
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 @@
assert_eq!(mp.next(), Some(5));
assert_eq!(mp.next(), None);
assert_eq!(mp.peek(), None);
-
}
#[test]
@@ -372,6 +537,70 @@
}
#[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 @@
}
#[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 @@
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 @@
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 @@
zip_eq(&a, &b).count();
}
-