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