| 213 | |
| 214 | template <typename Handle> |
| 215 | Status DisjointSet<Handle>::Merge(Handle x, Handle y) { |
| 216 | Rep* x_root = Find(x); |
| 217 | Rep* y_root = Find(y); |
| 218 | |
| 219 | // x and y are already in the same set |
| 220 | if (x_root == y_root) { |
| 221 | return Status::OK(); |
| 222 | } |
| 223 | // x and y are not in same set, so we merge them |
| 224 | // Use the occasion to strengthen what we know about the handle by merging the |
| 225 | // information about the 2 subsets. |
| 226 | if (x_root->rank < y_root->rank) { |
| 227 | TF_RETURN_IF_ERROR(processor_.Merge(y, x, &y_root->value)); |
| 228 | x_root->parent = y_root; |
| 229 | } else if (x_root->rank > y_root->rank) { |
| 230 | TF_RETURN_IF_ERROR(processor_.Merge(x, y, &x_root->value)); |
| 231 | y_root->parent = x_root; |
| 232 | } else { |
| 233 | TF_RETURN_IF_ERROR(processor_.Merge(x, y, &x_root->value)); |
| 234 | // Arbitrarily make one root the new parent |
| 235 | y_root->parent = x_root; |
| 236 | x_root->rank = x_root->rank + 1; |
| 237 | } |
| 238 | return Status::OK(); |
| 239 | } |
| 240 | |
| 241 | template <typename Handle> |
| 242 | typename DisjointSet<Handle>::Rep* DisjointSet<Handle>::Find(Handle value) { |
no test coverage detected