]>
Commit | Line | Data |
---|---|---|
f20569fa XL |
1 | |
2 | use std::collections::HashMap; | |
3 | use std::collections::hash_map::{Entry}; | |
4 | use std::hash::Hash; | |
5 | use std::fmt; | |
6 | ||
7 | /// An iterator adapter to filter out duplicate elements. | |
8 | /// | |
9 | /// See [`.unique_by()`](../trait.Itertools.html#method.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 | |
15 | used: HashMap<V, ()>, | |
16 | f: F, | |
17 | } | |
18 | ||
19 | impl<I, V, F> fmt::Debug for UniqueBy<I, V, F> | |
20 | where I: Iterator + fmt::Debug, | |
21 | V: fmt::Debug + Hash + Eq, | |
22 | { | |
23 | debug_fmt_fields!(UniqueBy, iter, used); | |
24 | } | |
25 | ||
26 | /// Create a new `UniqueBy` iterator. | |
27 | pub fn unique_by<I, V, F>(iter: I, f: F) -> UniqueBy<I, V, F> | |
28 | where V: Eq + Hash, | |
29 | F: FnMut(&I::Item) -> V, | |
30 | I: Iterator, | |
31 | { | |
32 | UniqueBy { | |
33 | iter: iter, | |
34 | used: HashMap::new(), | |
35 | f: f, | |
36 | } | |
37 | } | |
38 | ||
39 | // count the number of new unique keys in iterable (`used` is the set already seen) | |
40 | fn count_new_keys<I, K>(mut used: HashMap<K, ()>, iterable: I) -> usize | |
41 | where I: IntoIterator<Item=K>, | |
42 | K: Hash + Eq, | |
43 | { | |
44 | let iter = iterable.into_iter(); | |
45 | let current_used = used.len(); | |
46 | used.extend(iter.map(|key| (key, ()))); | |
47 | used.len() - current_used | |
48 | } | |
49 | ||
50 | impl<I, V, F> Iterator for UniqueBy<I, V, F> | |
51 | where I: Iterator, | |
52 | V: Eq + Hash, | |
53 | F: FnMut(&I::Item) -> V | |
54 | { | |
55 | type Item = I::Item; | |
56 | ||
57 | fn next(&mut self) -> Option<I::Item> { | |
58 | while let Some(v) = self.iter.next() { | |
59 | let key = (self.f)(&v); | |
60 | if self.used.insert(key, ()).is_none() { | |
61 | return Some(v); | |
62 | } | |
63 | } | |
64 | None | |
65 | } | |
66 | ||
67 | #[inline] | |
68 | fn size_hint(&self) -> (usize, Option<usize>) { | |
69 | let (low, hi) = self.iter.size_hint(); | |
70 | ((low > 0 && self.used.is_empty()) as usize, hi) | |
71 | } | |
72 | ||
73 | fn count(self) -> usize { | |
74 | let mut key_f = self.f; | |
75 | count_new_keys(self.used, self.iter.map(move |elt| key_f(&elt))) | |
76 | } | |
77 | } | |
78 | ||
79 | impl<I> Iterator for Unique<I> | |
80 | where I: Iterator, | |
81 | I::Item: Eq + Hash + Clone | |
82 | { | |
83 | type Item = I::Item; | |
84 | ||
85 | fn next(&mut self) -> Option<I::Item> { | |
86 | while let Some(v) = self.iter.iter.next() { | |
87 | if let Entry::Vacant(entry) = self.iter.used.entry(v) { | |
88 | let elt = entry.key().clone(); | |
89 | entry.insert(()); | |
90 | return Some(elt); | |
91 | } | |
92 | } | |
93 | None | |
94 | } | |
95 | ||
96 | #[inline] | |
97 | fn size_hint(&self) -> (usize, Option<usize>) { | |
98 | let (low, hi) = self.iter.iter.size_hint(); | |
99 | ((low > 0 && self.iter.used.is_empty()) as usize, hi) | |
100 | } | |
101 | ||
102 | fn count(self) -> usize { | |
103 | count_new_keys(self.iter.used, self.iter.iter) | |
104 | } | |
105 | } | |
106 | ||
107 | /// An iterator adapter to filter out duplicate elements. | |
108 | /// | |
109 | /// See [`.unique()`](../trait.Itertools.html#method.unique) for more information. | |
110 | #[derive(Clone)] | |
111 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] | |
112 | pub struct Unique<I: Iterator> { | |
113 | iter: UniqueBy<I, I::Item, ()>, | |
114 | } | |
115 | ||
116 | impl<I> fmt::Debug for Unique<I> | |
117 | where I: Iterator + fmt::Debug, | |
118 | I::Item: Hash + Eq + fmt::Debug, | |
119 | { | |
120 | debug_fmt_fields!(Unique, iter); | |
121 | } | |
122 | ||
123 | pub fn unique<I>(iter: I) -> Unique<I> | |
124 | where I: Iterator, | |
125 | I::Item: Eq + Hash, | |
126 | { | |
127 | Unique { | |
128 | iter: UniqueBy { | |
129 | iter: iter, | |
130 | used: HashMap::new(), | |
131 | f: (), | |
132 | } | |
133 | } | |
134 | } |