scirs2_sparse/
lil_array.rs

1// LIL Array implementation
2//
3// This module provides the LIL (List of Lists) array format,
4// which is efficient for incremental matrix construction and row-based operations.
5
6use scirs2_core::ndarray::{Array1, Array2, ArrayView1};
7use scirs2_core::numeric::{Float, SparseElement};
8use std::fmt::{self, Debug};
9use std::ops::{Add, Div, Mul, Sub};
10
11use crate::coo_array::CooArray;
12use crate::csr_array::CsrArray;
13use crate::error::{SparseError, SparseResult};
14use crate::sparray::{SparseArray, SparseSum};
15
16/// LIL Array format
17///
18/// The LIL (List of Lists) format stores data as a list of lists:
19/// - data: a vector of vectors, where each inner vector contains the non-zero values for a row
20/// - indices: a vector of vectors, where each inner vector contains the column indices for the non-zero values
21///
22/// # Notes
23///
24/// - Efficient for incremental construction (adding values row by row)
25/// - Good for row-based operations
26/// - Fast conversion to CSR format
27/// - Not memory-efficient for large sparse arrays
28/// - Not efficient for arithmetic operations
29///
30#[derive(Clone)]
31pub struct LilArray<T>
32where
33    T: SparseElement + Div<Output = T> + Float + 'static,
34{
35    /// Data for each row (list of lists of values)
36    data: Vec<Vec<T>>,
37    /// Column indices for each row
38    indices: Vec<Vec<usize>>,
39    /// Shape of the array
40    shape: (usize, usize),
41}
42
43impl<T> LilArray<T>
44where
45    T: SparseElement + Div<Output = T> + Float + 'static,
46{
47    /// Creates a new LIL array
48    ///
49    /// # Arguments
50    /// * `shape` - Shape of the sparse array (rows, cols)
51    ///
52    /// # Returns
53    /// A new empty `LilArray`
54    pub fn new(shape: (usize, usize)) -> Self {
55        let (rows, cols) = shape;
56        let data = vec![Vec::new(); rows];
57        let indices = vec![Vec::new(); rows];
58
59        Self {
60            data,
61            indices,
62            shape,
63        }
64    }
65
66    /// Creates a LIL array from existing data and indices
67    ///
68    /// # Arguments
69    /// * `data` - List of lists containing the non-zero values for each row
70    /// * `indices` - List of lists containing the column indices for the non-zero values
71    /// * `shape` - Shape of the sparse array
72    ///
73    /// # Returns
74    /// A new `LilArray`
75    ///
76    /// # Errors
77    /// Returns an error if the data and indices are not consistent or if any index is out of bounds
78    pub fn from_lists(
79        data: Vec<Vec<T>>,
80        indices: Vec<Vec<usize>>,
81        shape: (usize, usize),
82    ) -> SparseResult<Self> {
83        // Validate the data
84        if data.len() != shape.0 || indices.len() != shape.0 {
85            return Err(SparseError::InconsistentData {
86                reason: "Number of rows in data and indices must match the shape".to_string(),
87            });
88        }
89
90        for (i, (row_data, row_indices)) in data.iter().zip(indices.iter()).enumerate() {
91            if row_data.len() != row_indices.len() {
92                return Err(SparseError::InconsistentData {
93                    reason: format!("Row {i}: data and indices have different lengths"),
94                });
95            }
96
97            if let Some(&max_col) = row_indices.iter().max() {
98                if max_col >= shape.1 {
99                    return Err(SparseError::IndexOutOfBounds {
100                        index: (i, max_col),
101                        shape,
102                    });
103                }
104            }
105        }
106
107        // Create sorted copies of the data and indices
108        let mut new_data = Vec::with_capacity(shape.0);
109        let mut new_indices = Vec::with_capacity(shape.0);
110
111        for (row_data, row_indices) in data.iter().zip(indices.iter()) {
112            // Create sorted pairs
113            let mut pairs: Vec<(usize, T)> = row_indices
114                .iter()
115                .copied()
116                .zip(row_data.iter().copied())
117                .collect();
118            pairs.sort_by_key(|&(idx_, _)| idx_);
119
120            // Extract sorted data
121            let mut sorted_data = Vec::with_capacity(row_data.len());
122            let mut sorted_indices = Vec::with_capacity(row_indices.len());
123
124            for (idx, val) in pairs {
125                sorted_indices.push(idx);
126                sorted_data.push(val);
127            }
128
129            new_data.push(sorted_data);
130            new_indices.push(sorted_indices);
131        }
132
133        Ok(Self {
134            data: new_data,
135            indices: new_indices,
136            shape,
137        })
138    }
139
140    /// Create a LIL array from (row, col, data) triplets
141    ///
142    /// # Arguments
143    /// * `row` - Row indices
144    /// * `col` - Column indices
145    /// * `data` - Values
146    /// * `shape` - Shape of the sparse array
147    ///
148    /// # Returns
149    /// A new `LilArray`
150    ///
151    /// # Errors
152    /// Returns an error if the data is not consistent
153    pub fn from_triplets(
154        rows: &[usize],
155        cols: &[usize],
156        data: &[T],
157        shape: (usize, usize),
158    ) -> SparseResult<Self> {
159        if rows.len() != cols.len() || rows.len() != data.len() {
160            return Err(SparseError::InconsistentData {
161                reason: "rows, cols, and data must have the same length".to_string(),
162            });
163        }
164
165        let (num_rows, num_cols) = shape;
166
167        // Check if any index is out of bounds
168        if let Some(&max_row) = rows.iter().max() {
169            if max_row >= num_rows {
170                return Err(SparseError::IndexOutOfBounds {
171                    index: (max_row, 0),
172                    shape,
173                });
174            }
175        }
176
177        if let Some(&max_col) = cols.iter().max() {
178            if max_col >= num_cols {
179                return Err(SparseError::IndexOutOfBounds {
180                    index: (0, max_col),
181                    shape,
182                });
183            }
184        }
185
186        // Initialize the LIL array
187        let mut lil = LilArray::new(shape);
188
189        // Insert the values
190        for (&row, &col, &value) in rows
191            .iter()
192            .zip(cols.iter())
193            .zip(data.iter())
194            .map(|((r, c), d)| (r, c, d))
195        {
196            lil.set(row, col, value)?;
197        }
198
199        Ok(lil)
200    }
201
202    /// Get a reference to the data
203    pub fn get_data(&self) -> &Vec<Vec<T>> {
204        &self.data
205    }
206
207    /// Get a reference to the indices
208    pub fn get_indices(&self) -> &Vec<Vec<usize>> {
209        &self.indices
210    }
211
212    /// Sort the indices and data in each row
213    pub fn sort_indices(&mut self) {
214        for row in 0..self.shape.0 {
215            if !self.data[row].is_empty() {
216                // Create pairs of (col_idx, value)
217                let mut pairs: Vec<(usize, T)> = self.indices[row]
218                    .iter()
219                    .copied()
220                    .zip(self.data[row].iter().copied())
221                    .collect();
222
223                // Sort by column index
224                pairs.sort_by_key(|&(idx_, _)| idx_);
225
226                // Extract sorted data
227                self.indices[row].clear();
228                self.data[row].clear();
229
230                for (idx, val) in pairs {
231                    self.indices[row].push(idx);
232                    self.data[row].push(val);
233                }
234            }
235        }
236    }
237}
238
239impl<T> SparseArray<T> for LilArray<T>
240where
241    T: SparseElement + Div<Output = T> + Float + 'static,
242{
243    fn shape(&self) -> (usize, usize) {
244        self.shape
245    }
246
247    fn nnz(&self) -> usize {
248        self.indices.iter().map(|row| row.len()).sum()
249    }
250
251    fn dtype(&self) -> &str {
252        "float" // Placeholder
253    }
254
255    fn to_array(&self) -> Array2<T> {
256        let (rows, cols) = self.shape;
257        let mut result = Array2::zeros((rows, cols));
258
259        for row in 0..rows {
260            for (idx, &col) in self.indices[row].iter().enumerate() {
261                result[[row, col]] = self.data[row][idx];
262            }
263        }
264
265        result
266    }
267
268    fn toarray(&self) -> Array2<T> {
269        self.to_array()
270    }
271
272    fn to_coo(&self) -> SparseResult<Box<dyn SparseArray<T>>> {
273        let nnz = self.nnz();
274        let mut row_indices = Vec::with_capacity(nnz);
275        let mut col_indices = Vec::with_capacity(nnz);
276        let mut values = Vec::with_capacity(nnz);
277
278        for row in 0..self.shape.0 {
279            for (idx, &col) in self.indices[row].iter().enumerate() {
280                row_indices.push(row);
281                col_indices.push(col);
282                values.push(self.data[row][idx]);
283            }
284        }
285
286        CooArray::from_triplets(&row_indices, &col_indices, &values, self.shape, false)
287            .map(|array| Box::new(array) as Box<dyn SparseArray<T>>)
288    }
289
290    fn to_csr(&self) -> SparseResult<Box<dyn SparseArray<T>>> {
291        let (rows, cols) = self.shape;
292        let nnz = self.nnz();
293
294        let mut data = Vec::with_capacity(nnz);
295        let mut indices = Vec::with_capacity(nnz);
296        let mut indptr = Vec::with_capacity(rows + 1);
297
298        indptr.push(0);
299
300        for row in 0..rows {
301            for (idx, &col) in self.indices[row].iter().enumerate() {
302                indices.push(col);
303                data.push(self.data[row][idx]);
304            }
305            indptr.push(indptr.last().unwrap() + self.indices[row].len());
306        }
307
308        CsrArray::new(
309            Array1::from_vec(data),
310            Array1::from_vec(indices),
311            Array1::from_vec(indptr),
312            self.shape,
313        )
314        .map(|array| Box::new(array) as Box<dyn SparseArray<T>>)
315    }
316
317    fn to_csc(&self) -> SparseResult<Box<dyn SparseArray<T>>> {
318        // Convert to COO first, then to CSC (for simplicity)
319        self.to_coo()?.to_csc()
320    }
321
322    fn to_dok(&self) -> SparseResult<Box<dyn SparseArray<T>>> {
323        // Convert to COO first, then to DOK (for simplicity)
324        self.to_coo()?.to_dok()
325    }
326
327    fn to_lil(&self) -> SparseResult<Box<dyn SparseArray<T>>> {
328        Ok(Box::new(self.clone()))
329    }
330
331    fn to_dia(&self) -> SparseResult<Box<dyn SparseArray<T>>> {
332        // Convert to COO first, then to DIA (for simplicity)
333        self.to_coo()?.to_dia()
334    }
335
336    fn to_bsr(&self) -> SparseResult<Box<dyn SparseArray<T>>> {
337        // Convert to COO first, then to BSR (for simplicity)
338        self.to_coo()?.to_bsr()
339    }
340
341    fn add(&self, other: &dyn SparseArray<T>) -> SparseResult<Box<dyn SparseArray<T>>> {
342        // For efficiency, convert to CSR first
343        let self_csr = self.to_csr()?;
344        self_csr.add(other)
345    }
346
347    fn sub(&self, other: &dyn SparseArray<T>) -> SparseResult<Box<dyn SparseArray<T>>> {
348        // For efficiency, convert to CSR first
349        let self_csr = self.to_csr()?;
350        self_csr.sub(other)
351    }
352
353    fn mul(&self, other: &dyn SparseArray<T>) -> SparseResult<Box<dyn SparseArray<T>>> {
354        // For efficiency, convert to CSR first
355        let self_csr = self.to_csr()?;
356        self_csr.mul(other)
357    }
358
359    fn div(&self, other: &dyn SparseArray<T>) -> SparseResult<Box<dyn SparseArray<T>>> {
360        // For efficiency, convert to CSR first
361        let self_csr = self.to_csr()?;
362        self_csr.div(other)
363    }
364
365    fn dot(&self, other: &dyn SparseArray<T>) -> SparseResult<Box<dyn SparseArray<T>>> {
366        // For efficiency, convert to CSR first
367        let self_csr = self.to_csr()?;
368        self_csr.dot(other)
369    }
370
371    fn dot_vector(&self, other: &ArrayView1<T>) -> SparseResult<Array1<T>> {
372        let (rows, cols) = self.shape;
373        if cols != other.len() {
374            return Err(SparseError::DimensionMismatch {
375                expected: cols,
376                found: other.len(),
377            });
378        }
379
380        let mut result = Array1::zeros(rows);
381
382        for row in 0..rows {
383            for (idx, &col) in self.indices[row].iter().enumerate() {
384                result[row] = result[row] + self.data[row][idx] * other[col];
385            }
386        }
387
388        Ok(result)
389    }
390
391    fn transpose(&self) -> SparseResult<Box<dyn SparseArray<T>>> {
392        // LIL format isn't efficient for transpose operations
393        // Convert to COO first, which has a simple transpose operation
394        self.to_coo()?.transpose()
395    }
396
397    fn copy(&self) -> Box<dyn SparseArray<T>> {
398        Box::new(self.clone())
399    }
400
401    fn get(&self, i: usize, j: usize) -> T {
402        if i >= self.shape.0 || j >= self.shape.1 {
403            return T::sparse_zero();
404        }
405
406        match self.indices[i].binary_search(&j) {
407            Ok(pos) => self.data[i][pos],
408            Err(_) => T::sparse_zero(),
409        }
410    }
411
412    fn set(&mut self, i: usize, j: usize, value: T) -> SparseResult<()> {
413        if i >= self.shape.0 || j >= self.shape.1 {
414            return Err(SparseError::IndexOutOfBounds {
415                index: (i, j),
416                shape: self.shape,
417            });
418        }
419
420        match self.indices[i].binary_search(&j) {
421            Ok(pos) => {
422                if SparseElement::is_zero(&value) {
423                    // Remove zero value
424                    self.data[i].remove(pos);
425                    self.indices[i].remove(pos);
426                } else {
427                    // Update existing value
428                    self.data[i][pos] = value;
429                }
430            }
431            Err(pos) => {
432                if !SparseElement::is_zero(&value) {
433                    // Insert new non-zero value
434                    self.data[i].insert(pos, value);
435                    self.indices[i].insert(pos, j);
436                }
437            }
438        }
439
440        Ok(())
441    }
442
443    fn eliminate_zeros(&mut self) {
444        for row in 0..self.shape.0 {
445            let mut new_data = Vec::new();
446            let mut new_indices = Vec::new();
447
448            for (idx, &value) in self.data[row].iter().enumerate() {
449                if !SparseElement::is_zero(&value) {
450                    new_data.push(value);
451                    new_indices.push(self.indices[row][idx]);
452                }
453            }
454
455            self.data[row] = new_data;
456            self.indices[row] = new_indices;
457        }
458    }
459
460    fn sort_indices(&mut self) {
461        // Call the implementation from the struct
462        LilArray::sort_indices(self);
463    }
464
465    fn sorted_indices(&self) -> Box<dyn SparseArray<T>> {
466        let mut sorted = self.clone();
467        sorted.sort_indices();
468        Box::new(sorted)
469    }
470
471    fn has_sorted_indices(&self) -> bool {
472        // Check if each row has sorted indices
473        for row in 0..self.shape.0 {
474            if self.indices[row].len() > 1 {
475                for i in 1..self.indices[row].len() {
476                    if self.indices[row][i - 1] >= self.indices[row][i] {
477                        return false;
478                    }
479                }
480            }
481        }
482        true
483    }
484
485    fn sum(&self, axis: Option<usize>) -> SparseResult<SparseSum<T>> {
486        match axis {
487            None => {
488                // Sum over all elements
489                let mut sum = T::sparse_zero();
490                for row in 0..self.shape.0 {
491                    for &val in self.data[row].iter() {
492                        sum = sum + val;
493                    }
494                }
495                Ok(SparseSum::Scalar(sum))
496            }
497            Some(0) => {
498                // Sum over rows
499                let (_, cols) = self.shape;
500                let mut result = Array1::<T>::zeros(cols);
501
502                for row in 0..self.shape.0 {
503                    for (idx, &col) in self.indices[row].iter().enumerate() {
504                        result[col] = result[col] + self.data[row][idx];
505                    }
506                }
507
508                // Create a 1 x cols sparse array
509                let mut lil = LilArray::new((1, cols));
510                for (col, &val) in result.iter().enumerate() {
511                    if !SparseElement::is_zero(&val) {
512                        lil.set(0, col, val)?;
513                    }
514                }
515
516                Ok(SparseSum::SparseArray(Box::new(lil)))
517            }
518            Some(1) => {
519                // Sum over columns
520                let (rows, _) = self.shape;
521                let mut result = Array1::<T>::zeros(rows);
522
523                for row in 0..rows {
524                    for &val in self.data[row].iter() {
525                        result[row] = result[row] + val;
526                    }
527                }
528
529                // Create a rows x 1 sparse array
530                let mut lil = LilArray::new((rows, 1));
531                for (row, &val) in result.iter().enumerate() {
532                    if !SparseElement::is_zero(&val) {
533                        lil.set(row, 0, val)?;
534                    }
535                }
536
537                Ok(SparseSum::SparseArray(Box::new(lil)))
538            }
539            _ => Err(SparseError::InvalidAxis),
540        }
541    }
542
543    fn max(&self) -> T {
544        if self.nnz() == 0 {
545            // Empty sparse matrix - all elements are implicitly zero
546            return T::sparse_zero();
547        }
548
549        // Start with first non-zero value
550        let mut max_val = T::sparse_zero();
551        let mut found_value = false;
552        for row in 0..self.shape.0 {
553            for &val in self.data[row].iter() {
554                if !found_value {
555                    max_val = val;
556                    found_value = true;
557                } else if val > max_val {
558                    max_val = val;
559                }
560            }
561        }
562
563        // If matrix is not entirely filled and max is negative, zero is the max
564        let zero = T::sparse_zero();
565        if max_val < zero && self.nnz() < self.shape.0 * self.shape.1 {
566            zero
567        } else {
568            max_val
569        }
570    }
571
572    fn min(&self) -> T {
573        if self.nnz() == 0 {
574            return T::sparse_zero();
575        }
576
577        let mut min_val = T::sparse_zero();
578        for row in 0..self.shape.0 {
579            for &val in self.data[row].iter() {
580                if val < min_val {
581                    min_val = val;
582                }
583            }
584        }
585
586        // If matrix is not entirely filled and min is positive, zero is the min
587        if min_val > T::sparse_zero() && self.nnz() < self.shape.0 * self.shape.1 {
588            T::sparse_zero()
589        } else {
590            min_val
591        }
592    }
593
594    fn find(&self) -> (Array1<usize>, Array1<usize>, Array1<T>) {
595        let nnz = self.nnz();
596        let mut rows = Vec::with_capacity(nnz);
597        let mut cols = Vec::with_capacity(nnz);
598        let mut values = Vec::with_capacity(nnz);
599
600        for row in 0..self.shape.0 {
601            for (idx, &col) in self.indices[row].iter().enumerate() {
602                rows.push(row);
603                cols.push(col);
604                values.push(self.data[row][idx]);
605            }
606        }
607
608        (
609            Array1::from_vec(rows),
610            Array1::from_vec(cols),
611            Array1::from_vec(values),
612        )
613    }
614
615    fn slice(
616        &self,
617        row_range: (usize, usize),
618        col_range: (usize, usize),
619    ) -> SparseResult<Box<dyn SparseArray<T>>> {
620        let (start_row, end_row) = row_range;
621        let (start_col, end_col) = col_range;
622
623        if start_row >= self.shape.0
624            || end_row > self.shape.0
625            || start_col >= self.shape.1
626            || end_col > self.shape.1
627            || start_row >= end_row
628            || start_col >= end_col
629        {
630            return Err(SparseError::InvalidSliceRange);
631        }
632
633        let mut new_data = vec![Vec::new(); end_row - start_row];
634        let mut new_indices = vec![Vec::new(); end_row - start_row];
635
636        for row in start_row..end_row {
637            for (idx, &col) in self.indices[row].iter().enumerate() {
638                if col >= start_col && col < end_col {
639                    new_data[row - start_row].push(self.data[row][idx]);
640                    new_indices[row - start_row].push(col - start_col);
641                }
642            }
643        }
644
645        Ok(Box::new(LilArray {
646            data: new_data,
647            indices: new_indices,
648            shape: (end_row - start_row, end_col - start_col),
649        }))
650    }
651
652    fn as_any(&self) -> &dyn std::any::Any {
653        self
654    }
655}
656
657impl<T> fmt::Debug for LilArray<T>
658where
659    T: SparseElement + Div<Output = T> + Float + 'static,
660{
661    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
662        write!(
663            f,
664            "LilArray<{}x{}, nnz={}>",
665            self.shape.0,
666            self.shape.1,
667            self.nnz()
668        )
669    }
670}
671
672#[cfg(test)]
673mod tests {
674    use super::*;
675    use approx::assert_relative_eq;
676
677    #[test]
678    fn test_lil_array_construction() {
679        // Create an empty LIL array
680        let shape = (3, 3);
681        let lil = LilArray::<f64>::new(shape);
682
683        assert_eq!(lil.shape(), (3, 3));
684        assert_eq!(lil.nnz(), 0);
685
686        // Create from lists
687        let data = vec![vec![1.0, 2.0], vec![3.0], vec![4.0, 5.0]];
688        let indices = vec![vec![0, 2], vec![1], vec![0, 1]];
689
690        let lil = LilArray::from_lists(data, indices, shape).unwrap();
691
692        assert_eq!(lil.shape(), (3, 3));
693        assert_eq!(lil.nnz(), 5);
694        assert_eq!(lil.get(0, 0), 1.0);
695        assert_eq!(lil.get(0, 2), 2.0);
696        assert_eq!(lil.get(1, 1), 3.0);
697        assert_eq!(lil.get(2, 0), 4.0);
698        assert_eq!(lil.get(2, 1), 5.0);
699        assert_eq!(lil.get(0, 1), 0.0);
700    }
701
702    #[test]
703    fn test_lil_from_triplets() {
704        let rows = vec![0, 0, 1, 2, 2];
705        let cols = vec![0, 2, 1, 0, 1];
706        let data = vec![1.0, 2.0, 3.0, 4.0, 5.0];
707        let shape = (3, 3);
708
709        let lil = LilArray::from_triplets(&rows, &cols, &data, shape).unwrap();
710
711        assert_eq!(lil.shape(), (3, 3));
712        assert_eq!(lil.nnz(), 5);
713        assert_eq!(lil.get(0, 0), 1.0);
714        assert_eq!(lil.get(0, 2), 2.0);
715        assert_eq!(lil.get(1, 1), 3.0);
716        assert_eq!(lil.get(2, 0), 4.0);
717        assert_eq!(lil.get(2, 1), 5.0);
718        assert_eq!(lil.get(0, 1), 0.0);
719    }
720
721    #[test]
722    fn test_lil_array_to_array() {
723        let rows = vec![0, 0, 1, 2, 2];
724        let cols = vec![0, 2, 1, 0, 1];
725        let data = vec![1.0, 2.0, 3.0, 4.0, 5.0];
726        let shape = (3, 3);
727
728        let lil = LilArray::from_triplets(&rows, &cols, &data, shape).unwrap();
729        let dense = lil.to_array();
730
731        assert_eq!(dense.shape(), &[3, 3]);
732        assert_eq!(dense[[0, 0]], 1.0);
733        assert_eq!(dense[[0, 1]], 0.0);
734        assert_eq!(dense[[0, 2]], 2.0);
735        assert_eq!(dense[[1, 0]], 0.0);
736        assert_eq!(dense[[1, 1]], 3.0);
737        assert_eq!(dense[[1, 2]], 0.0);
738        assert_eq!(dense[[2, 0]], 4.0);
739        assert_eq!(dense[[2, 1]], 5.0);
740        assert_eq!(dense[[2, 2]], 0.0);
741    }
742
743    #[test]
744    fn test_lil_set_get() {
745        let mut lil = LilArray::<f64>::new((3, 3));
746
747        // Set some values
748        lil.set(0, 0, 1.0).unwrap();
749        lil.set(0, 2, 2.0).unwrap();
750        lil.set(1, 1, 3.0).unwrap();
751        lil.set(2, 0, 4.0).unwrap();
752        lil.set(2, 1, 5.0).unwrap();
753
754        // Check values
755        assert_eq!(lil.get(0, 0), 1.0);
756        assert_eq!(lil.get(0, 2), 2.0);
757        assert_eq!(lil.get(1, 1), 3.0);
758        assert_eq!(lil.get(2, 0), 4.0);
759        assert_eq!(lil.get(2, 1), 5.0);
760        assert_eq!(lil.get(0, 1), 0.0);
761
762        // Update a value
763        lil.set(0, 0, 6.0).unwrap();
764        assert_eq!(lil.get(0, 0), 6.0);
765
766        // Set to zero (should remove the entry)
767        lil.set(0, 0, 0.0).unwrap();
768        assert_eq!(lil.get(0, 0), 0.0);
769        assert_eq!(lil.nnz(), 4);
770    }
771
772    #[test]
773    fn test_lil_to_csr() {
774        let rows = vec![0, 0, 1, 2, 2];
775        let cols = vec![0, 2, 1, 0, 1];
776        let data = vec![1.0, 2.0, 3.0, 4.0, 5.0];
777        let shape = (3, 3);
778
779        let lil = LilArray::from_triplets(&rows, &cols, &data, shape).unwrap();
780
781        // Convert to CSR
782        let csr = lil.to_csr().unwrap();
783
784        // Check values
785        let dense = csr.to_array();
786        assert_eq!(dense[[0, 0]], 1.0);
787        assert_eq!(dense[[0, 1]], 0.0);
788        assert_eq!(dense[[0, 2]], 2.0);
789        assert_eq!(dense[[1, 0]], 0.0);
790        assert_eq!(dense[[1, 1]], 3.0);
791        assert_eq!(dense[[1, 2]], 0.0);
792        assert_eq!(dense[[2, 0]], 4.0);
793        assert_eq!(dense[[2, 1]], 5.0);
794        assert_eq!(dense[[2, 2]], 0.0);
795    }
796
797    #[test]
798    fn test_lil_to_coo() {
799        let rows = vec![0, 0, 1, 2, 2];
800        let cols = vec![0, 2, 1, 0, 1];
801        let data = vec![1.0, 2.0, 3.0, 4.0, 5.0];
802        let shape = (3, 3);
803
804        let lil = LilArray::from_triplets(&rows, &cols, &data, shape).unwrap();
805
806        // Convert to COO
807        let coo = lil.to_coo().unwrap();
808
809        // Check values
810        let dense = coo.to_array();
811        assert_eq!(dense[[0, 0]], 1.0);
812        assert_eq!(dense[[0, 1]], 0.0);
813        assert_eq!(dense[[0, 2]], 2.0);
814        assert_eq!(dense[[1, 0]], 0.0);
815        assert_eq!(dense[[1, 1]], 3.0);
816        assert_eq!(dense[[1, 2]], 0.0);
817        assert_eq!(dense[[2, 0]], 4.0);
818        assert_eq!(dense[[2, 1]], 5.0);
819        assert_eq!(dense[[2, 2]], 0.0);
820    }
821
822    #[test]
823    fn test_lil_dot_vector() {
824        let rows = vec![0, 0, 1, 2, 2];
825        let cols = vec![0, 2, 1, 0, 1];
826        let data = vec![1.0, 2.0, 3.0, 4.0, 5.0];
827        let shape = (3, 3);
828
829        let lil = LilArray::from_triplets(&rows, &cols, &data, shape).unwrap();
830
831        // Create a vector
832        let vector = Array1::from_vec(vec![1.0, 2.0, 3.0]);
833
834        // Compute dot product
835        let result = lil.dot_vector(&vector.view()).unwrap();
836
837        // Check result: row[0]: 1.0*1.0 + 0.0*2.0 + 2.0*3.0 = 7.0
838        //               row[1]: 0.0*1.0 + 3.0*2.0 + 0.0*3.0 = 6.0
839        //               row[2]: 4.0*1.0 + 5.0*2.0 + 0.0*3.0 = 14.0
840        assert_eq!(result.len(), 3);
841        assert_relative_eq!(result[0], 7.0, epsilon = 1e-10);
842        assert_relative_eq!(result[1], 6.0, epsilon = 1e-10);
843        assert_relative_eq!(result[2], 14.0, epsilon = 1e-10);
844    }
845
846    #[test]
847    fn test_lil_eliminate_zeros() {
848        let mut lil = LilArray::<f64>::new((2, 2));
849
850        lil.set(0, 0, 1.0).unwrap();
851        lil.set(0, 1, 0.0).unwrap(); // This won't actually add an entry
852        lil.set(1, 0, 2.0).unwrap();
853        lil.set(1, 1, 3.0).unwrap();
854
855        // Set a value then zero it (this can leave an explicit zero in some implementations)
856        lil.set(0, 1, 4.0).unwrap();
857        lil.set(0, 1, 0.0).unwrap();
858
859        // Manually insert a zero (normally this shouldn't happen)
860        lil.data[1][0] = 0.0;
861
862        assert_eq!(lil.nnz(), 3); // 3 entries, but one is zero
863
864        // Eliminate zeros
865        lil.eliminate_zeros();
866
867        assert_eq!(lil.nnz(), 2); // Now only 2 entries (the non-zeros)
868        assert_eq!(lil.get(0, 0), 1.0);
869        assert_eq!(lil.get(1, 1), 3.0);
870    }
871
872    #[test]
873    fn test_lil_sort_indices() {
874        // Create a LIL array with unsorted indices
875        let mut lil = LilArray::<f64>::new((2, 4));
876
877        // Insert in non-sorted order
878        lil.set(0, 3, 1.0).unwrap();
879        lil.set(0, 1, 2.0).unwrap();
880        lil.set(1, 2, 3.0).unwrap();
881        lil.set(1, 0, 4.0).unwrap();
882
883        // Manually mess up the sorting by directly swapping elements in the arrays
884        // This is needed because LilArray.set() keeps indices sorted
885        if lil.data[0].len() >= 2 {
886            lil.data[0].swap(0, 1);
887            lil.indices[0].swap(0, 1);
888        }
889
890        // Indices should be unsorted
891        assert!(!lil.has_sorted_indices());
892
893        // Sort indices
894        lil.sort_indices();
895
896        // Now indices should be sorted
897        assert!(lil.has_sorted_indices());
898
899        // Check values
900        assert_eq!(lil.get(0, 1), 2.0);
901        assert_eq!(lil.get(0, 3), 1.0);
902        assert_eq!(lil.get(1, 0), 4.0);
903        assert_eq!(lil.get(1, 2), 3.0);
904
905        // Check internal structure
906        assert_eq!(lil.indices[0][0], 1);
907        assert_eq!(lil.indices[0][1], 3);
908        assert_eq!(lil.data[0][0], 2.0);
909        assert_eq!(lil.data[0][1], 1.0);
910
911        assert_eq!(lil.indices[1][0], 0);
912        assert_eq!(lil.indices[1][1], 2);
913        assert_eq!(lil.data[1][0], 4.0);
914        assert_eq!(lil.data[1][1], 3.0);
915    }
916
917    #[test]
918    fn test_lil_slice() {
919        let rows = vec![0, 0, 1, 2, 2];
920        let cols = vec![0, 2, 1, 0, 1];
921        let data = vec![1.0, 2.0, 3.0, 4.0, 5.0];
922        let shape = (3, 3);
923
924        let lil = LilArray::from_triplets(&rows, &cols, &data, shape).unwrap();
925
926        // Get a slice
927        let slice = lil.slice((1, 3), (0, 2)).unwrap();
928
929        // Check slice shape
930        assert_eq!(slice.shape(), (2, 2));
931
932        // Check values
933        assert_eq!(slice.get(0, 1), 3.0);
934        assert_eq!(slice.get(1, 0), 4.0);
935        assert_eq!(slice.get(1, 1), 5.0);
936        assert_eq!(slice.get(0, 0), 0.0);
937    }
938}
scirs2_sparse/lil_array.rs

scirs2_sparse/
lil_array.rs
