library/core/src/iter/adapters/intersperse.rs

   1 use super::Peekable;
   2
   3 /// An iterator adapter that places a separator between all elements.
   4 #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
   5 #[derive(Debug, Clone)]
   6 pub struct Intersperse<I: Iterator>
   7 where
   8     I::Item: Clone,
   9 {
  10     separator: I::Item,
  11     iter: Peekable<I>,
  12     needs_sep: bool,
  13 }
  14
  15 impl<I: Iterator> Intersperse<I>
  16 where
  17     I::Item: Clone,
  18 {
  19     pub(in crate::iter) fn new(iter: I, separator: I::Item) -> Self {
  20         Self { iter: iter.peekable(), separator, needs_sep: false }
  21     }
  22 }
  23
  24 #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
  25 impl<I> Iterator for Intersperse<I>
  26 where
  27     I: Iterator,
  28     I::Item: Clone,
  29 {
  30     type Item = I::Item;
  31
  32     #[inline]
  33     fn next(&mut self) -> Option<I::Item> {
  34         if self.needs_sep && self.iter.peek().is_some() {
  35             self.needs_sep = false;
  36             Some(self.separator.clone())
  37         } else {
  38             self.needs_sep = true;
  39             self.iter.next()
  40         }
  41     }
  42
  43     fn fold<B, F>(self, init: B, f: F) -> B
  44     where
  45         Self: Sized,
  46         F: FnMut(B, Self::Item) -> B,
  47     {
  48         let separator = self.separator;
  49         intersperse_fold(self.iter, init, f, move || separator.clone(), self.needs_sep)
  50     }
  51
  52     fn size_hint(&self) -> (usize, Option<usize>) {
  53         intersperse_size_hint(&self.iter, self.needs_sep)
  54     }
  55 }
  56
  57 /// An iterator adapter that places a separator between all elements.
  58 #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
  59 pub struct IntersperseWith<I, G>
  60 where
  61     I: Iterator,
  62 {
  63     separator: G,
  64     iter: Peekable<I>,
  65     needs_sep: bool,
  66 }
  67
  68 // FIXME This manual implementation is needed as #[derive] misplaces trait bounds,
  69 // requiring <I as Iterator>::Item to be Debug on the struct-definition, which is
  70 // not what we want.
  71 #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
  72 impl<I, G> crate::fmt::Debug for IntersperseWith<I, G>
  73 where
  74     I: Iterator + crate::fmt::Debug,
  75     I::Item: crate::fmt::Debug,
  76     G: crate::fmt::Debug,
  77 {
  78     fn fmt(&self, f: &mut crate::fmt::Formatter<'_>) -> crate::fmt::Result {
  79         f.debug_struct("IntersperseWith")
  80             .field("separator", &self.separator)
  81             .field("iter", &self.iter)
  82             .field("needs_sep", &self.needs_sep)
  83             .finish()
  84     }
  85 }
  86
  87 // FIXME This manual implementation is needed as #[derive] misplaces trait bounds,
  88 // requiring <I as Iterator>::Item to be Clone on the struct-definition, which is
  89 // not what we want.
  90 #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
  91 impl<I, G> crate::clone::Clone for IntersperseWith<I, G>
  92 where
  93     I: Iterator + crate::clone::Clone,
  94     I::Item: crate::clone::Clone,
  95     G: Clone,
  96 {
  97     fn clone(&self) -> Self {
  98         IntersperseWith {
  99             separator: self.separator.clone(),
 100             iter: self.iter.clone(),
 101             needs_sep: self.needs_sep.clone(),
 102         }
 103     }
 104 }
 105
 106 impl<I, G> IntersperseWith<I, G>
 107 where
 108     I: Iterator,
 109     G: FnMut() -> I::Item,
 110 {
 111     pub(in crate::iter) fn new(iter: I, separator: G) -> Self {
 112         Self { iter: iter.peekable(), separator, needs_sep: false }
 113     }
 114 }
 115
 116 #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
 117 impl<I, G> Iterator for IntersperseWith<I, G>
 118 where
 119     I: Iterator,
 120     G: FnMut() -> I::Item,
 121 {
 122     type Item = I::Item;
 123
 124     #[inline]
 125     fn next(&mut self) -> Option<I::Item> {
 126         if self.needs_sep && self.iter.peek().is_some() {
 127             self.needs_sep = false;
 128             Some((self.separator)())
 129         } else {
 130             self.needs_sep = true;
 131             self.iter.next()
 132         }
 133     }
 134
 135     fn fold<B, F>(self, init: B, f: F) -> B
 136     where
 137         Self: Sized,
 138         F: FnMut(B, Self::Item) -> B,
 139     {
 140         intersperse_fold(self.iter, init, f, self.separator, self.needs_sep)
 141     }
 142
 143     fn size_hint(&self) -> (usize, Option<usize>) {
 144         intersperse_size_hint(&self.iter, self.needs_sep)
 145     }
 146 }
 147
 148 fn intersperse_size_hint<I>(iter: &I, needs_sep: bool) -> (usize, Option<usize>)
 149 where
 150     I: Iterator,
 151 {
 152     let (lo, hi) = iter.size_hint();
 153     let next_is_elem = !needs_sep;
 154     let lo = lo.saturating_sub(next_is_elem as usize).saturating_add(lo);
 155     let hi = match hi {
 156         Some(hi) => hi.saturating_sub(next_is_elem as usize).checked_add(hi),
 157         None => None,
 158     };
 159     (lo, hi)
 160 }
 161
 162 fn intersperse_fold<I, B, F, G>(
 163     mut iter: Peekable<I>,
 164     init: B,
 165     mut f: F,
 166     mut separator: G,
 167     needs_sep: bool,
 168 ) -> B
 169 where
 170     I: Iterator,
 171     F: FnMut(B, I::Item) -> B,
 172     G: FnMut() -> I::Item,
 173 {
 174     let mut accum = init;
 175
 176     // Use `peek()` first to avoid calling `next()` on an empty iterator.
 177     if !needs_sep || iter.peek().is_some() {
 178         if let Some(x) = iter.next() {
 179             accum = f(accum, x);
 180         }
 181     }
 182
 183     iter.fold(accum, |mut accum, x| {
 184         accum = f(accum, separator());
 185         accum = f(accum, x);
 186         accum
 187     })
 188 }