/rust/registry/src/index.crates.io-6f17d22bba15001f/itertools-0.10.5/src/duplicates_impl.rs

Source (jump to first uncovered line)
use std::hash::Hash;

mod private {
    use std::collections::HashMap;
    use std::hash::Hash;
    use std::fmt;

    #[derive(Clone)]
    #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
    pub struct DuplicatesBy<I: Iterator, Key, F> {
        pub(crate) iter: I,
        pub(crate) meta: Meta<Key, F>,
    }

    impl<I, V, F> fmt::Debug for DuplicatesBy<I, V, F>
    where
        I: Iterator + fmt::Debug,
        V: fmt::Debug + Hash + Eq,
    {
        debug_fmt_fields!(DuplicatesBy, iter, meta.used);
    }

    impl<I: Iterator, Key: Eq + Hash, F> DuplicatesBy<I, Key, F> {
        pub(crate) fn new(iter: I, key_method: F) -> Self {
            DuplicatesBy {
                iter,
                meta: Meta {
                    used: HashMap::new(),
                    pending: 0,
                    key_method,
                },
            }
        }
    }

    #[derive(Clone)]
    pub struct Meta<Key, F> {
        used: HashMap<Key, bool>,
        pending: usize,
        key_method: F,
    }

    impl<Key, F> Meta<Key, F>
    where
        Key: Eq + Hash,
    {
        /// Takes an item and returns it back to the caller if it's the second time we see it.
        /// Otherwise the item is consumed and None is returned
        #[inline(always)]
        fn filter<I>(&mut self, item: I) -> Option<I>
        where
            F: KeyMethod<Key, I>,
        {
            let kv = self.key_method.make(item);
            match self.used.get_mut(kv.key_ref()) {
                None => {
                    self.used.insert(kv.key(), false);
                    self.pending += 1;
                    None
                }
                Some(true) => None,
                Some(produced) => {
                    *produced = true;
                    self.pending -= 1;
                    Some(kv.value())
                }
            }
        }
    }

    impl<I, Key, F> Iterator for DuplicatesBy<I, Key, F>
    where
        I: Iterator,
        Key: Eq + Hash,
        F: KeyMethod<Key, I::Item>,
    {
        type Item = I::Item;

        fn next(&mut self) -> Option<Self::Item> {
            let DuplicatesBy { iter, meta } = self;
            iter.find_map(|v| meta.filter(v))
        }

        #[inline]
        fn size_hint(&self) -> (usize, Option<usize>) {
            let (_, hi) = self.iter.size_hint();
            let hi = hi.map(|hi| {
                if hi <= self.meta.pending {
                    // fewer or equally many iter-remaining elements than pending elements
                    // => at most, each iter-remaining element is matched
                    hi
                } else {
                    // fewer pending elements than iter-remaining elements
                    // => at most:
                    //    * each pending element is matched
                    //    * the other iter-remaining elements come in pairs
                    self.meta.pending + (hi - self.meta.pending) / 2
                }
            });
            // The lower bound is always 0 since we might only get unique items from now on
            (0, hi)
        }
    }

    impl<I, Key, F> DoubleEndedIterator for DuplicatesBy<I, Key, F>
    where
        I: DoubleEndedIterator,
        Key: Eq + Hash,
        F: KeyMethod<Key, I::Item>,
    {
        fn next_back(&mut self) -> Option<Self::Item> {
            let DuplicatesBy { iter, meta } = self;
            iter.rev().find_map(|v| meta.filter(v))
        }
    }

    /// A keying method for use with `DuplicatesBy`
    pub trait KeyMethod<K, V> {
        type Container: KeyXorValue<K, V>;

        fn make(&mut self, value: V) -> Self::Container;
    }

    /// Apply the identity function to elements before checking them for equality.
    #[derive(Debug)]
    pub struct ById;
    impl<V> KeyMethod<V, V> for ById {
        type Container = JustValue<V>;

        fn make(&mut self, v: V) -> Self::Container {
            JustValue(v)
        }
    }

    /// Apply a user-supplied function to elements before checking them for equality.
    pub struct ByFn<F>(pub(crate) F);
    impl<F> fmt::Debug for ByFn<F> {
        debug_fmt_fields!(ByFn,);
    }
    impl<K, V, F> KeyMethod<K, V> for ByFn<F>
    where
        F: FnMut(&V) -> K,
    {
        type Container = KeyValue<K, V>;

        fn make(&mut self, v: V) -> Self::Container {
            KeyValue((self.0)(&v), v)
        }
    }

    // Implementors of this trait can hold onto a key and a value but only give access to one of them
    // at a time. This allows the key and the value to be the same value internally
    pub trait KeyXorValue<K, V> {
        fn key_ref(&self) -> &K;
        fn key(self) -> K;
        fn value(self) -> V;
    }

    #[derive(Debug)]
    pub struct KeyValue<K, V>(K, V);
    impl<K, V> KeyXorValue<K, V> for KeyValue<K, V> {
        fn key_ref(&self) -> &K {
            &self.0
        }
        fn key(self) -> K {
            self.0
        }
        fn value(self) -> V {
            self.1
        }
    }

    #[derive(Debug)]
    pub struct JustValue<V>(V);
    impl<V> KeyXorValue<V, V> for JustValue<V> {
        fn key_ref(&self) -> &V {
            &self.0
        }
        fn key(self) -> V {
            self.0
        }
        fn value(self) -> V {
            self.0
        }
    }
}

/// An iterator adapter to filter for duplicate elements.
///
/// See [`.duplicates_by()`](crate::Itertools::duplicates_by) for more information.
pub type DuplicatesBy<I, V, F> = private::DuplicatesBy<I, V, private::ByFn<F>>;

/// Create a new `DuplicatesBy` iterator.
pub fn duplicates_by<I, Key, F>(iter: I, f: F) -> DuplicatesBy<I, Key, F>
where
    Key: Eq + Hash,
    F: FnMut(&I::Item) -> Key,
    I: Iterator,
{
    DuplicatesBy::new(iter, private::ByFn(f))
}

/// An iterator adapter to filter out duplicate elements.
///
/// See [`.duplicates()`](crate::Itertools::duplicates) for more information.
pub type Duplicates<I> = private::DuplicatesBy<I, <I as Iterator>::Item, private::ById>;

/// Create a new `Duplicates` iterator.
pub fn duplicates<I>(iter: I) -> Duplicates<I>
where
    I: Iterator,
    I::Item: Eq + Hash,
{
    Duplicates::new(iter, private::ById)
}


Coverage Report

Created: 2025-02-21 07:11

Line	Count	Source (jump to first uncovered line)
1		use std::hash::Hash;
2
3		mod private {
4		use std::collections::HashMap;
5		use std::hash::Hash;
6		use std::fmt;
7
8		#[derive(Clone)]
9		#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
10		pub struct DuplicatesBy<I: Iterator, Key, F> {
11		pub(crate) iter: I,
12		pub(crate) meta: Meta<Key, F>,
13		}
14
15		impl<I, V, F> fmt::Debug for DuplicatesBy<I, V, F>
16		where
17		I: Iterator + fmt::Debug,
18		V: fmt::Debug + Hash + Eq,
19		{
20		debug_fmt_fields!(DuplicatesBy, iter, meta.used);
21		}
22
23		impl<I: Iterator, Key: Eq + Hash, F> DuplicatesBy<I, Key, F> {
24	0	pub(crate) fn new(iter: I, key_method: F) -> Self {
25	0	DuplicatesBy {
26	0	iter,
27	0	meta: Meta {
28	0	used: HashMap::new(),
29	0	pending: 0,
30	0	key_method,
31	0	},
32	0	}
33	0	}
34		}
35
36		#[derive(Clone)]
37		pub struct Meta<Key, F> {
38		used: HashMap<Key, bool>,
39		pending: usize,
40		key_method: F,
41		}
42
43		impl<Key, F> Meta<Key, F>
44		where
45		Key: Eq + Hash,
46		{
47		/// Takes an item and returns it back to the caller if it's the second time we see it.
48		/// Otherwise the item is consumed and None is returned
49		#[inline(always)]
50	0	fn filter<I>(&mut self, item: I) -> Option<I>
51	0	where
52	0	F: KeyMethod<Key, I>,
53	0	{
54	0	let kv = self.key_method.make(item);
55	0	match self.used.get_mut(kv.key_ref()) {
56		None => {
57	0	self.used.insert(kv.key(), false);
58	0	self.pending += 1;
59	0	None
60		}
61	0	Some(true) => None,
62	0	Some(produced) => {
63	0	*produced = true;
64	0	self.pending -= 1;
65	0	Some(kv.value())
66		}
67		}
68	0	}
69		}
70
71		impl<I, Key, F> Iterator for DuplicatesBy<I, Key, F>
72		where
73		I: Iterator,
74		Key: Eq + Hash,
75		F: KeyMethod<Key, I::Item>,
76		{
77		type Item = I::Item;
78
79	0	fn next(&mut self) -> Option<Self::Item> {
80	0	let DuplicatesBy { iter, meta } = self;
81	0	iter.find_map(\|v\| meta.filter(v))
82	0	}
83
84		#[inline]
85	0	fn size_hint(&self) -> (usize, Option<usize>) {
86	0	let (_, hi) = self.iter.size_hint();
87	0	let hi = hi.map(\|hi\| {
88	0	if hi <= self.meta.pending {
89		// fewer or equally many iter-remaining elements than pending elements
90		// => at most, each iter-remaining element is matched
91	0	hi
92		} else {
93		// fewer pending elements than iter-remaining elements
94		// => at most:
95		// * each pending element is matched
96		// * the other iter-remaining elements come in pairs
97	0	self.meta.pending + (hi - self.meta.pending) / 2
98		}
99	0	});
100	0	// The lower bound is always 0 since we might only get unique items from now on
101	0	(0, hi)
102	0	}
103		}
104
105		impl<I, Key, F> DoubleEndedIterator for DuplicatesBy<I, Key, F>
106		where
107		I: DoubleEndedIterator,
108		Key: Eq + Hash,
109		F: KeyMethod<Key, I::Item>,
110		{
111	0	fn next_back(&mut self) -> Option<Self::Item> {
112	0	let DuplicatesBy { iter, meta } = self;
113	0	iter.rev().find_map(\|v\| meta.filter(v))
114	0	}
115		}
116
117		/// A keying method for use with `DuplicatesBy`
118		pub trait KeyMethod<K, V> {
119		type Container: KeyXorValue<K, V>;
120
121		fn make(&mut self, value: V) -> Self::Container;
122		}
123
124		/// Apply the identity function to elements before checking them for equality.
125		#[derive(Debug)]
126		pub struct ById;
127		impl<V> KeyMethod<V, V> for ById {
128		type Container = JustValue<V>;
129
130	0	fn make(&mut self, v: V) -> Self::Container {
131	0	JustValue(v)
132	0	}
133		}
134
135		/// Apply a user-supplied function to elements before checking them for equality.
136		pub struct ByFn<F>(pub(crate) F);
137		impl<F> fmt::Debug for ByFn<F> {
138		debug_fmt_fields!(ByFn,);
139		}
140		impl<K, V, F> KeyMethod<K, V> for ByFn<F>
141		where
142		F: FnMut(&V) -> K,
143		{
144		type Container = KeyValue<K, V>;
145
146	0	fn make(&mut self, v: V) -> Self::Container {
147	0	KeyValue((self.0)(&v), v)
148	0	}
149		}
150
151		// Implementors of this trait can hold onto a key and a value but only give access to one of them
152		// at a time. This allows the key and the value to be the same value internally
153		pub trait KeyXorValue<K, V> {
154		fn key_ref(&self) -> &K;
155		fn key(self) -> K;
156		fn value(self) -> V;
157		}
158
159		#[derive(Debug)]
160		pub struct KeyValue<K, V>(K, V);
161		impl<K, V> KeyXorValue<K, V> for KeyValue<K, V> {
162	0	fn key_ref(&self) -> &K {
163	0	&self.0
164	0	}
165	0	fn key(self) -> K {
166	0	self.0
167	0	}
168	0	fn value(self) -> V {
169	0	self.1
170	0	}
171		}
172
173		#[derive(Debug)]
174		pub struct JustValue<V>(V);
175		impl<V> KeyXorValue<V, V> for JustValue<V> {
176	0	fn key_ref(&self) -> &V {
177	0	&self.0
178	0	}
179	0	fn key(self) -> V {
180	0	self.0
181	0	}
182	0	fn value(self) -> V {
183	0	self.0
184	0	}
185		}
186		}
187
188		/// An iterator adapter to filter for duplicate elements.
189		///
190		/// See [`.duplicates_by()`](crate::Itertools::duplicates_by) for more information.
191		pub type DuplicatesBy<I, V, F> = private::DuplicatesBy<I, V, private::ByFn<F>>;
192
193		/// Create a new `DuplicatesBy` iterator.
194	0	pub fn duplicates_by<I, Key, F>(iter: I, f: F) -> DuplicatesBy<I, Key, F>
195	0	where
196	0	Key: Eq + Hash,
197	0	F: FnMut(&I::Item) -> Key,
198	0	I: Iterator,
199	0	{
200	0	DuplicatesBy::new(iter, private::ByFn(f))
201	0	}
202
203		/// An iterator adapter to filter out duplicate elements.
204		///
205		/// See [`.duplicates()`](crate::Itertools::duplicates) for more information.
206		pub type Duplicates<I> = private::DuplicatesBy<I, <I as Iterator>::Item, private::ById>;
207
208		/// Create a new `Duplicates` iterator.
209	0	pub fn duplicates<I>(iter: I) -> Duplicates<I>
210	0	where
211	0	I: Iterator,
212	0	I::Item: Eq + Hash,
213	0	{
214	0	Duplicates::new(iter, private::ById)
215	0	}
216