library/alloc/src/collections/vec_deque/pair_slices.rs

   1 use core::cmp::{self};
   2 use core::mem::replace;
   3
   4 use crate::alloc::Allocator;
   5
   6 use super::VecDeque;
   7
   8 /// PairSlices pairs up equal length slice parts of two deques
   9 ///
  10 /// For example, given deques "A" and "B" with the following division into slices:
  11 ///
  12 /// A: [0 1 2] [3 4 5]
  13 /// B: [a b] [c d e]
  14 ///
  15 /// It produces the following sequence of matching slices:
  16 ///
  17 /// ([0 1], [a b])
  18 /// (\[2\], \[c\])
  19 /// ([3 4], [d e])
  20 ///
  21 /// and the uneven remainder of either A or B is skipped.
  22 pub struct PairSlices<'a, 'b, T> {
  23     pub(crate) a0: &'a mut [T],
  24     pub(crate) a1: &'a mut [T],
  25     pub(crate) b0: &'b [T],
  26     pub(crate) b1: &'b [T],
  27 }
  28
  29 impl<'a, 'b, T> PairSlices<'a, 'b, T> {
  30     pub fn from<A: Allocator>(to: &'a mut VecDeque<T, A>, from: &'b VecDeque<T, A>) -> Self {
  31         let (a0, a1) = to.as_mut_slices();
  32         let (b0, b1) = from.as_slices();
  33         PairSlices { a0, a1, b0, b1 }
  34     }
  35
  36     pub fn has_remainder(&self) -> bool {
  37         !self.b0.is_empty()
  38     }
  39
  40     pub fn remainder(self) -> impl Iterator<Item = &'b [T]> {
  41         IntoIterator::into_iter([self.b0, self.b1])
  42     }
  43 }
  44
  45 impl<'a, 'b, T> Iterator for PairSlices<'a, 'b, T> {
  46     type Item = (&'a mut [T], &'b [T]);
  47     fn next(&mut self) -> Option<Self::Item> {
  48         // Get next part length
  49         let part = cmp::min(self.a0.len(), self.b0.len());
  50         if part == 0 {
  51             return None;
  52         }
  53         let (p0, p1) = replace(&mut self.a0, &mut []).split_at_mut(part);
  54         let (q0, q1) = self.b0.split_at(part);
  55
  56         // Move a1 into a0, if it's empty (and b1, b0 the same way).
  57         self.a0 = p1;
  58         self.b0 = q1;
  59         if self.a0.is_empty() {
  60             self.a0 = replace(&mut self.a1, &mut []);
  61         }
  62         if self.b0.is_empty() {
  63             self.b0 = replace(&mut self.b1, &[]);
  64         }
  65         Some((p0, q0))
  66     }
  67 }