# Reverse the scan of Iterator

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);
}
``````

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

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.

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.

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.

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
}
``````

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!

2 Likes