sketch_union_find_test.nx source
↩ module page · 134 lines · 4234 B
1// sketch_union_find_test.nx -- Disjoint Set Union verification.
2
3import "syscalls.nx"
4import "sketch_union_find.nx"
5import "sketch_types.nx"
6
7func main() -> i64 {
8 // ---- alloc ----
9 let uf: *UnionFind = nx_uf_alloc(10)
10 if uf == (0 as *UnionFind) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
11 if nx_uf_n_sets(uf) != 10 { return __syscall(93, 6, 0, 0, 0, 0, 0) }
12 // Reject n < 1.
13 if nx_uf_alloc(0) != (0 as *UnionFind) {
14 return __syscall(93, 7, 0, 0, 0, 0, 0)
15 }
16
17 // ---- initial state: every element in own set ----
18 if nx_uf_find(uf, 5) != 5 {
19 return __syscall(93, 10, 0, 0, 0, 0, 0)
20 }
21 if nx_uf_size_of(uf, 3) != 1 {
22 return __syscall(93, 11, 0, 0, 0, 0, 0)
23 }
24 if nx_uf_connected(uf, 1, 2) != 0 {
25 return __syscall(93, 12, 0, 0, 0, 0, 0)
26 }
27
28 // ---- union: 0-1 merged ----
29 nx_uf_union(uf, 0, 1)
30 if nx_uf_connected(uf, 0, 1) != 1 {
31 return __syscall(93, 20, 0, 0, 0, 0, 0)
32 }
33 if nx_uf_n_sets(uf) != 9 {
34 return __syscall(93, 21, 0, 0, 0, 0, 0)
35 }
36 if nx_uf_size_of(uf, 0) != 2 {
37 return __syscall(93, 22, 0, 0, 0, 0, 0)
38 }
39
40 // ---- chain of unions: 0-1-2-3 form one set ----
41 nx_uf_union(uf, 1, 2)
42 nx_uf_union(uf, 2, 3)
43 if nx_uf_connected(uf, 0, 3) != 1 {
44 return __syscall(93, 30, 0, 0, 0, 0, 0)
45 }
46 if nx_uf_size_of(uf, 1) != 4 {
47 return __syscall(93, 31, 0, 0, 0, 0, 0)
48 }
49 if nx_uf_n_sets(uf) != 7 { // n=10, 3 unions -> 7 sets
50 return __syscall(93, 32, 0, 0, 0, 0, 0)
51 }
52 // Items 4..9 still singletons.
53 if nx_uf_size_of(uf, 5) != 1 {
54 return __syscall(93, 33, 0, 0, 0, 0, 0)
55 }
56 if nx_uf_connected(uf, 0, 5) != 0 {
57 return __syscall(93, 34, 0, 0, 0, 0, 0)
58 }
59
60 // ---- redundant union is no-op ----
61 nx_uf_union(uf, 0, 3) // already connected
62 if nx_uf_n_sets(uf) != 7 {
63 return __syscall(93, 40, 0, 0, 0, 0, 0)
64 }
65
66 // ---- second cluster: {4, 5}; bridge to {0..3} ----
67 nx_uf_union(uf, 4, 5)
68 if nx_uf_size_of(uf, 4) != 2 {
69 return __syscall(93, 50, 0, 0, 0, 0, 0)
70 }
71 if nx_uf_connected(uf, 4, 0) != 0 {
72 return __syscall(93, 51, 0, 0, 0, 0, 0)
73 }
74 // Bridge: union the two clusters.
75 nx_uf_union(uf, 3, 4)
76 if nx_uf_connected(uf, 0, 5) != 1 {
77 return __syscall(93, 52, 0, 0, 0, 0, 0)
78 }
79 if nx_uf_size_of(uf, 0) != 6 { // {0,1,2,3,4,5}
80 return __syscall(93, 53, 0, 0, 0, 0, 0)
81 }
82
83 // ---- out-of-range queries ----
84 if nx_uf_find(uf, -1) != -1 {
85 return __syscall(93, 60, 0, 0, 0, 0, 0)
86 }
87 if nx_uf_find(uf, 999) != -1 {
88 return __syscall(93, 61, 0, 0, 0, 0, 0)
89 }
90 if nx_uf_connected(uf, -1, 5) != 0 {
91 return __syscall(93, 62, 0, 0, 0, 0, 0)
92 }
93
94 // ---- path compression: deep chain becomes flat after find ----
95 let uf2: *UnionFind = nx_uf_alloc(1000)
96 var i: i64 = 1
97 while i < 1000 {
98 nx_uf_union(uf2, i - 1, i)
99 i = i + 1
100 }
101 // After 999 unions, all 1000 elements in one set.
102 if nx_uf_n_sets(uf2) != 1 {
103 return __syscall(93, 70, 0, 0, 0, 0, 0)
104 }
105 if nx_uf_size_of(uf2, 500) != 1000 {
106 return __syscall(93, 71, 0, 0, 0, 0, 0)
107 }
108 // Find on a far-away node should still be fast (path compression).
109 if nx_uf_find(uf2, 999) != nx_uf_find(uf2, 0) {
110 return __syscall(93, 72, 0, 0, 0, 0, 0)
111 }
112 // After find(999), parent[999] should point directly to root.
113 let root: i64 = nx_uf_find(uf2, 999)
114 if uf2.parent[999] != root {
115 return __syscall(93, 73, 0, 0, 0, 0, 0)
116 }
117
118 // ---- typed envelope ----
119 let q: *ApproxI64 = nx_uf_query_size(uf2, 500)
120 if q.envelope_kind != NX_ENV_ABS {
121 return __syscall(93, 80, 0, 0, 0, 0, 0)
122 }
123 if q.param_a != 0 { // exact
124 return __syscall(93, 81, 0, 0, 0, 0, 0)
125 }
126 if q.value != 1000 {
127 return __syscall(93, 82, 0, 0, 0, 0, 0)
128 }
129 if q.maturity != NX_MATURITY_PRODUCTION {
130 return __syscall(93, 83, 0, 0, 0, 0, 0)
131 }
132
133 return 0
134}