blob: 25cf22b79e02046661918e8dba75061c65bc6092 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
// Copyright 2006 Google Inc.
// All Rights Reserved.
// Author: <renn@google.com> (Marius Renn)
// Local includes
#include "debugging.h"
#include "unionfind.h"
using namespace helium;
Unions::Unions()
: parents_(16), max_root_(0) {
}
void Unions::Unify(uint32 a, uint32 b) {
ASSERT((a != 0) && (b != 0)); // zero is reserved for no-value
if (a == b) return;
unsigned steps1, steps2;
uint32 r1 = FindParentOrAdd(a, steps1);
uint32 r2 = FindParentOrAdd(b, steps2);
if (r1 == r2) return; // Already in the same class
if(steps1 < steps2)
parents_.ValueAt(r1).parent = r2;
else
parents_.ValueAt(r2).parent = r1;
}
uint16 Unions::Find(uint32 value) {
if (value == 0) return 0;
if (value >= parents_.size()) {
int max_id = max_root_;
parents_.Resize(value + 1);
parents_.ValueAt(value).value = max_id;
max_root_++;
return max_id;
}
uint32 next_index, cur_index = value;
while ((next_index = parents_.ValueAt(cur_index).parent) != 0)
cur_index = next_index;
return parents_.ValueAt(cur_index).value;
}
uint32 Unions::FindParentOrAdd(uint32 value, unsigned& steps) {
// Special case: Value not in tree yet
if (value >= parents_.size()) {
parents_.Resize(value + 1);
steps = 0;
return value;
}
uint32 next_node;
for (steps = 0; (next_node = parents_.ValueAt(value).parent) != 0; steps++)
value = next_node;
return value;
}
void Unions::LabelRoots() {
max_root_ = 0;
for (unsigned r = 0; r < parents_.size(); r++) {
if (!parents_.ValueAt(r).parent) parents_.ValueAt(r).value = max_root_++;
}
}
|
