vendor/rustc-rayon/src/iter/intersperse.rs

   1 use super::plumbing::*;
   2 use super::*;
   3 use std::cell::Cell;
   4 use std::iter::{self, Fuse};
   5
   6 /// `Intersperse` is an iterator that inserts a particular item between each
   7 /// item of the adapted iterator.  This struct is created by the
   8 /// [`intersperse()`] method on [`ParallelIterator`]
   9 ///
  10 /// [`intersperse()`]: trait.ParallelIterator.html#method.intersperse
  11 /// [`ParallelIterator`]: trait.ParallelIterator.html
  12 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
  13 #[derive(Clone, Debug)]
  14 pub struct Intersperse<I>
  15 where
  16     I: ParallelIterator,
  17     I::Item: Clone,
  18 {
  19     base: I,
  20     item: I::Item,
  21 }
  22
  23 impl<I> Intersperse<I>
  24 where
  25     I: ParallelIterator,
  26     I::Item: Clone,
  27 {
  28     /// Creates a new `Intersperse` iterator
  29     pub(super) fn new(base: I, item: I::Item) -> Self {
  30         Intersperse { base, item }
  31     }
  32 }
  33
  34 impl<I> ParallelIterator for Intersperse<I>
  35 where
  36     I: ParallelIterator,
  37     I::Item: Clone + Send,
  38 {
  39     type Item = I::Item;
  40
  41     fn drive_unindexed<C>(self, consumer: C) -> C::Result
  42     where
  43         C: UnindexedConsumer<I::Item>,
  44     {
  45         let consumer1 = IntersperseConsumer::new(consumer, self.item);
  46         self.base.drive_unindexed(consumer1)
  47     }
  48
  49     fn opt_len(&self) -> Option<usize> {
  50         match self.base.opt_len()? {
  51             0 => Some(0),
  52             len => len.checked_add(len - 1),
  53         }
  54     }
  55 }
  56
  57 impl<I> IndexedParallelIterator for Intersperse<I>
  58 where
  59     I: IndexedParallelIterator,
  60     I::Item: Clone + Send,
  61 {
  62     fn drive<C>(self, consumer: C) -> C::Result
  63     where
  64         C: Consumer<Self::Item>,
  65     {
  66         let consumer1 = IntersperseConsumer::new(consumer, self.item);
  67         self.base.drive(consumer1)
  68     }
  69
  70     fn len(&self) -> usize {
  71         let len = self.base.len();
  72         if len > 0 {
  73             len.checked_add(len - 1).expect("overflow")
  74         } else {
  75             0
  76         }
  77     }
  78
  79     fn with_producer<CB>(self, callback: CB) -> CB::Output
  80     where
  81         CB: ProducerCallback<Self::Item>,
  82     {
  83         let len = self.len();
  84         return self.base.with_producer(Callback {
  85             callback,
  86             item: self.item,
  87             len,
  88         });
  89
  90         struct Callback<CB, T> {
  91             callback: CB,
  92             item: T,
  93             len: usize,
  94         }
  95
  96         impl<T, CB> ProducerCallback<T> for Callback<CB, T>
  97         where
  98             CB: ProducerCallback<T>,
  99             T: Clone + Send,
 100         {
 101             type Output = CB::Output;
 102
 103             fn callback<P>(self, base: P) -> CB::Output
 104             where
 105                 P: Producer<Item = T>,
 106             {
 107                 let producer = IntersperseProducer::new(base, self.item, self.len);
 108                 self.callback.callback(producer)
 109             }
 110         }
 111     }
 112 }
 113
 114 struct IntersperseProducer<P>
 115 where
 116     P: Producer,
 117 {
 118     base: P,
 119     item: P::Item,
 120     len: usize,
 121     clone_first: bool,
 122 }
 123
 124 impl<P> IntersperseProducer<P>
 125 where
 126     P: Producer,
 127 {
 128     fn new(base: P, item: P::Item, len: usize) -> Self {
 129         IntersperseProducer {
 130             base,
 131             item,
 132             len,
 133             clone_first: false,
 134         }
 135     }
 136 }
 137
 138 impl<P> Producer for IntersperseProducer<P>
 139 where
 140     P: Producer,
 141     P::Item: Clone + Send,
 142 {
 143     type Item = P::Item;
 144     type IntoIter = IntersperseIter<P::IntoIter>;
 145
 146     fn into_iter(self) -> Self::IntoIter {
 147         IntersperseIter {
 148             base: self.base.into_iter().fuse(),
 149             item: self.item,
 150             clone_first: self.len > 0 && self.clone_first,
 151
 152             // If there's more than one item, then even lengths end the opposite
 153             // of how they started with respect to interspersed clones.
 154             clone_last: self.len > 1 && ((self.len & 1 == 0) ^ self.clone_first),
 155         }
 156     }
 157
 158     fn min_len(&self) -> usize {
 159         self.base.min_len()
 160     }
 161     fn max_len(&self) -> usize {
 162         self.base.max_len()
 163     }
 164
 165     fn split_at(self, index: usize) -> (Self, Self) {
 166         debug_assert!(index <= self.len);
 167
 168         // The left needs half of the items from the base producer, and the
 169         // other half will be our interspersed item.  If we're not leading with
 170         // a cloned item, then we need to round up the base number of items,
 171         // otherwise round down.
 172         let base_index = (index + !self.clone_first as usize) / 2;
 173         let (left_base, right_base) = self.base.split_at(base_index);
 174
 175         let left = IntersperseProducer {
 176             base: left_base,
 177             item: self.item.clone(),
 178             len: index,
 179             clone_first: self.clone_first,
 180         };
 181
 182         let right = IntersperseProducer {
 183             base: right_base,
 184             item: self.item,
 185             len: self.len - index,
 186
 187             // If the index is odd, the right side toggles `clone_first`.
 188             clone_first: (index & 1 == 1) ^ self.clone_first,
 189         };
 190
 191         (left, right)
 192     }
 193
 194     fn fold_with<F>(self, folder: F) -> F
 195     where
 196         F: Folder<Self::Item>,
 197     {
 198         let folder1 = IntersperseFolder {
 199             base: folder,
 200             item: self.item,
 201             clone_first: self.clone_first,
 202         };
 203         self.base.fold_with(folder1).base
 204     }
 205 }
 206
 207 struct IntersperseIter<I>
 208 where
 209     I: Iterator,
 210 {
 211     base: Fuse<I>,
 212     item: I::Item,
 213     clone_first: bool,
 214     clone_last: bool,
 215 }
 216
 217 impl<I> Iterator for IntersperseIter<I>
 218 where
 219     I: DoubleEndedIterator + ExactSizeIterator,
 220     I::Item: Clone,
 221 {
 222     type Item = I::Item;
 223
 224     fn next(&mut self) -> Option<Self::Item> {
 225         if self.clone_first {
 226             self.clone_first = false;
 227             Some(self.item.clone())
 228         } else if let next @ Some(_) = self.base.next() {
 229             // If there are any items left, we'll need another clone in front.
 230             self.clone_first = self.base.len() != 0;
 231             next
 232         } else if self.clone_last {
 233             self.clone_last = false;
 234             Some(self.item.clone())
 235         } else {
 236             None
 237         }
 238     }
 239
 240     fn size_hint(&self) -> (usize, Option<usize>) {
 241         let len = self.len();
 242         (len, Some(len))
 243     }
 244 }
 245
 246 impl<I> DoubleEndedIterator for IntersperseIter<I>
 247 where
 248     I: DoubleEndedIterator + ExactSizeIterator,
 249     I::Item: Clone,
 250 {
 251     fn next_back(&mut self) -> Option<Self::Item> {
 252         if self.clone_last {
 253             self.clone_last = false;
 254             Some(self.item.clone())
 255         } else if let next_back @ Some(_) = self.base.next_back() {
 256             // If there are any items left, we'll need another clone in back.
 257             self.clone_last = self.base.len() != 0;
 258             next_back
 259         } else if self.clone_first {
 260             self.clone_first = false;
 261             Some(self.item.clone())
 262         } else {
 263             None
 264         }
 265     }
 266 }
 267
 268 impl<I> ExactSizeIterator for IntersperseIter<I>
 269 where
 270     I: DoubleEndedIterator + ExactSizeIterator,
 271     I::Item: Clone,
 272 {
 273     fn len(&self) -> usize {
 274         let len = self.base.len();
 275         len + len.saturating_sub(1) + self.clone_first as usize + self.clone_last as usize
 276     }
 277 }
 278
 279 struct IntersperseConsumer<C, T> {
 280     base: C,
 281     item: T,
 282     clone_first: Cell<bool>,
 283 }
 284
 285 impl<C, T> IntersperseConsumer<C, T>
 286 where
 287     C: Consumer<T>,
 288 {
 289     fn new(base: C, item: T) -> Self {
 290         IntersperseConsumer {
 291             base,
 292             item,
 293             clone_first: false.into(),
 294         }
 295     }
 296 }
 297
 298 impl<C, T> Consumer<T> for IntersperseConsumer<C, T>
 299 where
 300     C: Consumer<T>,
 301     T: Clone + Send,
 302 {
 303     type Folder = IntersperseFolder<C::Folder, T>;
 304     type Reducer = C::Reducer;
 305     type Result = C::Result;
 306
 307     fn split_at(mut self, index: usize) -> (Self, Self, Self::Reducer) {
 308         // We'll feed twice as many items to the base consumer, except if we're
 309         // not currently leading with a cloned item, then it's one less.
 310         let base_index = index + index.saturating_sub(!self.clone_first.get() as usize);
 311         let (left, right, reducer) = self.base.split_at(base_index);
 312
 313         let right = IntersperseConsumer {
 314             base: right,
 315             item: self.item.clone(),
 316             clone_first: true.into(),
 317         };
 318         self.base = left;
 319         (self, right, reducer)
 320     }
 321
 322     fn into_folder(self) -> Self::Folder {
 323         IntersperseFolder {
 324             base: self.base.into_folder(),
 325             item: self.item,
 326             clone_first: self.clone_first.get(),
 327         }
 328     }
 329
 330     fn full(&self) -> bool {
 331         self.base.full()
 332     }
 333 }
 334
 335 impl<C, T> UnindexedConsumer<T> for IntersperseConsumer<C, T>
 336 where
 337     C: UnindexedConsumer<T>,
 338     T: Clone + Send,
 339 {
 340     fn split_off_left(&self) -> Self {
 341         let left = IntersperseConsumer {
 342             base: self.base.split_off_left(),
 343             item: self.item.clone(),
 344             clone_first: self.clone_first.clone(),
 345         };
 346         self.clone_first.set(true);
 347         left
 348     }
 349
 350     fn to_reducer(&self) -> Self::Reducer {
 351         self.base.to_reducer()
 352     }
 353 }
 354
 355 struct IntersperseFolder<C, T> {
 356     base: C,
 357     item: T,
 358     clone_first: bool,
 359 }
 360
 361 impl<C, T> Folder<T> for IntersperseFolder<C, T>
 362 where
 363     C: Folder<T>,
 364     T: Clone,
 365 {
 366     type Result = C::Result;
 367
 368     fn consume(mut self, item: T) -> Self {
 369         if self.clone_first {
 370             self.base = self.base.consume(self.item.clone());
 371             if self.base.full() {
 372                 return self;
 373             }
 374         } else {
 375             self.clone_first = true;
 376         }
 377         self.base = self.base.consume(item);
 378         self
 379     }
 380
 381     fn consume_iter<I>(self, iter: I) -> Self
 382     where
 383         I: IntoIterator<Item = T>,
 384     {
 385         let mut clone_first = self.clone_first;
 386         let between_item = self.item;
 387         let base = self.base.consume_iter(iter.into_iter().flat_map(|item| {
 388             let first = if clone_first {
 389                 Some(between_item.clone())
 390             } else {
 391                 clone_first = true;
 392                 None
 393             };
 394             first.into_iter().chain(iter::once(item))
 395         }));
 396         IntersperseFolder {
 397             base,
 398             item: between_item,
 399             clone_first,
 400         }
 401     }
 402
 403     fn complete(self) -> C::Result {
 404         self.base.complete()
 405     }
 406
 407     fn full(&self) -> bool {
 408         self.base.full()
 409     }
 410 }