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);
}
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.
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!