trapped_rainwater.rs

//! Module to calculate trapped rainwater in an elevation map.

/// Computes the total volume of trapped rainwater in a given elevation map.
///
/// # Arguments
///
/// * `elevation_map` - A slice containing the heights of the terrain elevations.
///
/// # Returns
///
/// The total volume of trapped rainwater.
pub fn trapped_rainwater(elevation_map: &[u32]) -> u32 {
    let left_max = calculate_max_values(elevation_map, false);
    let right_max = calculate_max_values(elevation_map, true);
    let mut water_trapped = 0;
    // Calculate trapped water
    for i in 0..elevation_map.len() {
        water_trapped += left_max[i].min(right_max[i]) - elevation_map[i];
    }
    water_trapped
}

/// Determines the maximum heights from either direction in the elevation map.
///
/// # Arguments
///
/// * `elevation_map` - A slice representing the heights of the terrain elevations.
/// * `reverse` - A boolean that indicates the direction of calculation.
///   - `false` for left-to-right.
///   - `true` for right-to-left.
///
/// # Returns
///
/// A vector containing the maximum heights encountered up to each position.
fn calculate_max_values(elevation_map: &[u32], reverse: bool) -> Vec<u32> {
    let mut max_values = vec![0; elevation_map.len()];
    let mut current_max = 0;
    for i in create_iter(elevation_map.len(), reverse) {
        current_max = current_max.max(elevation_map[i]);
        max_values[i] = current_max;
    }
    max_values
}

/// Creates an iterator for the given length, optionally reversing it.
///
/// # Arguments
///
/// * `len` - The length of the iterator.
/// * `reverse` - A boolean that determines the order of iteration.
///   - `false` for forward iteration.
///   - `true` for reverse iteration.
///
/// # Returns
///
/// A boxed iterator that iterates over the range of indices.
fn create_iter(len: usize, reverse: bool) -> Box<dyn Iterator<Item = usize>> {
    if reverse {
        Box::new((0..len).rev())
    } else {
        Box::new(0..len)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    macro_rules! trapped_rainwater_tests {
        ($($name:ident: $test_case:expr,)*) => {
            $(
                #[test]
                fn $name() {
                    let (elevation_map, expected_trapped_water) = $test_case;
                    assert_eq!(trapped_rainwater(&elevation_map), expected_trapped_water);
                    let elevation_map_rev: Vec<u32> = elevation_map.iter().rev().cloned().collect();
                    assert_eq!(trapped_rainwater(&elevation_map_rev), expected_trapped_water);
                }
            )*
        };
    }

    trapped_rainwater_tests! {
        test_trapped_rainwater_basic: (
            [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1],
            6
        ),
        test_trapped_rainwater_peak_under_water: (
            [3, 0, 2, 0, 4],
            7,
        ),
        test_bucket: (
            [5, 1, 5],
            4
        ),
        test_skewed_bucket: (
            [4, 1, 5],
            3
        ),
        test_trapped_rainwater_empty: (
            [],
            0
        ),
        test_trapped_rainwater_flat: (
            [0, 0, 0, 0, 0],
            0
        ),
        test_trapped_rainwater_no_trapped_water: (
            [1, 1, 2, 4, 0, 0, 0],
            0
        ),
        test_trapped_rainwater_single_elevation_map: (
            [5],
            0
        ),
        test_trapped_rainwater_two_point_elevation_map: (
            [5, 1],
            0
        ),
        test_trapped_rainwater_large_elevation_map_difference: (
            [5, 1, 6, 1, 7, 1, 8],
            15
        ),
    }
}