bend-edit-distance Releases (4): 0.2.2.0 0xd65851cd1dee629f72e346cda168bc1d indexed https://jend.leeeet.dev/files.txt?path=bend-edit-distance@0.2.2.0 0.2.1.0 0x0c9b4ba6ffd5d745f166aece1048c08b unindexed https://jend.leeeet.dev/files.txt?path=bend-edit-distance@0.2.1.0 0.2.0.0 0x174bb51b869e4a6769b3eebe332457c5 unindexed https://jend.leeeet.dev/files.txt?path=bend-edit-distance@0.2.0.0 0.1.0.0 0x483ba00627509c62188f937a7cfd8f76 unindexed https://jend.leeeet.dev/files.txt?path=bend-edit-distance@0.1.0.0 Definitions (210, 1 to 100 shown): EdlibTypes.Mode (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=Mode) # Edlib sentinels are distinct constructors, never wrapped U32 values. type Mode is Data: NW{} SHW{} HW{} EdlibTypes.Task (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=Task) type Task is Data: Distance{} Locations{} Path{} EdlibTypes.Threshold (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=Threshold) type Threshold is Data: Unlimited{} MaxDistance{value: Nat} EdlibTypes.EqualityPair (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=EqualityPair) type EqualityPair is Data: EqualityPair{first: Char, second: Char} EdlibTypes.CigarFormat (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=CigarFormat) type CigarFormat is Data: Standard{} Extended{} EdlibTypes.AlignConfig (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=AlignConfig) type AlignConfig is Data: AlignConfig{mode: Mode, task: Task, threshold: Threshold, equalities: List<&2, EqualityPair>, cigar_format: CigarFormat} EdlibTypes.AlignJob (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=AlignJob) # Each independent batch job keeps its own configuration and orientation. type AlignJob is Data: AlignJob{query: String, target: String, config: AlignConfig} EdlibTypes.Status (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=Status) type Status is Data: Ok{} Error{} EdlibTypes.EditDistance (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=EditDistance) type EditDistance is Data: Found{value: Nat} NotFound{} EdlibTypes.Coordinate (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=Coordinate) type Coordinate is Data: BeforeStart{} Position{index: Nat} EdlibTypes.Operation (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=Operation) type Operation is Data: Match{} Insert{} Delete{} Mismatch{} EdlibTypes.CigarRun (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=CigarRun) # Encoded runs have positive counts and are merged after mapping to the selected # alphabet: adjacent Match/Mismatch operations form one Standard M run. type CigarRun is Data: CigarRun{count: Nat, symbol: Char} EdlibTypes.AlignResult (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=AlignResult) type AlignResult is Data: AlignResult{status: Status, distance: EditDistance, end_locations: List<&2, Coordinate>, start_locations: Maybe<&2, List<&2, Coordinate>>, alignment: Maybe<&2, List<&2, Operation>>, cigar: Maybe<&2, String>} EdlibTypes.default_config (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=default_config) def default_config() -> AlignConfig: EdlibTypes.pair_matches (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=pair_matches) # Literal equality plus explicitly configured symmetric pairs. Scanning the # pairs never follows a chain, so shared endpoints do not imply transitivity. def pair_matches(pair: EqualityPair, +a: Char, +b: Char) -> Bool: EdlibTypes.equal (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=equal) def equal(pairs: List<&2, EqualityPair>, +a: Char, +b: Char) -> Bool: EdlibTypes.end_coordinate (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=end_coordinate) def end_coordinate(length: Nat) -> Coordinate: EdlibTypes.distance_show (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=distance_show) def distance_show(distance: EditDistance) -> String: EdlibTypes.coordinate_show (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=coordinate_show) def coordinate_show(position: Coordinate) -> String: EdlibTypes.status_show (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=status_show) def status_show(status: Status) -> String: EdlibTypes.operation_show (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=operation_show) def operation_show(operation: Operation) -> String: EdlibTypes.operation_char (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=operation_char) def operation_char(format: CigarFormat, operation: Operation) -> Char: EdlibTypes.cigar_run_step (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=cigar_run_step) def cigar_run_step(runs: List<&2, CigarRun>, count: Nat, symbol: Char, next: Char, same: Bool) -> List<&2, CigarRun>: EdlibTypes.alignment_runs_reversed (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=alignment_runs_reversed) # The current run depends on the preceding symbol, so this scan is sequential. # Tail recursion keeps long homogeneous and alternating paths bounded in stack. def alignment_runs_reversed(operations: List<&2, Operation>, +format: CigarFormat, runs: List<&2, CigarRun>) -> List<&2, CigarRun>: EdlibTypes.alignment_runs (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=alignment_runs) def alignment_runs(operations: List<&2, Operation>, format: CigarFormat) -> List<&2, CigarRun>: EdlibTypes.cigar_runs_show (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=cigar_runs_show) def cigar_runs_show(runs: List<&2, CigarRun>) -> String: EdlibTypes.alignment_to_cigar (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=alignment_to_cigar) def alignment_to_cigar(operations: List<&2, Operation>, format: CigarFormat) -> String: EdlibTypes.coordinates_show (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=coordinates_show) def coordinates_show(locations: List<&2, Coordinate>) -> String: EdlibTypes.starts_show (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=starts_show) def starts_show(locations: Maybe<&2, List<&2, Coordinate>>) -> String: EdlibTypes.alignment_show (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=alignment_show) def alignment_show(alignment: Maybe<&2, List<&2, Operation>>) -> String: EdlibTypes.cigar_show (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=cigar_show) # CIGAR contains only decimal counts and MID=X, so needs no JSON escaping. def cigar_show(cigar: Maybe<&2, String>) -> String: EdlibTypes.result_show (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=result_show) def result_show(result: AlignResult) -> String: EdlibTypes.not_found (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=not_found) def not_found() -> AlignResult: EdlibTypes.within_threshold (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=within_threshold) def within_threshold(threshold: Threshold, distance: Nat) -> Bool: EdlibTypes.distance_result (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/EdlibTypes.bend&name=distance_result) def distance_result(distance: Nat, end: Coordinate, accepted: Bool) -> AlignResult: Lib.distance (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/lib.bend&name=distance) # Public CPU library entry point, independent of CLI and foreign transport. def distance(query: String, target: String) -> Nat: Lib.default_config (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/lib.bend&name=default_config) def default_config() -> Types.AlignConfig: Lib.align (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/lib.bend&name=align) def align(query: String, target: String, config: Types.AlignConfig) -> Types.AlignResult: Lib.align_batch (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/lib.bend&name=align_batch) # One result per job, in input order, with independent CPU alignment leaves. def align_batch(jobs: List<&2, Types.AlignJob>) -> List<&2, Types.AlignResult>: Lib.alignment_to_cigar (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/lib.bend&name=alignment_to_cigar) # Format any path, including an explicitly empty path, independently of align. def alignment_to_cigar(operations: List<&2, Types.Operation>, format: Types.CigarFormat) -> String: Alignment.Location (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Alignment.bend&name=Location) # Myers owns nonempty distance and location searches. This module builds # ordered results, preserves empty-input returns and validates reconstructed PATH. type Location is Data: Location{end: E.Coordinate, start: Nat} Alignment.Best (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Alignment.bend&name=Best) type Best is Data: Best{score: U32, locations: List<&2, Location>} Alignment.update_best (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Alignment.bend&name=update_best) def update_best(best: Best, score: U32, location: Location, comparison: Cmp) -> Best: Alignment.ordered (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Alignment.bend&name=ordered) def ordered(best: Best) -> Best: Alignment.ends (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Alignment.bend&name=ends) def ends(locations: List<&2, Location>) -> List<&2, E.Coordinate>: Alignment.starts (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Alignment.bend&name=starts) def starts(locations: List<&2, Location>) -> List<&2, E.Coordinate>: Alignment.span (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Alignment.bend&name=span) def span(target: String, location: Location) -> String: Alignment.path_result (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Alignment.bend&name=path_result) def path_result(score: U32, +locations: List<&2, Location>, +operations: List<&2, E.Operation>, format: E.CigarFormat) -> E.AlignResult: Alignment.location_valid (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Alignment.bend&name=location_valid) def location_valid(target: String, location: Location) -> Bool: Alignment.path_checked (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Alignment.bend&name=path_checked) def path_checked(score: U32, locations: List<&2, Location>, format: E.CigarFormat, operations: List<&2, E.Operation>, valid: Bool) -> E.AlignResult: Alignment.path_validate (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Alignment.bend&name=path_validate) def path_validate(query: String, segment: String, pairs: List<&2, E.EqualityPair>, +score: U32, locations: List<&2, Location>, format: E.CigarFormat, +operations: List<&2, E.Operation>, valid_location: Bool) -> E.AlignResult: Alignment.path_reconstruct (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Alignment.bend&name=path_reconstruct) def path_reconstruct(+query: String, +segment: String, +pairs: List<&2, E.EqualityPair>, score: U32, locations: List<&2, Location>, format: E.CigarFormat, valid_location: Bool) -> E.AlignResult: Alignment.result (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Alignment.bend&name=result) def result(query: String, target: String, task: E.Task, pairs: List<&2, E.EqualityPair>, format: E.CigarFormat, best: Best, accepted: Bool) -> E.AlignResult: Alignment.empty_result (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Alignment.bend&name=empty_result) # Pinned Edlib returns before applying k or calculating starts/path on empty # inputs, including PATH. Preserve that observable oracle behavior. def empty_result(query: String, target: String, config: E.AlignConfig) -> E.AlignResult: Batch.WeightedJob (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=WeightedJob) type WeightedJob is Data: WeightedJob{index: Nat, work: F32, job: E.AlignJob} Batch.Group (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=Group) type Group is Data: Group{room: Nat, work: F32, jobs: List<&2, WeightedJob>} Batch.Plan (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=Plan) # Build the entire plan before entering the alignment fork tree. Recursive # argument preparation in a parallel call can drain the native frontier. type Plan is Type: Empty{} Leaf{index: Nat, job: E.AlignJob} Fork{left: Plan, right: Plan} Serial{jobs: List<&2, WeightedJob>} Batch.IndexedResult (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=IndexedResult) type IndexedResult is Data: IndexedResult{index: Nat, result: E.AlignResult} Batch.axes (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=axes) def axes(mode: E.Mode, +qn: Nat, +tn: Nat) -> Nat & Nat: Batch.extra_work (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=extra_work) def extra_work(mode: E.Mode, task: E.Task, +q: F32, +t: F32, +blocks: F32, pairs: F32) -> F32: Batch.estimate_axes (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=estimate_axes) def estimate_axes(+mode: E.Mode, task: E.Task, pairs: List<&2, E.EqualityPair>, sizes: Nat & Nat) -> F32: Batch.estimate_sizes (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=estimate_sizes) # A scheduling heuristic, not a timing prediction: input scans, 256-symbol # profiles, full Myers columns, worst-case HW start searches and PATH DP. # F32 avoids wrapping a U32 product or allocating a quadratic unary Nat. # Bands, retries, similarity and the selected interval can change actual work. def estimate_sizes(qn: Nat, tn: Nat, config: E.AlignConfig) -> F32: Batch.estimate (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=estimate) def estimate(+job: E.AlignJob) -> F32: Batch.indexed (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=indexed) def indexed(jobs: List<&2, E.AlignJob>, +index: Nat) -> List<&2, WeightedJob>: Batch.heavier (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=heavier) def heavier(first: WeightedJob, second: WeightedJob) -> Bool: Batch.add (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=add) def add(group: Group, job: WeightedJob) -> Group: Batch.choose (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=choose) def choose(left: Group, right: Group) -> Bool: Batch.place (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=place) def place(job: WeightedJob, left: Group, right: Group, use_left: Bool) -> Group & Group: Batch.partition (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=partition) # Largest estimated jobs go to the lighter branch. Capacity bounds keep both # child counts within ceil(n/2), including zero/rounded/equal work estimates. def partition(jobs: List<&2, WeightedJob>, groups: Group & Group) -> Group & Group: Batch.group_jobs (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=group_jobs) def group_jobs(group: Group) -> List<&2, WeightedJob>: Batch.plan_step (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=plan_step) def plan_step(groups: Group & Group, next: List<&2, WeightedJob> -> List<&2, WeightedJob> -> Plan) -> Plan: Batch.plan (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=plan) def plan(fuel: Nat, jobs: List<&2, WeightedJob>) -> Plan: Batch.prepare (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=prepare) def prepare(+jobs: List<&2, E.AlignJob>) -> Plan: Batch.single (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=single) def single(index: Nat, job: E.AlignJob) -> IndexedResult: Batch.serial (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=serial) def serial(jobs: List<&2, WeightedJob>) -> List<&2, IndexedResult>: Batch.execute (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=execute) # Only ready, independent subplans enter parallel calls. A leaf uses the same # single-pair implementation; column carries and successive columns stay serial. def execute(plan: Plan) -> List<&2, IndexedResult>: Batch.earlier (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=earlier) def earlier(first: IndexedResult, second: IndexedResult) -> Bool: Batch.results (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=results) def results(values: List<&2, IndexedResult>) -> List<&2, E.AlignResult>: Batch.ordered (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=ordered) def ordered(values: List<&2, IndexedResult>) -> List<&2, E.AlignResult>: Batch.align_batch (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Batch.bend&name=align_batch) def align_batch(jobs: List<&2, E.AlignJob>) -> List<&2, E.AlignResult>: DistanceDP.initial_row (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=initial_row) def initial_row(length: Nat, +column: U32) -> List: DistanceDP.cell (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=cell) # D[i,j] = min(D[i-1,j] + 1, D[i,j-1] + 1, # D[i-1,j-1] + !equal(pairs, row_symbol, column_symbol)). def cell(above: U32, left: U32, diagonal: U32, row_symbol: Char, column_symbol: Char, pairs: List<&2, E.EqualityPair>) -> U32: DistanceDP.row_cells (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=row_cells) # Consume the old row as the new row is built. The left/diagonal dependency # makes adjacent cells sequential; copying a full matrix is unnecessary. def row_cells(columns: String, previous: List, diagonal: U32, left: U32, +symbol: Char, +pairs: List<&2, E.EqualityPair>) -> List: DistanceDP.next_row (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=next_row) def next_row(previous: List, columns: String, symbol: Char, +index: U32, pairs: List<&2, E.EqualityPair>) -> List: DistanceDP.last_cell (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=last_cell) def last_cell(row: List) -> Nat: DistanceDP.rows (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=rows) def rows(sequence: String, +columns: String, previous: List, +index: U32, +pairs: List<&2, E.EqualityPair>) -> Nat: DistanceDP.distance_shorter (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=distance_shorter) def distance_shorter(query: String, target: String, query_length: Nat, target_length: Nat, query_is_shorter: Bool, pairs: List<&2, E.EqualityPair>) -> Nat: DistanceDP.distance_with_equalities (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=distance_with_equalities) # Public entry point: importing this module does not import or call Myers. def distance_with_equalities(query: String, target: String, pairs: List<&2, E.EqualityPair>) -> Nat: DistanceDP.distance (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=distance) def distance(query: String, target: String) -> Nat: DistanceDP.initial_semiglobal_row (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=initial_semiglobal_row) # Directional DP keeps query rows and target columns in their original order. # D[i,0] = i in every mode. SHW has D[0,j] = j and a free target suffix; # HW has D[0,j] = 0 and both target ends free. Both minimize D[m,j]. def initial_semiglobal_row(length: Nat, +column: U32, +mode: E.Mode) -> List: DistanceDP.final_row (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=final_row) def final_row(query: String, +target: String, previous: List, +index: U32, +pairs: List<&2, E.EqualityPair>) -> List: DistanceDP.Best (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=Best) type Best is Data: Best{score: U32, ends: List<&2, E.Coordinate>} DistanceDP.collect_best (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=collect_best) def collect_best(best: Best, score: U32, end: E.Coordinate, comparison: Cmp) -> Best: DistanceDP.collect (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=collect) def collect(cells: List, +index: Nat, +best: Best) -> Best: DistanceDP.semiglobal_endpoints (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=semiglobal_endpoints) def semiglobal_endpoints(cells: List, include_before: Bool) -> Best: DistanceDP.semiglobal (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=semiglobal) def semiglobal(+query: String, +target: String, mode: E.Mode, pairs: List<&2, E.EqualityPair>) -> Best: DistanceDP.semiglobal_result.accept (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=semiglobal_result.accept) def semiglobal_result.accept(score: U32, ends: List<&2, E.Coordinate>, accepted: Bool) -> E.AlignResult: DistanceDP.semiglobal_result (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=semiglobal_result) def semiglobal_result(best: Best, +threshold: E.Threshold) -> E.AlignResult: DistanceDP.align (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/DistanceDP.bend&name=align) # The independent worker supports configured DISTANCE in every mode, including # Edlib's empty-input early return before threshold filtering. def align(query: String, target: String, config: E.AlignConfig) -> E.AlignResult: Myers.Peq (https://jend.leeeet.dev/definition.txt?path=bend-edit-distance@0.2.2.0/src/Myers.bend&name=Peq) type Peq is Data: Mask{bits: U32} Branch{low: Peq, high: Peq} More: https://jend.leeeet.dev/packages/bend-edit-distance.txt?definitions_offset=100