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