deq_runtime/misc/
union_find.rs1use serde::{Deserialize, Serialize};
2use std::iter::FromIterator;
3
4#[derive(Debug, Serialize, Deserialize, Clone)]
5pub struct UnionFindGeneric<NodeType: UnionNodeTrait> {
6 pub link_parent: Vec<usize>,
8 pub payload: Vec<NodeType>,
10 find_parent_list: Vec<usize>,
12}
13
14pub trait UnionNodeTrait {
15 fn union(left: &Self, right: &Self) -> (bool, Self);
17 fn clear(&mut self) {
19 unimplemented!("[`UnionNodeTrait::clear`] must be implemented")
20 }
21 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#[derive(Debug, Serialize, Deserialize, Clone)]
34pub struct ExampleUnionNode {
35 pub set_size: usize,
36}
37
38impl 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 (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), (false, val) => (k1, k0, val), };
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; }
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 let mut uf = ExampleUnionFind::new(100);
201 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}