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