def hw_locations

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

import Base
import bend-edit-distance@0.2.2.0/src/Alignment.bend as A

607# Independent starts share one reversed query profile. Split their searches
608# into balanced parallel branches, then concatenate in the original end order.
609def hw_locations(fuel: Nat, locations: List<&2, A.Location>,
610                   +reverse_target: String, +target_length: Nat,
611                   +profiles: List<&2, Peq>, +query_length: Nat,
612                   +maximum: Nat) -> List<&2, A.Location>:
613  match fuel locations:
614    case 0n _:
615      locations
616    case 1n+p Nil{}:
617      Nil{}
618    case 1n+p location <> Nil{}:
619      [hw_location(location, reverse_target, target_length, profiles, query_length, maximum)]
620    case Succ{+p} +values:
621      +half = Nat.div(List.length(&2, A.Location, values), 2n)
622      left right =
623        hw_locations(p, List.take(&2, A.Location, values, half),
624          reverse_target, target_length, profiles, query_length, maximum)
625        hw_locations(p, List.drop(&2, A.Location, values, half),
626          reverse_target, target_length, profiles, query_length, maximum)
627      List.append(&2, A.Location, left, right)