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