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, dedup_pred: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: usize, t: 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, dedup_pred:DedupEq)
286}
287