/rust/registry/src/index.crates.io-6f17d22bba15001f/indexmap-2.10.0/src/set/iter.rs

Source (jump to first uncovered line)
use crate::map::{ExtractCore, IndexMapCore};

use super::{Bucket, IndexSet, Slice};

use alloc::vec::{self, Vec};
use core::fmt;
use core::hash::{BuildHasher, Hash};
use core::iter::{Chain, FusedIterator};
use core::ops::RangeBounds;
use core::slice::Iter as SliceIter;

impl<'a, T, S> IntoIterator for &'a IndexSet<T, S> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<T, S> IntoIterator for IndexSet<T, S> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter::new(self.into_entries())
    }
}

/// An iterator over the items of an [`IndexSet`].
///
/// This `struct` is created by the [`IndexSet::iter`] method.
/// See its documentation for more.
pub struct Iter<'a, T> {
    iter: SliceIter<'a, Bucket<T>>,
}

impl<'a, T> Iter<'a, T> {
    pub(super) fn new(entries: &'a [Bucket<T>]) -> Self {
        Self {
            iter: entries.iter(),
        }
    }

    /// Returns a slice of the remaining entries in the iterator.
    pub fn as_slice(&self) -> &'a Slice<T> {
        Slice::from_slice(self.iter.as_slice())
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    iterator_methods!(Bucket::key_ref);
}

impl<T> DoubleEndedIterator for Iter<'_, T> {
    double_ended_iterator_methods!(Bucket::key_ref);
}

impl<T> ExactSizeIterator for Iter<'_, T> {
    fn len(&self) -> usize {
        self.iter.len()
    }
}

impl<T> FusedIterator for Iter<'_, T> {}

impl<T> Clone for Iter<'_, T> {
    fn clone(&self) -> Self {
        Iter {
            iter: self.iter.clone(),
        }
    }
}

impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_list().entries(self.clone()).finish()
    }
}

impl<T> Default for Iter<'_, T> {
    fn default() -> Self {
        Self { iter: [].iter() }
    }
}

/// An owning iterator over the items of an [`IndexSet`].
///
/// This `struct` is created by the [`IndexSet::into_iter`] method
/// (provided by the [`IntoIterator`] trait). See its documentation for more.
#[derive(Clone)]
pub struct IntoIter<T> {
    iter: vec::IntoIter<Bucket<T>>,
}

impl<T> IntoIter<T> {
    pub(super) fn new(entries: Vec<Bucket<T>>) -> Self {
        Self {
            iter: entries.into_iter(),
        }
    }

    /// Returns a slice of the remaining entries in the iterator.
    pub fn as_slice(&self) -> &Slice<T> {
        Slice::from_slice(self.iter.as_slice())
    }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    iterator_methods!(Bucket::key);
}

impl<T> DoubleEndedIterator for IntoIter<T> {
    double_ended_iterator_methods!(Bucket::key);
}

impl<T> ExactSizeIterator for IntoIter<T> {
    fn len(&self) -> usize {
        self.iter.len()
    }
}

impl<T> FusedIterator for IntoIter<T> {}

impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let iter = self.iter.as_slice().iter().map(Bucket::key_ref);
        f.debug_list().entries(iter).finish()
    }
}

impl<T> Default for IntoIter<T> {
    fn default() -> Self {
        Self {
            iter: Vec::new().into_iter(),
        }
    }
}

/// A draining iterator over the items of an [`IndexSet`].
///
/// This `struct` is created by the [`IndexSet::drain`] method.
/// See its documentation for more.
pub struct Drain<'a, T> {
    iter: vec::Drain<'a, Bucket<T>>,
}

impl<'a, T> Drain<'a, T> {
    pub(super) fn new(iter: vec::Drain<'a, Bucket<T>>) -> Self {
        Self { iter }
    }

    /// Returns a slice of the remaining entries in the iterator.
    pub fn as_slice(&self) -> &Slice<T> {
        Slice::from_slice(self.iter.as_slice())
    }
}

impl<T> Iterator for Drain<'_, T> {
    type Item = T;

    iterator_methods!(Bucket::key);
}

impl<T> DoubleEndedIterator for Drain<'_, T> {
    double_ended_iterator_methods!(Bucket::key);
}

impl<T> ExactSizeIterator for Drain<'_, T> {
    fn len(&self) -> usize {
        self.iter.len()
    }
}

impl<T> FusedIterator for Drain<'_, T> {}

impl<T: fmt::Debug> fmt::Debug for Drain<'_, T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let iter = self.iter.as_slice().iter().map(Bucket::key_ref);
        f.debug_list().entries(iter).finish()
    }
}

/// A lazy iterator producing elements in the difference of [`IndexSet`]s.
///
/// This `struct` is created by the [`IndexSet::difference`] method.
/// See its documentation for more.
pub struct Difference<'a, T, S> {
    iter: Iter<'a, T>,
    other: &'a IndexSet<T, S>,
}

impl<'a, T, S> Difference<'a, T, S> {
    pub(super) fn new<S1>(set: &'a IndexSet<T, S1>, other: &'a IndexSet<T, S>) -> Self {
        Self {
            iter: set.iter(),
            other,
        }
    }
}

impl<'a, T, S> Iterator for Difference<'a, T, S>
where
    T: Eq + Hash,
    S: BuildHasher,
{
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        while let Some(item) = self.iter.next() {
            if !self.other.contains(item) {
                return Some(item);
            }
        }
        None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, self.iter.size_hint().1)
    }
}

impl<T, S> DoubleEndedIterator for Difference<'_, T, S>
where
    T: Eq + Hash,
    S: BuildHasher,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        while let Some(item) = self.iter.next_back() {
            if !self.other.contains(item) {
                return Some(item);
            }
        }
        None
    }
}

impl<T, S> FusedIterator for Difference<'_, T, S>
where
    T: Eq + Hash,
    S: BuildHasher,
{
}

impl<T, S> Clone for Difference<'_, T, S> {
    fn clone(&self) -> Self {
        Difference {
            iter: self.iter.clone(),
            ..*self
        }
    }
}

impl<T, S> fmt::Debug for Difference<'_, T, S>
where
    T: fmt::Debug + Eq + Hash,
    S: BuildHasher,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_list().entries(self.clone()).finish()
    }
}

/// A lazy iterator producing elements in the intersection of [`IndexSet`]s.
///
/// This `struct` is created by the [`IndexSet::intersection`] method.
/// See its documentation for more.
pub struct Intersection<'a, T, S> {
    iter: Iter<'a, T>,
    other: &'a IndexSet<T, S>,
}

impl<'a, T, S> Intersection<'a, T, S> {
    pub(super) fn new<S1>(set: &'a IndexSet<T, S1>, other: &'a IndexSet<T, S>) -> Self {
        Self {
            iter: set.iter(),
            other,
        }
    }
}

impl<'a, T, S> Iterator for Intersection<'a, T, S>
where
    T: Eq + Hash,
    S: BuildHasher,
{
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        while let Some(item) = self.iter.next() {
            if self.other.contains(item) {
                return Some(item);
            }
        }
        None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, self.iter.size_hint().1)
    }
}

impl<T, S> DoubleEndedIterator for Intersection<'_, T, S>
where
    T: Eq + Hash,
    S: BuildHasher,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        while let Some(item) = self.iter.next_back() {
            if self.other.contains(item) {
                return Some(item);
            }
        }
        None
    }
}

impl<T, S> FusedIterator for Intersection<'_, T, S>
where
    T: Eq + Hash,
    S: BuildHasher,
{
}

impl<T, S> Clone for Intersection<'_, T, S> {
    fn clone(&self) -> Self {
        Intersection {
            iter: self.iter.clone(),
            ..*self
        }
    }
}

impl<T, S> fmt::Debug for Intersection<'_, T, S>
where
    T: fmt::Debug + Eq + Hash,
    S: BuildHasher,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_list().entries(self.clone()).finish()
    }
}

/// A lazy iterator producing elements in the symmetric difference of [`IndexSet`]s.
///
/// This `struct` is created by the [`IndexSet::symmetric_difference`] method.
/// See its documentation for more.
pub struct SymmetricDifference<'a, T, S1, S2> {
    iter: Chain<Difference<'a, T, S2>, Difference<'a, T, S1>>,
}

impl<'a, T, S1, S2> SymmetricDifference<'a, T, S1, S2>
where
    T: Eq + Hash,
    S1: BuildHasher,
    S2: BuildHasher,
{
    pub(super) fn new(set1: &'a IndexSet<T, S1>, set2: &'a IndexSet<T, S2>) -> Self {
        let diff1 = set1.difference(set2);
        let diff2 = set2.difference(set1);
        Self {
            iter: diff1.chain(diff2),
        }
    }
}

impl<'a, T, S1, S2> Iterator for SymmetricDifference<'a, T, S1, S2>
where
    T: Eq + Hash,
    S1: BuildHasher,
    S2: BuildHasher,
{
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next()
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }

    fn fold<B, F>(self, init: B, f: F) -> B
    where
        F: FnMut(B, Self::Item) -> B,
    {
        self.iter.fold(init, f)
    }
}

impl<T, S1, S2> DoubleEndedIterator for SymmetricDifference<'_, T, S1, S2>
where
    T: Eq + Hash,
    S1: BuildHasher,
    S2: BuildHasher,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        self.iter.next_back()
    }

    fn rfold<B, F>(self, init: B, f: F) -> B
    where
        F: FnMut(B, Self::Item) -> B,
    {
        self.iter.rfold(init, f)
    }
}

impl<T, S1, S2> FusedIterator for SymmetricDifference<'_, T, S1, S2>
where
    T: Eq + Hash,
    S1: BuildHasher,
    S2: BuildHasher,
{
}

impl<T, S1, S2> Clone for SymmetricDifference<'_, T, S1, S2> {
    fn clone(&self) -> Self {
        SymmetricDifference {
            iter: self.iter.clone(),
        }
    }
}

impl<T, S1, S2> fmt::Debug for SymmetricDifference<'_, T, S1, S2>
where
    T: fmt::Debug + Eq + Hash,
    S1: BuildHasher,
    S2: BuildHasher,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_list().entries(self.clone()).finish()
    }
}

/// A lazy iterator producing elements in the union of [`IndexSet`]s.
///
/// This `struct` is created by the [`IndexSet::union`] method.
/// See its documentation for more.
pub struct Union<'a, T, S> {
    iter: Chain<Iter<'a, T>, Difference<'a, T, S>>,
}

impl<'a, T, S> Union<'a, T, S>
where
    T: Eq + Hash,
    S: BuildHasher,
{
    pub(super) fn new<S2>(set1: &'a IndexSet<T, S>, set2: &'a IndexSet<T, S2>) -> Self
    where
        S2: BuildHasher,
    {
        Self {
            iter: set1.iter().chain(set2.difference(set1)),
        }
    }
}

impl<'a, T, S> Iterator for Union<'a, T, S>
where
    T: Eq + Hash,
    S: BuildHasher,
{
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next()
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }

    fn fold<B, F>(self, init: B, f: F) -> B
    where
        F: FnMut(B, Self::Item) -> B,
    {
        self.iter.fold(init, f)
    }
}

impl<T, S> DoubleEndedIterator for Union<'_, T, S>
where
    T: Eq + Hash,
    S: BuildHasher,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        self.iter.next_back()
    }

    fn rfold<B, F>(self, init: B, f: F) -> B
    where
        F: FnMut(B, Self::Item) -> B,
    {
        self.iter.rfold(init, f)
    }
}

impl<T, S> FusedIterator for Union<'_, T, S>
where
    T: Eq + Hash,
    S: BuildHasher,
{
}

impl<T, S> Clone for Union<'_, T, S> {
    fn clone(&self) -> Self {
        Union {
            iter: self.iter.clone(),
        }
    }
}

impl<T, S> fmt::Debug for Union<'_, T, S>
where
    T: fmt::Debug + Eq + Hash,
    S: BuildHasher,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_list().entries(self.clone()).finish()
    }
}

/// A splicing iterator for `IndexSet`.
///
/// This `struct` is created by [`IndexSet::splice()`].
/// See its documentation for more.
pub struct Splice<'a, I, T, S>
where
    I: Iterator<Item = T>,
    T: Hash + Eq,
    S: BuildHasher,
{
    iter: crate::map::Splice<'a, UnitValue<I>, T, (), S>,
}

impl<'a, I, T, S> Splice<'a, I, T, S>
where
    I: Iterator<Item = T>,
    T: Hash + Eq,
    S: BuildHasher,
{
    #[track_caller]
    pub(super) fn new<R>(set: &'a mut IndexSet<T, S>, range: R, replace_with: I) -> Self
    where
        R: RangeBounds<usize>,
    {
        Self {
            iter: set.map.splice(range, UnitValue(replace_with)),
        }
    }
}

impl<I, T, S> Iterator for Splice<'_, I, T, S>
where
    I: Iterator<Item = T>,
    T: Hash + Eq,
    S: BuildHasher,
{
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        Some(self.iter.next()?.0)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }
}

impl<I, T, S> DoubleEndedIterator for Splice<'_, I, T, S>
where
    I: Iterator<Item = T>,
    T: Hash + Eq,
    S: BuildHasher,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        Some(self.iter.next_back()?.0)
    }
}

impl<I, T, S> ExactSizeIterator for Splice<'_, I, T, S>
where
    I: Iterator<Item = T>,
    T: Hash + Eq,
    S: BuildHasher,
{
    fn len(&self) -> usize {
        self.iter.len()
    }
}

impl<I, T, S> FusedIterator for Splice<'_, I, T, S>
where
    I: Iterator<Item = T>,
    T: Hash + Eq,
    S: BuildHasher,
{
}

struct UnitValue<I>(I);

impl<I: Iterator> Iterator for UnitValue<I> {
    type Item = (I::Item, ());

    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|x| (x, ()))
    }
}

impl<I, T, S> fmt::Debug for Splice<'_, I, T, S>
where
    I: fmt::Debug + Iterator<Item = T>,
    T: fmt::Debug + Hash + Eq,
    S: BuildHasher,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(&self.iter, f)
    }
}

impl<I: fmt::Debug> fmt::Debug for UnitValue<I> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(&self.0, f)
    }
}

/// An extracting iterator for `IndexSet`.
///
/// This `struct` is created by [`IndexSet::extract_if()`].
/// See its documentation for more.
pub struct ExtractIf<'a, T, F> {
    inner: ExtractCore<'a, T, ()>,
    pred: F,
}

impl<T, F> ExtractIf<'_, T, F> {
    #[track_caller]
    pub(super) fn new<R>(core: &mut IndexMapCore<T, ()>, range: R, pred: F) -> ExtractIf<'_, T, F>
    where
        R: RangeBounds<usize>,
        F: FnMut(&T) -> bool,
    {
        ExtractIf {
            inner: core.extract(range),
            pred,
        }
    }
}

impl<T, F> Iterator for ExtractIf<'_, T, F>
where
    F: FnMut(&T) -> bool,
{
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner
            .extract_if(|bucket| (self.pred)(bucket.key_ref()))
            .map(Bucket::key)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, Some(self.inner.remaining()))
    }
}

impl<T, F> FusedIterator for ExtractIf<'_, T, F> where F: FnMut(&T) -> bool {}

impl<T, F> fmt::Debug for ExtractIf<'_, T, F>
where
    T: fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("ExtractIf").finish_non_exhaustive()
    }
}

Coverage Report

Created: 2025-07-12 06:26

Line	Count	Source (jump to first uncovered line)
1		use crate::map::{ExtractCore, IndexMapCore};
2
3		use super::{Bucket, IndexSet, Slice};
4
5		use alloc::vec::{self, Vec};
6		use core::fmt;
7		use core::hash::{BuildHasher, Hash};
8		use core::iter::{Chain, FusedIterator};
9		use core::ops::RangeBounds;
10		use core::slice::Iter as SliceIter;
11
12		impl<'a, T, S> IntoIterator for &'a IndexSet<T, S> {
13		type Item = &'a T;
14		type IntoIter = Iter<'a, T>;
15
16	0	fn into_iter(self) -> Self::IntoIter {
17	0	self.iter()
18	0	}
19		}
20
21		impl<T, S> IntoIterator for IndexSet<T, S> {
22		type Item = T;
23		type IntoIter = IntoIter<T>;
24
25	0	fn into_iter(self) -> Self::IntoIter {
26	0	IntoIter::new(self.into_entries())
27	0	}
28		}
29
30		/// An iterator over the items of an [`IndexSet`].
31		///
32		/// This `struct` is created by the [`IndexSet::iter`] method.
33		/// See its documentation for more.
34		pub struct Iter<'a, T> {
35		iter: SliceIter<'a, Bucket<T>>,
36		}
37
38		impl<'a, T> Iter<'a, T> {
39	0	pub(super) fn new(entries: &'a [Bucket<T>]) -> Self {
40	0	Self {
41	0	iter: entries.iter(),
42	0	}
43	0	}
44
45		/// Returns a slice of the remaining entries in the iterator.
46	0	pub fn as_slice(&self) -> &'a Slice<T> {
47	0	Slice::from_slice(self.iter.as_slice())
48	0	}
49		}
50
51		impl<'a, T> Iterator for Iter<'a, T> {
52		type Item = &'a T;
53
54		iterator_methods!(Bucket::key_ref);
55		}
56
57		impl<T> DoubleEndedIterator for Iter<'_, T> {
58		double_ended_iterator_methods!(Bucket::key_ref);
59		}
60
61		impl<T> ExactSizeIterator for Iter<'_, T> {
62	0	fn len(&self) -> usize {
63	0	self.iter.len()
64	0	}
65		}
66
67		impl<T> FusedIterator for Iter<'_, T> {}
68
69		impl<T> Clone for Iter<'_, T> {
70	0	fn clone(&self) -> Self {
71	0	Iter {
72	0	iter: self.iter.clone(),
73	0	}
74	0	}
75		}
76
77		impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
78	0	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
79	0	f.debug_list().entries(self.clone()).finish()
80	0	}
81		}
82
83		impl<T> Default for Iter<'_, T> {
84	0	fn default() -> Self {
85	0	Self { iter: [].iter() }
86	0	}
87		}
88
89		/// An owning iterator over the items of an [`IndexSet`].
90		///
91		/// This `struct` is created by the [`IndexSet::into_iter`] method
92		/// (provided by the [`IntoIterator`] trait). See its documentation for more.
93		#[derive(Clone)]
94		pub struct IntoIter<T> {
95		iter: vec::IntoIter<Bucket<T>>,
96		}
97
98		impl<T> IntoIter<T> {
99	0	pub(super) fn new(entries: Vec<Bucket<T>>) -> Self {
100	0	Self {
101	0	iter: entries.into_iter(),
102	0	}
103	0	}
104
105		/// Returns a slice of the remaining entries in the iterator.
106	0	pub fn as_slice(&self) -> &Slice<T> {
107	0	Slice::from_slice(self.iter.as_slice())
108	0	}
109		}
110
111		impl<T> Iterator for IntoIter<T> {
112		type Item = T;
113
114		iterator_methods!(Bucket::key);
115		}
116
117		impl<T> DoubleEndedIterator for IntoIter<T> {
118		double_ended_iterator_methods!(Bucket::key);
119		}
120
121		impl<T> ExactSizeIterator for IntoIter<T> {
122	0	fn len(&self) -> usize {
123	0	self.iter.len()
124	0	}
125		}
126
127		impl<T> FusedIterator for IntoIter<T> {}
128
129		impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
130	0	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
131	0	let iter = self.iter.as_slice().iter().map(Bucket::key_ref);
132	0	f.debug_list().entries(iter).finish()
133	0	}
134		}
135
136		impl<T> Default for IntoIter<T> {
137	0	fn default() -> Self {
138	0	Self {
139	0	iter: Vec::new().into_iter(),
140	0	}
141	0	}
142		}
143
144		/// A draining iterator over the items of an [`IndexSet`].
145		///
146		/// This `struct` is created by the [`IndexSet::drain`] method.
147		/// See its documentation for more.
148		pub struct Drain<'a, T> {
149		iter: vec::Drain<'a, Bucket<T>>,
150		}
151
152		impl<'a, T> Drain<'a, T> {
153	0	pub(super) fn new(iter: vec::Drain<'a, Bucket<T>>) -> Self {
154	0	Self { iter }
155	0	}
156
157		/// Returns a slice of the remaining entries in the iterator.
158	0	pub fn as_slice(&self) -> &Slice<T> {
159	0	Slice::from_slice(self.iter.as_slice())
160	0	}
161		}
162
163		impl<T> Iterator for Drain<'_, T> {
164		type Item = T;
165
166		iterator_methods!(Bucket::key);
167		}
168
169		impl<T> DoubleEndedIterator for Drain<'_, T> {
170		double_ended_iterator_methods!(Bucket::key);
171		}
172
173		impl<T> ExactSizeIterator for Drain<'_, T> {
174	0	fn len(&self) -> usize {
175	0	self.iter.len()
176	0	}
177		}
178
179		impl<T> FusedIterator for Drain<'_, T> {}
180
181		impl<T: fmt::Debug> fmt::Debug for Drain<'_, T> {
182	0	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
183	0	let iter = self.iter.as_slice().iter().map(Bucket::key_ref);
184	0	f.debug_list().entries(iter).finish()
185	0	}
186		}
187
188		/// A lazy iterator producing elements in the difference of [`IndexSet`]s.
189		///
190		/// This `struct` is created by the [`IndexSet::difference`] method.
191		/// See its documentation for more.
192		pub struct Difference<'a, T, S> {
193		iter: Iter<'a, T>,
194		other: &'a IndexSet<T, S>,
195		}
196
197		impl<'a, T, S> Difference<'a, T, S> {
198	0	pub(super) fn new<S1>(set: &'a IndexSet<T, S1>, other: &'a IndexSet<T, S>) -> Self {
199	0	Self {
200	0	iter: set.iter(),
201	0	other,
202	0	}
203	0	}
204		}
205
206		impl<'a, T, S> Iterator for Difference<'a, T, S>
207		where
208		T: Eq + Hash,
209		S: BuildHasher,
210		{
211		type Item = &'a T;
212
213	0	fn next(&mut self) -> Option<Self::Item> {
214	0	while let Some(item) = self.iter.next() {
215	0	if !self.other.contains(item) {
216	0	return Some(item);
217	0	}
218		}
219	0	None
220	0	}
221
222	0	fn size_hint(&self) -> (usize, Option<usize>) {
223	0	(0, self.iter.size_hint().1)
224	0	}
225		}
226
227		impl<T, S> DoubleEndedIterator for Difference<'_, T, S>
228		where
229		T: Eq + Hash,
230		S: BuildHasher,
231		{
232	0	fn next_back(&mut self) -> Option<Self::Item> {
233	0	while let Some(item) = self.iter.next_back() {
234	0	if !self.other.contains(item) {
235	0	return Some(item);
236	0	}
237		}
238	0	None
239	0	}
240		}
241
242		impl<T, S> FusedIterator for Difference<'_, T, S>
243		where
244		T: Eq + Hash,
245		S: BuildHasher,
246		{
247		}
248
249		impl<T, S> Clone for Difference<'_, T, S> {
250	0	fn clone(&self) -> Self {
251	0	Difference {
252	0	iter: self.iter.clone(),
253	0	..*self
254	0	}
255	0	}
256		}
257
258		impl<T, S> fmt::Debug for Difference<'_, T, S>
259		where
260		T: fmt::Debug + Eq + Hash,
261		S: BuildHasher,
262		{
263	0	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
264	0	f.debug_list().entries(self.clone()).finish()
265	0	}
266		}
267
268		/// A lazy iterator producing elements in the intersection of [`IndexSet`]s.
269		///
270		/// This `struct` is created by the [`IndexSet::intersection`] method.
271		/// See its documentation for more.
272		pub struct Intersection<'a, T, S> {
273		iter: Iter<'a, T>,
274		other: &'a IndexSet<T, S>,
275		}
276
277		impl<'a, T, S> Intersection<'a, T, S> {
278	0	pub(super) fn new<S1>(set: &'a IndexSet<T, S1>, other: &'a IndexSet<T, S>) -> Self {
279	0	Self {
280	0	iter: set.iter(),
281	0	other,
282	0	}
283	0	}
284		}
285
286		impl<'a, T, S> Iterator for Intersection<'a, T, S>
287		where
288		T: Eq + Hash,
289		S: BuildHasher,
290		{
291		type Item = &'a T;
292
293	0	fn next(&mut self) -> Option<Self::Item> {
294	0	while let Some(item) = self.iter.next() {
295	0	if self.other.contains(item) {
296	0	return Some(item);
297	0	}
298		}
299	0	None
300	0	}
301
302	0	fn size_hint(&self) -> (usize, Option<usize>) {
303	0	(0, self.iter.size_hint().1)
304	0	}
305		}
306
307		impl<T, S> DoubleEndedIterator for Intersection<'_, T, S>
308		where
309		T: Eq + Hash,
310		S: BuildHasher,
311		{
312	0	fn next_back(&mut self) -> Option<Self::Item> {
313	0	while let Some(item) = self.iter.next_back() {
314	0	if self.other.contains(item) {
315	0	return Some(item);
316	0	}
317		}
318	0	None
319	0	}
320		}
321
322		impl<T, S> FusedIterator for Intersection<'_, T, S>
323		where
324		T: Eq + Hash,
325		S: BuildHasher,
326		{
327		}
328
329		impl<T, S> Clone for Intersection<'_, T, S> {
330	0	fn clone(&self) -> Self {
331	0	Intersection {
332	0	iter: self.iter.clone(),
333	0	..*self
334	0	}
335	0	}
336		}
337
338		impl<T, S> fmt::Debug for Intersection<'_, T, S>
339		where
340		T: fmt::Debug + Eq + Hash,
341		S: BuildHasher,
342		{
343	0	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
344	0	f.debug_list().entries(self.clone()).finish()
345	0	}
346		}
347
348		/// A lazy iterator producing elements in the symmetric difference of [`IndexSet`]s.
349		///
350		/// This `struct` is created by the [`IndexSet::symmetric_difference`] method.
351		/// See its documentation for more.
352		pub struct SymmetricDifference<'a, T, S1, S2> {
353		iter: Chain<Difference<'a, T, S2>, Difference<'a, T, S1>>,
354		}
355
356		impl<'a, T, S1, S2> SymmetricDifference<'a, T, S1, S2>
357		where
358		T: Eq + Hash,
359		S1: BuildHasher,
360		S2: BuildHasher,
361		{
362	0	pub(super) fn new(set1: &'a IndexSet<T, S1>, set2: &'a IndexSet<T, S2>) -> Self {
363	0	let diff1 = set1.difference(set2);
364	0	let diff2 = set2.difference(set1);
365	0	Self {
366	0	iter: diff1.chain(diff2),
367	0	}
368	0	}
369		}
370
371		impl<'a, T, S1, S2> Iterator for SymmetricDifference<'a, T, S1, S2>
372		where
373		T: Eq + Hash,
374		S1: BuildHasher,
375		S2: BuildHasher,
376		{
377		type Item = &'a T;
378
379	0	fn next(&mut self) -> Option<Self::Item> {
380	0	self.iter.next()
381	0	}
382
383	0	fn size_hint(&self) -> (usize, Option<usize>) {
384	0	self.iter.size_hint()
385	0	}
386
387	0	fn fold<B, F>(self, init: B, f: F) -> B
388	0	where
389	0	F: FnMut(B, Self::Item) -> B,
390	0	{
391	0	self.iter.fold(init, f)
392	0	}
393		}
394
395		impl<T, S1, S2> DoubleEndedIterator for SymmetricDifference<'_, T, S1, S2>
396		where
397		T: Eq + Hash,
398		S1: BuildHasher,
399		S2: BuildHasher,
400		{
401	0	fn next_back(&mut self) -> Option<Self::Item> {
402	0	self.iter.next_back()
403	0	}
404
405	0	fn rfold<B, F>(self, init: B, f: F) -> B
406	0	where
407	0	F: FnMut(B, Self::Item) -> B,
408	0	{
409	0	self.iter.rfold(init, f)
410	0	}
411		}
412
413		impl<T, S1, S2> FusedIterator for SymmetricDifference<'_, T, S1, S2>
414		where
415		T: Eq + Hash,
416		S1: BuildHasher,
417		S2: BuildHasher,
418		{
419		}
420
421		impl<T, S1, S2> Clone for SymmetricDifference<'_, T, S1, S2> {
422	0	fn clone(&self) -> Self {
423	0	SymmetricDifference {
424	0	iter: self.iter.clone(),
425	0	}
426	0	}
427		}
428
429		impl<T, S1, S2> fmt::Debug for SymmetricDifference<'_, T, S1, S2>
430		where
431		T: fmt::Debug + Eq + Hash,
432		S1: BuildHasher,
433		S2: BuildHasher,
434		{
435	0	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
436	0	f.debug_list().entries(self.clone()).finish()
437	0	}
438		}
439
440		/// A lazy iterator producing elements in the union of [`IndexSet`]s.
441		///
442		/// This `struct` is created by the [`IndexSet::union`] method.
443		/// See its documentation for more.
444		pub struct Union<'a, T, S> {
445		iter: Chain<Iter<'a, T>, Difference<'a, T, S>>,
446		}
447
448		impl<'a, T, S> Union<'a, T, S>
449		where
450		T: Eq + Hash,
451		S: BuildHasher,
452		{
453	0	pub(super) fn new<S2>(set1: &'a IndexSet<T, S>, set2: &'a IndexSet<T, S2>) -> Self
454	0	where
455	0	S2: BuildHasher,
456	0	{
457	0	Self {
458	0	iter: set1.iter().chain(set2.difference(set1)),
459	0	}
460	0	}
461		}
462
463		impl<'a, T, S> Iterator for Union<'a, T, S>
464		where
465		T: Eq + Hash,
466		S: BuildHasher,
467		{
468		type Item = &'a T;
469
470	0	fn next(&mut self) -> Option<Self::Item> {
471	0	self.iter.next()
472	0	}
473
474	0	fn size_hint(&self) -> (usize, Option<usize>) {
475	0	self.iter.size_hint()
476	0	}
477
478	0	fn fold<B, F>(self, init: B, f: F) -> B
479	0	where
480	0	F: FnMut(B, Self::Item) -> B,
481	0	{
482	0	self.iter.fold(init, f)
483	0	}
484		}
485
486		impl<T, S> DoubleEndedIterator for Union<'_, T, S>
487		where
488		T: Eq + Hash,
489		S: BuildHasher,
490		{
491	0	fn next_back(&mut self) -> Option<Self::Item> {
492	0	self.iter.next_back()
493	0	}
494
495	0	fn rfold<B, F>(self, init: B, f: F) -> B
496	0	where
497	0	F: FnMut(B, Self::Item) -> B,
498	0	{
499	0	self.iter.rfold(init, f)
500	0	}
501		}
502
503		impl<T, S> FusedIterator for Union<'_, T, S>
504		where
505		T: Eq + Hash,
506		S: BuildHasher,
507		{
508		}
509
510		impl<T, S> Clone for Union<'_, T, S> {
511	0	fn clone(&self) -> Self {
512	0	Union {
513	0	iter: self.iter.clone(),
514	0	}
515	0	}
516		}
517
518		impl<T, S> fmt::Debug for Union<'_, T, S>
519		where
520		T: fmt::Debug + Eq + Hash,
521		S: BuildHasher,
522		{
523	0	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
524	0	f.debug_list().entries(self.clone()).finish()
525	0	}
526		}
527
528		/// A splicing iterator for `IndexSet`.
529		///
530		/// This `struct` is created by [`IndexSet::splice()`].
531		/// See its documentation for more.
532		pub struct Splice<'a, I, T, S>
533		where
534		I: Iterator<Item = T>,
535		T: Hash + Eq,
536		S: BuildHasher,
537		{
538		iter: crate::map::Splice<'a, UnitValue<I>, T, (), S>,
539		}
540
541		impl<'a, I, T, S> Splice<'a, I, T, S>
542		where
543		I: Iterator<Item = T>,
544		T: Hash + Eq,
545		S: BuildHasher,
546		{
547		#[track_caller]
548	0	pub(super) fn new<R>(set: &'a mut IndexSet<T, S>, range: R, replace_with: I) -> Self
549	0	where
550	0	R: RangeBounds<usize>,
551	0	{
552	0	Self {
553	0	iter: set.map.splice(range, UnitValue(replace_with)),
554	0	}
555	0	}
556		}
557
558		impl<I, T, S> Iterator for Splice<'_, I, T, S>
559		where
560		I: Iterator<Item = T>,
561		T: Hash + Eq,
562		S: BuildHasher,
563		{
564		type Item = T;
565
566	0	fn next(&mut self) -> Option<Self::Item> {
567	0	Some(self.iter.next()?.0)
568	0	}
569
570	0	fn size_hint(&self) -> (usize, Option<usize>) {
571	0	self.iter.size_hint()
572	0	}
573		}
574
575		impl<I, T, S> DoubleEndedIterator for Splice<'_, I, T, S>
576		where
577		I: Iterator<Item = T>,
578		T: Hash + Eq,
579		S: BuildHasher,
580		{
581	0	fn next_back(&mut self) -> Option<Self::Item> {
582	0	Some(self.iter.next_back()?.0)
583	0	}
584		}
585
586		impl<I, T, S> ExactSizeIterator for Splice<'_, I, T, S>
587		where
588		I: Iterator<Item = T>,
589		T: Hash + Eq,
590		S: BuildHasher,
591		{
592	0	fn len(&self) -> usize {
593	0	self.iter.len()
594	0	}
595		}
596
597		impl<I, T, S> FusedIterator for Splice<'_, I, T, S>
598		where
599		I: Iterator<Item = T>,
600		T: Hash + Eq,
601		S: BuildHasher,
602		{
603		}
604
605		struct UnitValue<I>(I);
606
607		impl<I: Iterator> Iterator for UnitValue<I> {
608		type Item = (I::Item, ());
609
610	0	fn next(&mut self) -> Option<Self::Item> {
611	0	self.0.next().map(\|x\| (x, ()))
612	0	}
613		}
614
615		impl<I, T, S> fmt::Debug for Splice<'_, I, T, S>
616		where
617		I: fmt::Debug + Iterator<Item = T>,
618		T: fmt::Debug + Hash + Eq,
619		S: BuildHasher,
620		{
621	0	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
622	0	fmt::Debug::fmt(&self.iter, f)
623	0	}
624		}
625
626		impl<I: fmt::Debug> fmt::Debug for UnitValue<I> {
627	0	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
628	0	fmt::Debug::fmt(&self.0, f)
629	0	}
630		}
631
632		/// An extracting iterator for `IndexSet`.
633		///
634		/// This `struct` is created by [`IndexSet::extract_if()`].
635		/// See its documentation for more.
636		pub struct ExtractIf<'a, T, F> {
637		inner: ExtractCore<'a, T, ()>,
638		pred: F,
639		}
640
641		impl<T, F> ExtractIf<'_, T, F> {
642		#[track_caller]
643	0	pub(super) fn new<R>(core: &mut IndexMapCore<T, ()>, range: R, pred: F) -> ExtractIf<'_, T, F>
644	0	where
645	0	R: RangeBounds<usize>,
646	0	F: FnMut(&T) -> bool,
647	0	{
648	0	ExtractIf {
649	0	inner: core.extract(range),
650	0	pred,
651	0	}
652	0	}
653		}
654
655		impl<T, F> Iterator for ExtractIf<'_, T, F>
656		where
657		F: FnMut(&T) -> bool,
658		{
659		type Item = T;
660
661	0	fn next(&mut self) -> Option<Self::Item> {
662	0	self.inner
663	0	.extract_if(\|bucket\| (self.pred)(bucket.key_ref()))
664	0	.map(Bucket::key)
665	0	}
666
667	0	fn size_hint(&self) -> (usize, Option<usize>) {
668	0	(0, Some(self.inner.remaining()))
669	0	}
670		}
671
672		impl<T, F> FusedIterator for ExtractIf<'_, T, F> where F: FnMut(&T) -> bool {}
673
674		impl<T, F> fmt::Debug for ExtractIf<'_, T, F>
675		where
676		T: fmt::Debug,
677		{
678	0	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
679	0	f.debug_struct("ExtractIf").finish_non_exhaustive()
680	0	}
681		}