itertools/adaptors/
coalesce.rs

1use std::fmt;
2use std::iter::FusedIterator;
3
4use crate::size_hint;
5
6#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
7pub struct CoalesceBy<I, F, C>
8where
9    I: Iterator,
10    C: CountItem<I::Item>,
11{
12    iter: I,
13    /// `last` is `None` while no item have been taken out of `iter` (at definition).
14    /// Then `last` will be `Some(Some(item))` until `iter` is exhausted,
15    /// in which case `last` will be `Some(None)`.
16    last: Option<Option<C::CItem>>,
17    f: F,
18}
19
20impl<I, F, C> Clone for CoalesceBy<I, F, C>
21where
22    I: Clone + Iterator,
23    F: Clone,
24    C: CountItem<I::Item>,
25    C::CItem: Clone,
26{
27    clone_fields!(last, iter, f);
28}
29
30impl<I, F, C> fmt::Debug for CoalesceBy<I, F, C>
31where
32    I: Iterator + fmt::Debug,
33    C: CountItem<I::Item>,
34    C::CItem: fmt::Debug,
35{
36    debug_fmt_fields!(CoalesceBy, iter, last);
37}
38
39pub trait CoalescePredicate<Item, T> {
40    fn coalesce_pair(&mut self, t: T, item: Item) -> Result<T, (T, T)>;
41}
42
43impl<I, F, C> Iterator for CoalesceBy<I, F, C>
44where
45    I: Iterator,
46    F: CoalescePredicate<I::Item, C::CItem>,
47    C: CountItem<I::Item>,
48{
49    type Item = C::CItem;
50
51    fn next(&mut self) -> Option<Self::Item> {
52        let Self { iter, last, f } = self;
53        // this fuses the iterator
54        let init = match last {
55            Some(elt) => elt.take(),
56            None => {
57                *last = Some(None);
58                iter.next().map(C::new)
59            }
60        }?;
61
62        Some(
63            iter.try_fold(init, |accum, next| match f.coalesce_pair(accum, next) {
64                Ok(joined) => Ok(joined),
65                Err((last_, next_)) => {
66                    *last = Some(Some(next_));
67                    Err(last_)
68                }
69            })
70            .unwrap_or_else(|x| x),
71        )
72    }
73
74    fn size_hint(&self) -> (usize, Option<usize>) {
75        let (low, hi) = size_hint::add_scalar(
76            self.iter.size_hint(),
77            matches!(self.last, Some(Some(_))) as usize,
78        );
79        ((low > 0) as usize, hi)
80    }
81
82    fn fold<Acc, FnAcc>(self, acc: Acc, mut fn_acc: FnAcc) -> Acc
83    where
84        FnAcc: FnMut(Acc, Self::Item) -> Acc,
85    {
86        let Self {
87            mut iter,
88            last,
89            mut f,
90        } = self;
91        if let Some(last) = last.unwrap_or_else(|| iter.next().map(C::new)) {
92            let (last, acc) = iter.fold((last, acc), |(last, acc), elt| {
93                match f.coalesce_pair(last, elt) {
94                    Ok(joined) => (joined, acc),
95                    Err((last_, next_)) => (next_, fn_acc(acc, last_)),
96                }
97            });
98            fn_acc(acc, last)
99        } else {
100            acc
101        }
102    }
103}
104
105impl<I, F, C> FusedIterator for CoalesceBy<I, F, C>
106where
107    I: Iterator,
108    F: CoalescePredicate<I::Item, C::CItem>,
109    C: CountItem<I::Item>,
110{
111}
112
113pub struct NoCount;
114
115pub struct WithCount;
116
117pub trait CountItem<T> {
118    type CItem;
119    fn new(t: T) -> Self::CItem;
120}
121
122impl<T> CountItem<T> for NoCount {
123    type CItem = T;
124    #[inline(always)]
125    fn new(t: T) -> T {
126        t
127    }
128}
129
130impl<T> CountItem<T> for WithCount {
131    type CItem = (usize, T);
132    #[inline(always)]
133    fn new(t: T) -> (usize, T) {
134        (1, t)
135    }
136}
137
138/// An iterator adaptor that may join together adjacent elements.
139///
140/// See [`.coalesce()`](crate::Itertools::coalesce) for more information.
141pub type Coalesce<I, F> = CoalesceBy<I, F, NoCount>;
142
143impl<F, Item, T> CoalescePredicate<Item, T> for F
144where
145    F: FnMut(T, Item) -> Result<T, (T, T)>,
146{
147    fn coalesce_pair(&mut self, t: T, item: Item) -> Result<T, (T, T)> {
148        self(t, item)
149    }
150}
151
152/// Create a new `Coalesce`.
153pub fn coalesce<I, F>(iter: I, f: F) -> Coalesce<I, F>
154where
155    I: Iterator,
156{
157    Coalesce {
158        last: None,
159        iter,
160        f,
161    }
162}
163
164/// An iterator adaptor that removes repeated duplicates, determining equality using a comparison function.
165///
166/// See [`.dedup_by()`](crate::Itertools::dedup_by) or [`.dedup()`](crate::Itertools::dedup) for more information.
167pub type DedupBy<I, Pred> = CoalesceBy<I, DedupPred2CoalescePred<Pred>, NoCount>;
168
169#[derive(Clone)]
170pub struct DedupPred2CoalescePred<DP>(DP);
171
172impl<DP> fmt::Debug for DedupPred2CoalescePred<DP> {
173    debug_fmt_fields!(DedupPred2CoalescePred,);
174}
175
176pub trait DedupPredicate<T> {
177    // TODO replace by Fn(&T, &T)->bool once Rust supports it
178    fn dedup_pair(&mut self, a: &T, b: &T) -> bool;
179}
180
181impl<DP, T> CoalescePredicate<T, T> for DedupPred2CoalescePred<DP>
182where
183    DP: DedupPredicate<T>,
184{
185    fn coalesce_pair(&mut self, t: T, item: T) -> Result<T, (T, T)> {
186        if self.0.dedup_pair(&t, &item) {
187            Ok(t)
188        } else {
189            Err((t, item))
190        }
191    }
192}
193
194#[derive(Clone, Debug)]
195pub struct DedupEq;
196
197impl<T: PartialEq> DedupPredicate<T> for DedupEq {
198    fn dedup_pair(&mut self, a: &T, b: &T) -> bool {
199        a == b
200    }
201}
202
203impl<T, F: FnMut(&T, &T) -> bool> DedupPredicate<T> for F {
204    fn dedup_pair(&mut self, a: &T, b: &T) -> bool {
205        self(a, b)
206    }
207}
208
209/// Create a new `DedupBy`.
210pub fn dedup_by<I, Pred>(iter: I, dedup_pred: Pred) -> DedupBy<I, Pred>
211where
212    I: Iterator,
213{
214    DedupBy {
215        last: None,
216        iter,
217        f: DedupPred2CoalescePred(dedup_pred),
218    }
219}
220
221/// An iterator adaptor that removes repeated duplicates.
222///
223/// See [`.dedup()`](crate::Itertools::dedup) for more information.
224pub type Dedup<I> = DedupBy<I, DedupEq>;
225
226/// Create a new `Dedup`.
227pub fn dedup<I>(iter: I) -> Dedup<I>
228where
229    I: Iterator,
230{
231    dedup_by(iter, DedupEq)
232}
233
234/// An iterator adaptor that removes repeated duplicates, while keeping a count of how many
235/// repeated elements were present. This will determine equality using a comparison function.
236///
237/// See [`.dedup_by_with_count()`](crate::Itertools::dedup_by_with_count) or
238/// [`.dedup_with_count()`](crate::Itertools::dedup_with_count) for more information.
239pub type DedupByWithCount<I, Pred> =
240    CoalesceBy<I, DedupPredWithCount2CoalescePred<Pred>, WithCount>;
241
242#[derive(Clone, Debug)]
243pub struct DedupPredWithCount2CoalescePred<DP>(DP);
244
245impl<DP, T> CoalescePredicate<T, (usize, T)> for DedupPredWithCount2CoalescePred<DP>
246where
247    DP: DedupPredicate<T>,
248{
249    fn coalesce_pair(
250        &mut self,
251        (c, t): (usize, T),
252        item: T,
253    ) -> Result<(usize, T), ((usize, T), (usize, T))> {
254        if self.0.dedup_pair(&t, &item) {
255            Ok((c + 1, t))
256        } else {
257            Err(((c, t), (1, item)))
258        }
259    }
260}
261
262/// An iterator adaptor that removes repeated duplicates, while keeping a count of how many
263/// repeated elements were present.
264///
265/// See [`.dedup_with_count()`](crate::Itertools::dedup_with_count) for more information.
266pub type DedupWithCount<I> = DedupByWithCount<I, DedupEq>;
267
268/// Create a new `DedupByWithCount`.
269pub fn dedup_by_with_count<I, Pred>(iter: I, dedup_pred: Pred) -> DedupByWithCount<I, Pred>
270where
271    I: Iterator,
272{
273    DedupByWithCount {
274        last: None,
275        iter,
276        f: DedupPredWithCount2CoalescePred(dedup_pred),
277    }
278}
279
280/// Create a new `DedupWithCount`.
281pub fn dedup_with_count<I>(iter: I) -> DedupWithCount<I>
282where
283    I: Iterator,
284{
285    dedup_by_with_count(iter, DedupEq)
286}
itertools/adaptors/coalesce.rs

itertools/adaptors/
coalesce.rs
