use crate::core::core_types::{NodeId, Orientation, Path, Step};
use crate::error::{PanGraphXError, PanResult};
use crate::formats::odgi::encoding::to_usize;
use rayon::prelude::*;
#[derive(Clone, Copy)]
pub(super) struct StepLink {
pub(super) next_node: u32,
pub(super) rank_rev: u32,
}
impl StepLink {
pub(super) const END: u32 = u32::MAX;
}
pub(super) struct PathMeta {
pub(super) name: Vec<u8>,
pub(super) length: u64,
pub(super) first_handle: u64,
pub(super) first_rank: u64,
}
pub(super) struct StepTable {
pub(super) offsets: Vec<usize>,
pub(super) links: Vec<StepLink>,
pub(super) rank_to_node: Vec<NodeId>,
}
pub(super) const WALK_LANES: usize = 16;
pub(super) struct Walk {
index: usize,
name: Vec<u8>,
steps: Vec<Step>,
length: usize,
node: usize,
rank: usize,
}
impl StepTable {
fn broken(name: &[u8], what: &str) -> PanGraphXError {
PanGraphXError::Parse(format!(
"ODGI path {} {what}",
String::from_utf8_lossy(name)
))
}
fn start(&self, index: usize, meta: PathMeta) -> PanResult<Walk> {
let length = to_usize(meta.length, "path length")?;
if length > self.links.len() {
return Err(Self::broken(
&meta.name,
"is longer than the number of stored steps",
));
}
Ok(Walk {
index,
steps: Vec::with_capacity(length),
length,
node: to_usize(meta.first_handle >> 1, "node rank")?,
rank: to_usize(meta.first_rank, "step rank")?,
name: meta.name,
})
}
fn advance(&self, walk: &mut Walk) -> PanResult<()> {
let (Some(&start), Some(&end)) =
(self.offsets.get(walk.node), self.offsets.get(walk.node + 1))
else {
return Err(Self::broken(&walk.name, "refers to a missing node"));
};
if walk.rank >= end - start {
return Err(Self::broken(&walk.name, "refers to a missing step"));
}
let link = self.links[start + walk.rank];
walk.steps.push(Step::new(
self.rank_to_node[walk.node],
Orientation::from(link.rank_rev & 1 == 1),
)?);
if walk.steps.len() < walk.length {
if link.next_node == StepLink::END {
return Err(Self::broken(&walk.name, "ends before its length"));
}
walk.node = link.next_node as usize;
walk.rank = (link.rank_rev >> 1) as usize;
}
Ok(())
}
fn walk_batch(&self, metas: Vec<PathMeta>) -> PanResult<Vec<Path>> {
let mut paths: Vec<Option<Path>> = (0..metas.len()).map(|_| None).collect();
let mut pending = metas.into_iter().enumerate();
let mut lanes: Vec<Walk> = Vec::with_capacity(WALK_LANES);
loop {
while lanes.len() < WALK_LANES
&& let Some((index, meta)) = pending.next()
{
lanes.push(self.start(index, meta)?);
}
if lanes.is_empty() {
break;
}
for walk in &mut lanes {
if walk.steps.len() < walk.length {
self.advance(walk)?;
}
}
let mut lane = 0;
while lane < lanes.len() {
if lanes[lane].steps.len() == lanes[lane].length {
let walk = lanes.swap_remove(lane);
paths[walk.index] = Some(Path {
name: walk.name,
steps: walk.steps,
overlaps: Vec::new(),
});
} else {
lane += 1;
}
}
}
Ok(paths.into_iter().flatten().collect())
}
pub(super) fn walk_all(&self, metas: Vec<PathMeta>) -> PanResult<Vec<Path>> {
let total = metas.iter().try_fold(0_usize, |total, meta| {
usize::try_from(meta.length)
.ok()
.and_then(|length| total.checked_add(length))
});
if total.is_none_or(|total| total > self.links.len()) {
return Err(PanGraphXError::Parse(
"ODGI paths are longer than the number of stored steps".to_string(),
));
}
let batch = metas
.len()
.div_ceil(rayon::current_num_threads())
.clamp(1, WALK_LANES);
let mut batches = Vec::new();
let mut metas = metas.into_iter().peekable();
while metas.peek().is_some() {
batches.push(metas.by_ref().take(batch).collect::<Vec<_>>());
}
let walked = batches
.into_par_iter()
.map(|batch| self.walk_batch(batch))
.collect::<PanResult<Vec<_>>>()?;
Ok(walked.into_iter().flatten().collect())
}
}