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

scirs2_sparse/
lil_array.rs
