use std::collections::hash_map::Entry; use std::collections::HashMap; use std::fmt; use std::hash::Hash; use std::iter::FusedIterator; /// An iterator adapter to filter out duplicate elements. /// /// See [`.unique_by()`](crate::Itertools::unique) for more information. #[derive(Clone)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct UniqueBy { iter: I, // Use a Hashmap for the Entry API in order to prevent hashing twice. // This can maybe be replaced with a HashSet once `get_or_insert_with` // or a proper Entry API for Hashset is stable and meets this msrv used: HashMap, f: F, } impl fmt::Debug for UniqueBy where I: Iterator + fmt::Debug, V: fmt::Debug + Hash + Eq, { debug_fmt_fields!(UniqueBy, iter, used); } /// Create a new `UniqueBy` iterator. pub fn unique_by(iter: I, f: F) -> UniqueBy where V: Eq + Hash, F: FnMut(&I::Item) -> V, I: Iterator, { UniqueBy { iter, used: HashMap::new(), f, } } // count the number of new unique keys in iterable (`used` is the set already seen) fn count_new_keys(mut used: HashMap, iterable: I) -> usize where I: IntoIterator, K: Hash + Eq, { let iter = iterable.into_iter(); let current_used = used.len(); used.extend(iter.map(|key| (key, ()))); used.len() - current_used } impl Iterator for UniqueBy where I: Iterator, V: Eq + Hash, F: FnMut(&I::Item) -> V, { type Item = I::Item; fn next(&mut self) -> Option { while let Some(v) = self.iter.next() { let key = (self.f)(&v); if self.used.insert(key, ()).is_none() { return Some(v); } } None } #[inline] fn size_hint(&self) -> (usize, Option) { let (low, hi) = self.iter.size_hint(); ((low > 0 && self.used.is_empty()) as usize, hi) } fn count(self) -> usize { let mut key_f = self.f; count_new_keys(self.used, self.iter.map(move |elt| key_f(&elt))) } } impl DoubleEndedIterator for UniqueBy where I: DoubleEndedIterator, V: Eq + Hash, F: FnMut(&I::Item) -> V, { fn next_back(&mut self) -> Option { while let Some(v) = self.iter.next_back() { let key = (self.f)(&v); if self.used.insert(key, ()).is_none() { return Some(v); } } None } } impl FusedIterator for UniqueBy where I: FusedIterator, V: Eq + Hash, F: FnMut(&I::Item) -> V, { } impl Iterator for Unique where I: Iterator, I::Item: Eq + Hash + Clone, { type Item = I::Item; fn next(&mut self) -> Option { while let Some(v) = self.iter.iter.next() { if let Entry::Vacant(entry) = self.iter.used.entry(v) { let elt = entry.key().clone(); entry.insert(()); return Some(elt); } } None } #[inline] fn size_hint(&self) -> (usize, Option) { let (low, hi) = self.iter.iter.size_hint(); ((low > 0 && self.iter.used.is_empty()) as usize, hi) } fn count(self) -> usize { count_new_keys(self.iter.used, self.iter.iter) } } impl DoubleEndedIterator for Unique where I: DoubleEndedIterator, I::Item: Eq + Hash + Clone, { fn next_back(&mut self) -> Option { while let Some(v) = self.iter.iter.next_back() { if let Entry::Vacant(entry) = self.iter.used.entry(v) { let elt = entry.key().clone(); entry.insert(()); return Some(elt); } } None } } impl FusedIterator for Unique where I: FusedIterator, I::Item: Eq + Hash + Clone, { } /// An iterator adapter to filter out duplicate elements. /// /// See [`.unique()`](crate::Itertools::unique) for more information. #[derive(Clone)] #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] pub struct Unique where I: Iterator, I::Item: Eq + Hash + Clone, { iter: UniqueBy, } impl fmt::Debug for Unique where I: Iterator + fmt::Debug, I::Item: Hash + Eq + fmt::Debug + Clone, { debug_fmt_fields!(Unique, iter); } pub fn unique(iter: I) -> Unique where I: Iterator, I::Item: Eq + Hash + Clone, { Unique { iter: UniqueBy { iter, used: HashMap::new(), f: (), }, } }