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

   1 use super::Peekable;
   2
   3 /// An iterator adapter that places a separator between all elements.
   4 ///
   5 /// This `struct` is created by [`Iterator::intersperse`]. See its documentation
   6 /// for more information.
   7 #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
   8 #[derive(Debug, Clone)]
   9 pub struct Intersperse<I: Iterator>
  10 where
  11     I::Item: Clone,
  12 {
  13     separator: I::Item,
  14     iter: Peekable<I>,
  15     needs_sep: bool,
  16 }
  17
  18 impl<I: Iterator> Intersperse<I>
  19 where
  20     I::Item: Clone,
  21 {
  22     pub(in crate::iter) fn new(iter: I, separator: I::Item) -> Self {
  23         Self { iter: iter.peekable(), separator, needs_sep: false }
  24     }
  25 }
  26
  27 #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
  28 impl<I> Iterator for Intersperse<I>
  29 where
  30     I: Iterator,
  31     I::Item: Clone,
  32 {
  33     type Item = I::Item;
  34
  35     #[inline]
  36     fn next(&mut self) -> Option<I::Item> {
  37         if self.needs_sep && self.iter.peek().is_some() {
  38             self.needs_sep = false;
  39             Some(self.separator.clone())
  40         } else {
  41             self.needs_sep = true;
  42             self.iter.next()
  43         }
  44     }
  45
  46     fn fold<B, F>(self, init: B, f: F) -> B
  47     where
  48         Self: Sized,
  49         F: FnMut(B, Self::Item) -> B,
  50     {
  51         let separator = self.separator;
  52         intersperse_fold(self.iter, init, f, move || separator.clone(), self.needs_sep)
  53     }
  54
  55     fn size_hint(&self) -> (usize, Option<usize>) {
  56         intersperse_size_hint(&self.iter, self.needs_sep)
  57     }
  58 }
  59
  60 /// An iterator adapter that places a separator between all elements.
  61 ///
  62 /// This `struct` is created by [`Iterator::intersperse_with`]. See its
  63 /// documentation for more information.
  64 #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
  65 pub struct IntersperseWith<I, G>
  66 where
  67     I: Iterator,
  68 {
  69     separator: G,
  70     iter: Peekable<I>,
  71     needs_sep: bool,
  72 }
  73
  74 #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
  75 impl<I, G> crate::fmt::Debug for IntersperseWith<I, G>
  76 where
  77     I: Iterator + crate::fmt::Debug,
  78     I::Item: crate::fmt::Debug,
  79     G: crate::fmt::Debug,
  80 {
  81     fn fmt(&self, f: &mut crate::fmt::Formatter<'_>) -> crate::fmt::Result {
  82         f.debug_struct("IntersperseWith")
  83             .field("separator", &self.separator)
  84             .field("iter", &self.iter)
  85             .field("needs_sep", &self.needs_sep)
  86             .finish()
  87     }
  88 }
  89
  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     (
 155         lo.saturating_sub(next_is_elem as usize).saturating_add(lo),
 156         hi.and_then(|hi| hi.saturating_sub(next_is_elem as usize).checked_add(hi)),
 157     )
 158 }
 159
 160 fn intersperse_fold<I, B, F, G>(
 161     mut iter: Peekable<I>,
 162     init: B,
 163     mut f: F,
 164     mut separator: G,
 165     needs_sep: bool,
 166 ) -> B
 167 where
 168     I: Iterator,
 169     F: FnMut(B, I::Item) -> B,
 170     G: FnMut() -> I::Item,
 171 {
 172     let mut accum = init;
 173
 174     // Use `peek()` first to avoid calling `next()` on an empty iterator.
 175     if !needs_sep || iter.peek().is_some() {
 176         if let Some(x) = iter.next() {
 177             accum = f(accum, x);
 178         }
 179     }
 180
 181     iter.fold(accum, |mut accum, x| {
 182         accum = f(accum, separator());
 183         accum = f(accum, x);
 184         accum
 185     })
 186 }