use std::fmt; use std::iter::FusedIterator; use crate::size_hint; pub struct CoalesceBy where I: Iterator, { iter: I, last: Option, f: F, } impl Clone for CoalesceBy where I: Iterator, { clone_fields!(last, iter, f); } impl fmt::Debug for CoalesceBy where I: Iterator + fmt::Debug, T: fmt::Debug, { debug_fmt_fields!(CoalesceBy, iter); } pub trait CoalescePredicate { fn coalesce_pair(&mut self, t: T, item: Item) -> Result; } impl Iterator for CoalesceBy where I: Iterator, F: CoalescePredicate, { type Item = T; fn next(&mut self) -> Option { // this fuses the iterator let last = self.last.take()?; let self_last = &mut self.last; let self_f = &mut self.f; Some( self.iter .try_fold(last, |last, next| match self_f.coalesce_pair(last, next) { Ok(joined) => Ok(joined), Err((last_, next_)) => { *self_last = Some(next_); Err(last_) } }) .unwrap_or_else(|x| x), ) } fn size_hint(&self) -> (usize, Option) { let (low, hi) = size_hint::add_scalar(self.iter.size_hint(), self.last.is_some() as usize); ((low > 0) as usize, hi) } fn fold(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, T> FusedIterator for CoalesceBy {} /// An iterator adaptor that may join together adjacent elements. /// /// See [`.coalesce()`](crate::Itertools::coalesce) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub type Coalesce = CoalesceBy::Item>; impl CoalescePredicate for F where F: FnMut(T, Item) -> Result, { fn coalesce_pair(&mut self, t: T, item: Item) -> Result { self(t, item) } } /// Create a new `Coalesce`. pub fn coalesce(mut iter: I, f: F) -> Coalesce 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()`](crate::Itertools::dedup_by) or [`.dedup()`](crate::Itertools::dedup) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub type DedupBy = CoalesceBy, ::Item>; #[derive(Clone)] pub struct DedupPred2CoalescePred(DP); impl fmt::Debug for DedupPred2CoalescePred { debug_fmt_fields!(DedupPred2CoalescePred,); } pub trait DedupPredicate { // TODO replace by Fn(&T, &T)->bool once Rust supports it fn dedup_pair(&mut self, a: &T, b: &T) -> bool; } impl CoalescePredicate for DedupPred2CoalescePred where DP: DedupPredicate, { fn coalesce_pair(&mut self, t: T, item: T) -> Result { if self.0.dedup_pair(&t, &item) { Ok(t) } else { Err((t, item)) } } } #[derive(Clone, Debug)] pub struct DedupEq; impl DedupPredicate for DedupEq { fn dedup_pair(&mut self, a: &T, b: &T) -> bool { a == b } } impl bool> DedupPredicate for F { fn dedup_pair(&mut self, a: &T, b: &T) -> bool { self(a, b) } } /// Create a new `DedupBy`. pub fn dedup_by(mut iter: I, dedup_pred: Pred) -> DedupBy where I: Iterator, { DedupBy { last: iter.next(), iter, f: DedupPred2CoalescePred(dedup_pred), } } /// An iterator adaptor that removes repeated duplicates. /// /// See [`.dedup()`](crate::Itertools::dedup) for more information. pub type Dedup = DedupBy; /// Create a new `Dedup`. pub fn dedup(iter: I) -> Dedup 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()`](crate::Itertools::dedup_by_with_count) or /// [`.dedup_with_count()`](crate::Itertools::dedup_with_count) for more information. #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub type DedupByWithCount = CoalesceBy, (usize, ::Item)>; #[derive(Clone, Debug)] pub struct DedupPredWithCount2CoalescePred(DP); impl CoalescePredicate for DedupPredWithCount2CoalescePred where DP: DedupPredicate, { 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()`](crate::Itertools::dedup_with_count) for more information. pub type DedupWithCount = DedupByWithCount; /// Create a new `DedupByWithCount`. pub fn dedup_by_with_count(mut iter: I, dedup_pred: Pred) -> DedupByWithCount 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(iter: I) -> DedupWithCount where I: Iterator, { dedup_by_with_count(iter, DedupEq) }