use crate::error::{PanGraphXError, PanResult};
use gbz_construct::bwt::BWT;
use gbz_construct::support::{ByteCodeIter, RLEIter};
use gbz_construct::{ENDMARKER, GBWT};
use rayon::prelude::*;
const RECORDS_PER_TASK: usize = 1 << 15;
#[derive(Clone, Copy)]
pub(super) struct FlatEdge {
pub(super) successor: u32,
offset: u32,
}
#[derive(Clone, Copy)]
struct FlatRun {
rank: u32,
len: u32,
}
pub(super) struct FlatBwt {
alphabet_offset: usize,
edge_ends: Vec<u32>,
run_ends: Vec<u32>,
edges: Vec<FlatEdge>,
runs: Vec<FlatRun>,
}
#[derive(Default)]
struct DecodedRecords {
edge_ends: Vec<u32>,
run_ends: Vec<u32>,
edges: Vec<FlatEdge>,
runs: Vec<FlatRun>,
}
fn invalid_record(record: usize) -> PanGraphXError {
PanGraphXError::Parse(format!("GBZ file has an invalid GBWT record {record}"))
}
fn too_large() -> PanGraphXError {
PanGraphXError::Parse("GBZ file has a BWT too large to decode".to_string())
}
fn small(value: usize, record: usize) -> PanResult<u32> {
u32::try_from(value).map_err(|_| invalid_record(record))
}
impl DecodedRecords {
fn decode(bwt: &BWT, records: std::ops::Range<usize>) -> PanResult<Self> {
let mut decoded = Self {
edge_ends: Vec::with_capacity(records.len()),
run_ends: Vec::with_capacity(records.len()),
..Self::default()
};
for record in records {
if let Some((edges, runs)) = bwt.compressed_record(record) {
decoded.push_record(record, edges, runs)?;
}
decoded
.edge_ends
.push(u32::try_from(decoded.edges.len()).map_err(|_| too_large())?);
decoded
.run_ends
.push(u32::try_from(decoded.runs.len()).map_err(|_| too_large())?);
}
Ok(decoded)
}
fn push_record(&mut self, record: usize, edges: &[u8], runs: &[u8]) -> PanResult<()> {
let mut ints = ByteCodeIter::new(edges);
let sigma = ints.next().ok_or_else(|| invalid_record(record))?;
let mut successor = 0usize;
for _ in 0..sigma {
let gap = ints.next().ok_or_else(|| invalid_record(record))?;
let offset = ints.next().ok_or_else(|| invalid_record(record))?;
successor = successor
.checked_add(gap)
.ok_or_else(|| invalid_record(record))?;
self.edges.push(FlatEdge {
successor: small(successor, record)?,
offset: small(offset, record)?,
});
}
if sigma > 1 {
for run in RLEIter::with_sigma(runs, sigma) {
if run.value >= sigma {
return Err(invalid_record(record));
}
self.runs.push(FlatRun {
rank: small(run.value, record)?,
len: small(run.len, record)?,
});
}
}
Ok(())
}
}
impl FlatBwt {
pub(super) fn new(gbwt: &GBWT) -> PanResult<Self> {
let bwt: &BWT = gbwt.as_ref();
let record_count = bwt.len();
let tasks: Vec<DecodedRecords> = (0..record_count.div_ceil(RECORDS_PER_TASK))
.into_par_iter()
.map(|task| {
let start = task * RECORDS_PER_TASK;
DecodedRecords::decode(bwt, start..record_count.min(start + RECORDS_PER_TASK))
})
.collect::<PanResult<_>>()?;
let mut flat = Self {
alphabet_offset: gbwt.alphabet_offset(),
edge_ends: Vec::with_capacity(record_count),
run_ends: Vec::with_capacity(record_count),
edges: Vec::with_capacity(tasks.iter().map(|task| task.edges.len()).sum()),
runs: Vec::with_capacity(tasks.iter().map(|task| task.runs.len()).sum()),
};
for task in tasks {
let edge_base = u32::try_from(flat.edges.len()).map_err(|_| too_large())?;
let run_base = u32::try_from(flat.runs.len()).map_err(|_| too_large())?;
for (edge_end, run_end) in task.edge_ends.iter().zip(&task.run_ends) {
flat.edge_ends
.push(edge_base.checked_add(*edge_end).ok_or_else(too_large)?);
flat.run_ends
.push(run_base.checked_add(*run_end).ok_or_else(too_large)?);
}
flat.edges.extend_from_slice(&task.edges);
flat.runs.extend_from_slice(&task.runs);
}
Ok(flat)
}
#[inline]
fn record(
&self,
node: usize,
) -> PanResult<(usize, std::ops::Range<usize>, std::ops::Range<usize>)> {
let record = node.wrapping_sub(self.alphabet_offset);
let (Some(&edge_end), Some(&run_end)) =
(self.edge_ends.get(record), self.run_ends.get(record))
else {
return Err(PanGraphXError::Parse(format!(
"GBZ file refers to GBWT node {node}, which is not in the alphabet"
)));
};
let previous = |ends: &[u32]| record.checked_sub(1).map_or(0, |i| ends[i] as usize);
Ok((
record,
previous(&self.edge_ends)..edge_end as usize,
previous(&self.run_ends)..run_end as usize,
))
}
pub(super) fn edges(&self, node: usize) -> PanResult<&[FlatEdge]> {
let (_, edges, _) = self.record(node)?;
Ok(&self.edges[edges])
}
#[inline]
pub(super) fn lf(&self, node: usize, offset: usize) -> PanResult<Option<(usize, usize)>> {
let (record, edges, runs) = self.record(node)?;
let edges = &self.edges[edges];
let (edge, position) = if let [edge] = edges {
(*edge, offset)
} else {
let runs = &self.runs[runs];
let mut run_start = 0usize;
let containing = runs.iter().position(|run| {
let contains = offset - run_start < run.len as usize;
if !contains {
run_start += run.len as usize;
}
contains
});
let containing = containing.ok_or_else(|| invalid_record(record))?;
let rank = runs[containing].rank;
let earlier: usize = runs[..containing]
.iter()
.filter(|run| run.rank == rank)
.map(|run| run.len as usize)
.sum();
let edge = *edges
.get(rank as usize)
.ok_or_else(|| invalid_record(record))?;
(edge, earlier + offset - run_start)
};
if edge.successor as usize == ENDMARKER {
return Ok(None);
}
Ok(Some((
edge.successor as usize,
edge.offset as usize + position,
)))
}
}