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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
/*
* dsf.c: some functions to handle a disjoint set forest,
* which is a data structure useful in any solver which has to
* worry about avoiding closed loops.
*/
#include <assert.h>
#include <string.h>
#include "puzzles.h"
/*void print_dsf(int *dsf, int size)
{
int *printed_elements = snewn(size, int);
int *equal_elements = snewn(size, int);
int *inverse_elements = snewn(size, int);
int printed_count = 0, equal_count, inverse_count;
int i, n;
bool inverse;
memset(printed_elements, -1, sizeof(int) * size);
while (1) {
equal_count = 0;
inverse_count = 0;
for (i = 0; i < size; ++i) {
if (!memchr(printed_elements, i, sizeof(int) * size))
break;
}
if (i == size)
goto done;
i = dsf_canonify(dsf, i);
for (n = 0; n < size; ++n) {
if (edsf_canonify(dsf, n, &inverse) == i) {
if (inverse)
inverse_elements[inverse_count++] = n;
else
equal_elements[equal_count++] = n;
}
}
for (n = 0; n < equal_count; ++n) {
fprintf(stderr, "%d ", equal_elements[n]);
printed_elements[printed_count++] = equal_elements[n];
}
if (inverse_count) {
fprintf(stderr, "!= ");
for (n = 0; n < inverse_count; ++n) {
fprintf(stderr, "%d ", inverse_elements[n]);
printed_elements[printed_count++] = inverse_elements[n];
}
}
fprintf(stderr, "\n");
}
done:
sfree(printed_elements);
sfree(equal_elements);
sfree(inverse_elements);
}*/
void dsf_init(int *dsf, int size)
{
int i;
for (i = 0; i < size; i++) dsf[i] = 6;
/* Bottom bit of each element of this array stores whether that
* element is opposite to its parent, which starts off as
* false. Second bit of each element stores whether that element
* is the root of its tree or not. If it's not the root, the
* remaining 30 bits are the parent, otherwise the remaining 30
* bits are the number of elements in the tree. */
}
int *snew_dsf(int size)
{
int *ret;
ret = snewn(size, int);
dsf_init(ret, size);
/*print_dsf(ret, size); */
return ret;
}
int dsf_canonify(int *dsf, int index)
{
return edsf_canonify(dsf, index, NULL);
}
void dsf_merge(int *dsf, int v1, int v2)
{
edsf_merge(dsf, v1, v2, false);
}
int dsf_size(int *dsf, int index) {
return dsf[dsf_canonify(dsf, index)] >> 2;
}
int edsf_canonify(int *dsf, int index, bool *inverse_return)
{
int start_index = index, canonical_index;
bool inverse = false;
/* fprintf(stderr, "dsf = %p\n", dsf); */
/* fprintf(stderr, "Canonify %2d\n", index); */
assert(index >= 0);
/* Find the index of the canonical element of the 'equivalence class' of
* which start_index is a member, and figure out whether start_index is the
* same as or inverse to that. */
while ((dsf[index] & 2) == 0) {
inverse ^= (dsf[index] & 1);
index = dsf[index] >> 2;
/* fprintf(stderr, "index = %2d, ", index); */
/* fprintf(stderr, "inverse = %d\n", inverse); */
}
canonical_index = index;
if (inverse_return)
*inverse_return = inverse;
/* Update every member of this 'equivalence class' to point directly at the
* canonical member. */
index = start_index;
while (index != canonical_index) {
int nextindex = dsf[index] >> 2;
bool nextinverse = inverse ^ (dsf[index] & 1);
dsf[index] = (canonical_index << 2) | inverse;
inverse = nextinverse;
index = nextindex;
}
assert(!inverse);
/* fprintf(stderr, "Return %2d\n", index); */
return index;
}
void edsf_merge(int *dsf, int v1, int v2, bool inverse)
{
bool i1, i2;
/* fprintf(stderr, "dsf = %p\n", dsf); */
/* fprintf(stderr, "Merge [%2d,%2d], %d\n", v1, v2, inverse); */
v1 = edsf_canonify(dsf, v1, &i1);
assert(dsf[v1] & 2);
inverse ^= i1;
v2 = edsf_canonify(dsf, v2, &i2);
assert(dsf[v2] & 2);
inverse ^= i2;
/* fprintf(stderr, "Doing [%2d,%2d], %d\n", v1, v2, inverse); */
if (v1 == v2)
assert(!inverse);
else {
/*
* We always make the smaller of v1 and v2 the new canonical
* element. This ensures that the canonical element of any
* class in this structure is always the first element in
* it. 'Keen' depends critically on this property.
*
* (Jonas Koelker previously had this code choosing which
* way round to connect the trees by examining the sizes of
* the classes being merged, so that the root of the
* larger-sized class became the new root. This gives better
* asymptotic performance, but I've changed it to do it this
* way because I like having a deterministic canonical
* element.)
*/
if (v1 > v2) {
int v3 = v1;
v1 = v2;
v2 = v3;
}
dsf[v1] += (dsf[v2] >> 2) << 2;
dsf[v2] = (v1 << 2) | inverse;
}
v2 = edsf_canonify(dsf, v2, &i2);
assert(v2 == v1);
assert(i2 == inverse);
/* fprintf(stderr, "dsf[%2d] = %2d\n", v2, dsf[v2]); */
}
|
