def build_peq_table

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

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

48# A byte-indexed immutable table replaces the C++ transformed alphabet.
49# Low bits select branches, so lookup takes eight steps for every byte.
50# Both halves of the table have equal, independent work and run in parallel.
51def build_peq_table(+depth: Nat, +query: String, +symbol: U32, +step: U32,
52                    +pairs: List<&2, E.EqualityPair>) -> Peq:
53  match depth:
54    case 0n:
55      Mask{build_peq_word(query, Chr{symbol}, 1, pairs)}
56    case 1n+p:
57      low high = build_peq_table(p, query, symbol, U32.shl(step), pairs) build_peq_table(p, query, U32.add(symbol, step), U32.shl(step), pairs)
58      Branch{low, high}