Reverse the scan of Iterator


#1

I’m working on a Rust implementation of the Trapping Rain Water programming problem. I have a partial solution that looks idiomatic, although I am a beginner so any help in that respect is appreciated. The problem I am having is that I cannot take the reverse of a scan. Which I need in order to compute the right-to-left prefix scan max operation.

I tried to reason about the type system at first it doesn’t seem possible to take the reverse of a scan, since the scan operation produces results on-demand. OTOH since Vector is an ExactSizeIterator can’t we take advantage of this fact to reverse the scan for this specific trait?

Here’s my current implementation. It doesn’t compile because I try to reverse the scan.

use std::cmp;

fn scan_max(max: &mut u32, elem: u32) -> Option<u32> {
    *max = cmp::max(*max, elem);
    Some(*max)
}

pub fn capacity(heights: Vec<u32>) -> u32 {

    let left_max = heights.iter().scan(0, |max, &e| scan_max(max, e));

    let right_max = heights.iter().rev().scan(0, |max, &e| scan_max(max, e)).rev();

    let min = left_max.zip(right_max).map(|(l, r)| cmp::min(l, r));

    let delta = heights.iter().zip(min).map(|(h, m)| m - h);

    delta.fold(0, |sum, x| sum + x)
}

#[test]
fn test_capacity() {
    let heights = vec![2,6,3,5,2,8,1,4,2,2,5,3,5,7,4,1];
    assert_eq!(capacity(heights), 35);
}

#2

Does .rev() before .scan() work?


#3

Yup it’s valid to .rev() before .scan(). The catch is that I need to reverse() before the scan() and then I need to reverse() again after the scan.


#4

So I was talking to some people on IRC, and this is my understanding of the situation. Iterators are lazy, and since Scan is a stateful iterator, you would first need to consume Scan in its entirity before calling reverse. So I’m guessing that you will need to ::collect() after scanning and before reversing.


#5

Either that, or you can implement your own scan_backwards iterator adapter. It’s not a difficult iterator adapter so it could be a good learning experience too. You could implement it for iterators that satisfy DoubleEndedIterator and instead of calling next you can call next_back.

Look at the source here: https://doc.rust-lang.org/src/core/up/src/libcore/iter/mod.rs.html#1552

Edit: Well, now that I think about it, I don’t think this would work very well. And is equivalent to just doing .rev().scan and doesn’t avoid the fact that you need to ::collect before rev() again. In my mind I was doing this in place on an iterator.


#6

Thanks for the feedback! I restarted and wrote a very imperative implementation as a baseline. I’ll rewrite it again in a functional style. I am planning on writing several CPU and GPU implementations in Rust as a learning exercise. Here’s the imperative form:

use std::cmp;

fn scan_max_asc(input: &[u32], output: &mut [u32]) {
    let len = input.len();
    let mut max = 0;
    for i in 0..len {
        max = cmp::max(max, input[i]);
        output[i] = max;
    }
}

fn scan_max_dsc(input: &[u32], output: &mut [u32]) {
    let len = input.len();
    let mut max = 0;
    for i in (0..len).rev() {
        max = cmp::max(max, input[i]);
        output[i] = max;
    }
}

pub fn capacity(heights: Vec<u32>) -> u32 {
    let len = heights.len();
    let mut lmax = vec![0; len];
    let mut rmax = vec![0; len];
    scan_max_asc(&heights, &mut lmax);
    scan_max_dsc(&heights, &mut rmax);
    let mut sum = 0;
    for i in 0..len {
        let min = cmp::min(lmax[i], rmax[i]);
        let delta = min - heights[i];
        sum += delta;
    }
    sum
}

#7

If anyone is interested in the followup to this thread I’m keeping track of the different implementations at https://github.com/mspiegel/rainwater. Thanks!