bluejay_validator/
utils.rs

1use itertools::Itertools;
2use std::cmp::{Eq, Ord};
3use std::collections::BTreeMap;
4use std::hash::Hash;
5
6pub fn duplicates<T: Copy, I: Iterator<Item = T>, K: Hash + Ord + Eq + Copy>(
7    mut iter: I,
8    key: fn(T) -> K,
9) -> impl Iterator<Item = (K, Vec<T>)> {
10    // If 0 or 1 items, no duplicates possible — avoid any allocation
11    let Some((first, second)) = iter.next().zip(iter.next()) else {
12        return Vec::new().into_iter();
13    };
14
15    let items: Vec<T> = [first, second].into_iter().chain(iter).collect();
16
17    // Quick O(n²) check for duplicates before allocating BTreeMap
18    let has_dupes = items
19        .iter()
20        .array_combinations()
21        .any(|[a, b]| key(*a) == key(*b));
22
23    if !has_dupes {
24        return Vec::new().into_iter();
25    }
26
27    // Only allocate BTreeMap when we know there are duplicates
28    let mut indexed = BTreeMap::new();
29    for el in items {
30        indexed.entry(key(el)).or_insert_with(Vec::new).push(el);
31    }
32
33    indexed
34        .into_iter()
35        .filter(|(_, values)| values.len() > 1)
36        .collect::<Vec<_>>()
37        .into_iter()
38}
bluejay_validator/utils.rs

bluejay_validator/
utils.rs
