use crate::application::index::validate_mutable_output;
use crate::domain::scalar::Scalar;
use leto::{Array, ArrayView, ArrayViewMut, LetoError, Result, VecStorage};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum ScanDirection {
Forward,
Reverse,
}
pub trait ScanOp<T: Scalar>: Copy + Send + Sync + 'static {
fn identity() -> T;
fn combine(acc: T, x: T) -> T;
}
#[derive(Clone, Copy, Debug, Default)]
pub struct CumSumOp;
#[derive(Clone, Copy, Debug, Default)]
pub struct CumProdOp;
impl<T: Scalar> ScanOp<T> for CumSumOp {
#[inline(always)]
fn identity() -> T {
T::ZERO
}
#[inline(always)]
fn combine(acc: T, x: T) -> T {
acc.add(x)
}
}
impl<T: Scalar> ScanOp<T> for CumProdOp {
#[inline(always)]
fn identity() -> T {
T::ONE
}
#[inline(always)]
fn combine(acc: T, x: T) -> T {
acc.mul(x)
}
}
#[inline]
fn fill_outer_index<const N: usize>(
outer_flat: usize,
shape: &[usize; N],
axis: usize,
index: &mut [usize; N],
) {
let mut rem = outer_flat;
for d in (0..N).rev() {
if d == axis {
continue;
}
index[d] = rem % shape[d];
rem /= shape[d];
}
}
pub fn scan_axis_into<Op, T, const N: usize>(
input: &ArrayView<'_, T, N>,
axis: usize,
direction: ScanDirection,
output: &mut ArrayViewMut<'_, T, N>,
) -> Result<()>
where
Op: ScanOp<T>,
T: Scalar,
{
if axis >= N {
return Err(LetoError::StorageError {
reason: format!("scan axis {axis} is out of bounds for rank {N}"),
});
}
if input.shape() != output.shape() {
return Err(LetoError::ShapeMismatch {
lhs: input.shape().to_vec(),
rhs: output.shape().to_vec(),
});
}
input.layout().validate_storage_len(input.data().len())?;
validate_mutable_output(output, "scan")?;
let shape = input.shape();
let len = shape[axis];
if len == 0 {
return Ok(());
}
let outer: usize = shape
.iter()
.enumerate()
.filter(|&(d, _)| d != axis)
.map(|(_, &s)| s)
.product();
let input_layout = input.layout();
let output_layout = output.layout();
let input_data = input.data();
let output_data = output.data_mut();
let in_axis_step = input_layout.strides()[axis];
let out_axis_step = output_layout.strides()[axis];
let mut index = [0usize; N];
for outer_flat in 0..outer {
fill_outer_index(outer_flat, &shape, axis, &mut index);
index[axis] = match direction {
ScanDirection::Forward => 0,
ScanDirection::Reverse => len - 1,
};
let mut in_off = input_layout.offset_of(index)? as isize;
let mut out_off = output_layout.offset_of(index)? as isize;
let (in_step, out_step) = match direction {
ScanDirection::Forward => (in_axis_step, out_axis_step),
ScanDirection::Reverse => (-in_axis_step, -out_axis_step),
};
let mut acc = Op::identity();
for _ in 0..len {
acc = Op::combine(acc, input_data[in_off as usize]);
output_data[out_off as usize] = acc;
in_off += in_step;
out_off += out_step;
}
}
Ok(())
}
pub fn scan_axis<Op, T, const N: usize>(
input: &ArrayView<'_, T, N>,
axis: usize,
direction: ScanDirection,
) -> Result<Array<T, VecStorage<T>, N>>
where
Op: ScanOp<T>,
T: Scalar,
{
let layout = leto::Layout::c_contiguous(input.shape())?;
let mut output = Array::new(layout, VecStorage::fill(layout.size(), T::ZERO))?;
scan_axis_into::<Op, T, N>(input, axis, direction, &mut output.view_mut())?;
Ok(output)
}
#[inline]
pub fn cumsum<T: Scalar, const N: usize>(
input: &ArrayView<'_, T, N>,
axis: usize,
) -> Result<Array<T, VecStorage<T>, N>> {
scan_axis::<CumSumOp, T, N>(input, axis, ScanDirection::Forward)
}
#[inline]
pub fn cumsum_into<T: Scalar, const N: usize>(
input: &ArrayView<'_, T, N>,
axis: usize,
output: &mut ArrayViewMut<'_, T, N>,
) -> Result<()> {
scan_axis_into::<CumSumOp, T, N>(input, axis, ScanDirection::Forward, output)
}