1use std::collections::HashMap;
2
3use rsomics_common::{Result, RsomicsError};
4use rsomics_intervals::Interval;
5use smallvec::SmallVec;
6
7const BIN_SIZE: u64 = 16 * 1024;
8
9#[derive(Clone, Copy, Debug, Eq, PartialEq)]
10pub(crate) enum Strand {
11 Forward,
12 Reverse,
13 Unknown,
14}
15
16impl Strand {
17 pub(crate) fn parse(value: &str) -> Result<Self> {
18 match value {
19 "+" => Ok(Self::Forward),
20 "-" => Ok(Self::Reverse),
21 "." => Ok(Self::Unknown),
22 _ => Err(RsomicsError::InvalidInput(format!(
23 "invalid annotation strand {value:?}"
24 ))),
25 }
26 }
27
28 pub(crate) const fn as_str(self) -> &'static str {
29 match self {
30 Self::Forward => "+",
31 Self::Reverse => "-",
32 Self::Unknown => ".",
33 }
34 }
35}
36
37#[derive(Clone, Copy, Debug, Eq, PartialEq)]
38pub enum StrandMode {
39 Unstranded,
40 Sense,
41 Antisense,
42}
43
44#[derive(Clone, Copy, Debug, Eq, PartialEq)]
45pub enum CountLevel {
46 MetaFeature,
47 Feature,
48}
49
50#[derive(Clone, Debug)]
51pub(crate) struct Block {
52 pub(crate) chrom: Option<u32>,
53 pub(crate) start: u64,
54 pub(crate) end: u64,
55}
56
57pub(crate) type Blocks = SmallVec<[Block; 2]>;
58pub(crate) type Hits = SmallVec<[Hit; 4]>;
59
60impl Block {
61 pub(crate) fn new(chrom: Option<u32>, start: u64, end: u64) -> Result<Self> {
62 let interval = Interval::new((), start, end)
63 .map_err(|error| RsomicsError::InvalidInput(error.to_string()))?;
64 if interval.is_empty() {
65 return Err(RsomicsError::InvalidInput(
66 "alignment block has zero length".to_owned(),
67 ));
68 }
69 Ok(Self {
70 chrom,
71 start: interval.start(),
72 end: interval.end(),
73 })
74 }
75
76 pub(crate) const fn len(&self) -> u64 {
77 self.end - self.start
78 }
79}
80
81#[derive(Clone, Debug)]
82pub(crate) struct PartInput {
83 pub(crate) id: String,
84 pub(crate) chrom: String,
85 pub(crate) start: u64,
86 pub(crate) end: u64,
87 pub(crate) strand: Strand,
88}
89
90#[derive(Clone, Debug)]
91struct Part {
92 interval: Interval<String>,
93 chrom_id: u32,
94 strand: Strand,
95 row: usize,
96}
97
98#[derive(Clone, Debug)]
99pub(crate) struct FeatureRow {
100 id: String,
101 parts: Vec<usize>,
102 length: u64,
103}
104
105impl FeatureRow {
106 #[must_use]
107 pub(crate) fn id(&self) -> &str {
108 &self.id
109 }
110
111 #[must_use]
112 pub(crate) const fn length(&self) -> u64 {
113 self.length
114 }
115}
116
117#[derive(Clone, Debug)]
118pub(crate) struct FeatureSet {
119 rows: Vec<FeatureRow>,
120 parts: Vec<Part>,
121 chrom_ids: HashMap<String, u32>,
122 index: HashMap<u32, HashMap<u64, Vec<usize>>>,
123}
124
125#[derive(Clone, Copy, Debug, Eq, PartialEq)]
126pub(crate) struct Hit {
127 pub(crate) row: usize,
128 pub(crate) overlap_bases: u64,
129 pub(crate) feature_overlap_bases: u64,
130 pub(crate) feature_length: u64,
131}
132
133impl FeatureSet {
134 pub(crate) fn build(inputs: Vec<PartInput>, level: CountLevel) -> Result<Self> {
135 if inputs.is_empty() {
136 return Err(RsomicsError::InvalidInput(
137 "annotation contains no selected features".to_owned(),
138 ));
139 }
140
141 let mut rows = Vec::<FeatureRow>::new();
142 let mut parts = Vec::<Part>::with_capacity(inputs.len());
143 let mut groups = HashMap::<String, usize>::new();
144 let mut chrom_ids = HashMap::<String, u32>::new();
145
146 for input in inputs {
147 let next_chrom_id = u32::try_from(chrom_ids.len()).map_err(|_| {
148 RsomicsError::InvalidInput("too many annotation chromosomes".to_owned())
149 })?;
150 let chrom_id = *chrom_ids
151 .entry(input.chrom.clone())
152 .or_insert(next_chrom_id);
153 let interval = Interval::new(input.chrom, input.start, input.end)
154 .map_err(|error| RsomicsError::InvalidInput(error.to_string()))?;
155 if interval.is_empty() {
156 return Err(RsomicsError::InvalidInput(format!(
157 "feature {} has zero length",
158 input.id
159 )));
160 }
161 let row = match level {
162 CountLevel::Feature => {
163 let row = rows.len();
164 rows.push(FeatureRow {
165 id: input.id,
166 parts: Vec::new(),
167 length: 0,
168 });
169 row
170 }
171 CountLevel::MetaFeature => match groups.get(&input.id).copied() {
172 Some(row) => row,
173 None => {
174 let row = rows.len();
175 groups.insert(input.id.clone(), row);
176 rows.push(FeatureRow {
177 id: input.id,
178 parts: Vec::new(),
179 length: 0,
180 });
181 row
182 }
183 },
184 };
185 let part = parts.len();
186 parts.push(Part {
187 interval,
188 chrom_id,
189 strand: input.strand,
190 row,
191 });
192 rows[row].parts.push(part);
193 }
194
195 for row in &mut rows {
196 row.length = union_length(row.parts.iter().map(|&part| &parts[part]));
197 }
198
199 let mut index: HashMap<u32, HashMap<u64, Vec<usize>>> = HashMap::new();
200 for (part_index, part) in parts.iter().enumerate() {
201 let first = part.interval.start() / BIN_SIZE;
202 let last = (part.interval.end() - 1) / BIN_SIZE;
203 let bins = index.entry(part.chrom_id).or_default();
204 for bin in first..=last {
205 bins.entry(bin).or_default().push(part_index);
206 }
207 }
208
209 Ok(Self {
210 rows,
211 parts,
212 chrom_ids,
213 index,
214 })
215 }
216
217 #[must_use]
218 pub(crate) fn rows(&self) -> &[FeatureRow] {
219 &self.rows
220 }
221
222 pub(crate) fn chrom_id(&self, name: &str) -> Option<u32> {
223 self.chrom_ids.get(name).copied()
224 }
225
226 pub(crate) fn hits(
227 &self,
228 blocks: &[Block],
229 strand_mode: StrandMode,
230 reverse: bool,
231 track_feature_fraction: bool,
232 ) -> Hits {
233 let mut candidates = SmallVec::<[usize; 16]>::new();
234 for block in blocks {
235 let Some(chrom) = block.chrom else {
236 continue;
237 };
238 let Some(bins) = self.index.get(&chrom) else {
239 continue;
240 };
241 let first = block.start / BIN_SIZE;
242 let last = (block.end - 1) / BIN_SIZE;
243 for bin in first..=last {
244 if let Some(parts) = bins.get(&bin) {
245 candidates.extend_from_slice(parts);
246 }
247 }
248 }
249 candidates.sort_unstable();
250 candidates.dedup();
251
252 let mut intersections = SmallVec::<[(usize, u32, u64, u64); 16]>::new();
253 let mut feature_overlaps = SmallVec::<[(usize, u64, u64); 16]>::new();
254 for part_index in candidates {
255 let part = &self.parts[part_index];
256 if !strand_matches(part.strand, strand_mode, reverse) {
257 continue;
258 }
259 let mut part_intersections = SmallVec::<[(u64, u64); 4]>::new();
260 for block in blocks
261 .iter()
262 .filter(|block| block.chrom == Some(part.chrom_id))
263 {
264 let start = block.start.max(part.interval.start());
265 let end = block.end.min(part.interval.end());
266 if start < end {
267 intersections.push((part.row, part.chrom_id, start, end));
268 if track_feature_fraction {
269 part_intersections.push((start, end));
270 }
271 }
272 }
273 if track_feature_fraction {
274 let overlap = union_interval_length(&mut part_intersections);
275 if overlap > 0 {
276 feature_overlaps.push((part.row, overlap, part.interval.len()));
277 }
278 }
279 }
280 union_hits(intersections, feature_overlaps)
281 }
282
283 pub(crate) fn fields(&self, row: usize) -> (String, String, String, String) {
284 let row = &self.rows[row];
285 let mut chrom = Vec::with_capacity(row.parts.len());
286 let mut start = Vec::with_capacity(row.parts.len());
287 let mut end = Vec::with_capacity(row.parts.len());
288 let mut strand = Vec::with_capacity(row.parts.len());
289 for &part in &row.parts {
290 let part = &self.parts[part];
291 chrom.push(part.interval.chrom());
292 start.push((part.interval.start() + 1).to_string());
293 end.push(part.interval.end().to_string());
294 strand.push(part.strand.as_str());
295 }
296 (
297 chrom.join(";"),
298 start.join(";"),
299 end.join(";"),
300 strand.join(";"),
301 )
302 }
303}
304
305fn strand_matches(feature: Strand, mode: StrandMode, reverse: bool) -> bool {
306 match mode {
307 StrandMode::Unstranded => true,
308 StrandMode::Sense => matches!(
309 (feature, reverse),
310 (Strand::Forward, false) | (Strand::Reverse, true)
311 ),
312 StrandMode::Antisense => matches!(
313 (feature, reverse),
314 (Strand::Forward, true) | (Strand::Reverse, false)
315 ),
316 }
317}
318
319fn union_length<'a>(parts: impl Iterator<Item = &'a Part>) -> u64 {
320 union_tuples(
321 parts
322 .map(|part| {
323 (
324 part.interval.chrom().to_owned(),
325 part.interval.start(),
326 part.interval.end(),
327 )
328 })
329 .collect(),
330 )
331}
332
333fn union_tuples(mut intervals: Vec<(String, u64, u64)>) -> u64 {
334 intervals.sort_unstable_by(|left, right| {
335 left.0
336 .cmp(&right.0)
337 .then(left.1.cmp(&right.1))
338 .then(left.2.cmp(&right.2))
339 });
340 let mut total = 0;
341 let mut current: Option<(String, u64, u64)> = None;
342 for (chrom, start, end) in intervals {
343 match current.as_mut() {
344 Some((current_chrom, _, current_end))
345 if *current_chrom == chrom && start <= *current_end =>
346 {
347 *current_end = (*current_end).max(end);
348 }
349 Some((_, current_start, current_end)) => {
350 total += *current_end - *current_start;
351 current = Some((chrom, start, end));
352 }
353 None => current = Some((chrom, start, end)),
354 }
355 }
356 if let Some((_, start, end)) = current {
357 total += end - start;
358 }
359 total
360}
361
362fn union_interval_length(intervals: &mut SmallVec<[(u64, u64); 4]>) -> u64 {
363 intervals.sort_unstable();
364 let mut total = 0;
365 let mut current = None;
366 for (start, end) in intervals.drain(..) {
367 match current.as_mut() {
368 Some((_, current_end)) if start <= *current_end => {
369 *current_end = (*current_end).max(end);
370 }
371 Some((current_start, current_end)) => {
372 total += *current_end - *current_start;
373 current = Some((start, end));
374 }
375 None => current = Some((start, end)),
376 }
377 }
378 if let Some((start, end)) = current {
379 total += end - start;
380 }
381 total
382}
383
384fn union_hits(
385 mut intervals: SmallVec<[(usize, u32, u64, u64); 16]>,
386 feature_overlaps: SmallVec<[(usize, u64, u64); 16]>,
387) -> Hits {
388 let mut best = HashMap::<usize, (u64, u64)>::new();
389 for (row, overlap, length) in feature_overlaps {
390 let candidate = (overlap, length);
391 let current = best.entry(row).or_insert(candidate);
392 if u128::from(overlap) * u128::from(current.1) > u128::from(current.0) * u128::from(length)
393 {
394 *current = candidate;
395 }
396 }
397 intervals.sort_unstable();
398 let mut hits = Hits::new();
399 let mut current: Option<(usize, u32, u64, u64)> = None;
400 let mut row_total = 0;
401 for (row, chrom, start, end) in intervals {
402 match current.as_mut() {
403 Some((current_row, current_chrom, _, current_end))
404 if *current_row == row && *current_chrom == chrom && start <= *current_end =>
405 {
406 *current_end = (*current_end).max(end);
407 }
408 Some((current_row, _, current_start, current_end)) => {
409 row_total += *current_end - *current_start;
410 if *current_row != row {
411 let (feature_overlap_bases, feature_length) =
412 best.get(current_row).copied().unwrap_or((1, 1));
413 hits.push(Hit {
414 row: *current_row,
415 overlap_bases: row_total,
416 feature_overlap_bases,
417 feature_length,
418 });
419 row_total = 0;
420 }
421 current = Some((row, chrom, start, end));
422 }
423 None => current = Some((row, chrom, start, end)),
424 }
425 }
426 if let Some((row, _, start, end)) = current {
427 row_total += end - start;
428 let (feature_overlap_bases, feature_length) = best.get(&row).copied().unwrap_or((1, 1));
429 hits.push(Hit {
430 row,
431 overlap_bases: row_total,
432 feature_overlap_bases,
433 feature_length,
434 });
435 }
436 hits
437}
438
439#[cfg(test)]
440mod tests {
441 use super::*;
442
443 fn part(id: &str, start: u64, end: u64, strand: Strand) -> PartInput {
444 PartInput {
445 id: id.to_owned(),
446 chrom: "chr1".to_owned(),
447 start,
448 end,
449 strand,
450 }
451 }
452
453 #[test]
454 fn meta_feature_length_is_a_union() {
455 let features = FeatureSet::build(
456 vec![
457 part("g", 300, 350, Strand::Forward),
458 part("g", 340, 400, Strand::Forward),
459 ],
460 CountLevel::MetaFeature,
461 )
462 .unwrap();
463 assert_eq!(features.rows()[0].length(), 100);
464 }
465
466 #[test]
467 fn query_deduplicates_overlapping_parts_and_blocks() {
468 let features = FeatureSet::build(
469 vec![
470 part("g", 100, 150, Strand::Forward),
471 part("g", 140, 200, Strand::Forward),
472 ],
473 CountLevel::MetaFeature,
474 )
475 .unwrap();
476 let hits = features.hits(
477 &[Block::new(Some(0), 130, 170).unwrap()],
478 StrandMode::Unstranded,
479 false,
480 false,
481 );
482 assert_eq!(hits[0].overlap_bases, 40);
483 }
484
485 #[test]
486 fn strand_modes_filter_candidates() {
487 let features = FeatureSet::build(
488 vec![
489 part("plus", 100, 200, Strand::Forward),
490 part("minus", 100, 200, Strand::Reverse),
491 ],
492 CountLevel::MetaFeature,
493 )
494 .unwrap();
495 let block = Block::new(Some(0), 120, 140).unwrap();
496 assert_eq!(
497 features.hits(
498 std::slice::from_ref(&block),
499 StrandMode::Sense,
500 false,
501 false,
502 )[0]
503 .row,
504 0
505 );
506 assert_eq!(
507 features.hits(&[block], StrandMode::Antisense, false, false)[0].row,
508 1
509 );
510 }
511}