algebra-sparse 0.4.0-beta.1

// Copyright (C) 2020-2025 algebra-sparse authors. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

use crate::{CsMatrix, Real};

/// An immutable view of a sparse vector.
///
/// This provides efficient read-only access to sparse vector data without allocation.
/// Sparse vectors store only non-zero elements and their indices, making them
/// memory-efficient for vectors with few non-zero elements.
///
/// # Format
///
/// The sparse vector uses two parallel arrays:
/// - `indices`: Indices of non-zero elements
/// - `values`: Non-zero values corresponding to each index
///
/// # Examples
///
/// ```rust
/// use algebra_sparse::CsVecRef;
///
/// let indices = [0, 2, 4];
/// let values = [1.0, 3.0, 5.0];
/// let sparse_vec = CsVecRef::from_parts_unchecked(&indices, &values, 6);
///
/// // Iterate over non-zero elements
/// for (index, value) in sparse_vec.iter() {
///     println!("vec[{}] = {}", index, value);
/// }
/// ```
#[non_exhaustive]
#[derive(Clone, Copy)]
pub struct CsVecRef<'a, T> {
    /// The indices of non-zero elements.
    indices: &'a [usize],
    /// The non-zero values corresponding to each index.
    values: &'a [T],
    /// The total length of the vector (including zero elements).
    ///
    /// # Note
    ///
    /// This is not the length of `values`, but the full vector length.
    len: usize,
}

impl<'a, T> CsVecRef<'a, T> {
    /// Creates a `CsVecRef` from raw parts without checking validity.
    ///
    /// # Safety
    /// This function does not validate that the provided parts form a valid sparse vector.
    /// The `indices` and `values` arrays should have the same length, and indices should be
    /// in ascending order and within bounds [0, len).
    ///
    /// # Arguments
    /// * `indices` - Indices of non-zero elements
    /// * `values` - Non-zero values corresponding to each index
    /// * `len` - Total length of the vector
    #[inline]
    pub fn from_parts_unchecked(indices: &'a [usize], values: &'a [T], len: usize) -> Self {
        Self {
            indices,
            values,
            len,
        }
    }

    /// Returns an iterator over the non-zero elements of the vector.
    ///
    /// The iterator yields tuples of (index, value) for each non-zero element.
    ///
    /// # Returns
    /// An iterator over (index, value) pairs
    #[inline]
    pub fn iter(&self) -> impl Iterator<Item = (usize, T)>
    where
        T: Copy,
    {
        self.indices
            .iter()
            .copied()
            .zip(self.values.iter().copied())
    }

    /// Returns the total length of the vector.
    ///
    /// This is the full length of the vector, not the number of non-zero elements.
    ///
    /// # Returns
    /// The total length including zero elements
    #[inline]
    pub fn len(&self) -> usize {
        self.len
    }

    /// Returns true if the vector is empty (has length 0).
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Returns the indices of the non-zero elements.
    ///
    /// # Returns
    /// A slice of indices for non-zero elements
    #[inline]
    pub fn indices(&self) -> &'a [usize] {
        self.indices
    }

    /// Returns all non-zero values in the vector.
    ///
    /// # Returns
    /// A slice of non-zero values
    #[inline]
    pub fn values(&self) -> &'a [T] {
        self.values
    }
}

/// A mutable view of a sparse vector.
///
/// This provides mutable access to the values of a sparse vector while keeping
/// the structure (indices) immutable. This is useful for modifying existing
/// non-zero elements without changing the sparsity pattern.
///
/// # Note
///
/// Only the values can be modified. The indices and structure cannot be changed
/// through this type. To change the structure, you need to use a `CsVecBuilder`.
pub struct CsVecMut<'a, T> {
    /// The indices of non-zero elements (immutable).
    pub col_indices: &'a [usize],
    /// The non-zero values (mutable).
    pub values: &'a mut [T],
}

/// A builder for constructing sparse vectors efficiently.
///
/// This builder allows efficient construction of sparse vectors by adding elements
/// in order. When the builder is dropped, the vector is automatically finalized
/// and added to the parent matrix.
///
/// # Features
///
/// - Automatic filtering of values below zero threshold
/// - Validation of index ordering (must be in ascending order)
/// - Efficient batch operations
/// - Automatic finalization when dropped
///
/// # Examples
///
/// ```rust
/// use algebra_sparse::{CsMatrix, CsVecBuilder};
/// use nalgebra::DMatrix;
///
/// let mut matrix = CsMatrix::new(3);
/// {
///     let mut builder = matrix.new_lane_builder(1e-10);
///     builder.push(0, 1.0);
///     builder.push(2, 2.0);
///     // Vector is automatically added when builder goes out of scope
/// }
/// ```
pub struct CsVecBuilder<'a, T> {
    secondary_indices: &'a mut Vec<usize>,
    primary_offsets: &'a mut Vec<usize>,
    values: &'a mut Vec<T>,
    mat_value_start: usize,
    num_nonzero_values: usize,
    zero_threshold: T,
}

impl<'a, T> CsVecBuilder<'a, T>
where
    T: Real,
{
    /// Creates a new sparse vector builder for the given matrix.
    ///
    /// When the builder is dropped, a new lane will be added to the sparse matrix
    /// if the builder contains any non-zero elements.
    ///
    /// # Arguments
    /// * `m` - A mutable reference to the sparse matrix
    /// * `zero_threshold` - The threshold below which values are considered zero
    #[inline]
    pub fn new(m: &'a mut CsMatrix<T>, zero_threshold: T) -> Self {
        Self {
            secondary_indices: &mut m.secondary_indices,
            primary_offsets: &mut m.primary_offsets,
            values: &mut m.values,
            mat_value_start: 0,
            num_nonzero_values: 0,
            zero_threshold,
        }
    }

    /// Creates a builder from raw parts without checking validity.
    ///
    /// # Safety
    /// This function does not validate the provided parts. Use with caution.
    pub fn from_parts_unchecked(
        secondary_indices: &'a mut Vec<usize>,
        primary_offsets: &'a mut Vec<usize>,
        values: &'a mut Vec<T>,
        mat_value_start: usize,
        zero_threshold: T,
    ) -> Self {
        Self {
            secondary_indices,
            primary_offsets,
            values,
            mat_value_start,
            zero_threshold,
            num_nonzero_values: 0,
        }
    }

    /// Pushes a value to the vector without checking if it is zero or if the index is in order.
    ///
    /// # Safety
    /// This function bypasses validation checks. Ensure that:
    /// - The value is not zero (above threshold)
    /// - The index is in ascending order
    /// - The index is within valid bounds
    ///
    /// # Arguments
    /// * `index` - Index of the element
    /// * `value` - Value to add
    #[inline]
    pub fn push_unchecked(&mut self, index: usize, value: T) {
        #[cfg(debug_assertions)]
        {
            self.validate(index, value);
        }
        self.secondary_indices.push(index);
        self.values.push(value);
        self.num_nonzero_values += 1;
    }

    /// Pushes a value to the vector with validation.
    ///
    /// # Arguments
    /// * `col` - Column index of the element
    /// * `value` - Value to add
    ///
    /// # Panics
    ///
    /// Panics if:
    /// - The value is zero (below threshold)
    /// - The column index is not in ascending order
    #[inline]
    pub fn push(&mut self, col: usize, value: T) {
        self.validate(col, value);
        self.push_unchecked(col, value);
    }

    /// Pushes multiple values to the vector with validation.
    ///
    /// # Arguments
    /// * `idx_values` - Iterator of (index, value) pairs
    ///
    /// # Panics
    ///
    /// Panics if any of the values are zero or if the indices are not in ascending order.
    pub fn extend(&mut self, idx_values: impl IntoIterator<Item = (usize, T)>) {
        for (col, value) in idx_values {
            self.push(col, value);
        }
    }

    /// Pushes multiple values to the vector without validation.
    ///
    /// # Safety
    /// This function bypasses validation checks.
    ///
    /// # Arguments
    /// * `idx_values` - Iterator of (index, value) pairs
    pub fn extend_unchecked(&mut self, idx_values: impl IntoIterator<Item = (usize, T)>) {
        for (col, value) in idx_values {
            self.push_unchecked(col, value);
        }
    }

    /// Pushes all non-zero values to the sparse vector.
    ///
    /// This method automatically discards any values that are below the zero threshold.
    /// This is useful when converting from dense data where many values might be zero.
    ///
    /// # Arguments
    /// * `idx_values` - Iterator of (index, value) pairs
    #[inline]
    pub fn extend_with_nonzeros(&mut self, idx_values: impl IntoIterator<Item = (usize, T)>) {
        for (idx, value) in idx_values {
            if value.abs() > self.zero_threshold {
                self.push_unchecked(idx, value);
            }
        }
    }

    /// Finishes the builder and returns the number of non-zero elements.
    ///
    /// This method is called automatically when the builder is dropped,
    /// but can be called explicitly to get the count of non-zero elements.
    ///
    /// # Returns
    /// The number of non-zero elements added
    ///
    /// # Note
    ///
    /// If the number of non-zero elements is zero, the sparse vector will be discarded
    /// and not added to the matrix.
    #[inline]
    pub fn finish(self) -> usize {
        self.num_nonzero_values
    }

    #[inline]
    fn validate(&self, index: usize, value: T) {
        assert!(
            value.abs() > self.zero_threshold,
            "Cannot push zero value to Sparse Vec"
        );
        if self.num_nonzero_values > 0 {
            if let Some(last) = self.secondary_indices.last() {
                assert!(
                    index > *last,
                    "sparse element indices must be in ascending order"
                );
            }
        }
    }
}

/// Automatically finalizes the sparse vector when the builder is dropped.
///
/// This implementation ensures that the sparse vector is properly added to the
/// parent matrix when the builder goes out of scope. If no non-zero elements
/// were added, the empty lane is discarded.
impl<T> Drop for CsVecBuilder<'_, T> {
    fn drop(&mut self) {
        // Push the row offset
        if self.num_nonzero_values == 0 {
            // discard empty lane
            return;
        }
        self.primary_offsets
            .push(self.values.len() - self.mat_value_start);
    }
}