nx_seed_sort.nx source
↩ module page · 91 lines · 3662 B
1// nx_seed_sort.nx -- in-place sort of seed-pair arrays by (r, q).
2//
3// license_tier: INDEPENDENT_REDERIVE
4// genealogy_id: international-research-sources/knuth-volume-3-insertion-sort
5//
6// G1.2b of NISHI_GENOMICS_SUBSTRATE_ROADMAP.md. Closes the
7// composability gap between nx_align_match (G1.2) and nx_align_chain
8// (G1.3): match outputs seed pairs in (outer-q, inner-r) order;
9// chain DP requires pre-sorted-by-r input. This primitive bridges
10// them so the seed-and-extend pipeline composes without test-time
11// hand-sorting.
12//
13// Algorithm: classic insertion sort over paired (q, r) arrays, kept
14// in lock-step. Sort key is (r_pos, q_pos) ascending lexicographic
15// -- r is the primary axis (chain DP precondition) and q breaks ties
16// deterministically so the leftmost-tie chain rule remains stable.
17//
18// Why insertion sort: O(n^2) reference impl is fine for short-read
19// seed counts (n ~ 50-500); long-read or chromosome-scale needs a
20// non-comparison sort (G1.5 nx_seed_sort_radix, 8-bit r-byte buckets).
21//
22// API:
23// sort_seeds_by_r(seeds_q, seeds_r, n) -> i64 always 0; in-place
24//
25// nx_safety_envelope: (schema: nishi-library/seeds/safety-critical-standards.toml)
26// intended_use: "Seed-pair sort bridging match -> chain;
27// substrate primitive that removes the
28// 'caller pre-sort' precondition from the
29// chain DP"
30// sil_target: SIL2
31// asil_target: QM
32// dal_target: DAL C
33// iec_62304_class: B
34// evidence: [no_floating_point, deterministic,
35// bit_equal_reproducible,
36// insertion_sort_textbook,
37// lex_tiebreak_stable,
38// end_to_end_KAT_matcher_output_validates,
39// license_tier_INDEPENDENT_REDERIVE]
40// hazard_register: [bug-tape-paired-array-desync-on-swap,
41// bug-tape-sort-instability-breaks-chain-tiebreak,
42// bug-tape-sort-bad-bounds-buffer-overrun]
43// residual_risk: "O(n^2) on adversarial reverse input; fine
44// for short-read scale. Caller responsible
45// for matching seeds_q[i] / seeds_r[i]
46// semantics (same seed pair); function only
47// moves indices in lock-step."
48// verdict: NOT_YET_EVALUATED
49
50import "nx_syscalls.nx"
51
52// In-place insertion sort of paired (q, r) arrays by (r, q) lex.
53func sort_seeds_by_r(seeds_q: *i64, seeds_r: *i64, n: i64) -> i64 {
54 if n <= 1 { return 0 }
55
56 var i: i64 = 1
57 while i < n {
58 let key_q: i64 = seeds_q[i]
59 let key_r: i64 = seeds_r[i]
60 var j: i64 = i - 1
61 var keep_going: i64 = 1
62 while keep_going == 1 {
63 if j < 0 {
64 keep_going = 0
65 } else {
66 // shift if seeds[j] > key in (r, q) lex order
67 let rj: i64 = seeds_r[j]
68 let qj: i64 = seeds_q[j]
69 var greater: i64 = 0
70 if rj > key_r {
71 greater = 1
72 } else {
73 if rj == key_r {
74 if qj > key_q { greater = 1 }
75 }
76 }
77 if greater == 1 {
78 seeds_q[j + 1] = qj
79 seeds_r[j + 1] = rj
80 j = j - 1
81 } else {
82 keep_going = 0
83 }
84 }
85 }
86 seeds_q[j + 1] = key_q
87 seeds_r[j + 1] = key_r
88 i = i + 1
89 }
90 return 0
91}