Sliding Window practice

main.rs

use std::collections::VecDeque;


pub struct SlidingWindowMaximumIterator<'a, T : 'a> {
  ascend: VecDeque<&'a T>,
  slice: &'a [T],
  sizek: usize,
  index: usize
}

impl<'a, T> SlidingWindowMaximumIterator<'a, T> 
  where T : Ord + std::fmt::Debug
{
  pub fn new(slice: &'a [T], sizek: usize) -> SlidingWindowMaximumIterator<'a, T> {
    assert!(sizek > 0);

    let mut iter = SlidingWindowMaximumIterator {
      ascend: VecDeque::with_capacity(sizek),
      slice: slice,
      sizek: sizek,
      index: 0
    };
  
    // Get the descending minima...
    if let Some(max) = slice[0..sizek].iter().max() {
      let mut _max = max;
      let mut max_traversed = false;
      for x in slice[0..sizek].iter() {
        if x == max { max_traversed = true; }
        if max_traversed && x <= _max { 
          _max = x; iter.ascend.push_back(x); 
        }
      }
    }

    iter
  }
}

impl<'a, T> Iterator for SlidingWindowMaximumIterator<'a, T> 
  where T : Ord + std::fmt::Debug
{
  type Item = &'a T;

  fn next(&mut self) -> Option<Self::Item> {
    if self.index + self.sizek > self.slice.len() { return None }

    let item = &self.slice[self.index + self.sizek - 1];
    
    // Remove all elements smaller than the most recent addition to the window.
    while !self.ascend.is_empty() && *self.ascend.back().unwrap() < item {
      self.ascend.pop_back();
    }
  
    if self.index > 0 { self.ascend.push_back(item); }
  
    // Determine if the initial element needs to be removed.
    let init_el_same = if let Some(x) = self.ascend.front() {
      *x == &self.slice[self.index]
    } else { false };

    self.index += 1;

    if init_el_same { 
      self.ascend.pop_front() 
    } else { 
      Some(*self.ascend.front().unwrap()) 
    }
  }

  fn size_hint(&self) -> (usize, Option<usize>) {
    (self.slice.len() / self.sizek, Some(self.slice.len() / self.sizek))
  }
}


#[test]
fn it_works() {
  let ints = vec![1, 3, -1, -3, 5, 9, 6, 7];
  let maxs: Vec<isize> = SlidingWindowMaximumIterator::new(&ints[..], 3)
    .map(|x| *x)
    .collect();

  assert_eq!(vec![3, 3, 5, 9, 9, 9], maxs);

  let uints = vec![5, 2, 8, 6, 4, 7];
  let maxs0: Vec<usize> = SlidingWindowMaximumIterator::new(&uints[..], 3)
    .map(|x| *x)
    .collect();

  assert_eq!(vec![8, 8, 8, 7], maxs0);
}