itertools/
unique_impl.rs

1use core::hash::BuildHasher;
2use std::collections::hash_map::Entry;
3use std::collections::hash_map::RandomState;
4use std::collections::HashMap;
5use std::fmt;
6use std::hash::Hash;
7use std::iter::FusedIterator;
8
9/// An iterator adapter to filter out duplicate elements.
10///
11/// See [`.unique_by()`](crate::Itertools::unique) for more information.
12#[derive(Clone)]
13#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
14pub struct UniqueBy<I: Iterator, V, F, S = RandomState>
15where
16    S: BuildHasher,
17{
18    iter: I,
19    // Use a Hashmap for the Entry API in order to prevent hashing twice.
20    // This can maybe be replaced with a HashSet once `get_or_insert_with`
21    // or a proper Entry API for Hashset is stable and meets this msrv
22    used: HashMap<V, (), S>,
23    f: F,
24}
25
26impl<I, V, F, S> fmt::Debug for UniqueBy<I, V, F, S>
27where
28    I: Iterator + fmt::Debug,
29    V: fmt::Debug + Hash + Eq,
30    S: BuildHasher,
31{
32    debug_fmt_fields!(UniqueBy, iter, used);
33}
34
35/// Create a new `UniqueBy` iterator.
36pub fn unique_by_with_hasher<I, V, F, S>(iter: I, f: F, hash_builder: S) -> UniqueBy<I, V, F, S>
37where
38    V: Eq + Hash,
39    F: FnMut(&I::Item) -> V,
40    I: Iterator,
41    S: BuildHasher,
42{
43    UniqueBy {
44        iter,
45        used: HashMap::with_hasher(hash_builder),
46        f,
47    }
48}
49
50// count the number of new unique keys in iterable (`used` is the set already seen)
51fn count_new_keys<I, K, S>(mut used: HashMap<K, (), S>, iterable: I) -> usize
52where
53    I: IntoIterator<Item = K>,
54    K: Hash + Eq,
55    S: BuildHasher,
56{
57    let iter = iterable.into_iter();
58    let current_used = used.len();
59    used.extend(iter.map(|key| (key, ())));
60    used.len() - current_used
61}
62
63impl<I, V, F, S> Iterator for UniqueBy<I, V, F, S>
64where
65    I: Iterator,
66    V: Eq + Hash,
67    F: FnMut(&I::Item) -> V,
68    S: BuildHasher,
69{
70    type Item = I::Item;
71
72    fn next(&mut self) -> Option<Self::Item> {
73        let Self { iter, used, f } = self;
74        iter.find(|v| used.insert(f(v), ()).is_none())
75    }
76
77    #[inline]
78    fn size_hint(&self) -> (usize, Option<usize>) {
79        let (low, hi) = self.iter.size_hint();
80        (usize::from(low > 0 && self.used.is_empty()), hi)
81    }
82
83    fn count(self) -> usize {
84        let mut key_f = self.f;
85        count_new_keys(self.used, self.iter.map(move |elt| key_f(&elt)))
86    }
87}
88
89impl<I, V, F, S> DoubleEndedIterator for UniqueBy<I, V, F, S>
90where
91    I: DoubleEndedIterator,
92    V: Eq + Hash,
93    F: FnMut(&I::Item) -> V,
94    S: BuildHasher,
95{
96    fn next_back(&mut self) -> Option<Self::Item> {
97        let Self { iter, used, f } = self;
98        iter.rfind(|v| used.insert(f(v), ()).is_none())
99    }
100}
101
102impl<I, V, F, S> FusedIterator for UniqueBy<I, V, F, S>
103where
104    I: FusedIterator,
105    V: Eq + Hash,
106    F: FnMut(&I::Item) -> V,
107    S: BuildHasher,
108{
109}
110
111impl<I, S> Iterator for Unique<I, S>
112where
113    I: Iterator,
114    I::Item: Eq + Hash + Clone,
115    S: BuildHasher,
116{
117    type Item = I::Item;
118
119    fn next(&mut self) -> Option<Self::Item> {
120        let UniqueBy { iter, used, .. } = &mut self.iter;
121        iter.find_map(|v| {
122            if let Entry::Vacant(entry) = used.entry(v) {
123                let elt = entry.key().clone();
124                entry.insert(());
125                return Some(elt);
126            }
127            None
128        })
129    }
130
131    #[inline]
132    fn size_hint(&self) -> (usize, Option<usize>) {
133        let (low, hi) = self.iter.iter.size_hint();
134        (usize::from(low > 0 && self.iter.used.is_empty()), hi)
135    }
136
137    fn count(self) -> usize {
138        count_new_keys(self.iter.used, self.iter.iter)
139    }
140}
141
142impl<I, S> DoubleEndedIterator for Unique<I, S>
143where
144    I: DoubleEndedIterator,
145    I::Item: Eq + Hash + Clone,
146    S: BuildHasher,
147{
148    fn next_back(&mut self) -> Option<Self::Item> {
149        let UniqueBy { iter, used, .. } = &mut self.iter;
150        iter.rev().find_map(|v| {
151            if let Entry::Vacant(entry) = used.entry(v) {
152                let elt = entry.key().clone();
153                entry.insert(());
154                return Some(elt);
155            }
156            None
157        })
158    }
159}
160
161impl<I, S> FusedIterator for Unique<I, S>
162where
163    I: FusedIterator,
164    I::Item: Eq + Hash + Clone,
165    S: BuildHasher,
166{
167}
168
169/// An iterator adapter to filter out duplicate elements.
170///
171/// See [`.unique()`](crate::Itertools::unique) for more information.
172#[derive(Clone)]
173#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
174pub struct Unique<I, S = RandomState>
175where
176    I: Iterator,
177    I::Item: Eq + Hash + Clone,
178    S: BuildHasher,
179{
180    iter: UniqueBy<I, I::Item, (), S>,
181}
182
183impl<I, S> fmt::Debug for Unique<I, S>
184where
185    I: Iterator + fmt::Debug,
186    I::Item: Hash + Eq + fmt::Debug + Clone,
187    S: BuildHasher,
188{
189    debug_fmt_fields!(Unique, iter);
190}
191
192pub fn unique_with_hasher<I, S>(iter: I, hash_builder: S) -> Unique<I, S>
193where
194    I: Iterator,
195    I::Item: Eq + Hash + Clone,
196    S: BuildHasher,
197{
198    Unique {
199        iter: UniqueBy {
200            iter,
201            used: HashMap::with_hasher(hash_builder),
202            f: (),
203        },
204    }
205}
itertools/unique_impl.rs

itertools/
unique_impl.rs
