use std::cmp::Ordering;
use crate::{Error, Result};
pub fn element_offset(query: &[u64], is_sorted: bool, indices: &[u64]) -> Result<Option<u64>> {
let rank = query.len();
if rank == 0 {
return Err(Error::IndexRankMismatch {
index_rank: 0,
shape_rank: 0,
});
}
if !indices.len().is_multiple_of(rank) {
return Err(Error::InvalidLayout(format!(
"coo: indices.len()={} is not a multiple of rank={rank}",
indices.len()
)));
}
let nnz = indices.len() / rank;
let coords = |r: usize| &indices[r * rank..r * rank + rank];
if is_sorted {
let (mut lo, mut hi) = (0usize, nnz);
while lo < hi {
let mid = lo + (hi - lo) / 2;
match coords(mid).cmp(query) {
Ordering::Less => lo = mid + 1,
Ordering::Greater => hi = mid,
Ordering::Equal => return Ok(Some(mid as u64)),
}
}
Ok(None)
} else {
for r in 0..nnz {
if coords(r) == query {
return Ok(Some(r as u64));
}
}
Ok(None)
}
}
#[cfg(test)]
mod tests {
use super::*;
const INDICES: &[u64] = &[0, 1, 2, 0, 2, 3, 3, 3];
#[test]
fn sorted_lookup_hits() {
assert_eq!(element_offset(&[0, 1], true, INDICES).unwrap(), Some(0));
assert_eq!(element_offset(&[2, 0], true, INDICES).unwrap(), Some(1));
assert_eq!(element_offset(&[2, 3], true, INDICES).unwrap(), Some(2));
assert_eq!(element_offset(&[3, 3], true, INDICES).unwrap(), Some(3));
}
#[test]
fn sorted_lookup_structural_zeros() {
assert_eq!(element_offset(&[0, 0], true, INDICES).unwrap(), None);
assert_eq!(element_offset(&[1, 1], true, INDICES).unwrap(), None);
assert_eq!(element_offset(&[2, 2], true, INDICES).unwrap(), None);
assert_eq!(element_offset(&[3, 0], true, INDICES).unwrap(), None);
}
#[test]
fn unsorted_lookup_matches_sorted() {
let unsorted: &[u64] = &[2, 3, 0, 1, 3, 3, 2, 0];
assert_eq!(element_offset(&[0, 1], false, unsorted).unwrap(), Some(1));
assert_eq!(element_offset(&[2, 3], false, unsorted).unwrap(), Some(0));
assert_eq!(element_offset(&[3, 3], false, unsorted).unwrap(), Some(2));
assert_eq!(element_offset(&[1, 1], false, unsorted).unwrap(), None);
}
#[test]
fn rank_3_lookup() {
let indices: &[u64] = &[0, 0, 1, 0, 2, 3, 1, 1, 0];
assert_eq!(element_offset(&[0, 2, 3], true, indices).unwrap(), Some(1));
assert_eq!(element_offset(&[1, 1, 0], true, indices).unwrap(), Some(2));
assert_eq!(element_offset(&[1, 1, 2], true, indices).unwrap(), None);
}
#[test]
fn empty_tensor_is_all_zeros() {
assert_eq!(element_offset(&[0, 0], true, &[]).unwrap(), None);
assert_eq!(element_offset(&[0, 0], false, &[]).unwrap(), None);
}
#[test]
fn rank_zero_query_is_rejected() {
assert!(matches!(
element_offset(&[], true, &[]),
Err(Error::IndexRankMismatch { .. })
));
}
#[test]
fn indices_not_multiple_of_rank_is_rejected() {
assert!(matches!(
element_offset(&[0, 0], true, &[0, 1, 2]),
Err(Error::InvalidLayout(_))
));
}
}