hurray_core/layout/addressing/
csc.rs

1//! CSC (Compressed Sparse Column) sparse layout element lookup.
2//!
3//! The column analog of CSR (`docs/spec/layouts/csc.md`): within a column, the stored row
4//! indices are strictly increasing, so a non-zero is found by binary-searching the
5//! column's slice of `row_indices`. Mirrors the standalone-function API validated by
6//! [`super::csf::element_offset`].
7
8use crate::{Error, Result};
9
10/// Looks up the storage offset (`values` / `row_indices` buffer index) of logical index
11/// `(row, col)` in a CSC matrix, or returns `None` if the element is a structural zero.
12///
13/// # Arguments
14///
15/// - `query` — logical index `[row, col]`; MUST have length 2 (CSC is rank-2).
16/// - `row_indices` — the `row_indices` buffer (buffer 1) as `uint64`: the row of each
17///   non-zero, in column-major storage order (`nnz` entries).
18/// - `col_ptr` — the `col_ptr` buffer (buffer 2) as `uint64`: `ncols + 1` entries, where
19///   `col_ptr[j]` is the first storage index of column `j` and `col_ptr[ncols] = nnz`.
20///
21/// # Errors
22///
23/// - [`Error::IndexRankMismatch`] — `query.len() != 2`.
24/// - [`Error::IndexOutOfRange`] — `col` is not a valid column (`col >= ncols`).
25/// - [`Error::InvalidLayout`] — `col_ptr` is empty, or a `col_ptr` entry points outside
26///   `row_indices` / is non-monotone for the queried column.
27///
28/// The caller is responsible for validating `row` against `shape[0]`; an out-of-range row
29/// simply reports a structural zero (`None`).
30///
31/// # Examples
32///
33/// ```
34/// use hurray_core::layout::addressing::csc::element_offset;
35///
36/// // 3×3 matrix, stored column-major:
37/// //   col 0: (0,0)
38/// //   col 1: (2,1)
39/// //   col 2: (0,2)
40/// let row_indices: &[u64] = &[0, 2, 0];
41/// let col_ptr: &[u64] = &[0, 1, 2, 3];
42///
43/// assert_eq!(element_offset(&[2, 1], row_indices, col_ptr).unwrap(), Some(1));
44/// assert_eq!(element_offset(&[0, 2], row_indices, col_ptr).unwrap(), Some(2));
45/// assert_eq!(element_offset(&[1, 1], row_indices, col_ptr).unwrap(), None); // structural zero
46/// ```
47pub fn element_offset(query: &[u64], row_indices: &[u64], col_ptr: &[u64]) -> Result<Option<u64>> {
48    if query.len() != 2 {
49        return Err(Error::IndexRankMismatch {
50            index_rank: query.len(),
51            shape_rank: 2,
52        });
53    }
54    let (row, col) = (query[0], query[1]);
55
56    if col_ptr.is_empty() {
57        return Err(Error::InvalidLayout(
58            "csc: col_ptr must have at least ncols+1 = 1 entries".into(),
59        ));
60    }
61    let ncols = (col_ptr.len() - 1) as u64;
62    if col >= ncols {
63        return Err(Error::IndexOutOfRange {
64            dim: 1,
65            index: col,
66            size: ncols,
67        });
68    }
69
70    let start = col_ptr[col as usize] as usize;
71    let end = col_ptr[col as usize + 1] as usize;
72    if start > end || end > row_indices.len() {
73        return Err(Error::InvalidLayout(format!(
74            "csc: col_ptr[{col}..{}] = [{start}..{end}] out of bounds for row_indices.len()={}",
75            col + 1,
76            row_indices.len()
77        )));
78    }
79
80    match row_indices[start..end].binary_search(&row) {
81        Ok(k) => Ok(Some((start + k) as u64)),
82        Err(_) => Ok(None),
83    }
84}
85
86#[cfg(test)]
87mod tests {
88    use super::*;
89
90    // 4×4 matrix, stored column-major:
91    //   col 0: (0,0)=a, (3,0)=b
92    //   col 1: (1,1)=c
93    //   col 2: (3,2)=d
94    //   col 3: (0,3)=e, (3,3)=f
95    // values order: a,b,c,d,e,f
96    const ROW_INDICES: &[u64] = &[0, 3, 1, 3, 0, 3];
97    const COL_PTR: &[u64] = &[0, 2, 3, 4, 6];
98
99    #[test]
100    fn lookup_hits() {
101        assert_eq!(
102            element_offset(&[0, 0], ROW_INDICES, COL_PTR).unwrap(),
103            Some(0)
104        );
105        assert_eq!(
106            element_offset(&[3, 0], ROW_INDICES, COL_PTR).unwrap(),
107            Some(1)
108        );
109        assert_eq!(
110            element_offset(&[1, 1], ROW_INDICES, COL_PTR).unwrap(),
111            Some(2)
112        );
113        assert_eq!(
114            element_offset(&[3, 2], ROW_INDICES, COL_PTR).unwrap(),
115            Some(3)
116        );
117        assert_eq!(
118            element_offset(&[0, 3], ROW_INDICES, COL_PTR).unwrap(),
119            Some(4)
120        );
121        assert_eq!(
122            element_offset(&[3, 3], ROW_INDICES, COL_PTR).unwrap(),
123            Some(5)
124        );
125    }
126
127    #[test]
128    fn structural_zeros() {
129        assert_eq!(element_offset(&[1, 0], ROW_INDICES, COL_PTR).unwrap(), None);
130        assert_eq!(element_offset(&[0, 1], ROW_INDICES, COL_PTR).unwrap(), None);
131        assert_eq!(element_offset(&[0, 2], ROW_INDICES, COL_PTR).unwrap(), None); // col 2 has only row 3
132        assert_eq!(element_offset(&[2, 3], ROW_INDICES, COL_PTR).unwrap(), None);
133    }
134
135    #[test]
136    fn wrong_rank_rejected() {
137        assert!(matches!(
138            element_offset(&[0], ROW_INDICES, COL_PTR),
139            Err(Error::IndexRankMismatch { .. })
140        ));
141    }
142
143    #[test]
144    fn col_out_of_range_rejected() {
145        assert!(matches!(
146            element_offset(&[0, 4], ROW_INDICES, COL_PTR),
147            Err(Error::IndexOutOfRange { dim: 1, .. })
148        ));
149    }
150
151    #[test]
152    fn empty_col_ptr_rejected() {
153        assert!(matches!(
154            element_offset(&[0, 0], ROW_INDICES, &[]),
155            Err(Error::InvalidLayout(_))
156        ));
157    }
158
159    #[test]
160    fn empty_matrix() {
161        assert_eq!(element_offset(&[0, 0], &[], &[0, 0, 0]).unwrap(), None);
162    }
163}
hurray_core/layout/addressing/csc.rs

hurray_core/layout/addressing/
csc.rs
