brep_kernel/geometry/
union_find.rs

1/// Deterministic union-find (smallest index wins as representative).
2pub struct UnionFind {
3    parent: Vec<usize>,
4}
5
6impl UnionFind {
7    pub fn new(n: usize) -> Self {
8        Self {
9            parent: (0..n).collect(),
10        }
11    }
12
13    pub fn find(&mut self, x: usize) -> usize {
14        let mut root = x;
15        while self.parent[root] != root {
16            root = self.parent[root];
17        }
18        let mut cur = x;
19        while self.parent[cur] != root {
20            let next = self.parent[cur];
21            self.parent[cur] = root;
22            cur = next;
23        }
24        root
25    }
26
27    pub fn union(&mut self, a: usize, b: usize) {
28        let (ra, rb) = (self.find(a), self.find(b));
29        if ra != rb {
30            let (lo, hi) = if ra < rb { (ra, rb) } else { (rb, ra) };
31            self.parent[hi] = lo;
32        }
33    }
34}
35
36/// Path-halving over an existing parent slice; preserves the caller's root policy.
37#[inline]
38pub fn find_root(parent: &mut [usize], mut index: usize) -> usize {
39    while parent[index] != index {
40        parent[index] = parent[parent[index]];
41        index = parent[index];
42    }
43    index
44}
45
46/// Full compression for sparse identifiers, preserving the caller's chosen representative.
47pub fn find_keyed_root<K, S>(parent: &mut std::collections::HashMap<K, K, S>, key: K) -> K
48where
49    K: Copy + Eq + std::hash::Hash,
50    S: std::hash::BuildHasher,
51{
52    let next = *parent.entry(key).or_insert(key);
53    if next == key { return key; }
54    let root = find_keyed_root(parent, next);
55    parent.insert(key, root);
56    root
57}
brep_kernel/geometry/union_find.rs

brep_kernel/geometry/
union_find.rs
