nphysics2d/utils/
union_find.rs

1//! The union find algorithm.
2
3/// An element used by the union-find algorithm.
4#[derive(Copy, Clone, Debug, Hash)]
5pub struct UnionFindSet {
6    /// The parent of this union find element.
7    parent: usize,
8    /// The rank of this union find element.
9    rank: usize,
10}
11
12impl UnionFindSet {
13    /// Creates a new `UnionFindSet`.
14    #[inline]
15    pub fn new(key: usize) -> UnionFindSet {
16        UnionFindSet {
17            parent: key,
18            rank: 0,
19        }
20    }
21
22    /// Reinitialize this set.
23    #[inline]
24    pub fn reinit(&mut self, key: usize) {
25        self.parent = key;
26        self.rank = 0;
27    }
28}
29
30/// Performs the `find` part of the union-find algorithm.
31pub fn find(x: usize, sets: &mut [UnionFindSet]) -> usize {
32    if sets[x].parent != x {
33        sets[x].parent = find(sets[x].parent, sets);
34    }
35
36    sets[x].parent
37}
38
39/// Performs the `union` part of the union-find algorithm.
40pub fn union(x: usize, y: usize, sets: &mut [UnionFindSet]) {
41    let x_root = find(x, sets);
42    let y_root = find(y, sets);
43
44    if x_root == y_root {
45        return;
46    }
47
48    let rankx = sets[x_root].rank;
49    let ranky = sets[y_root].rank;
50
51    if rankx < ranky {
52        sets[x_root].parent = y_root
53    } else if rankx > ranky {
54        sets[y_root].parent = x_root
55    } else {
56        sets[y_root].parent = x_root;
57        sets[x_root].rank = rankx + 1
58    }
59}
nphysics2d/utils/union_find.rs

nphysics2d/utils/
union_find.rs
