pofk_algorithm 0.0.3

A collection of efficient algorithms implemented in Rust for real-world projects.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

//! ➕ Prefix Sum (Generic, Additive)
//!
//! Computes the prefix sum of a slice, returning a new Vec of the same length.
//!
//! # Type Parameters
//! * `T`: The element type. Must implement `Copy + std::ops::Add<Output = T>`.
//!
//! # Arguments
//! * `slice` - The slice to compute prefix sums for.
//!
//! # Returns
//! * `Vec<T>` - The prefix sums.
//!
//! # Example
//! ```rust
//! use pofk_algorithm::list_algorithms::prefix_sum::prefix_sum;
//! let arr = [1, 2, 3, 4];
//! let sums = prefix_sum(&arr);
//! assert_eq!(sums, vec![1, 3, 6, 10]);
//! ```
pub fn prefix_sum<T>(slice: &[T]) -> Vec<T>
where
    T: Copy + std::ops::Add<Output = T>,
{
    let mut result = Vec::with_capacity(slice.len());
    let mut sum: Option<T> = None;
    for &item in slice {
        sum = Some(match sum {
            Some(s) => s + item,
            None => item,
        });
        result.push(sum.unwrap());
    }
    result
}