nx_sequence_edit_test.nx source
↩ module page · 93 lines · 3694 B
1// nx_sequence_edit_test.nx -- KAT for Levenshtein edit distance.
2//
3// All vectors hand-verifiable from the Wagner-Fischer recurrence
4// stated in nx_sequence_edit.nx. Includes the classic textbook
5// d("kitten","sitting")=3 vector.
6//
7// expect_exit: 0
8//
9// license_tier: ORIGINAL
10
11import "nx_syscalls.nx"
12import "nx_sequence_edit.nx"
13
14func write_str(buf: *u8, s0: i64, s1: i64, s2: i64, s3: i64,
15 s4: i64, s5: i64, s6: i64, s7: i64) -> i64 {
16 buf[0] = s0 & 0xff
17 buf[1] = s1 & 0xff
18 buf[2] = s2 & 0xff
19 buf[3] = s3 & 0xff
20 buf[4] = s4 & 0xff
21 buf[5] = s5 & 0xff
22 buf[6] = s6 & 0xff
23 buf[7] = s7 & 0xff
24 return 0
25}
26
27func main() -> i64 {
28
29 let a: *u8 = sys_mmap(16)
30 let b: *u8 = sys_mmap(16)
31
32 // -------- A: trivial boundaries --------
33 if edit_distance(a, 0, b, 0) != 0 { return 1 } // both empty
34 a[0] = 0x41 // 'A'
35 if edit_distance(a, 1, b, 0) != 1 { return 2 } // delete 1
36 if edit_distance(b, 0, a, 1) != 1 { return 3 } // insert 1
37
38 // -------- B: identical DNA quad --------
39 write_str(a, 0x41, 0x43, 0x47, 0x54, 0, 0, 0, 0) // "ACGT"
40 write_str(b, 0x41, 0x43, 0x47, 0x54, 0, 0, 0, 0) // "ACGT"
41 if edit_distance(a, 4, b, 4) != 0 { return 10 }
42
43 // -------- C: one substitution --------
44 write_str(b, 0x41, 0x43, 0x41, 0x54, 0, 0, 0, 0) // "ACAT"
45 if edit_distance(a, 4, b, 4) != 1 { return 11 } // G->A at pos 2
46
47 // -------- D: one insertion --------
48 write_str(b, 0x41, 0x43, 0x47, 0x54, 0x41, 0, 0, 0) // "ACGTA"
49 if edit_distance(a, 4, b, 5) != 1 { return 12 }
50 if edit_distance(b, 5, a, 4) != 1 { return 13 } // symmetric
51
52 // -------- E: one deletion (middle) --------
53 write_str(a, 0x41, 0x43, 0x47, 0x54, 0, 0, 0, 0) // "ACGT"
54 write_str(b, 0x41, 0x47, 0x54, 0, 0, 0, 0, 0) // "AGT"
55 if edit_distance(a, 4, b, 3) != 1 { return 14 } // delete C
56
57 // -------- F: all-different DNA quad --------
58 write_str(a, 0x41, 0x41, 0x41, 0x41, 0, 0, 0, 0) // "AAAA"
59 write_str(b, 0x54, 0x54, 0x54, 0x54, 0, 0, 0, 0) // "TTTT"
60 if edit_distance(a, 4, b, 4) != 4 { return 15 }
61
62 // -------- G: rotation by one --------
63 write_str(a, 0x41, 0x47, 0x43, 0x54, 0, 0, 0, 0) // "AGCT"
64 write_str(b, 0x47, 0x43, 0x54, 0x41, 0, 0, 0, 0) // "GCTA"
65 if edit_distance(a, 4, b, 4) != 2 { return 16 } // delete-front + insert-back
66
67 // -------- H: classic Wagner-Fischer "kitten" / "sitting" = 3 --------
68 let k: *u8 = sys_mmap(16)
69 let s: *u8 = sys_mmap(16)
70 k[0]=0x6B; k[1]=0x69; k[2]=0x74; k[3]=0x74; k[4]=0x65; k[5]=0x6E // kitten
71 s[0]=0x73; s[1]=0x69; s[2]=0x74; s[3]=0x74; s[4]=0x69; s[5]=0x6E; s[6]=0x67 // sitting
72 if edit_distance(k, 6, s, 7) != 3 { return 20 }
73
74 // -------- I: published "Saturday"/"Sunday" = 3 --------
75 let sat: *u8 = sys_mmap(16)
76 let sun: *u8 = sys_mmap(16)
77 sat[0]=0x53; sat[1]=0x61; sat[2]=0x74; sat[3]=0x75; sat[4]=0x72; sat[5]=0x64; sat[6]=0x61; sat[7]=0x79
78 sun[0]=0x53; sun[1]=0x75; sun[2]=0x6E; sun[3]=0x64; sun[4]=0x61; sun[5]=0x79
79 if edit_distance(sat, 8, sun, 6) != 3 { return 21 }
80
81 // -------- J: invalid negative length --------
82 if edit_distance(a, -1, b, 4) != -1 { return 30 }
83 if edit_distance(a, 4, b, -1) != -1 { return 31 }
84
85 // -------- K: symmetry on a real DNA pair --------
86 write_str(a, 0x41, 0x43, 0x47, 0x54, 0x41, 0x43, 0x47, 0x54) // ACGTACGT
87 write_str(b, 0x41, 0x43, 0x41, 0x54, 0x47, 0x43, 0x47, 0x54) // ACATGCGT
88 let d1: i64 = edit_distance(a, 8, b, 8)
89 let d2: i64 = edit_distance(b, 8, a, 8)
90 if d1 != d2 { return 40 }
91
92 return 0
93}