use crate::Error;
pub fn element_offset(
query_coords: &[u64],
mode_order: &[u32],
pos_levels: &[&[u64]],
crd_levels: &[&[u64]],
) -> crate::Result<Option<u64>> {
let rank = mode_order.len();
if query_coords.len() != rank {
return Err(Error::IndexRankMismatch {
index_rank: query_coords.len(),
shape_rank: rank,
});
}
let mut p: u64 = 0;
for level in 0..rank {
let dim_idx = mode_order[level] as usize;
if dim_idx >= query_coords.len() {
return Err(Error::InvalidLayout(format!(
"csf: mode_order[{level}]={dim_idx} out of range for rank {rank}"
)));
}
let q_l: u64 = query_coords[dim_idx];
let pos = pos_levels[level];
let crd = crd_levels[level];
let p_usize = p as usize;
if p_usize + 1 >= pos.len() {
return Err(Error::InvalidLayout(format!(
"csf: pos_{level}[{p}..{}] out of bounds (pos_{level}.len()={})",
p_usize + 1,
pos.len()
)));
}
let slice_start = pos[p_usize] as usize;
let slice_end = pos[p_usize + 1] as usize;
if slice_start > slice_end {
return Err(Error::InvalidLayout(format!(
"csf: pos_{level}[{p}]={slice_start} > pos_{level}[{}]={slice_end} (not non-decreasing)",
p_usize + 1
)));
}
if slice_end > crd.len() {
return Err(Error::InvalidLayout(format!(
"csf: pos_{level}[{}]={slice_end} exceeds crd_{level}.len()={}",
p_usize + 1,
crd.len()
)));
}
let slice = &crd[slice_start..slice_end];
match slice.binary_search(&q_l) {
Ok(relative_offset) => {
let abs = pos[p_usize]
.checked_add(relative_offset as u64)
.ok_or(Error::AddressOverflow)?;
p = abs;
}
Err(_) => {
return Ok(None);
}
}
}
Ok(Some(p))
}
pub fn validate_index_buffers(
nnz: u64,
mode_order: &[u32],
shape_dims: &[u64],
pos_levels: &[&[u64]],
crd_levels: &[&[u64]],
) -> crate::Result<()> {
let rank = mode_order.len();
if pos_levels.len() != rank {
return Err(Error::InvalidLayout(format!(
"csf: pos_levels.len()={} != rank={}",
pos_levels.len(),
rank
)));
}
if crd_levels.len() != rank {
return Err(Error::InvalidLayout(format!(
"csf: crd_levels.len()={} != rank={}",
crd_levels.len(),
rank
)));
}
let mut n_prev: u64 = 1;
for level in 0..rank {
let pos = pos_levels[level];
let crd = crd_levels[level];
let dim_idx = mode_order[level] as usize;
let coord_bound = if dim_idx < shape_dims.len() {
shape_dims[dim_idx]
} else {
return Err(Error::InvalidLayout(format!(
"csf: mode_order[{level}]={dim_idx} out of range for shape.len()={}",
shape_dims.len()
)));
};
let expected_pos_len = (n_prev as usize).saturating_add(1);
if pos.len() != expected_pos_len {
return Err(Error::InvalidLayout(format!(
"csf: pos_{level}.len()={} != n_{{L-1}}+1={} (n_{{L-1}}={n_prev})",
pos.len(),
expected_pos_len
)));
}
if pos[0] != 0 {
return Err(Error::InvalidLayout(format!(
"csf: pos_{level}[0]={} must be 0",
pos[0]
)));
}
for k in 0..(pos.len() - 1) {
if pos[k] > pos[k + 1] {
return Err(Error::InvalidLayout(format!(
"csf: pos_{level}[{k}]={} > pos_{level}[{}]={} (not non-decreasing)",
pos[k],
k + 1,
pos[k + 1]
)));
}
}
let n_l = pos[n_prev as usize]; if level == rank - 1 && n_l != nnz {
return Err(Error::InvalidLayout(format!(
"csf: pos_{level}[n_{{rank-1}}]={n_l} must equal nnz={nnz}"
)));
}
if crd.len() as u64 != n_l {
return Err(Error::InvalidLayout(format!(
"csf: crd_{level}.len()={} != n_{level}={n_l}",
crd.len()
)));
}
for k in 0..(n_prev as usize) {
let start = pos[k] as usize;
let end = pos[k + 1] as usize;
let sibling_slice = &crd[start..end];
let mut prev_coord: Option<u64> = None;
for (j, &coord) in sibling_slice.iter().enumerate() {
if coord >= coord_bound {
return Err(Error::InvalidLayout(format!(
"csf: crd_{level}[{}]={coord} >= shape[mode_order[{level}]]={coord_bound}",
start + j
)));
}
if let Some(prev) = prev_coord {
if coord <= prev {
return Err(Error::InvalidLayout(format!(
"csf: crd_{level}[{start}..{end}] is not strictly increasing at index {} ({prev} >= {coord})",
start + j
)));
}
}
prev_coord = Some(coord);
}
}
n_prev = n_l;
}
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
const MODE_ORDER: &[u32] = &[0, 1, 2];
const SHAPE_DIMS: &[u64] = &[2, 3, 4];
const POS_0: &[u64] = &[0, 2];
const CRD_0: &[u64] = &[0, 1];
const POS_1: &[u64] = &[0, 2, 3];
const CRD_1: &[u64] = &[0, 2, 1];
const POS_2: &[u64] = &[0, 1, 2, 4];
const CRD_2: &[u64] = &[1, 3, 0, 2];
fn spec_pos_levels() -> Vec<&'static [u64]> {
vec![POS_0, POS_1, POS_2]
}
fn spec_crd_levels() -> Vec<&'static [u64]> {
vec![CRD_0, CRD_1, CRD_2]
}
#[test]
fn element_offset_spec_lookup_1_1_2() {
let result = element_offset(
&[1, 1, 2],
MODE_ORDER,
&spec_pos_levels(),
&spec_crd_levels(),
)
.unwrap();
assert_eq!(result, Some(3));
}
#[test]
fn element_offset_spec_lookup_0_0_1() {
let result = element_offset(
&[0, 0, 1],
MODE_ORDER,
&spec_pos_levels(),
&spec_crd_levels(),
)
.unwrap();
assert_eq!(result, Some(0));
}
#[test]
fn element_offset_spec_lookup_0_2_3() {
let result = element_offset(
&[0, 2, 3],
MODE_ORDER,
&spec_pos_levels(),
&spec_crd_levels(),
)
.unwrap();
assert_eq!(result, Some(1));
}
#[test]
fn element_offset_spec_lookup_1_1_0() {
let result = element_offset(
&[1, 1, 0],
MODE_ORDER,
&spec_pos_levels(),
&spec_crd_levels(),
)
.unwrap();
assert_eq!(result, Some(2));
}
#[test]
fn element_offset_structural_zero_returns_none() {
let result = element_offset(
&[0, 1, 0],
MODE_ORDER,
&spec_pos_levels(),
&spec_crd_levels(),
)
.unwrap();
assert_eq!(result, None);
}
#[test]
fn element_offset_structural_zero_at_level_1() {
let result = element_offset(
&[1, 0, 0],
MODE_ORDER,
&spec_pos_levels(),
&spec_crd_levels(),
)
.unwrap();
assert_eq!(result, None);
}
#[test]
fn element_offset_structural_zero_at_level_0() {
let result = element_offset(
&[2, 0, 0],
MODE_ORDER,
&spec_pos_levels(),
&spec_crd_levels(),
)
.unwrap();
assert_eq!(result, None);
}
#[test]
fn element_offset_rank_mismatch_returns_error() {
let err = element_offset(
&[0, 1], MODE_ORDER,
&spec_pos_levels(),
&spec_crd_levels(),
)
.unwrap_err();
assert!(matches!(err, crate::Error::IndexRankMismatch { .. }));
}
#[test]
fn element_offset_non_identity_mode_order() {
let mode_order: &[u32] = &[2, 1, 0];
let pos_levels: Vec<&[u64]> = vec![&[0, 1], &[0, 1], &[0, 1]];
let crd_levels: Vec<&[u64]> = vec![&[1], &[0], &[0]];
let result = element_offset(&[0, 0, 1], mode_order, &pos_levels, &crd_levels).unwrap();
assert_eq!(result, Some(0));
let result = element_offset(&[0, 0, 0], mode_order, &pos_levels, &crd_levels).unwrap();
assert_eq!(result, None);
}
#[test]
fn validate_index_buffers_spec_example_is_valid() {
assert!(validate_index_buffers(
4,
MODE_ORDER,
SHAPE_DIMS,
&spec_pos_levels(),
&spec_crd_levels(),
)
.is_ok());
}
#[test]
fn validate_index_buffers_empty_tensor_is_valid() {
let pos_levels: Vec<&[u64]> = vec![&[0, 0], &[0], &[0]];
let crd_levels: Vec<&[u64]> = vec![&[], &[], &[]];
assert!(
validate_index_buffers(0, MODE_ORDER, SHAPE_DIMS, &pos_levels, &crd_levels).is_ok()
);
}
#[test]
fn validate_rejects_pos_not_starting_at_zero() {
let pos_levels: Vec<&[u64]> = vec![&[1, 2], &[0, 2, 3], &[0, 1, 2, 4]]; let result =
validate_index_buffers(4, MODE_ORDER, SHAPE_DIMS, &pos_levels, &spec_crd_levels());
assert!(matches!(result, Err(crate::Error::InvalidLayout(_))));
}
#[test]
fn validate_rejects_non_monotone_pos() {
let pos_levels: Vec<&[u64]> = vec![&[0, 2], &[0, 3, 2], &[0, 1, 2, 4]];
let result =
validate_index_buffers(4, MODE_ORDER, SHAPE_DIMS, &pos_levels, &spec_crd_levels());
assert!(matches!(result, Err(crate::Error::InvalidLayout(_))));
}
#[test]
fn validate_rejects_terminal_pos_mismatch_nnz() {
let pos_levels: Vec<&[u64]> = vec![&[0, 2], &[0, 2, 3], &[0, 1, 2, 3]];
let result =
validate_index_buffers(4, MODE_ORDER, SHAPE_DIMS, &pos_levels, &spec_crd_levels());
assert!(matches!(result, Err(crate::Error::InvalidLayout(_))));
}
#[test]
fn validate_rejects_duplicate_siblings() {
let crd_levels: Vec<&[u64]> = vec![&[0, 0], CRD_1, CRD_2];
let result =
validate_index_buffers(4, MODE_ORDER, SHAPE_DIMS, &spec_pos_levels(), &crd_levels);
assert!(matches!(result, Err(crate::Error::InvalidLayout(_))));
}
#[test]
fn validate_rejects_decreasing_siblings() {
let crd_levels: Vec<&[u64]> = vec![&[1, 0], CRD_1, CRD_2];
let result =
validate_index_buffers(4, MODE_ORDER, SHAPE_DIMS, &spec_pos_levels(), &crd_levels);
assert!(matches!(result, Err(crate::Error::InvalidLayout(_))));
}
#[test]
fn validate_rejects_out_of_bounds_coordinate() {
let crd_levels: Vec<&[u64]> = vec![CRD_0, CRD_1, &[1, 3, 0, 4]];
let result =
validate_index_buffers(4, MODE_ORDER, SHAPE_DIMS, &spec_pos_levels(), &crd_levels);
assert!(matches!(result, Err(crate::Error::InvalidLayout(_))));
}
}