def trim_semiglobal

bend-edit-distance@0.2.2.0 · src/Myers.bend:465

import Base
import bend-edit-distance@0.2.2.0/EdlibTypes.bend as E

465# If the bottom score is >= k+32 every cell in that block is > k. Only
466# trailing blocks are removed. HW always retains block zero: its free top
467# boundary can seed a new alignment after an arbitrarily long target prefix.
468def trim_semiglobal(entries: List<&2, BandEntry>, rest: List<&2, Peq>,
469                    +mode: E.Mode, +index: Nat, +maximum: Nat) -> List<&2, BandEntry> & List<&2, Peq>:
470  match entries mode:
471    case Nil{} _:
472      (Nil{}, rest)
473    case BandEntry{profile, Block{pv, mv, +score}} <> tail E.HW{}:
474      trim_last.join(BandEntry{profile, Block{pv, mv, score}},
475        trim_semiglobal(tail, rest, mode, 1n+index, maximum),
476        Bool.or(Nat.is_eq(index, 0n), Nat.is_lt(U32.to_nat(score), Nat.add(maximum, 32n))))
477    case BandEntry{profile, Block{pv, mv, +score}} <> tail _:
478      trim_last.join(BandEntry{profile, Block{pv, mv, score}},
479        trim_semiglobal(tail, rest, mode, 1n+index, maximum),
480        Nat.is_lt(U32.to_nat(score), Nat.add(maximum, 32n)))