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