1#![cfg(feature = "use_std")]
2
3use crate::MinMaxResult;
4use std::collections::HashMap;
5use std::cmp::Ordering;
6use std::hash::Hash;
7use std::iter::Iterator;
8use std::ops::{Add, Mul};
9
10/// A wrapper to allow for an easy [`into_grouping_map_by`](crate::Itertools::into_grouping_map_by)
11#[derive(Clone, Debug)]
12pub struct MapForGrouping<I, F>(I, F);
13
14impl<I, F> MapForGrouping<I, F> {
15 pub(crate) fn new(iter: I, key_mapper: F) -> Self {
16 Self(iter, key_mapper)
17 }
18}
19
20impl<K, V, I, F> Iterator for MapForGrouping<I, F>
21 where I: Iterator<Item = V>,
22 K: Hash + Eq,
23 F: FnMut(&V) -> K,
24{
25 type Item = (K, V);
26 fn next(&mut self) -> Option<Self::Item> {
27 self.0.next().map(|val| ((self.1)(&val), val))
28 }
29}
30
31/// Creates a new `GroupingMap` from `iter`
32pub fn new<I, K, V>(iter: I) -> GroupingMap<I>
33 where I: Iterator<Item = (K, V)>,
34 K: Hash + Eq,
35{
36 GroupingMap { iter }
37}
38
39/// `GroupingMapBy` is an intermediate struct for efficient group-and-fold operations.
40///
41/// See [`GroupingMap`] for more informations.
42pub type GroupingMapBy<I, F> = GroupingMap<MapForGrouping<I, F>>;
43
44/// `GroupingMap` is an intermediate struct for efficient group-and-fold operations.
45/// It groups elements by their key and at the same time fold each group
46/// using some aggregating operation.
47///
48/// No method on this struct performs temporary allocations.
49#[derive(Clone, Debug)]
50#[must_use = "GroupingMap is lazy and do nothing unless consumed"]
51pub struct GroupingMap<I> {
52 iter: I,
53}
54
55impl<I, K, V> GroupingMap<I>
56 where I: Iterator<Item = (K, V)>,
57 K: Hash + Eq,
58{
59 /// This is the generic way to perform any operation on a `GroupingMap`.
60 /// It's suggested to use this method only to implement custom operations
61 /// when the already provided ones are not enough.
62 ///
63 /// Groups elements from the `GroupingMap` source by key and applies `operation` to the elements
64 /// of each group sequentially, passing the previously accumulated value, a reference to the key
65 /// and the current element as arguments, and stores the results in an `HashMap`.
66 ///
67 /// The `operation` function is invoked on each element with the following parameters:
68 /// - the current value of the accumulator of the group if there is currently one;
69 /// - a reference to the key of the group this element belongs to;
70 /// - the element from the source being aggregated;
71 ///
72 /// If `operation` returns `Some(element)` then the accumulator is updated with `element`,
73 /// otherwise the previous accumulation is discarded.
74 ///
75 /// Return a `HashMap` associating the key of each group with the result of aggregation of
76 /// that group's elements. If the aggregation of the last element of a group discards the
77 /// accumulator then there won't be an entry associated to that group's key.
78 ///
79 /// ```
80 /// use itertools::Itertools;
81 ///
82 /// let data = vec![2, 8, 5, 7, 9, 0, 4, 10];
83 /// let lookup = data.into_iter()
84 /// .into_grouping_map_by(|&n| n % 4)
85 /// .aggregate(|acc, _key, val| {
86 /// if val == 0 || val == 10 {
87 /// None
88 /// } else {
89 /// Some(acc.unwrap_or(0) + val)
90 /// }
91 /// });
92 ///
93 /// assert_eq!(lookup[&0], 4); // 0 resets the accumulator so only 4 is summed
94 /// assert_eq!(lookup[&1], 5 + 9);
95 /// assert_eq!(lookup.get(&2), None); // 10 resets the accumulator and nothing is summed afterward
96 /// assert_eq!(lookup[&3], 7);
97 /// assert_eq!(lookup.len(), 3); // The final keys are only 0, 1 and 2
98 /// ```
99 pub fn aggregate<FO, R>(self, mut operation: FO) -> HashMap<K, R>
100 where FO: FnMut(Option<R>, &K, V) -> Option<R>,
101 {
102 let mut destination_map = HashMap::new();
103
104 self.iter.for_each(|(key, val)| {
105 let acc = destination_map.remove(&key);
106 if let Some(op_res) = operation(acc, &key, val) {
107 destination_map.insert(key, op_res);
108 }
109 });
110
111 destination_map
112 }
113
114 /// Groups elements from the `GroupingMap` source by key and applies `operation` to the elements
115 /// of each group sequentially, passing the previously accumulated value, a reference to the key
116 /// and the current element as arguments, and stores the results in a new map.
117 ///
118 /// `init` is the value from which will be cloned the initial value of each accumulator.
119 ///
120 /// `operation` is a function that is invoked on each element with the following parameters:
121 /// - the current value of the accumulator of the group;
122 /// - a reference to the key of the group this element belongs to;
123 /// - the element from the source being accumulated.
124 ///
125 /// Return a `HashMap` associating the key of each group with the result of folding that group's elements.
126 ///
127 /// ```
128 /// use itertools::Itertools;
129 ///
130 /// let lookup = (1..=7)
131 /// .into_grouping_map_by(|&n| n % 3)
132 /// .fold(0, |acc, _key, val| acc + val);
133 ///
134 /// assert_eq!(lookup[&0], 3 + 6);
135 /// assert_eq!(lookup[&1], 1 + 4 + 7);
136 /// assert_eq!(lookup[&2], 2 + 5);
137 /// assert_eq!(lookup.len(), 3);
138 /// ```
139 pub fn fold<FO, R>(self, init: R, mut operation: FO) -> HashMap<K, R>
140 where R: Clone,
141 FO: FnMut(R, &K, V) -> R,
142 {
143 self.aggregate(|acc, key, val| {
144 let acc = acc.unwrap_or_else(|| init.clone());
145 Some(operation(acc, key, val))
146 })
147 }
148
149 /// Groups elements from the `GroupingMap` source by key and applies `operation` to the elements
150 /// of each group sequentially, passing the previously accumulated value, a reference to the key
151 /// and the current element as arguments, and stores the results in a new map.
152 ///
153 /// This is similar to [`fold`] but the initial value of the accumulator is the first element of the group.
154 ///
155 /// `operation` is a function that is invoked on each element with the following parameters:
156 /// - the current value of the accumulator of the group;
157 /// - a reference to the key of the group this element belongs to;
158 /// - the element from the source being accumulated.
159 ///
160 /// Return a `HashMap` associating the key of each group with the result of folding that group's elements.
161 ///
162 /// [`fold`]: GroupingMap::fold
163 ///
164 /// ```
165 /// use itertools::Itertools;
166 ///
167 /// let lookup = (1..=7)
168 /// .into_grouping_map_by(|&n| n % 3)
169 /// .fold_first(|acc, _key, val| acc + val);
170 ///
171 /// assert_eq!(lookup[&0], 3 + 6);
172 /// assert_eq!(lookup[&1], 1 + 4 + 7);
173 /// assert_eq!(lookup[&2], 2 + 5);
174 /// assert_eq!(lookup.len(), 3);
175 /// ```
176 pub fn fold_first<FO>(self, mut operation: FO) -> HashMap<K, V>
177 where FO: FnMut(V, &K, V) -> V,
178 {
179 self.aggregate(|acc, key, val| {
180 Some(match acc {
181 Some(acc) => operation(acc, key, val),
182 None => val,
183 })
184 })
185 }
186
187 /// Groups elements from the `GroupingMap` source by key and collects the elements of each group in
188 /// an instance of `C`. The iteration order is preserved when inserting elements.
189 ///
190 /// Return a `HashMap` associating the key of each group with the collection containing that group's elements.
191 ///
192 /// ```
193 /// use itertools::Itertools;
194 /// use std::collections::HashSet;
195 ///
196 /// let lookup = vec![0, 1, 2, 3, 4, 5, 6, 2, 3, 6].into_iter()
197 /// .into_grouping_map_by(|&n| n % 3)
198 /// .collect::<HashSet<_>>();
199 ///
200 /// assert_eq!(lookup[&0], vec![0, 3, 6].into_iter().collect::<HashSet<_>>());
201 /// assert_eq!(lookup[&1], vec![1, 4].into_iter().collect::<HashSet<_>>());
202 /// assert_eq!(lookup[&2], vec![2, 5].into_iter().collect::<HashSet<_>>());
203 /// assert_eq!(lookup.len(), 3);
204 /// ```
205 pub fn collect<C>(self) -> HashMap<K, C>
206 where C: Default + Extend<V>,
207 {
208 let mut destination_map = HashMap::new();
209
210 self.iter.for_each(|(key, val)| {
211 destination_map.entry(key).or_insert_with(C::default).extend(Some(val));
212 });
213
214 destination_map
215 }
216
217 /// Groups elements from the `GroupingMap` source by key and finds the maximum of each group.
218 ///
219 /// If several elements are equally maximum, the last element is picked.
220 ///
221 /// Returns a `HashMap` associating the key of each group with the maximum of that group's elements.
222 ///
223 /// ```
224 /// use itertools::Itertools;
225 ///
226 /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter()
227 /// .into_grouping_map_by(|&n| n % 3)
228 /// .max();
229 ///
230 /// assert_eq!(lookup[&0], 12);
231 /// assert_eq!(lookup[&1], 7);
232 /// assert_eq!(lookup[&2], 8);
233 /// assert_eq!(lookup.len(), 3);
234 /// ```
235 pub fn max(self) -> HashMap<K, V>
236 where V: Ord,
237 {
238 self.max_by(|_, v1, v2| V::cmp(v1, v2))
239 }
240
241 /// Groups elements from the `GroupingMap` source by key and finds the maximum of each group
242 /// with respect to the specified comparison function.
243 ///
244 /// If several elements are equally maximum, the last element is picked.
245 ///
246 /// Returns a `HashMap` associating the key of each group with the maximum of that group's elements.
247 ///
248 /// ```
249 /// use itertools::Itertools;
250 ///
251 /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter()
252 /// .into_grouping_map_by(|&n| n % 3)
253 /// .max_by(|_key, x, y| y.cmp(x));
254 ///
255 /// assert_eq!(lookup[&0], 3);
256 /// assert_eq!(lookup[&1], 1);
257 /// assert_eq!(lookup[&2], 5);
258 /// assert_eq!(lookup.len(), 3);
259 /// ```
260 pub fn max_by<F>(self, mut compare: F) -> HashMap<K, V>
261 where F: FnMut(&K, &V, &V) -> Ordering,
262 {
263 self.fold_first(|acc, key, val| match compare(key, &acc, &val) {
264 Ordering::Less | Ordering::Equal => val,
265 Ordering::Greater => acc
266 })
267 }
268
269 /// Groups elements from the `GroupingMap` source by key and finds the element of each group
270 /// that gives the maximum from the specified function.
271 ///
272 /// If several elements are equally maximum, the last element is picked.
273 ///
274 /// Returns a `HashMap` associating the key of each group with the maximum of that group's elements.
275 ///
276 /// ```
277 /// use itertools::Itertools;
278 ///
279 /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter()
280 /// .into_grouping_map_by(|&n| n % 3)
281 /// .max_by_key(|_key, &val| val % 4);
282 ///
283 /// assert_eq!(lookup[&0], 3);
284 /// assert_eq!(lookup[&1], 7);
285 /// assert_eq!(lookup[&2], 5);
286 /// assert_eq!(lookup.len(), 3);
287 /// ```
288 pub fn max_by_key<F, CK>(self, mut f: F) -> HashMap<K, V>
289 where F: FnMut(&K, &V) -> CK,
290 CK: Ord,
291 {
292 self.max_by(|key, v1, v2| f(key, v1).cmp(&f(key, v2)))
293 }
294
295 /// Groups elements from the `GroupingMap` source by key and finds the minimum of each group.
296 ///
297 /// If several elements are equally minimum, the first element is picked.
298 ///
299 /// Returns a `HashMap` associating the key of each group with the minimum of that group's elements.
300 ///
301 /// ```
302 /// use itertools::Itertools;
303 ///
304 /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter()
305 /// .into_grouping_map_by(|&n| n % 3)
306 /// .min();
307 ///
308 /// assert_eq!(lookup[&0], 3);
309 /// assert_eq!(lookup[&1], 1);
310 /// assert_eq!(lookup[&2], 5);
311 /// assert_eq!(lookup.len(), 3);
312 /// ```
313 pub fn min(self) -> HashMap<K, V>
314 where V: Ord,
315 {
316 self.min_by(|_, v1, v2| V::cmp(v1, v2))
317 }
318
319 /// Groups elements from the `GroupingMap` source by key and finds the minimum of each group
320 /// with respect to the specified comparison function.
321 ///
322 /// If several elements are equally minimum, the first element is picked.
323 ///
324 /// Returns a `HashMap` associating the key of each group with the minimum of that group's elements.
325 ///
326 /// ```
327 /// use itertools::Itertools;
328 ///
329 /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter()
330 /// .into_grouping_map_by(|&n| n % 3)
331 /// .min_by(|_key, x, y| y.cmp(x));
332 ///
333 /// assert_eq!(lookup[&0], 12);
334 /// assert_eq!(lookup[&1], 7);
335 /// assert_eq!(lookup[&2], 8);
336 /// assert_eq!(lookup.len(), 3);
337 /// ```
338 pub fn min_by<F>(self, mut compare: F) -> HashMap<K, V>
339 where F: FnMut(&K, &V, &V) -> Ordering,
340 {
341 self.fold_first(|acc, key, val| match compare(key, &acc, &val) {
342 Ordering::Less | Ordering::Equal => acc,
343 Ordering::Greater => val
344 })
345 }
346
347 /// Groups elements from the `GroupingMap` source by key and finds the element of each group
348 /// that gives the minimum from the specified function.
349 ///
350 /// If several elements are equally minimum, the first element is picked.
351 ///
352 /// Returns a `HashMap` associating the key of each group with the minimum of that group's elements.
353 ///
354 /// ```
355 /// use itertools::Itertools;
356 ///
357 /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter()
358 /// .into_grouping_map_by(|&n| n % 3)
359 /// .min_by_key(|_key, &val| val % 4);
360 ///
361 /// assert_eq!(lookup[&0], 12);
362 /// assert_eq!(lookup[&1], 4);
363 /// assert_eq!(lookup[&2], 8);
364 /// assert_eq!(lookup.len(), 3);
365 /// ```
366 pub fn min_by_key<F, CK>(self, mut f: F) -> HashMap<K, V>
367 where F: FnMut(&K, &V) -> CK,
368 CK: Ord,
369 {
370 self.min_by(|key, v1, v2| f(key, v1).cmp(&f(key, v2)))
371 }
372
373 /// Groups elements from the `GroupingMap` source by key and find the maximum and minimum of
374 /// each group.
375 ///
376 /// If several elements are equally maximum, the last element is picked.
377 /// If several elements are equally minimum, the first element is picked.
378 ///
379 /// See [.minmax()](crate::Itertools::minmax) for the non-grouping version.
380 ///
381 /// Differences from the non grouping version:
382 /// - It never produces a `MinMaxResult::NoElements`
383 /// - It doesn't have any speedup
384 ///
385 /// Returns a `HashMap` associating the key of each group with the minimum and maximum of that group's elements.
386 ///
387 /// ```
388 /// use itertools::Itertools;
389 /// use itertools::MinMaxResult::{OneElement, MinMax};
390 ///
391 /// let lookup = vec![1, 3, 4, 5, 7, 9, 12].into_iter()
392 /// .into_grouping_map_by(|&n| n % 3)
393 /// .minmax();
394 ///
395 /// assert_eq!(lookup[&0], MinMax(3, 12));
396 /// assert_eq!(lookup[&1], MinMax(1, 7));
397 /// assert_eq!(lookup[&2], OneElement(5));
398 /// assert_eq!(lookup.len(), 3);
399 /// ```
400 pub fn minmax(self) -> HashMap<K, MinMaxResult<V>>
401 where V: Ord,
402 {
403 self.minmax_by(|_, v1, v2| V::cmp(v1, v2))
404 }
405
406 /// Groups elements from the `GroupingMap` source by key and find the maximum and minimum of
407 /// each group with respect to the specified comparison function.
408 ///
409 /// If several elements are equally maximum, the last element is picked.
410 /// If several elements are equally minimum, the first element is picked.
411 ///
412 /// It has the same differences from the non-grouping version as `minmax`.
413 ///
414 /// Returns a `HashMap` associating the key of each group with the minimum and maximum of that group's elements.
415 ///
416 /// ```
417 /// use itertools::Itertools;
418 /// use itertools::MinMaxResult::{OneElement, MinMax};
419 ///
420 /// let lookup = vec![1, 3, 4, 5, 7, 9, 12].into_iter()
421 /// .into_grouping_map_by(|&n| n % 3)
422 /// .minmax_by(|_key, x, y| y.cmp(x));
423 ///
424 /// assert_eq!(lookup[&0], MinMax(12, 3));
425 /// assert_eq!(lookup[&1], MinMax(7, 1));
426 /// assert_eq!(lookup[&2], OneElement(5));
427 /// assert_eq!(lookup.len(), 3);
428 /// ```
429 pub fn minmax_by<F>(self, mut compare: F) -> HashMap<K, MinMaxResult<V>>
430 where F: FnMut(&K, &V, &V) -> Ordering,
431 {
432 self.aggregate(|acc, key, val| {
433 Some(match acc {
434 Some(MinMaxResult::OneElement(e)) => {
435 if compare(key, &val, &e) == Ordering::Less {
436 MinMaxResult::MinMax(val, e)
437 } else {
438 MinMaxResult::MinMax(e, val)
439 }
440 }
441 Some(MinMaxResult::MinMax(min, max)) => {
442 if compare(key, &val, &min) == Ordering::Less {
443 MinMaxResult::MinMax(val, max)
444 } else if compare(key, &val, &max) != Ordering::Less {
445 MinMaxResult::MinMax(min, val)
446 } else {
447 MinMaxResult::MinMax(min, max)
448 }
449 }
450 None => MinMaxResult::OneElement(val),
451 Some(MinMaxResult::NoElements) => unreachable!(),
452 })
453 })
454 }
455
456 /// Groups elements from the `GroupingMap` source by key and find the elements of each group
457 /// that gives the minimum and maximum from the specified function.
458 ///
459 /// If several elements are equally maximum, the last element is picked.
460 /// If several elements are equally minimum, the first element is picked.
461 ///
462 /// It has the same differences from the non-grouping version as `minmax`.
463 ///
464 /// Returns a `HashMap` associating the key of each group with the minimum and maximum of that group's elements.
465 ///
466 /// ```
467 /// use itertools::Itertools;
468 /// use itertools::MinMaxResult::{OneElement, MinMax};
469 ///
470 /// let lookup = vec![1, 3, 4, 5, 7, 9, 12].into_iter()
471 /// .into_grouping_map_by(|&n| n % 3)
472 /// .minmax_by_key(|_key, &val| val % 4);
473 ///
474 /// assert_eq!(lookup[&0], MinMax(12, 3));
475 /// assert_eq!(lookup[&1], MinMax(4, 7));
476 /// assert_eq!(lookup[&2], OneElement(5));
477 /// assert_eq!(lookup.len(), 3);
478 /// ```
479 pub fn minmax_by_key<F, CK>(self, mut f: F) -> HashMap<K, MinMaxResult<V>>
480 where F: FnMut(&K, &V) -> CK,
481 CK: Ord,
482 {
483 self.minmax_by(|key, v1, v2| f(key, v1).cmp(&f(key, v2)))
484 }
485
486 /// Groups elements from the `GroupingMap` source by key and sums them.
487 ///
488 /// This is just a shorthand for `self.fold_first(|acc, _, val| acc + val)`.
489 /// It is more limited than `Iterator::sum` since it doesn't use the `Sum` trait.
490 ///
491 /// Returns a `HashMap` associating the key of each group with the sum of that group's elements.
492 ///
493 /// ```
494 /// use itertools::Itertools;
495 ///
496 /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter()
497 /// .into_grouping_map_by(|&n| n % 3)
498 /// .sum();
499 ///
500 /// assert_eq!(lookup[&0], 3 + 9 + 12);
501 /// assert_eq!(lookup[&1], 1 + 4 + 7);
502 /// assert_eq!(lookup[&2], 5 + 8);
503 /// assert_eq!(lookup.len(), 3);
504 /// ```
505 pub fn sum(self) -> HashMap<K, V>
506 where V: Add<V, Output = V>
507 {
508 self.fold_first(|acc, _, val| acc + val)
509 }
510
511 /// Groups elements from the `GroupingMap` source by key and multiply them.
512 ///
513 /// This is just a shorthand for `self.fold_first(|acc, _, val| acc * val)`.
514 /// It is more limited than `Iterator::product` since it doesn't use the `Product` trait.
515 ///
516 /// Returns a `HashMap` associating the key of each group with the product of that group's elements.
517 ///
518 /// ```
519 /// use itertools::Itertools;
520 ///
521 /// let lookup = vec![1, 3, 4, 5, 7, 8, 9, 12].into_iter()
522 /// .into_grouping_map_by(|&n| n % 3)
523 /// .product();
524 ///
525 /// assert_eq!(lookup[&0], 3 * 9 * 12);
526 /// assert_eq!(lookup[&1], 1 * 4 * 7);
527 /// assert_eq!(lookup[&2], 5 * 8);
528 /// assert_eq!(lookup.len(), 3);
529 /// ```
530 pub fn product(self) -> HashMap<K, V>
531 where V: Mul<V, Output = V>,
532 {
533 self.fold_first(|acc, _, val| acc * val)
534 }
535}
536