def traceback

bend-edit-distance@0.2.2.0 · src/Reconstruction.bend:79

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

79# Rows and their operations are reversed so left moves consume the current
80# row directly. Entering the row above skips only its unused right suffix.
81# Including boundary rows/columns handles all-insertion/deletion paths.
82def traceback(fuel: Nat, current: List<&2, TraceCell>,
83               previous: List<&2, List<&2, TraceCell>>, +width: Nat,
84               +column: Nat, operations: List<&2, E.Operation>) -> List<&2, E.Operation>:
85  match fuel current previous:
86    case 0n _ _:
87      operations
88    case 1n+p _ Nil{}:
89      List.append(&2, E.Operation, List.replicate(E.Operation, column, E.Delete{}), operations)
90    case 1n+p Nil{} _:
91      operations
92    case 1n+p TraceCell{_, E.Insert{}} <> _ row <> rest:
93      traceback(p, List.drop(&2, TraceCell, row, Nat.sub(width, column)),
94        rest, width, column, E.Insert{} <> operations)
95    case 1n+p TraceCell{_, E.Delete{}} <> tail +rows:
96      traceback(p, tail, rows, width, Nat.sub(column, 1n), E.Delete{} <> operations)
97    case 1n+p TraceCell{_, operation} <> _ row <> rest:
98      +next_column = Nat.sub(column, 1n)
99      traceback(p, List.drop(&2, TraceCell, row, Nat.sub(width, next_column)),
100        rest, width, next_column, operation <> operations)