#![warn(missing_docs, clippy::default_numeric_fallback)]
#![crate_name = "itertools"]
#![cfg_attr(not(feature = "use_std"), no_std)]
#[cfg(not(feature = "use_std"))]
extern crate core as std;
#[cfg(feature = "use_alloc")]
extern crate alloc;
#[cfg(feature = "use_alloc")]
use alloc::{collections::VecDeque, string::String, vec::Vec};
pub use either::Either;
use core::borrow::Borrow;
use std::cmp::Ordering;
#[cfg(feature = "use_std")]
use std::collections::HashMap;
#[cfg(feature = "use_std")]
use std::collections::HashSet;
use std::fmt;
#[cfg(feature = "use_alloc")]
use std::fmt::Write;
#[cfg(feature = "use_std")]
use std::hash::Hash;
use std::iter::{once, IntoIterator};
#[cfg(feature = "use_alloc")]
type VecDequeIntoIter<T> = alloc::collections::vec_deque::IntoIter<T>;
#[cfg(feature = "use_alloc")]
type VecIntoIter<T> = alloc::vec::IntoIter<T>;
use std::iter::FromIterator;
#[macro_use]
mod impl_macros;
#[doc(hidden)]
pub use std::iter as __std_iter;
pub mod structs {
#[cfg(feature = "use_alloc")]
pub use crate::adaptors::MultiProduct;
pub use crate::adaptors::{
Batching, Coalesce, Dedup, DedupBy, DedupByWithCount, DedupWithCount, FilterMapOk,
FilterOk, Interleave, InterleaveShortest, MapInto, MapOk, Positions, Product, PutBack,
TakeWhileRef, TupleCombinations, Update, WhileSome,
};
#[cfg(feature = "use_alloc")]
pub use crate::combinations::Combinations;
#[cfg(feature = "use_alloc")]
pub use crate::combinations_with_replacement::CombinationsWithReplacement;
pub use crate::cons_tuples_impl::ConsTuples;
#[cfg(feature = "use_std")]
pub use crate::duplicates_impl::{Duplicates, DuplicatesBy};
pub use crate::exactly_one_err::ExactlyOneError;
pub use crate::flatten_ok::FlattenOk;
pub use crate::format::{Format, FormatWith};
#[allow(deprecated)]
#[cfg(feature = "use_alloc")]
pub use crate::groupbylazy::GroupBy;
#[cfg(feature = "use_alloc")]
pub use crate::groupbylazy::{Chunk, ChunkBy, Chunks, Group, Groups, IntoChunks};
#[cfg(feature = "use_std")]
pub use crate::grouping_map::{GroupingMap, GroupingMapBy};
pub use crate::intersperse::{Intersperse, IntersperseWith};
#[cfg(feature = "use_alloc")]
pub use crate::kmerge_impl::{KMerge, KMergeBy};
pub use crate::merge_join::{Merge, MergeBy, MergeJoinBy};
#[cfg(feature = "use_alloc")]
pub use crate::multipeek_impl::MultiPeek;
pub use crate::pad_tail::PadUsing;
#[cfg(feature = "use_alloc")]
pub use crate::peek_nth::PeekNth;
pub use crate::peeking_take_while::PeekingTakeWhile;
#[cfg(feature = "use_alloc")]
pub use crate::permutations::Permutations;
#[cfg(feature = "use_alloc")]
pub use crate::powerset::Powerset;
pub use crate::process_results_impl::ProcessResults;
#[cfg(feature = "use_alloc")]
pub use crate::put_back_n_impl::PutBackN;
#[cfg(feature = "use_alloc")]
pub use crate::rciter_impl::RcIter;
pub use crate::repeatn::RepeatN;
#[allow(deprecated)]
pub use crate::sources::{Iterate, Unfold};
pub use crate::take_while_inclusive::TakeWhileInclusive;
#[cfg(feature = "use_alloc")]
pub use crate::tee::Tee;
pub use crate::tuple_impl::{CircularTupleWindows, TupleBuffer, TupleWindows, Tuples};
#[cfg(feature = "use_std")]
pub use crate::unique_impl::{Unique, UniqueBy};
pub use crate::with_position::WithPosition;
pub use crate::zip_eq_impl::ZipEq;
pub use crate::zip_longest::ZipLongest;
pub use crate::ziptuple::Zip;
}
pub mod traits {
pub use crate::iter_index::IteratorIndex;
pub use crate::tuple_impl::HomogeneousTuple;
}
pub use crate::concat_impl::concat;
pub use crate::cons_tuples_impl::cons_tuples;
pub use crate::diff::diff_with;
pub use crate::diff::Diff;
#[cfg(feature = "use_alloc")]
pub use crate::kmerge_impl::kmerge_by;
pub use crate::minmax::MinMaxResult;
pub use crate::peeking_take_while::PeekingNext;
pub use crate::process_results_impl::process_results;
pub use crate::repeatn::repeat_n;
#[allow(deprecated)]
pub use crate::sources::{iterate, unfold};
#[allow(deprecated)]
pub use crate::structs::*;
pub use crate::unziptuple::{multiunzip, MultiUnzip};
pub use crate::with_position::Position;
pub use crate::ziptuple::multizip;
mod adaptors;
mod either_or_both;
pub use crate::either_or_both::EitherOrBoth;
#[doc(hidden)]
pub mod free;
#[doc(inline)]
pub use crate::free::*;
#[cfg(feature = "use_alloc")]
mod combinations;
#[cfg(feature = "use_alloc")]
mod combinations_with_replacement;
mod concat_impl;
mod cons_tuples_impl;
mod diff;
#[cfg(feature = "use_std")]
mod duplicates_impl;
mod exactly_one_err;
#[cfg(feature = "use_alloc")]
mod extrema_set;
mod flatten_ok;
mod format;
#[cfg(feature = "use_alloc")]
mod group_map;
#[cfg(feature = "use_alloc")]
mod groupbylazy;
#[cfg(feature = "use_std")]
mod grouping_map;
mod intersperse;
mod iter_index;
#[cfg(feature = "use_alloc")]
mod k_smallest;
#[cfg(feature = "use_alloc")]
mod kmerge_impl;
#[cfg(feature = "use_alloc")]
mod lazy_buffer;
mod merge_join;
mod minmax;
#[cfg(feature = "use_alloc")]
mod multipeek_impl;
mod pad_tail;
#[cfg(feature = "use_alloc")]
mod peek_nth;
mod peeking_take_while;
#[cfg(feature = "use_alloc")]
mod permutations;
#[cfg(feature = "use_alloc")]
mod powerset;
mod process_results_impl;
#[cfg(feature = "use_alloc")]
mod put_back_n_impl;
#[cfg(feature = "use_alloc")]
mod rciter_impl;
mod repeatn;
mod size_hint;
mod sources;
mod take_while_inclusive;
#[cfg(feature = "use_alloc")]
mod tee;
mod tuple_impl;
#[cfg(feature = "use_std")]
mod unique_impl;
mod unziptuple;
mod with_position;
mod zip_eq_impl;
mod zip_longest;
mod ziptuple;
#[macro_export]
macro_rules! iproduct {
(@flatten $I:expr,) => (
$I
);
(@flatten $I:expr, $J:expr, $($K:expr,)*) => (
$crate::iproduct!(@flatten $crate::cons_tuples($crate::iproduct!($I, $J)), $($K,)*)
);
() => (
$crate::__std_iter::once(())
);
($I:expr $(,)?) => (
$crate::__std_iter::IntoIterator::into_iter($I).map(|elt| (elt,))
);
($I:expr, $J:expr $(,)?) => (
$crate::Itertools::cartesian_product(
$crate::__std_iter::IntoIterator::into_iter($I),
$crate::__std_iter::IntoIterator::into_iter($J),
)
);
($I:expr, $J:expr, $($K:expr),+ $(,)?) => (
$crate::iproduct!(@flatten $crate::iproduct!($I, $J), $($K,)+)
);
}
#[macro_export]
macro_rules! izip {
( @closure $p:pat => $tup:expr ) => {
|$p| $tup
};
( @closure $p:pat => ( $($tup:tt)* ) , $_iter:expr $( , $tail:expr )* ) => {
$crate::izip!(@closure ($p, b) => ( $($tup)*, b ) $( , $tail )*)
};
($first:expr $(,)*) => {
$crate::__std_iter::IntoIterator::into_iter($first)
};
($first:expr, $second:expr $(,)*) => {
$crate::izip!($first)
.zip($second)
};
( $first:expr $( , $rest:expr )* $(,)* ) => {
$crate::izip!($first)
$(
.zip($rest)
)*
.map(
$crate::izip!(@closure a => (a) $( , $rest )*)
)
};
}
#[macro_export]
macro_rules! chain {
() => {
core::iter::empty()
};
($first:expr $(, $rest:expr )* $(,)?) => {
{
let iter = core::iter::IntoIterator::into_iter($first);
$(
let iter =
core::iter::Iterator::chain(
iter,
core::iter::IntoIterator::into_iter($rest));
)*
iter
}
};
}
pub trait Itertools: Iterator {
fn interleave<J>(self, other: J) -> Interleave<Self, J::IntoIter>
where
J: IntoIterator<Item = Self::Item>,
Self: Sized,
{
interleave(self, other)
}
fn interleave_shortest<J>(self, other: J) -> InterleaveShortest<Self, J::IntoIter>
where
J: IntoIterator<Item = Self::Item>,
Self: Sized,
{
adaptors::interleave_shortest(self, other.into_iter())
}
fn intersperse(self, element: Self::Item) -> Intersperse<Self>
where
Self: Sized,
Self::Item: Clone,
{
intersperse::intersperse(self, element)
}
fn intersperse_with<F>(self, element: F) -> IntersperseWith<Self, F>
where
Self: Sized,
F: FnMut() -> Self::Item,
{
intersperse::intersperse_with(self, element)
}
fn get<R>(self, index: R) -> R::Output
where
Self: Sized,
R: traits::IteratorIndex<Self>,
{
iter_index::get(self, index)
}
#[inline]
fn zip_longest<J>(self, other: J) -> ZipLongest<Self, J::IntoIter>
where
J: IntoIterator,
Self: Sized,
{
zip_longest::zip_longest(self, other.into_iter())
}
#[inline]
fn zip_eq<J>(self, other: J) -> ZipEq<Self, J::IntoIter>
where
J: IntoIterator,
Self: Sized,
{
zip_eq(self, other)
}
fn batching<B, F>(self, f: F) -> Batching<Self, F>
where
F: FnMut(&mut Self) -> Option<B>,
Self: Sized,
{
adaptors::batching(self, f)
}
#[cfg(feature = "use_alloc")]
fn chunk_by<K, F>(self, key: F) -> ChunkBy<K, Self, F>
where
Self: Sized,
F: FnMut(&Self::Item) -> K,
K: PartialEq,
{
groupbylazy::new(self, key)
}
#[deprecated(note = "Use .chunk_by() instead", since = "0.13.0")]
#[cfg(feature = "use_alloc")]
fn group_by<K, F>(self, key: F) -> ChunkBy<K, Self, F>
where
Self: Sized,
F: FnMut(&Self::Item) -> K,
K: PartialEq,
{
self.chunk_by(key)
}
#[cfg(feature = "use_alloc")]
fn chunks(self, size: usize) -> IntoChunks<Self>
where
Self: Sized,
{
assert!(size != 0);
groupbylazy::new_chunks(self, size)
}
fn tuple_windows<T>(self) -> TupleWindows<Self, T>
where
Self: Sized + Iterator<Item = T::Item>,
T: traits::HomogeneousTuple,
T::Item: Clone,
{
tuple_impl::tuple_windows(self)
}
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)
}
fn tuples<T>(self) -> Tuples<Self, T>
where
Self: Sized + Iterator<Item = T::Item>,
T: traits::HomogeneousTuple,
{
tuple_impl::tuples(self)
}
#[cfg(feature = "use_alloc")]
fn tee(self) -> (Tee<Self>, Tee<Self>)
where
Self: Sized,
Self::Item: Clone,
{
tee::new(self)
}
fn map_into<R>(self) -> MapInto<Self, R>
where
Self: Sized,
Self::Item: Into<R>,
{
adaptors::map_into(self)
}
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_ok(self, f)
}
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)
}
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)
}
fn flatten_ok<T, E>(self) -> FlattenOk<Self, T, E>
where
Self: Iterator<Item = Result<T, E>> + Sized,
T: IntoIterator,
{
flatten_ok::flatten_ok(self)
}
fn process_results<F, T, E, R>(self, processor: F) -> Result<R, E>
where
Self: Iterator<Item = Result<T, E>> + Sized,
F: FnOnce(ProcessResults<Self, E>) -> R,
{
process_results(self, processor)
}
fn merge<J>(self, other: J) -> Merge<Self, J::IntoIter>
where
Self: Sized,
Self::Item: PartialOrd,
J: IntoIterator<Item = Self::Item>,
{
merge(self, other)
}
fn merge_by<J, F>(self, other: J, is_first: F) -> MergeBy<Self, J::IntoIter, F>
where
Self: Sized,
J: IntoIterator<Item = Self::Item>,
F: FnMut(&Self::Item, &Self::Item) -> bool,
{
merge_join::merge_by_new(self, other, is_first)
}
#[inline]
fn merge_join_by<J, F, T>(self, other: J, cmp_fn: F) -> MergeJoinBy<Self, J::IntoIter, F>
where
J: IntoIterator,
F: FnMut(&Self::Item, &J::Item) -> T,
Self: Sized,
{
merge_join_by(self, other, cmp_fn)
}
#[cfg(feature = "use_alloc")]
fn kmerge(self) -> KMerge<<Self::Item as IntoIterator>::IntoIter>
where
Self: Sized,
Self::Item: IntoIterator,
<Self::Item as IntoIterator>::Item: PartialOrd,
{
kmerge(self)
}
#[cfg(feature = "use_alloc")]
fn kmerge_by<F>(self, first: F) -> KMergeBy<<Self::Item as IntoIterator>::IntoIter, F>
where
Self: Sized,
Self::Item: IntoIterator,
F: FnMut(&<Self::Item as IntoIterator>::Item, &<Self::Item as IntoIterator>::Item) -> bool,
{
kmerge_by(self, first)
}
fn cartesian_product<J>(self, other: J) -> Product<Self, J::IntoIter>
where
Self: Sized,
Self::Item: Clone,
J: IntoIterator,
J::IntoIter: Clone,
{
adaptors::cartesian_product(self, other.into_iter())
}
#[cfg(feature = "use_alloc")]
fn multi_cartesian_product(self) -> MultiProduct<<Self::Item as IntoIterator>::IntoIter>
where
Self: Sized,
Self::Item: IntoIterator,
<Self::Item as IntoIterator>::IntoIter: Clone,
<Self::Item as IntoIterator>::Item: Clone,
{
adaptors::multi_cartesian_product(self)
}
fn coalesce<F>(self, f: F) -> Coalesce<Self, F>
where
Self: Sized,
F: FnMut(Self::Item, Self::Item) -> Result<Self::Item, (Self::Item, Self::Item)>,
{
adaptors::coalesce(self, f)
}
fn dedup(self) -> Dedup<Self>
where
Self: Sized,
Self::Item: PartialEq,
{
adaptors::dedup(self)
}
fn dedup_by<Cmp>(self, cmp: Cmp) -> DedupBy<Self, Cmp>
where
Self: Sized,
Cmp: FnMut(&Self::Item, &Self::Item) -> bool,
{
adaptors::dedup_by(self, cmp)
}
fn dedup_with_count(self) -> DedupWithCount<Self>
where
Self: Sized,
{
adaptors::dedup_with_count(self)
}
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)
}
#[cfg(feature = "use_std")]
fn duplicates(self) -> Duplicates<Self>
where
Self: Sized,
Self::Item: Eq + Hash,
{
duplicates_impl::duplicates(self)
}
#[cfg(feature = "use_std")]
fn duplicates_by<V, F>(self, f: F) -> DuplicatesBy<Self, V, F>
where
Self: Sized,
V: Eq + Hash,
F: FnMut(&Self::Item) -> V,
{
duplicates_impl::duplicates_by(self, f)
}
#[cfg(feature = "use_std")]
fn unique(self) -> Unique<Self>
where
Self: Sized,
Self::Item: Clone + Eq + Hash,
{
unique_impl::unique(self)
}
#[cfg(feature = "use_std")]
fn unique_by<V, F>(self, f: F) -> UniqueBy<Self, V, F>
where
Self: Sized,
V: Eq + Hash,
F: FnMut(&Self::Item) -> V,
{
unique_impl::unique_by(self, f)
}
fn peeking_take_while<F>(&mut self, accept: F) -> PeekingTakeWhile<Self, F>
where
Self: Sized + PeekingNext,
F: FnMut(&Self::Item) -> bool,
{
peeking_take_while::peeking_take_while(self, accept)
}
fn take_while_ref<F>(&mut self, accept: F) -> TakeWhileRef<Self, F>
where
Self: Clone,
F: FnMut(&Self::Item) -> bool,
{
adaptors::take_while_ref(self, accept)
}
fn take_while_inclusive<F>(self, accept: F) -> TakeWhileInclusive<Self, F>
where
Self: Sized,
F: FnMut(&Self::Item) -> bool,
{
take_while_inclusive::TakeWhileInclusive::new(self, accept)
}
fn while_some<A>(self) -> WhileSome<Self>
where
Self: Sized + Iterator<Item = Option<A>>,
{
adaptors::while_some(self)
}
fn tuple_combinations<T>(self) -> TupleCombinations<Self, T>
where
Self: Sized + Clone,
Self::Item: Clone,
T: adaptors::HasCombination<Self>,
{
adaptors::tuple_combinations(self)
}
#[cfg(feature = "use_alloc")]
fn combinations(self, k: usize) -> Combinations<Self>
where
Self: Sized,
Self::Item: Clone,
{
combinations::combinations(self, k)
}
#[cfg(feature = "use_alloc")]
fn combinations_with_replacement(self, k: usize) -> CombinationsWithReplacement<Self>
where
Self: Sized,
Self::Item: Clone,
{
combinations_with_replacement::combinations_with_replacement(self, k)
}
#[cfg(feature = "use_alloc")]
fn permutations(self, k: usize) -> Permutations<Self>
where
Self: Sized,
Self::Item: Clone,
{
permutations::permutations(self, k)
}
#[cfg(feature = "use_alloc")]
fn powerset(self) -> Powerset<Self>
where
Self: Sized,
Self::Item: Clone,
{
powerset::powerset(self)
}
fn pad_using<F>(self, min: usize, f: F) -> PadUsing<Self, F>
where
Self: Sized,
F: FnMut(usize) -> Self::Item,
{
pad_tail::pad_using(self, min, f)
}
fn with_position(self) -> WithPosition<Self>
where
Self: Sized,
{
with_position::with_position(self)
}
fn positions<P>(self, predicate: P) -> Positions<Self, P>
where
Self: Sized,
P: FnMut(Self::Item) -> bool,
{
adaptors::positions(self, predicate)
}
fn update<F>(self, updater: F) -> Update<Self, F>
where
Self: Sized,
F: FnMut(&mut Self::Item),
{
adaptors::update(self, updater)
}
fn next_tuple<T>(&mut self) -> Option<T>
where
Self: Sized + Iterator<Item = T::Item>,
T: traits::HomogeneousTuple,
{
T::collect_from_iter_no_buf(self)
}
fn collect_tuple<T>(mut self) -> Option<T>
where
Self: Sized + Iterator<Item = T::Item>,
T: traits::HomogeneousTuple,
{
match self.next_tuple() {
elt @ Some(_) => match self.next() {
Some(_) => None,
None => elt,
},
_ => None,
}
}
fn find_position<P>(&mut self, mut pred: P) -> Option<(usize, Self::Item)>
where
P: FnMut(&Self::Item) -> bool,
{
self.enumerate().find(|(_, elt)| pred(elt))
}
fn find_or_last<P>(mut self, mut predicate: P) -> Option<Self::Item>
where
Self: Sized,
P: FnMut(&Self::Item) -> bool,
{
let mut prev = None;
self.find_map(|x| {
if predicate(&x) {
Some(x)
} else {
prev = Some(x);
None
}
})
.or(prev)
}
fn find_or_first<P>(mut self, mut predicate: P) -> Option<Self::Item>
where
Self: Sized,
P: FnMut(&Self::Item) -> bool,
{
let first = self.next()?;
Some(if predicate(&first) {
first
} else {
self.find(|x| predicate(x)).unwrap_or(first)
})
}
fn contains<Q>(&mut self, query: &Q) -> bool
where
Self: Sized,
Self::Item: Borrow<Q>,
Q: PartialEq,
{
self.any(|x| x.borrow() == query)
}
fn all_equal(&mut self) -> bool
where
Self: Sized,
Self::Item: PartialEq,
{
match self.next() {
None => true,
Some(a) => self.all(|x| a == x),
}
}
#[allow(clippy::type_complexity)]
fn all_equal_value(&mut self) -> Result<Self::Item, Option<(Self::Item, Self::Item)>>
where
Self: Sized,
Self::Item: PartialEq,
{
let first = self.next().ok_or(None)?;
let other = self.find(|x| x != &first);
if let Some(other) = other {
Err(Some((first, other)))
} else {
Ok(first)
}
}
#[cfg(feature = "use_std")]
fn all_unique(&mut self) -> bool
where
Self: Sized,
Self::Item: Eq + Hash,
{
let mut used = HashSet::new();
self.all(move |elt| used.insert(elt))
}
fn dropping(mut self, n: usize) -> Self
where
Self: Sized,
{
if n > 0 {
self.nth(n - 1);
}
self
}
fn dropping_back(mut self, n: usize) -> Self
where
Self: Sized + DoubleEndedIterator,
{
if n > 0 {
(&mut self).rev().nth(n - 1);
}
self
}
fn concat(self) -> Self::Item
where
Self: Sized,
Self::Item:
Extend<<<Self as Iterator>::Item as IntoIterator>::Item> + IntoIterator + Default,
{
concat(self)
}
#[cfg(feature = "use_alloc")]
fn collect_vec(self) -> Vec<Self::Item>
where
Self: Sized,
{
self.collect()
}
fn try_collect<T, U, E>(self) -> Result<U, E>
where
Self: Sized + Iterator<Item = Result<T, E>>,
Result<U, E>: FromIterator<Result<T, E>>,
{
self.collect()
}
#[inline]
fn set_from<'a, A: 'a, J>(&mut self, from: J) -> usize
where
Self: Iterator<Item = &'a mut A>,
J: IntoIterator<Item = A>,
{
from.into_iter()
.zip(self)
.map(|(new, old)| *old = new)
.count()
}
#[cfg(feature = "use_alloc")]
fn join(&mut self, sep: &str) -> String
where
Self::Item: std::fmt::Display,
{
match self.next() {
None => String::new(),
Some(first_elt) => {
let (lower, _) = self.size_hint();
let mut result = String::with_capacity(sep.len() * lower);
write!(&mut result, "{}", first_elt).unwrap();
self.for_each(|elt| {
result.push_str(sep);
write!(&mut result, "{}", elt).unwrap();
});
result
}
}
}
fn format(self, sep: &str) -> Format<Self>
where
Self: Sized,
{
format::new_format_default(self, sep)
}
fn format_with<F>(self, sep: &str, format: F) -> FormatWith<Self, F>
where
Self: Sized,
F: FnMut(Self::Item, &mut dyn FnMut(&dyn fmt::Display) -> fmt::Result) -> fmt::Result,
{
format::new_format(self, sep, format)
}
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,
{
for elt in self {
match elt {
Ok(v) => start = f(start, v),
Err(u) => return Err(u),
}
}
Ok(start)
}
fn fold_options<A, B, F>(&mut self, mut start: B, mut f: F) -> Option<B>
where
Self: Iterator<Item = Option<A>>,
F: FnMut(B, A) -> B,
{
for elt in self {
match elt {
Some(v) => start = f(start, v),
None => return None,
}
}
Some(start)
}
#[deprecated(
note = "Use [`Iterator::reduce`](https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.reduce) instead",
since = "0.10.2"
)]
fn fold1<F>(mut self, f: F) -> Option<Self::Item>
where
F: FnMut(Self::Item, Self::Item) -> Self::Item,
Self: Sized,
{
self.next().map(move |x| self.fold(x, f))
}
fn tree_reduce<F>(mut self, mut f: F) -> Option<Self::Item>
where
F: FnMut(Self::Item, Self::Item) -> Self::Item,
Self: Sized,
{
type State<T> = Result<T, Option<T>>;
fn inner0<T, II, FF>(it: &mut II, f: &mut FF) -> State<T>
where
II: Iterator<Item = T>,
FF: FnMut(T, T) -> T,
{
let a = if let Some(v) = it.next() {
v
} else {
return Err(None);
};
let b = if let Some(v) = it.next() {
v
} else {
return Err(Some(a));
};
Ok(f(a, b))
}
fn inner<T, II, FF>(stop: usize, it: &mut II, f: &mut FF) -> State<T>
where
II: Iterator<Item = T>,
FF: FnMut(T, T) -> T,
{
let mut x = inner0(it, f)?;
for height in 0..stop {
let next = if height == 0 {
inner0(it, f)
} else {
inner(height, it, f)
};
match next {
Ok(y) => x = f(x, y),
Err(None) => return Err(Some(x)),
Err(Some(y)) => return Err(Some(f(x, y))),
}
}
Ok(x)
}
match inner(usize::MAX, &mut self, &mut f) {
Err(x) => x,
_ => unreachable!(),
}
}
#[deprecated(note = "Use .tree_reduce() instead", since = "0.13.0")]
fn tree_fold1<F>(self, f: F) -> Option<Self::Item>
where
F: FnMut(Self::Item, Self::Item) -> Self::Item,
Self: Sized,
{
self.tree_reduce(f)
}
fn fold_while<B, F>(&mut self, init: B, mut f: F) -> FoldWhile<B>
where
Self: Sized,
F: FnMut(B, Self::Item) -> FoldWhile<B>,
{
use Result::{Err as Break, Ok as Continue};
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),
}
}
fn sum1<S>(mut self) -> Option<S>
where
Self: Sized,
S: std::iter::Sum<Self::Item>,
{
self.next().map(|first| once(first).chain(self).sum())
}
fn product1<P>(mut self) -> Option<P>
where
Self: Sized,
P: std::iter::Product<Self::Item>,
{
self.next().map(|first| once(first).chain(self).product())
}
#[cfg(feature = "use_alloc")]
fn sorted_unstable(self) -> VecIntoIter<Self::Item>
where
Self: Sized,
Self::Item: Ord,
{
let mut v = Vec::from_iter(self);
v.sort_unstable();
v.into_iter()
}
#[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()
}
#[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()
}
#[cfg(feature = "use_alloc")]
fn sorted(self) -> VecIntoIter<Self::Item>
where
Self: Sized,
Self::Item: Ord,
{
let mut v = Vec::from_iter(self);
v.sort();
v.into_iter()
}
#[cfg(feature = "use_alloc")]
fn sorted_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_by(cmp);
v.into_iter()
}
#[cfg(feature = "use_alloc")]
fn sorted_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_by_key(f);
v.into_iter()
}
#[cfg(feature = "use_alloc")]
fn sorted_by_cached_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_by_cached_key(f);
v.into_iter()
}
#[cfg(feature = "use_alloc")]
fn k_smallest(self, k: usize) -> VecIntoIter<Self::Item>
where
Self: Sized,
Self::Item: Ord,
{
use alloc::collections::BinaryHeap;
if k == 0 {
self.last();
return Vec::new().into_iter();
}
if k == 1 {
return self.min().into_iter().collect_vec().into_iter();
}
let mut iter = self.fuse();
let mut heap: BinaryHeap<_> = iter.by_ref().take(k).collect();
iter.for_each(|i| {
debug_assert_eq!(heap.len(), k);
if *heap.peek().unwrap() > i {
*heap.peek_mut().unwrap() = i;
}
});
heap.into_sorted_vec().into_iter()
}
#[cfg(feature = "use_alloc")]
fn k_smallest_by<F>(self, k: usize, cmp: F) -> VecIntoIter<Self::Item>
where
Self: Sized,
F: FnMut(&Self::Item, &Self::Item) -> Ordering,
{
k_smallest::k_smallest_general(self, k, cmp).into_iter()
}
#[cfg(feature = "use_alloc")]
fn k_smallest_by_key<F, K>(self, k: usize, key: F) -> VecIntoIter<Self::Item>
where
Self: Sized,
F: FnMut(&Self::Item) -> K,
K: Ord,
{
self.k_smallest_by(k, k_smallest::key_to_cmp(key))
}
#[cfg(feature = "use_alloc")]
fn k_largest(self, k: usize) -> VecIntoIter<Self::Item>
where
Self: Sized,
Self::Item: Ord,
{
self.k_largest_by(k, Self::Item::cmp)
}
#[cfg(feature = "use_alloc")]
fn k_largest_by<F>(self, k: usize, mut cmp: F) -> VecIntoIter<Self::Item>
where
Self: Sized,
F: FnMut(&Self::Item, &Self::Item) -> Ordering,
{
self.k_smallest_by(k, move |a, b| cmp(b, a))
}
#[cfg(feature = "use_alloc")]
fn k_largest_by_key<F, K>(self, k: usize, key: F) -> VecIntoIter<Self::Item>
where
Self: Sized,
F: FnMut(&Self::Item) -> K,
K: Ord,
{
self.k_largest_by(k, k_smallest::key_to_cmp(key))
}
#[cfg(feature = "use_alloc")]
fn tail(self, n: usize) -> VecDequeIntoIter<Self::Item>
where
Self: Sized,
{
match n {
0 => {
self.last();
VecDeque::new()
}
1 => self.last().into_iter().collect(),
_ => {
let (low, _) = self.size_hint();
let mut iter = self.fuse().skip(low.saturating_sub(n));
let mut data: Vec<_> = iter.by_ref().take(n).collect();
let idx = iter.fold(0, |i, val| {
debug_assert_eq!(data.len(), n);
data[i] = val;
if i + 1 == n {
0
} else {
i + 1
}
});
let mut data = VecDeque::from(data);
data.rotate_left(idx);
data
}
}
.into_iter()
}
fn partition_map<A, B, F, L, R>(self, mut predicate: F) -> (A, B)
where
Self: Sized,
F: FnMut(Self::Item) -> Either<L, R>,
A: Default + Extend<L>,
B: Default + Extend<R>,
{
let mut left = A::default();
let mut right = B::default();
self.for_each(|val| match predicate(val) {
Either::Left(v) => left.extend(Some(v)),
Either::Right(v) => right.extend(Some(v)),
});
(left, right)
}
fn partition_result<A, B, T, E>(self) -> (A, B)
where
Self: Iterator<Item = Result<T, E>> + Sized,
A: Default + Extend<T>,
B: Default + Extend<E>,
{
self.partition_map(|r| match r {
Ok(v) => Either::Left(v),
Err(v) => Either::Right(v),
})
}
#[cfg(feature = "use_std")]
fn into_group_map<K, V>(self) -> HashMap<K, Vec<V>>
where
Self: Iterator<Item = (K, V)> + Sized,
K: Hash + Eq,
{
group_map::into_group_map(self)
}
#[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: FnMut(&V) -> K,
{
group_map::into_group_map_by(self, f)
}
#[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)
}
#[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::new_map_for_grouping(self, key_mapper))
}
#[cfg(feature = "use_alloc")]
fn min_set(self) -> Vec<Self::Item>
where
Self: Sized,
Self::Item: Ord,
{
extrema_set::min_set_impl(self, |_| (), |x, y, _, _| x.cmp(y))
}
#[cfg(feature = "use_alloc")]
fn min_set_by<F>(self, mut compare: F) -> Vec<Self::Item>
where
Self: Sized,
F: FnMut(&Self::Item, &Self::Item) -> Ordering,
{
extrema_set::min_set_impl(self, |_| (), |x, y, _, _| compare(x, y))
}
#[cfg(feature = "use_alloc")]
fn min_set_by_key<K, F>(self, key: F) -> Vec<Self::Item>
where
Self: Sized,
K: Ord,
F: FnMut(&Self::Item) -> K,
{
extrema_set::min_set_impl(self, key, |_, _, kx, ky| kx.cmp(ky))
}
#[cfg(feature = "use_alloc")]
fn max_set(self) -> Vec<Self::Item>
where
Self: Sized,
Self::Item: Ord,
{
extrema_set::max_set_impl(self, |_| (), |x, y, _, _| x.cmp(y))
}
#[cfg(feature = "use_alloc")]
fn max_set_by<F>(self, mut compare: F) -> Vec<Self::Item>
where
Self: Sized,
F: FnMut(&Self::Item, &Self::Item) -> Ordering,
{
extrema_set::max_set_impl(self, |_| (), |x, y, _, _| compare(x, y))
}
#[cfg(feature = "use_alloc")]
fn max_set_by_key<K, F>(self, key: F) -> Vec<Self::Item>
where
Self: Sized,
K: Ord,
F: FnMut(&Self::Item) -> K,
{
extrema_set::max_set_impl(self, key, |_, _, kx, ky| kx.cmp(ky))
}
fn minmax(self) -> MinMaxResult<Self::Item>
where
Self: Sized,
Self::Item: PartialOrd,
{
minmax::minmax_impl(self, |_| (), |x, y, _, _| x < y)
}
fn minmax_by_key<K, F>(self, key: F) -> MinMaxResult<Self::Item>
where
Self: Sized,
K: PartialOrd,
F: FnMut(&Self::Item) -> K,
{
minmax::minmax_impl(self, key, |_, _, xk, yk| xk < yk)
}
fn minmax_by<F>(self, mut compare: F) -> MinMaxResult<Self::Item>
where
Self: Sized,
F: FnMut(&Self::Item, &Self::Item) -> Ordering,
{
minmax::minmax_impl(self, |_| (), |x, y, _, _| Ordering::Less == compare(x, y))
}
fn position_max(self) -> Option<usize>
where
Self: Sized,
Self::Item: Ord,
{
self.enumerate()
.max_by(|x, y| Ord::cmp(&x.1, &y.1))
.map(|x| x.0)
}
fn position_max_by_key<K, F>(self, mut key: F) -> Option<usize>
where
Self: Sized,
K: Ord,
F: FnMut(&Self::Item) -> K,
{
self.enumerate()
.max_by(|x, y| Ord::cmp(&key(&x.1), &key(&y.1)))
.map(|x| x.0)
}
fn position_max_by<F>(self, mut compare: F) -> Option<usize>
where
Self: Sized,
F: FnMut(&Self::Item, &Self::Item) -> Ordering,
{
self.enumerate()
.max_by(|x, y| compare(&x.1, &y.1))
.map(|x| x.0)
}
fn position_min(self) -> Option<usize>
where
Self: Sized,
Self::Item: Ord,
{
self.enumerate()
.min_by(|x, y| Ord::cmp(&x.1, &y.1))
.map(|x| x.0)
}
fn position_min_by_key<K, F>(self, mut key: F) -> Option<usize>
where
Self: Sized,
K: Ord,
F: FnMut(&Self::Item) -> K,
{
self.enumerate()
.min_by(|x, y| Ord::cmp(&key(&x.1), &key(&y.1)))
.map(|x| x.0)
}
fn position_min_by<F>(self, mut compare: F) -> Option<usize>
where
Self: Sized,
F: FnMut(&Self::Item, &Self::Item) -> Ordering,
{
self.enumerate()
.min_by(|x, y| compare(&x.1, &y.1))
.map(|x| x.0)
}
fn position_minmax(self) -> MinMaxResult<usize>
where
Self: Sized,
Self::Item: PartialOrd,
{
use crate::MinMaxResult::{MinMax, NoElements, OneElement};
match minmax::minmax_impl(self.enumerate(), |_| (), |x, y, _, _| x.1 < y.1) {
NoElements => NoElements,
OneElement(x) => OneElement(x.0),
MinMax(x, y) => MinMax(x.0, y.0),
}
}
fn position_minmax_by_key<K, F>(self, mut key: F) -> MinMaxResult<usize>
where
Self: Sized,
K: PartialOrd,
F: FnMut(&Self::Item) -> K,
{
use crate::MinMaxResult::{MinMax, NoElements, OneElement};
match self.enumerate().minmax_by_key(|e| key(&e.1)) {
NoElements => NoElements,
OneElement(x) => OneElement(x.0),
MinMax(x, y) => MinMax(x.0, y.0),
}
}
fn position_minmax_by<F>(self, mut compare: F) -> MinMaxResult<usize>
where
Self: Sized,
F: FnMut(&Self::Item, &Self::Item) -> Ordering,
{
use crate::MinMaxResult::{MinMax, NoElements, OneElement};
match self.enumerate().minmax_by(|x, y| compare(&x.1, &y.1)) {
NoElements => NoElements,
OneElement(x) => OneElement(x.0),
MinMax(x, y) => MinMax(x.0, y.0),
}
}
fn exactly_one(mut self) -> Result<Self::Item, ExactlyOneError<Self>>
where
Self: Sized,
{
match self.next() {
Some(first) => match self.next() {
Some(second) => Err(ExactlyOneError::new(
Some(Either::Left([first, second])),
self,
)),
None => Ok(first),
},
None => Err(ExactlyOneError::new(None, self)),
}
}
fn at_most_one(mut self) -> Result<Option<Self::Item>, ExactlyOneError<Self>>
where
Self: Sized,
{
match self.next() {
Some(first) => match self.next() {
Some(second) => Err(ExactlyOneError::new(
Some(Either::Left([first, second])),
self,
)),
None => Ok(Some(first)),
},
None => Ok(None),
}
}
#[cfg(feature = "use_alloc")]
fn multipeek(self) -> MultiPeek<Self>
where
Self: Sized,
{
multipeek_impl::multipeek(self)
}
#[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
}
#[cfg(feature = "use_std")]
fn counts_by<K, F>(self, f: F) -> HashMap<K, usize>
where
Self: Sized,
K: Eq + Hash,
F: FnMut(Self::Item) -> K,
{
self.map(f).counts()
}
fn multiunzip<FromI>(self) -> FromI
where
Self: Sized + MultiUnzip<FromI>,
{
MultiUnzip::multiunzip(self)
}
fn try_len(&self) -> Result<usize, size_hint::SizeHint> {
let sh = self.size_hint();
match sh {
(lo, Some(hi)) if lo == hi => Ok(lo),
_ => Err(sh),
}
}
}
impl<T> Itertools for T where T: Iterator + ?Sized {}
pub fn equal<I, J>(a: I, b: J) -> bool
where
I: IntoIterator,
J: IntoIterator,
I::Item: PartialEq<J::Item>,
{
a.into_iter().eq(b)
}
pub fn assert_equal<I, J>(a: I, b: J)
where
I: IntoIterator,
J: IntoIterator,
I::Item: fmt::Debug + PartialEq<J::Item>,
J::Item: fmt::Debug,
{
let mut ia = a.into_iter();
let mut ib = b.into_iter();
let mut i: usize = 0;
loop {
match (ia.next(), ib.next()) {
(None, None) => return,
(a, b) => {
let equal = match (&a, &b) {
(Some(a), Some(b)) => a == b,
_ => false,
};
assert!(
equal,
"Failed assertion {a:?} == {b:?} for iteration {i}",
i = i,
a = a,
b = b
);
i += 1;
}
}
}
}
pub fn partition<'a, A: 'a, I, F>(iter: I, mut pred: F) -> usize
where
I: IntoIterator<Item = &'a mut A>,
I::IntoIter: DoubleEndedIterator,
F: FnMut(&A) -> bool,
{
let mut split_index = 0;
let mut iter = iter.into_iter();
while let Some(front) = iter.next() {
if !pred(front) {
match iter.rfind(|back| pred(back)) {
Some(back) => std::mem::swap(front, back),
None => break,
}
}
split_index += 1;
}
split_index
}
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub enum FoldWhile<T> {
Continue(T),
Done(T),
}
impl<T> FoldWhile<T> {
pub fn into_inner(self) -> T {
match self {
Self::Continue(x) | Self::Done(x) => x,
}
}
pub fn is_done(&self) -> bool {
match *self {
Self::Continue(_) => false,
Self::Done(_) => true,
}
}
}