nx_sketch_union_find.nx source
↩ module page · 158 lines · 4907 B
1// sketch_union_find.nx -- Disjoint Set Union (Union-Find) primitive.
2//
3// Foundational data structure for connectivity / clustering. Maintains
4// a partition of {0, 1, ..., n-1} into disjoint sets. Operations:
5// find(x): which set is x in? (returns representative element)
6// union(x, y): merge x's set with y's set
7// connected(x, y): same set?
8// size_of(x): cardinality of x's set
9//
10// OPTIMIZATIONS:
11// - Path compression: find(x) flattens the parent chain so subsequent
12// finds are O(1) on the same nodes.
13// - Union by size: smaller tree attaches under larger; keeps tree
14// height O(log n).
15//
16// With both optimizations: nearly-O(1) amortized per operation
17// (technically O(α(n)) inverse-Ackermann; practically constant).
18//
19// USE CASES:
20// - Kruskal's MST (connectivity tracking)
21// - online clustering (merge clusters as new edges arrive)
22// - dynamic connectivity (undirected only)
23// - compilation: equivalence classes for SSA, alias analysis
24// - image processing: connected components
25//
26// LOSSLESS-LANGUAGE DISCIPLINE:
27// Production tier, exact semantics. No envelope returned --
28// operations are deterministic with O(α(n)) guarantee.
29
30// nx_safety_envelope:
31// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
32// sil_target: SIL1
33// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
34// verdict: NOT_YET_EVALUATED
35
36import "nx_syscalls.nx"
37import "nx_sketch_types.nx"
38
39const NX_UF_MIN_N: i64 = 1
40const NX_UF_MAX_N: i64 = 100000000 // 100M
41
42struct UnionFind {
43 parent: *i64, // parent[i] is the parent of i (-1 for root)
44 size: *i64, // size of set rooted at i (only valid at roots)
45 n: i64,
46 n_sets: i64, // count of distinct sets
47}
48
49// === construction =================================================
50//
51// Initially each element is in its own set: parent[i] = i, size[i] = 1.
52
53func nx_uf_alloc(n: i64) -> *UnionFind {
54 if n < NX_UF_MIN_N { return 0 as *UnionFind }
55 if n > NX_UF_MAX_N { return 0 as *UnionFind }
56 let raw: *u8 = sys_mmap(40)
57 let uf: *UnionFind = raw as *UnionFind
58 uf.parent = sys_mmap(n * 8) as *i64
59 uf.size = sys_mmap(n * 8) as *i64
60 var i: i64 = 0
61 while i < n {
62 uf.parent[i] = i
63 uf.size[i] = 1
64 i = i + 1
65 }
66 uf.n = n
67 uf.n_sets = n
68 return uf
69}
70
71// === find (with path compression) ================================
72//
73// Walk parent chain to root. On the way back down, re-point every
74// node to the root for amortized O(1) future finds.
75
76func nx_uf_find(uf: *UnionFind, x: i64) -> i64 {
77 if x < 0 { return -1 }
78 if x >= uf.n { return -1 }
79 // Find root.
80 var root: i64 = x
81 var done: i64 = 0
82 while done == 0 {
83 let p: i64 = uf.parent[root]
84 if p == root { done = 1 }
85 if done == 0 { root = p }
86 }
87 // Path compression: re-point intermediate nodes to root.
88 var cur: i64 = x
89 while cur != root {
90 let next: i64 = uf.parent[cur]
91 uf.parent[cur] = root
92 cur = next
93 }
94 return root
95}
96
97// === union (by size) =============================================
98//
99// Find roots of x and y; if different, attach smaller-size root under
100// larger. Update size of new root. Decrement n_sets.
101
102func nx_uf_union(uf: *UnionFind, x: i64, y: i64) -> i64 {
103 let rx: i64 = nx_uf_find(uf, x)
104 let ry: i64 = nx_uf_find(uf, y)
105 if rx < 0 { return -1 }
106 if ry < 0 { return -1 }
107 if rx == ry { return 0 } // already in same set; no-op
108 let sx: i64 = uf.size[rx]
109 let sy: i64 = uf.size[ry]
110 if sx < sy {
111 uf.parent[rx] = ry
112 uf.size[ry] = sx + sy
113 }
114 if sx >= sy {
115 uf.parent[ry] = rx
116 uf.size[rx] = sx + sy
117 }
118 uf.n_sets = uf.n_sets - 1
119 return 0
120}
121
122// === connected (predicate) =======================================
123
124func nx_uf_connected(uf: *UnionFind, x: i64, y: i64) -> i64 {
125 let rx: i64 = nx_uf_find(uf, x)
126 let ry: i64 = nx_uf_find(uf, y)
127 if rx < 0 { return 0 }
128 if ry < 0 { return 0 }
129 if rx == ry { return 1 }
130 return 0
131}
132
133// === size-of-set =================================================
134
135func nx_uf_size_of(uf: *UnionFind, x: i64) -> i64 {
136 let rx: i64 = nx_uf_find(uf, x)
137 if rx < 0 { return 0 }
138 return uf.size[rx]
139}
140
141func nx_uf_n_sets(uf: *UnionFind) -> i64 {
142 return uf.n_sets
143}
144
145// === query (typed envelope wrapper for "size of set containing x") =
146//
147// Exact semantics -- envelope is degenerate (zero error).
148
149func nx_uf_query_size(uf: *UnionFind, x: i64) -> *ApproxI64 {
150 let s: i64 = nx_uf_size_of(uf, x)
151 return nx_approx_new(s, NX_ENV_ABS, 0, 1000000000,
152 NX_MATURITY_PRODUCTION,
153 NX_ADV_HONEST)
154}
155
156func nx_uf_memory_bytes(uf: *UnionFind) -> i64 {
157 return 40 + uf.n * 16
158}