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