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