Skip to main content

deq_runtime/misc/
union_find.rs

1use serde::{Deserialize, Serialize};
2use std::iter::FromIterator;
3
4#[derive(Debug, Serialize, Deserialize, Clone)]
5pub struct UnionFindGeneric<NodeType: UnionNodeTrait> {
6    /// tree structure, each node has a parent
7    pub link_parent: Vec<usize>,
8    /// the node information, has the same length as `link_parent`
9    pub payload: Vec<NodeType>,
10    /// internal cache of parent list when calling `find`
11    find_parent_list: Vec<usize>,
12}
13
14pub trait UnionNodeTrait {
15    /// return `is_left`, `after_union`
16    fn union(left: &Self, right: &Self) -> (bool, Self);
17    /// clear the state, if [`UnionFindGeneric::clear`] is called then this must be provided
18    fn clear(&mut self) {
19        unimplemented!("[`UnionNodeTrait::clear`] must be implemented")
20    }
21    /// default structure
22    fn default() -> Self
23    where
24        Self: std::marker::Sized,
25    {
26        unimplemented!("[`UnionNodeTrait::default`] must be implemented")
27    }
28}
29
30pub type ExampleUnionFind = UnionFindGeneric<ExampleUnionNode>;
31
32/// define your own union-find node data structure like this
33#[derive(Debug, Serialize, Deserialize, Clone)]
34pub struct ExampleUnionNode {
35    pub set_size: usize,
36}
37
38/// example trait implementation
39impl UnionNodeTrait for ExampleUnionNode {
40    #[inline]
41    fn union(left: &Self, right: &Self) -> (bool, Self) {
42        let result = Self {
43            set_size: left.set_size + right.set_size,
44        };
45        // if left size is larger, choose left (weighted union)
46        (left.set_size >= right.set_size, result)
47    }
48    #[inline]
49    fn clear(&mut self) {
50        self.set_size = 1;
51    }
52    #[inline]
53    fn default() -> Self {
54        Self { set_size: 1 }
55    }
56}
57
58impl<NodeType: UnionNodeTrait> FromIterator<NodeType> for UnionFindGeneric<NodeType> {
59    #[inline]
60    fn from_iter<T: IntoIterator<Item = NodeType>>(iterator: T) -> Self {
61        let mut uf = Self {
62            link_parent: vec![],
63            payload: vec![],
64            find_parent_list: Vec::new(),
65        };
66        uf.extend(iterator);
67        uf
68    }
69}
70
71impl<NodeType: UnionNodeTrait> Extend<NodeType> for UnionFindGeneric<NodeType> {
72    #[inline]
73    fn extend<T: IntoIterator<Item = NodeType>>(&mut self, iterable: T) {
74        let len = self.payload.len();
75        let payload = iterable.into_iter();
76        self.payload.extend(payload);
77
78        let new_len = self.payload.len();
79        self.link_parent.extend(len..new_len);
80
81        self.find_parent_list.reserve(self.link_parent.len());
82    }
83}
84
85impl<NodeType: UnionNodeTrait> Default for UnionFindGeneric<NodeType> {
86    #[inline]
87    fn default() -> Self {
88        Self::new(0)
89    }
90}
91
92impl<NodeType: UnionNodeTrait> UnionFindGeneric<NodeType> {
93    #[inline]
94    #[allow(dead_code)]
95    pub fn new(len: usize) -> Self {
96        Self::from_iter((0..len).map(|_| NodeType::default()))
97    }
98
99    #[inline]
100    #[allow(dead_code)]
101    pub fn size(&self) -> usize {
102        self.payload.len()
103    }
104
105    #[inline]
106    #[allow(dead_code)]
107    pub fn insert(&mut self, data: NodeType) -> usize {
108        let key = self.payload.len();
109        self.link_parent.push(key);
110        self.payload.push(data);
111        key
112    }
113
114    #[inline]
115    pub fn union(&mut self, key0: usize, key1: usize) -> bool {
116        let k0 = self.find(key0);
117        let k1 = self.find(key1);
118        if k0 == k1 {
119            return false;
120        }
121
122        let (parent, child, val) = match NodeType::union(&self.payload[k0], &self.payload[k1]) {
123            (true, val) => (k0, k1, val),  // left
124            (false, val) => (k1, k0, val), // right
125        };
126        self.payload[parent] = val;
127        self.link_parent[child] = parent;
128
129        true
130    }
131
132    #[inline]
133    pub fn find(&mut self, key: usize) -> usize {
134        let mut k = key;
135        let mut p = self.link_parent[k];
136        while p != k {
137            self.find_parent_list.push(k);
138            k = p;
139            p = self.link_parent[p];
140        }
141        let root = k;
142        for k in self.find_parent_list.iter() {
143            self.link_parent[*k] = root; // path compression
144        }
145        self.find_parent_list.clear();
146        root
147    }
148
149    #[inline]
150    pub fn immutable_find(&self, key: usize) -> usize {
151        let mut k = key;
152        let mut p = self.link_parent[k];
153        while p != k {
154            k = p;
155            p = self.link_parent[p];
156        }
157        k
158    }
159
160    #[inline]
161    pub fn get(&mut self, key: usize) -> &NodeType {
162        let root_key = self.find(key);
163        &self.payload[root_key]
164    }
165
166    #[inline]
167    pub fn immutable_get(&self, key: usize) -> &NodeType {
168        let root_key = self.immutable_find(key);
169        &self.payload[root_key]
170    }
171
172    #[inline]
173    pub fn get_mut(&mut self, key: usize) -> &mut NodeType {
174        let root_key = self.find(key);
175        &mut self.payload[root_key]
176    }
177
178    pub fn clear(&mut self) {
179        debug_assert!(self.payload.len() == self.link_parent.len());
180        for i in 0..self.link_parent.len() {
181            self.link_parent[i] = i;
182            let node = &mut self.payload[i];
183            node.clear();
184        }
185    }
186
187    pub fn remove_all(&mut self) {
188        self.payload.clear();
189        self.link_parent.clear();
190    }
191}
192
193#[cfg(test)]
194mod tests {
195    use super::*;
196
197    #[test]
198    fn union_find_algorithm_test_1() {
199        // cargo test union_find_algorithm_test_1 -- --nocapture
200        let mut uf = ExampleUnionFind::new(100);
201        // test from https://github.com/gifnksm/union-find-rs/blob/master/src/tests.rs
202        assert_eq!(1, uf.get(0).set_size);
203        assert_eq!(1, uf.get(1).set_size);
204        assert!(uf.find(0) != uf.find(1));
205        assert!(uf.immutable_find(0) != uf.immutable_find(1));
206        assert!(uf.find(1) != uf.find(2));
207        assert!(uf.immutable_find(1) != uf.immutable_find(2));
208        assert!(uf.union(0, 1));
209        assert!(uf.find(0) == uf.find(1));
210        assert!(uf.immutable_find(0) == uf.immutable_find(1));
211        assert_eq!(2, uf.get(0).set_size);
212        assert_eq!(2, uf.get(1).set_size);
213        assert_eq!(1, uf.get(2).set_size);
214        assert!(!uf.union(0, 1));
215        assert_eq!(2, uf.get(0).set_size);
216        assert_eq!(2, uf.get(1).set_size);
217        assert_eq!(1, uf.get(2).set_size);
218        assert!(uf.union(1, 2));
219        assert_eq!(3, uf.get(0).set_size);
220        assert_eq!(3, uf.get(1).set_size);
221        assert_eq!(3, uf.get(2).set_size);
222        assert!(uf.immutable_find(0) == uf.immutable_find(1));
223        assert!(uf.find(0) == uf.find(1));
224        assert!(uf.immutable_find(2) == uf.immutable_find(1));
225        assert!(uf.find(2) == uf.find(1));
226        let k100 = uf.insert(ExampleUnionNode::default());
227        assert_eq!(k100, 100);
228        let _ = uf.union(k100, 0);
229        assert_eq!(4, uf.get(100).set_size);
230        assert_eq!(101, uf.size());
231        uf.clear();
232    }
233}