]>
git.proxmox.com Git - rustc.git/blob - vendor/itertools-0.11.0/src/unique_impl.rs
1 use std
::collections
::HashMap
;
2 use std
::collections
::hash_map
::Entry
;
5 use std
::iter
::FusedIterator
;
7 /// An iterator adapter to filter out duplicate elements.
9 /// See [`.unique_by()`](crate::Itertools::unique) for more information.
11 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
12 pub struct UniqueBy
<I
: Iterator
, V
, F
> {
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
21 impl<I
, V
, F
> fmt
::Debug
for UniqueBy
<I
, V
, F
>
22 where I
: Iterator
+ fmt
::Debug
,
23 V
: fmt
::Debug
+ Hash
+ Eq
,
25 debug_fmt_fields
!(UniqueBy
, iter
, used
);
28 /// Create a new `UniqueBy` iterator.
29 pub fn unique_by
<I
, V
, F
>(iter
: I
, f
: F
) -> UniqueBy
<I
, V
, F
>
31 F
: FnMut(&I
::Item
) -> V
,
41 // count the number of new unique keys in iterable (`used` is the set already seen)
42 fn count_new_keys
<I
, K
>(mut used
: HashMap
<K
, ()>, iterable
: I
) -> usize
43 where I
: IntoIterator
<Item
=K
>,
46 let iter
= iterable
.into_iter();
47 let current_used
= used
.len();
48 used
.extend(iter
.map(|key
| (key
, ())));
49 used
.len() - current_used
52 impl<I
, V
, F
> Iterator
for UniqueBy
<I
, V
, F
>
55 F
: FnMut(&I
::Item
) -> V
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() {
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
)
75 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
)))
81 impl<I
, V
, F
> DoubleEndedIterator
for UniqueBy
<I
, V
, F
>
82 where I
: DoubleEndedIterator
,
84 F
: FnMut(&I
::Item
) -> V
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() {
97 impl<I
, V
, F
> FusedIterator
for UniqueBy
<I
, V
, F
>
98 where I
: FusedIterator
,
100 F
: FnMut(&I
::Item
) -> V
103 impl<I
> Iterator
for Unique
<I
>
105 I
::Item
: Eq
+ Hash
+ Clone
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();
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
)
126 fn count(self) -> usize {
127 count_new_keys(self.iter
.used
, self.iter
.iter
)
131 impl<I
> DoubleEndedIterator
for Unique
<I
>
132 where I
: DoubleEndedIterator
,
133 I
::Item
: Eq
+ Hash
+ Clone
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();
147 impl<I
> FusedIterator
for Unique
<I
>
148 where I
: FusedIterator
,
149 I
::Item
: Eq
+ Hash
+ Clone
152 /// An iterator adapter to filter out duplicate elements.
154 /// See [`.unique()`](crate::Itertools::unique) for more information.
156 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
157 pub struct Unique
<I
: Iterator
> {
158 iter
: UniqueBy
<I
, I
::Item
, ()>,
161 impl<I
> fmt
::Debug
for Unique
<I
>
162 where I
: Iterator
+ fmt
::Debug
,
163 I
::Item
: Hash
+ Eq
+ fmt
::Debug
,
165 debug_fmt_fields
!(Unique
, iter
);
168 pub fn unique
<I
>(iter
: I
) -> Unique
<I
>
175 used
: HashMap
::new(),