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