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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
// Begin License:
// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
// All rights reserved.
//
// This file is part of the Carve CSG Library (http://carve-csg.com/)
//
// This file may be used under the terms of either the GNU General
// Public License version 2 or 3 (at your option) as published by the
// Free Software Foundation and appearing in the files LICENSE.GPL2
// and LICENSE.GPL3 included in the packaging of this file.
//
// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE.
// End:
#pragma once
#include <carve/carve.hpp>
#include <vector>
namespace carve {
namespace djset {
class djset {
protected:
struct elem {
size_t parent, rank;
elem(size_t p, size_t r) : parent(p), rank(r) {}
elem() {}
};
std::vector<elem> set;
size_t n_sets;
public:
djset() : set(), n_sets(0) {
}
djset(size_t N) {
n_sets = N;
set.reserve(N);
for (size_t i = 0; i < N; ++i) {
set.push_back(elem(i,0));
}
}
void init(size_t N) {
if (N == set.size()) {
for (size_t i = 0; i < N; ++i) {
set[i] = elem(i,0);
}
n_sets = N;
} else {
djset temp(N);
std::swap(set, temp.set);
std::swap(n_sets, temp.n_sets);
}
}
size_t count() const {
return n_sets;
}
size_t find_set_head(size_t a) {
if (a == set[a].parent) return a;
size_t a_head = a;
while (set[a_head].parent != a_head) a_head = set[a_head].parent;
set[a].parent = a_head;
return a_head;
}
bool same_set(size_t a, size_t b) {
return find_set_head(a) == find_set_head(b);
}
void merge_sets(size_t a, size_t b) {
a = find_set_head(a);
b = find_set_head(b);
if (a != b) {
n_sets--;
if (set[a].rank < set[b].rank) {
set[a].parent = b;
} else if (set[b].rank < set[a].rank) {
set[b].parent = a;
} else {
set[a].rank++;
set[b].parent = a;
}
}
}
void get_index_to_set(std::vector<size_t> &index_set, std::vector<size_t> &set_size) {
index_set.clear();
index_set.resize(set.size(), n_sets);
set_size.clear();
set_size.resize(n_sets, 0);
size_t c = 0;
for (size_t i = 0; i < set.size(); ++i) {
size_t s = find_set_head(i);
if (index_set[s] == n_sets) index_set[s] = c++;
index_set[i] = index_set[s];
set_size[index_set[s]]++;
}
}
template<typename in_iter_t, typename out_collection_t>
void collate(in_iter_t in, out_collection_t &out) {
std::vector<size_t> set_id(set.size(), n_sets);
out.clear();
out.resize(n_sets);
size_t c = 0;
for (size_t i = 0; i < set.size(); ++i) {
size_t s = find_set_head(i);
if (set_id[s] == n_sets) set_id[s] = c++;
s = set_id[s];
std::insert_iterator<typename out_collection_t::value_type> j(out[s], out[s].end());
*j = *in++;
}
}
};
}
}
|
