use super::*;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(super) enum Terminal {
Five,
Three,
Excise,
None,
}
pub(super) fn trace_hit(
name: &str,
start: usize,
end: usize,
cost: usize,
action: Option<HitAction>,
) {
tracing::trace!(
adapter = name,
start,
end,
cost,
action = match action {
Some(HitAction::TrimFivePrime) => "trim 5'",
Some(HitAction::TrimThreePrime) => "trim 3'",
Some(HitAction::Excise) => "excise and split",
None => "no action",
},
"Adapter hit"
);
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(super) enum HitAction {
TrimFivePrime,
TrimThreePrime,
Excise,
}
pub(super) fn nearer_end(start: usize, end: usize, n: usize) -> Terminal {
if start <= n - end {
Terminal::Five
} else {
Terminal::Three
}
}
pub(super) fn classify_terminal(start: usize, end: usize, n: usize, end_size: usize) -> Terminal {
let in_head = start <= end_size;
let in_tail = end >= n.saturating_sub(end_size);
match (in_head, in_tail) {
(true, true) => match (start <= FLANK_SLACK, n - end <= FLANK_SLACK) {
(false, false) => Terminal::Excise,
(true, false) => Terminal::Five,
(false, true) => Terminal::Three,
(true, true) => nearer_end(start, end, n),
},
(true, false) => Terminal::Five,
(false, true) => Terminal::Three,
(false, false) => Terminal::None,
}
}
pub(super) fn ends_only_terminal(start: usize, end: usize, n: usize, end_size: usize) -> Terminal {
match classify_terminal(start, end, n, end_size) {
Terminal::Excise => nearer_end(start, end, n),
other => other,
}
}
#[derive(Debug, Clone, Copy)]
pub(super) enum Site {
Head,
Tail { head_end: usize },
Interior,
}
pub(super) fn terminal_windows(
n: usize,
end_size: usize,
len: usize,
k_end: usize,
) -> (usize, usize) {
let reach = end_size + len + k_end;
(reach.min(n), n.saturating_sub(reach))
}
pub(super) struct Keep<'a> {
pub(super) adapters: &'a [Adapter],
pub(super) budgets: &'a [Budget],
panel_gates: &'a [bool],
split_classes: &'a [usize],
paired: &'a [bool],
class: usize,
pub(super) five_bounded: bool,
pub(super) three_bounded: bool,
pub(super) gate_panels: bool,
pub(super) error_rate: f64,
pub(super) n: usize,
pub(super) end_size: usize,
pub(super) split: bool,
pub(super) lo: usize,
pub(super) hi: usize,
pub(super) interior: Vec<(usize, usize)>,
excised: Vec<Applied>,
five: Vec<Applied>,
three: Vec<Applied>,
fixed_lo: usize,
fixed_hi: usize,
pub(super) acted: Vec<usize>,
pub(super) deferred: Vec<Deferred>,
}
#[derive(Debug, Clone, Copy)]
pub(super) struct Applied {
adapter_idx: usize,
start: usize,
end: usize,
clip_start: usize,
clip_end: usize,
standalone: bool,
}
#[derive(Debug, Clone, Copy)]
pub(super) struct Deferred {
pub(super) adapter_idx: usize,
pub(super) start: usize,
pub(super) end: usize,
pub(super) cost: usize,
pub(super) clip_start: usize,
pub(super) clip_end: usize,
pub(super) action: HitAction,
}
impl<'a> Keep<'a> {
pub(super) fn new(
cfg: &'a AdapterConfig,
index: &'a CandidateIndex,
n: usize,
split: bool,
) -> Self {
Self {
adapters: &cfg.adapters,
budgets: &index.budgets,
panel_gates: &index.panel_gates,
split_classes: &index.split_classes,
paired: &index.paired,
class: interior_class(n),
five_bounded: false,
three_bounded: false,
gate_panels: true,
error_rate: cfg.error_rate,
n,
end_size: cfg.end_size.min(n),
split,
lo: 0,
hi: n,
interior: Vec::new(),
excised: Vec::new(),
five: Vec::new(),
three: Vec::new(),
fixed_lo: 0,
fixed_hi: n,
acted: Vec::new(),
deferred: Vec::new(),
}
}
pub(super) fn partial_hit_is_valid(&self, adapter_idx: usize, hit: Hit) -> bool {
let overhang = hit.left_overhang + hit.right_overhang;
if overhang == 0 {
return true;
}
let overlap = self.adapters[adapter_idx].seq.len() - overhang;
overlap >= MIN_OVERLAP
&& (hit.left_overhang == 0 || hit.start == 0)
&& (hit.right_overhang == 0 || hit.end == self.n)
&& self.residue_within_budget(hit, overlap)
}
pub(super) fn residue_within_budget(&self, hit: Hit, overlap: usize) -> bool {
let charged = overhang_cost(
self.error_rate as f32,
hit.left_overhang,
hit.right_overhang,
);
hit.cost.saturating_sub(charged) <= partial_budget(self.error_rate, overlap)
}
pub(super) fn accept(&mut self, site: Site, adapter_idx: usize, hit: Hit) {
let adapter = &self.adapters[adapter_idx];
let Hit {
start, end, cost, ..
} = hit;
if !self.partial_hit_is_valid(adapter_idx, hit) {
return;
}
let terminal = if self.split {
classify_terminal(start, end, self.n, self.end_size)
} else {
ends_only_terminal(start, end, self.n, self.end_size)
};
let action = match (site, terminal) {
(Site::Head, Terminal::Five) => HitAction::TrimFivePrime,
(Site::Head, Terminal::Excise) if self.splits(adapter_idx) => HitAction::Excise,
(Site::Head, Terminal::Excise) => match nearer_end(start, end, self.n) {
Terminal::Five => HitAction::TrimFivePrime,
_ => HitAction::TrimThreePrime,
},
(Site::Tail { .. }, Terminal::Three) => HitAction::TrimThreePrime,
(Site::Interior, _) if start <= FLANK_SLACK => HitAction::TrimFivePrime,
(Site::Interior, _) if self.n - end <= FLANK_SLACK => HitAction::TrimThreePrime,
(Site::Interior, Terminal::None) if self.splits(adapter_idx) => HitAction::Excise,
(Site::Interior, Terminal::None) => {
trace_hit(&adapter.name, start, end, cost, None);
return;
},
(Site::Head, Terminal::None) => {
trace_hit(&adapter.name, start, end, cost, None);
return;
},
(Site::Tail { head_end }, Terminal::None) => {
if start >= head_end {
trace_hit(&adapter.name, start, end, cost, None);
}
return;
},
_ => return,
};
if action == HitAction::Excise && hit.clip_start + hit.clip_end >= MIN_OVERLAP {
trace_hit(&adapter.name, start, end, cost, None);
return;
}
let whole = hit.left_overhang + hit.right_overhang == 0;
let terminal = matches!(site, Site::Head | Site::Tail { .. })
&& matches!(action, HitAction::TrimFivePrime | HitAction::TrimThreePrime);
if whole && terminal && cost > self.budgets[adapter_idx].k_far {
self.deferred.push(Deferred {
adapter_idx,
start,
end,
cost,
clip_start: hit.clip_start,
clip_end: hit.clip_end,
action,
});
return;
}
self.apply(
adapter_idx,
start,
end,
cost,
(hit.clip_start, hit.clip_end),
action,
);
}
pub(super) fn apply(
&mut self,
adapter_idx: usize,
start: usize,
end: usize,
cost: usize,
(clip_start, clip_end): (usize, usize),
action: HitAction,
) {
trace_hit(
&self.adapters[adapter_idx].name,
start,
end,
cost,
Some(action),
);
self.acted.push(adapter_idx);
let applied = Applied {
adapter_idx,
start,
end,
clip_start,
clip_end,
standalone: false,
};
match action {
HitAction::TrimFivePrime => {
self.lo = self.lo.max(end);
self.five.push(applied);
self.five_bounded |= self.panel_gates[adapter_idx];
},
HitAction::TrimThreePrime => {
self.hi = self.hi.min(start);
self.three.push(applied);
self.three_bounded |= self.panel_gates[adapter_idx];
},
HitAction::Excise => {
self.interior.push((start, end));
self.excised.push(applied);
},
}
}
pub(super) fn accept_pair(
&mut self,
(closing_idx, closing): (usize, Hit),
(opening_idx, opening): (usize, Hit),
) {
let interior = |hit: &Hit| {
hit.start > FLANK_SLACK
&& self.n - hit.end > FLANK_SLACK
&& classify_terminal(hit.start, hit.end, self.n, self.end_size) == Terminal::None
&& hit.clip_start + hit.clip_end < MIN_OVERLAP
};
if !self.split || !interior(&closing) || !interior(&opening) {
return;
}
for (adapter_idx, hit) in [(closing_idx, closing), (opening_idx, opening)] {
self.apply(
adapter_idx,
hit.start,
hit.end,
hit.cost,
(hit.clip_start, hit.clip_end),
HitAction::Excise,
);
if let Some(applied) = self.excised.last_mut() {
applied.standalone = true;
}
}
}
pub(super) fn accept_standalone(&mut self, adapter_idx: usize, hit: Hit) {
let excisions = self.excised.len();
self.accept(Site::Interior, adapter_idx, hit);
if self.excised.len() > excisions
&& let Some(applied) = self.excised.last_mut()
{
applied.standalone = true;
}
}
pub(super) fn splits(&self, adapter_idx: usize) -> bool {
self.split_classes[adapter_idx] > self.class
}
pub(super) fn trim_five_fixed(&mut self, end: usize) {
self.lo = self.lo.max(end);
self.fixed_lo = self.fixed_lo.max(end);
}
pub(super) fn trim_three_fixed(&mut self, start: usize) {
self.hi = self.hi.min(start);
self.fixed_hi = self.fixed_hi.min(start);
}
pub(super) fn refine(&mut self) {
if !self.five.is_empty() {
self.five.sort_unstable_by_key(|a| std::cmp::Reverse(a.end));
let mut lo = self.fixed_lo;
for a in &self.five {
if a.end <= lo {
break;
}
lo = lo.max(a.end - a.clip_end);
}
self.lo = lo;
}
if !self.three.is_empty() {
self.three.sort_unstable_by_key(|a| a.start);
let mut hi = self.fixed_hi;
for a in &self.three {
if a.start >= hi {
break;
}
hi = hi.min(a.start + a.clip_start);
}
self.hi = hi;
}
for (cut, a) in self.interior.iter_mut().zip(&self.excised) {
*cut = (a.start + a.clip_start, a.end - a.clip_end);
}
}
pub(super) fn settle(&mut self) {
loop {
let (lo, hi) = (self.lo, self.hi);
let anchored = self.deferred.iter().position(|d| match d.action {
HitAction::TrimFivePrime => d.start <= lo + FLANK_SLACK && d.end > lo,
HitAction::TrimThreePrime => d.end + FLANK_SLACK >= hi && d.start < hi,
HitAction::Excise => false,
});
let Some(i) = anchored else {
return;
};
let d = self.deferred.swap_remove(i);
self.apply(
d.adapter_idx,
d.start,
d.end,
d.cost,
(d.clip_start, d.clip_end),
d.action,
);
}
}
fn backs(&self, (s, e): (usize, usize), adapter_idx: usize) -> bool {
self.interior.iter().zip(&self.excised).any(|(&(t, u), b)| {
let reach = if self.paired[b.adapter_idx] {
self.end_size.max(FLANK_SLACK)
} else {
FLANK_SLACK
};
b.adapter_idx != adapter_idx
&& t <= e + reach
&& u + reach >= s
&& s.saturating_sub(t) + u.saturating_sub(e) >= MIN_OVERLAP
})
}
pub(super) fn into_cuts(mut self, min_piece: usize) -> (usize, usize, Vec<(usize, usize)>) {
self.settle();
self.refine();
for d in &self.deferred {
trace_hit(
&self.adapters[d.adapter_idx].name,
d.start,
d.end,
d.cost,
None,
);
}
let backed: Vec<bool> = self
.interior
.iter()
.zip(&self.excised)
.map(|(&cut, a)| {
!self.paired[a.adapter_idx] || a.standalone || self.backs(cut, a.adapter_idx)
})
.collect();
let Keep {
lo, hi, interior, ..
} = self;
if lo >= hi {
return (lo, hi, Vec::new());
}
let mut cuts: Vec<(usize, usize)> = interior
.into_iter()
.zip(backed)
.filter(|&(_, backed)| backed)
.filter_map(|((s, e), _)| {
let s = s.max(lo);
let e = e.min(hi);
(s < e).then_some((s, e))
})
.collect();
cuts.sort_unstable();
let mut merged: Vec<(usize, usize)> = Vec::new();
for (s, e) in cuts {
if let Some(last) = merged.last_mut() {
let gap = s.saturating_sub(last.1);
if s <= last.1 || gap <= FLANK_SLACK || gap < min_piece {
last.1 = last.1.max(e);
continue;
}
}
merged.push((s, e));
}
(lo, hi, merged)
}
}