use crate::tensor::{Device, IntTensor};
use crate::{Backend, TensorData};
use alloc::vec::Vec;
use burn_std::{Element, ElementConversion, IntDType};

/// Compute the indices of the elements that are non-zero, grouped by element.
///
/// # Arguments
///
/// * `data` - The input tensor data.
///
/// # Returns
///
/// A 2D tensor containing the indices of all non-zero elements of the given tensor.
/// Each row contains the indices of a non-zero element.
///
/// # Remarks
///
/// This is a fallback solution that used only when the backend doesn't have the corresponding implementation.
/// Ideally, it is supposed to be implemented by the backend and the backend implementation will be resolved
/// by static dispatch. It is not designed for direct usage by users, and not recommended to import
/// or use this function directly.
pub fn argwhere_data<B: Backend>(
    data: TensorData,
    device: &Device<B>,
    out_dtype: IntDType,
) -> IntTensor<B> {
    let out = match out_dtype {
        IntDType::I64 => argwhere_data_impl::<i64>(data),
        IntDType::I32 => argwhere_data_impl::<i32>(data),
        IntDType::I16 => argwhere_data_impl::<i16>(data),
        IntDType::I8 => argwhere_data_impl::<i8>(data),
        IntDType::U64 => argwhere_data_impl::<u64>(data),
        IntDType::U32 => argwhere_data_impl::<u32>(data),
        IntDType::U16 => argwhere_data_impl::<u16>(data),
        IntDType::U8 => argwhere_data_impl::<u8>(data),
    };

    B::int_from_data(out, device)
}

fn argwhere_data_impl<I: Element>(data: TensorData) -> TensorData {
    let dims = &data.shape;
    let ndims = dims.len();
    let count_nonzero = data.iter::<bool>().filter(|&v| v).count();

    /// Converts a flat index into a vector of indices for the specified tensor shape
    fn unravel_index<I: Element>(index: usize, shape: &[usize]) -> Vec<I> {
        shape
            .iter()
            .rev()
            .scan(index, |i, size| {
                let dim_idx = *i % size;
                *i /= size;
                Some((dim_idx as i64).elem())
            })
            .collect::<Vec<_>>()
            .into_iter()
            .rev()
            .collect()
    }

    let indices = data
        .iter::<bool>()
        .enumerate()
        .filter_map(|(index, v)| if v { Some(index) } else { None })
        .map(|index| unravel_index::<I>(index, dims))
        .collect::<Vec<_>>()
        .concat();

    TensorData::new(indices, [count_nonzero, ndims])
}
