1use super::{Bucket, Entries, IndexSet, Slice};
2
3use alloc::vec::{self, Vec};
4use core::fmt;
5use core::hash::{BuildHasher, Hash};
6use core::iter::{Chain, FusedIterator};
7use core::slice::Iter as SliceIter;
8
9impl<'a, T, S> IntoIterator for &'a IndexSet<T, S> {
10 type Item = &'a T;
11 type IntoIter = Iter<'a, T>;
12
13 fn into_iter(self) -> Self::IntoIter {
14 self.iter()
15 }
16}
17
18impl<T, S> IntoIterator for IndexSet<T, S> {
19 type Item = T;
20 type IntoIter = IntoIter<T>;
21
22 fn into_iter(self) -> Self::IntoIter {
23 IntoIter::new(self.into_entries())
24 }
25}
26
27/// An iterator over the items of a `IndexSet`.
28///
29/// This `struct` is created by the [`iter`] method on [`IndexSet`].
30/// See its documentation for more.
31///
32/// [`IndexSet`]: struct.IndexSet.html
33/// [`iter`]: struct.IndexSet.html#method.iter
34pub struct Iter<'a, T> {
35 iter: SliceIter<'a, Bucket<T>>,
36}
37
38impl<'a, T> Iter<'a, T> {
39 pub(super) fn new(entries: &'a [Bucket<T>]) -> Self {
40 Self {
41 iter: entries.iter(),
42 }
43 }
44
45 /// Returns a slice of the remaining entries in the iterator.
46 pub fn as_slice(&self) -> &'a Slice<T> {
47 Slice::from_slice(self.iter.as_slice())
48 }
49}
50
51impl<'a, T> Iterator for Iter<'a, T> {
52 type Item = &'a T;
53
54 iterator_methods!(Bucket::key_ref);
55}
56
57impl<T> DoubleEndedIterator for Iter<'_, T> {
58 double_ended_iterator_methods!(Bucket::key_ref);
59}
60
61impl<T> ExactSizeIterator for Iter<'_, T> {
62 fn len(&self) -> usize {
63 self.iter.len()
64 }
65}
66
67impl<T> FusedIterator for Iter<'_, T> {}
68
69impl<T> Clone for Iter<'_, T> {
70 fn clone(&self) -> Self {
71 Iter {
72 iter: self.iter.clone(),
73 }
74 }
75}
76
77impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
78 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
79 f.debug_list().entries(self.clone()).finish()
80 }
81}
82
83impl<T> Default for Iter<'_, T> {
84 fn default() -> Self {
85 Self { iter: [].iter() }
86 }
87}
88
89/// An owning iterator over the items of a `IndexSet`.
90///
91/// This `struct` is created by the [`into_iter`] method on [`IndexSet`]
92/// (provided by the `IntoIterator` trait). See its documentation for more.
93///
94/// [`IndexSet`]: struct.IndexSet.html
95/// [`into_iter`]: struct.IndexSet.html#method.into_iter
96pub struct IntoIter<T> {
97 iter: vec::IntoIter<Bucket<T>>,
98}
99
100impl<T> IntoIter<T> {
101 pub(super) fn new(entries: Vec<Bucket<T>>) -> Self {
102 Self {
103 iter: entries.into_iter(),
104 }
105 }
106
107 /// Returns a slice of the remaining entries in the iterator.
108 pub fn as_slice(&self) -> &Slice<T> {
109 Slice::from_slice(self.iter.as_slice())
110 }
111}
112
113impl<T> Iterator for IntoIter<T> {
114 type Item = T;
115
116 iterator_methods!(Bucket::key);
117}
118
119impl<T> DoubleEndedIterator for IntoIter<T> {
120 double_ended_iterator_methods!(Bucket::key);
121}
122
123impl<T> ExactSizeIterator for IntoIter<T> {
124 fn len(&self) -> usize {
125 self.iter.len()
126 }
127}
128
129impl<T> FusedIterator for IntoIter<T> {}
130
131impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
132 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
133 let iter: impl Iterator = self.iter.as_slice().iter().map(Bucket::key_ref);
134 f.debug_list().entries(iter).finish()
135 }
136}
137
138impl<T> Default for IntoIter<T> {
139 fn default() -> Self {
140 Self {
141 iter: Vec::new().into_iter(),
142 }
143 }
144}
145
146/// A draining iterator over the items of a `IndexSet`.
147///
148/// This `struct` is created by the [`drain`] method on [`IndexSet`].
149/// See its documentation for more.
150///
151/// [`IndexSet`]: struct.IndexSet.html
152/// [`drain`]: struct.IndexSet.html#method.drain
153pub struct Drain<'a, T> {
154 iter: vec::Drain<'a, Bucket<T>>,
155}
156
157impl<'a, T> Drain<'a, T> {
158 pub(super) fn new(iter: vec::Drain<'a, Bucket<T>>) -> Self {
159 Self { iter }
160 }
161
162 /// Returns a slice of the remaining entries in the iterator.
163 pub fn as_slice(&self) -> &Slice<T> {
164 Slice::from_slice(self.iter.as_slice())
165 }
166}
167
168impl<T> Iterator for Drain<'_, T> {
169 type Item = T;
170
171 iterator_methods!(Bucket::key);
172}
173
174impl<T> DoubleEndedIterator for Drain<'_, T> {
175 double_ended_iterator_methods!(Bucket::key);
176}
177
178impl<T> ExactSizeIterator for Drain<'_, T> {
179 fn len(&self) -> usize {
180 self.iter.len()
181 }
182}
183
184impl<T> FusedIterator for Drain<'_, T> {}
185
186impl<T: fmt::Debug> fmt::Debug for Drain<'_, T> {
187 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
188 let iter: impl Iterator = self.iter.as_slice().iter().map(Bucket::key_ref);
189 f.debug_list().entries(iter).finish()
190 }
191}
192
193/// A lazy iterator producing elements in the difference of `IndexSet`s.
194///
195/// This `struct` is created by the [`difference`] method on [`IndexSet`].
196/// See its documentation for more.
197///
198/// [`IndexSet`]: struct.IndexSet.html
199/// [`difference`]: struct.IndexSet.html#method.difference
200pub struct Difference<'a, T, S> {
201 iter: Iter<'a, T>,
202 other: &'a IndexSet<T, S>,
203}
204
205impl<'a, T, S> Difference<'a, T, S> {
206 pub(super) fn new<S1>(set: &'a IndexSet<T, S1>, other: &'a IndexSet<T, S>) -> Self {
207 Self {
208 iter: set.iter(),
209 other,
210 }
211 }
212}
213
214impl<'a, T, S> Iterator for Difference<'a, T, S>
215where
216 T: Eq + Hash,
217 S: BuildHasher,
218{
219 type Item = &'a T;
220
221 fn next(&mut self) -> Option<Self::Item> {
222 while let Some(item: &T) = self.iter.next() {
223 if !self.other.contains(item) {
224 return Some(item);
225 }
226 }
227 None
228 }
229
230 fn size_hint(&self) -> (usize, Option<usize>) {
231 (0, self.iter.size_hint().1)
232 }
233}
234
235impl<T, S> DoubleEndedIterator for Difference<'_, T, S>
236where
237 T: Eq + Hash,
238 S: BuildHasher,
239{
240 fn next_back(&mut self) -> Option<Self::Item> {
241 while let Some(item: &T) = self.iter.next_back() {
242 if !self.other.contains(item) {
243 return Some(item);
244 }
245 }
246 None
247 }
248}
249
250impl<T, S> FusedIterator for Difference<'_, T, S>
251where
252 T: Eq + Hash,
253 S: BuildHasher,
254{
255}
256
257impl<T, S> Clone for Difference<'_, T, S> {
258 fn clone(&self) -> Self {
259 Difference {
260 iter: self.iter.clone(),
261 ..*self
262 }
263 }
264}
265
266impl<T, S> fmt::Debug for Difference<'_, T, S>
267where
268 T: fmt::Debug + Eq + Hash,
269 S: BuildHasher,
270{
271 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
272 f.debug_list().entries(self.clone()).finish()
273 }
274}
275
276/// A lazy iterator producing elements in the intersection of `IndexSet`s.
277///
278/// This `struct` is created by the [`intersection`] method on [`IndexSet`].
279/// See its documentation for more.
280///
281/// [`IndexSet`]: struct.IndexSet.html
282/// [`intersection`]: struct.IndexSet.html#method.intersection
283pub struct Intersection<'a, T, S> {
284 iter: Iter<'a, T>,
285 other: &'a IndexSet<T, S>,
286}
287
288impl<'a, T, S> Intersection<'a, T, S> {
289 pub(super) fn new<S1>(set: &'a IndexSet<T, S1>, other: &'a IndexSet<T, S>) -> Self {
290 Self {
291 iter: set.iter(),
292 other,
293 }
294 }
295}
296
297impl<'a, T, S> Iterator for Intersection<'a, T, S>
298where
299 T: Eq + Hash,
300 S: BuildHasher,
301{
302 type Item = &'a T;
303
304 fn next(&mut self) -> Option<Self::Item> {
305 while let Some(item: &T) = self.iter.next() {
306 if self.other.contains(item) {
307 return Some(item);
308 }
309 }
310 None
311 }
312
313 fn size_hint(&self) -> (usize, Option<usize>) {
314 (0, self.iter.size_hint().1)
315 }
316}
317
318impl<T, S> DoubleEndedIterator for Intersection<'_, T, S>
319where
320 T: Eq + Hash,
321 S: BuildHasher,
322{
323 fn next_back(&mut self) -> Option<Self::Item> {
324 while let Some(item: &T) = self.iter.next_back() {
325 if self.other.contains(item) {
326 return Some(item);
327 }
328 }
329 None
330 }
331}
332
333impl<T, S> FusedIterator for Intersection<'_, T, S>
334where
335 T: Eq + Hash,
336 S: BuildHasher,
337{
338}
339
340impl<T, S> Clone for Intersection<'_, T, S> {
341 fn clone(&self) -> Self {
342 Intersection {
343 iter: self.iter.clone(),
344 ..*self
345 }
346 }
347}
348
349impl<T, S> fmt::Debug for Intersection<'_, T, S>
350where
351 T: fmt::Debug + Eq + Hash,
352 S: BuildHasher,
353{
354 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
355 f.debug_list().entries(self.clone()).finish()
356 }
357}
358
359/// A lazy iterator producing elements in the symmetric difference of `IndexSet`s.
360///
361/// This `struct` is created by the [`symmetric_difference`] method on
362/// [`IndexSet`]. See its documentation for more.
363///
364/// [`IndexSet`]: struct.IndexSet.html
365/// [`symmetric_difference`]: struct.IndexSet.html#method.symmetric_difference
366pub struct SymmetricDifference<'a, T, S1, S2> {
367 iter: Chain<Difference<'a, T, S2>, Difference<'a, T, S1>>,
368}
369
370impl<'a, T, S1, S2> SymmetricDifference<'a, T, S1, S2>
371where
372 T: Eq + Hash,
373 S1: BuildHasher,
374 S2: BuildHasher,
375{
376 pub(super) fn new(set1: &'a IndexSet<T, S1>, set2: &'a IndexSet<T, S2>) -> Self {
377 let diff1: Difference<'_, T, S2> = set1.difference(set2);
378 let diff2: Difference<'_, T, S1> = set2.difference(set1);
379 Self {
380 iter: diff1.chain(diff2),
381 }
382 }
383}
384
385impl<'a, T, S1, S2> Iterator for SymmetricDifference<'a, T, S1, S2>
386where
387 T: Eq + Hash,
388 S1: BuildHasher,
389 S2: BuildHasher,
390{
391 type Item = &'a T;
392
393 fn next(&mut self) -> Option<Self::Item> {
394 self.iter.next()
395 }
396
397 fn size_hint(&self) -> (usize, Option<usize>) {
398 self.iter.size_hint()
399 }
400
401 fn fold<B, F>(self, init: B, f: F) -> B
402 where
403 F: FnMut(B, Self::Item) -> B,
404 {
405 self.iter.fold(init, f)
406 }
407}
408
409impl<T, S1, S2> DoubleEndedIterator for SymmetricDifference<'_, T, S1, S2>
410where
411 T: Eq + Hash,
412 S1: BuildHasher,
413 S2: BuildHasher,
414{
415 fn next_back(&mut self) -> Option<Self::Item> {
416 self.iter.next_back()
417 }
418
419 fn rfold<B, F>(self, init: B, f: F) -> B
420 where
421 F: FnMut(B, Self::Item) -> B,
422 {
423 self.iter.rfold(init, f)
424 }
425}
426
427impl<T, S1, S2> FusedIterator for SymmetricDifference<'_, T, S1, S2>
428where
429 T: Eq + Hash,
430 S1: BuildHasher,
431 S2: BuildHasher,
432{
433}
434
435impl<T, S1, S2> Clone for SymmetricDifference<'_, T, S1, S2> {
436 fn clone(&self) -> Self {
437 SymmetricDifference {
438 iter: self.iter.clone(),
439 }
440 }
441}
442
443impl<T, S1, S2> fmt::Debug for SymmetricDifference<'_, T, S1, S2>
444where
445 T: fmt::Debug + Eq + Hash,
446 S1: BuildHasher,
447 S2: BuildHasher,
448{
449 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
450 f.debug_list().entries(self.clone()).finish()
451 }
452}
453
454/// A lazy iterator producing elements in the union of `IndexSet`s.
455///
456/// This `struct` is created by the [`union`] method on [`IndexSet`].
457/// See its documentation for more.
458///
459/// [`IndexSet`]: struct.IndexSet.html
460/// [`union`]: struct.IndexSet.html#method.union
461pub struct Union<'a, T, S> {
462 iter: Chain<Iter<'a, T>, Difference<'a, T, S>>,
463}
464
465impl<'a, T, S> Union<'a, T, S>
466where
467 T: Eq + Hash,
468 S: BuildHasher,
469{
470 pub(super) fn new<S2>(set1: &'a IndexSet<T, S>, set2: &'a IndexSet<T, S2>) -> Self
471 where
472 S2: BuildHasher,
473 {
474 Self {
475 iter: set1.iter().chain(set2.difference(set1)),
476 }
477 }
478}
479
480impl<'a, T, S> Iterator for Union<'a, T, S>
481where
482 T: Eq + Hash,
483 S: BuildHasher,
484{
485 type Item = &'a T;
486
487 fn next(&mut self) -> Option<Self::Item> {
488 self.iter.next()
489 }
490
491 fn size_hint(&self) -> (usize, Option<usize>) {
492 self.iter.size_hint()
493 }
494
495 fn fold<B, F>(self, init: B, f: F) -> B
496 where
497 F: FnMut(B, Self::Item) -> B,
498 {
499 self.iter.fold(init, f)
500 }
501}
502
503impl<T, S> DoubleEndedIterator for Union<'_, T, S>
504where
505 T: Eq + Hash,
506 S: BuildHasher,
507{
508 fn next_back(&mut self) -> Option<Self::Item> {
509 self.iter.next_back()
510 }
511
512 fn rfold<B, F>(self, init: B, f: F) -> B
513 where
514 F: FnMut(B, Self::Item) -> B,
515 {
516 self.iter.rfold(init, f)
517 }
518}
519
520impl<T, S> FusedIterator for Union<'_, T, S>
521where
522 T: Eq + Hash,
523 S: BuildHasher,
524{
525}
526
527impl<T, S> Clone for Union<'_, T, S> {
528 fn clone(&self) -> Self {
529 Union {
530 iter: self.iter.clone(),
531 }
532 }
533}
534
535impl<T, S> fmt::Debug for Union<'_, T, S>
536where
537 T: fmt::Debug + Eq + Hash,
538 S: BuildHasher,
539{
540 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
541 f.debug_list().entries(self.clone()).finish()
542 }
543}
544