diff options
Diffstat (limited to 'apps/plugins/puzzles/dsf.c')
-rw-r--r-- | apps/plugins/puzzles/dsf.c | 192 |
1 files changed, 192 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/dsf.c b/apps/plugins/puzzles/dsf.c new file mode 100644 index 0000000000..1a2fa8c4be --- /dev/null +++ b/apps/plugins/puzzles/dsf.c | |||
@@ -0,0 +1,192 @@ | |||
1 | /* | ||
2 | * dsf.c: some functions to handle a disjoint set forest, | ||
3 | * which is a data structure useful in any solver which has to | ||
4 | * worry about avoiding closed loops. | ||
5 | */ | ||
6 | |||
7 | #include "rbassert.h" | ||
8 | #include <string.h> | ||
9 | |||
10 | #include "puzzles.h" | ||
11 | |||
12 | /*void print_dsf(int *dsf, int size) | ||
13 | { | ||
14 | int *printed_elements = snewn(size, int); | ||
15 | int *equal_elements = snewn(size, int); | ||
16 | int *inverse_elements = snewn(size, int); | ||
17 | int printed_count = 0, equal_count, inverse_count; | ||
18 | int i, n, inverse; | ||
19 | |||
20 | memset(printed_elements, -1, sizeof(int) * size); | ||
21 | |||
22 | while (1) { | ||
23 | equal_count = 0; | ||
24 | inverse_count = 0; | ||
25 | for (i = 0; i < size; ++i) { | ||
26 | if (!memchr(printed_elements, i, sizeof(int) * size)) | ||
27 | break; | ||
28 | } | ||
29 | if (i == size) | ||
30 | goto done; | ||
31 | |||
32 | i = dsf_canonify(dsf, i); | ||
33 | |||
34 | for (n = 0; n < size; ++n) { | ||
35 | if (edsf_canonify(dsf, n, &inverse) == i) { | ||
36 | if (inverse) | ||
37 | inverse_elements[inverse_count++] = n; | ||
38 | else | ||
39 | equal_elements[equal_count++] = n; | ||
40 | } | ||
41 | } | ||
42 | |||
43 | for (n = 0; n < equal_count; ++n) { | ||
44 | fprintf(stderr, "%d ", equal_elements[n]); | ||
45 | printed_elements[printed_count++] = equal_elements[n]; | ||
46 | } | ||
47 | if (inverse_count) { | ||
48 | fprintf(stderr, "!= "); | ||
49 | for (n = 0; n < inverse_count; ++n) { | ||
50 | fprintf(stderr, "%d ", inverse_elements[n]); | ||
51 | printed_elements[printed_count++] = inverse_elements[n]; | ||
52 | } | ||
53 | } | ||
54 | fprintf(stderr, "\n"); | ||
55 | } | ||
56 | done: | ||
57 | |||
58 | sfree(printed_elements); | ||
59 | sfree(equal_elements); | ||
60 | sfree(inverse_elements); | ||
61 | }*/ | ||
62 | |||
63 | void dsf_init(int *dsf, int size) | ||
64 | { | ||
65 | int i; | ||
66 | |||
67 | for (i = 0; i < size; i++) dsf[i] = 6; | ||
68 | /* Bottom bit of each element of this array stores whether that | ||
69 | * element is opposite to its parent, which starts off as | ||
70 | * false. Second bit of each element stores whether that element | ||
71 | * is the root of its tree or not. If it's not the root, the | ||
72 | * remaining 30 bits are the parent, otherwise the remaining 30 | ||
73 | * bits are the number of elements in the tree. */ | ||
74 | } | ||
75 | |||
76 | int *snew_dsf(int size) | ||
77 | { | ||
78 | int *ret; | ||
79 | |||
80 | ret = snewn(size, int); | ||
81 | dsf_init(ret, size); | ||
82 | |||
83 | /*print_dsf(ret, size); */ | ||
84 | |||
85 | return ret; | ||
86 | } | ||
87 | |||
88 | int dsf_canonify(int *dsf, int index) | ||
89 | { | ||
90 | return edsf_canonify(dsf, index, NULL); | ||
91 | } | ||
92 | |||
93 | void dsf_merge(int *dsf, int v1, int v2) | ||
94 | { | ||
95 | edsf_merge(dsf, v1, v2, FALSE); | ||
96 | } | ||
97 | |||
98 | int dsf_size(int *dsf, int index) { | ||
99 | return dsf[dsf_canonify(dsf, index)] >> 2; | ||
100 | } | ||
101 | |||
102 | int edsf_canonify(int *dsf, int index, int *inverse_return) | ||
103 | { | ||
104 | int start_index = index, canonical_index; | ||
105 | int inverse = 0; | ||
106 | |||
107 | /* fprintf(stderr, "dsf = %p\n", dsf); */ | ||
108 | /* fprintf(stderr, "Canonify %2d\n", index); */ | ||
109 | |||
110 | assert(index >= 0); | ||
111 | |||
112 | /* Find the index of the canonical element of the 'equivalence class' of | ||
113 | * which start_index is a member, and figure out whether start_index is the | ||
114 | * same as or inverse to that. */ | ||
115 | while ((dsf[index] & 2) == 0) { | ||
116 | inverse ^= (dsf[index] & 1); | ||
117 | index = dsf[index] >> 2; | ||
118 | /* fprintf(stderr, "index = %2d, ", index); */ | ||
119 | /* fprintf(stderr, "inverse = %d\n", inverse); */ | ||
120 | } | ||
121 | canonical_index = index; | ||
122 | |||
123 | if (inverse_return) | ||
124 | *inverse_return = inverse; | ||
125 | |||
126 | /* Update every member of this 'equivalence class' to point directly at the | ||
127 | * canonical member. */ | ||
128 | index = start_index; | ||
129 | while (index != canonical_index) { | ||
130 | int nextindex = dsf[index] >> 2; | ||
131 | int nextinverse = inverse ^ (dsf[index] & 1); | ||
132 | dsf[index] = (canonical_index << 2) | inverse; | ||
133 | inverse = nextinverse; | ||
134 | index = nextindex; | ||
135 | } | ||
136 | |||
137 | assert(inverse == 0); | ||
138 | |||
139 | /* fprintf(stderr, "Return %2d\n", index); */ | ||
140 | |||
141 | return index; | ||
142 | } | ||
143 | |||
144 | void edsf_merge(int *dsf, int v1, int v2, int inverse) | ||
145 | { | ||
146 | int i1, i2; | ||
147 | |||
148 | /* fprintf(stderr, "dsf = %p\n", dsf); */ | ||
149 | /* fprintf(stderr, "Merge [%2d,%2d], %d\n", v1, v2, inverse); */ | ||
150 | |||
151 | v1 = edsf_canonify(dsf, v1, &i1); | ||
152 | assert(dsf[v1] & 2); | ||
153 | inverse ^= i1; | ||
154 | v2 = edsf_canonify(dsf, v2, &i2); | ||
155 | assert(dsf[v2] & 2); | ||
156 | inverse ^= i2; | ||
157 | |||
158 | /* fprintf(stderr, "Doing [%2d,%2d], %d\n", v1, v2, inverse); */ | ||
159 | |||
160 | if (v1 == v2) | ||
161 | assert(!inverse); | ||
162 | else { | ||
163 | assert(inverse == 0 || inverse == 1); | ||
164 | /* | ||
165 | * We always make the smaller of v1 and v2 the new canonical | ||
166 | * element. This ensures that the canonical element of any | ||
167 | * class in this structure is always the first element in | ||
168 | * it. 'Keen' depends critically on this property. | ||
169 | * | ||
170 | * (Jonas Koelker previously had this code choosing which | ||
171 | * way round to connect the trees by examining the sizes of | ||
172 | * the classes being merged, so that the root of the | ||
173 | * larger-sized class became the new root. This gives better | ||
174 | * asymptotic performance, but I've changed it to do it this | ||
175 | * way because I like having a deterministic canonical | ||
176 | * element.) | ||
177 | */ | ||
178 | if (v1 > v2) { | ||
179 | int v3 = v1; | ||
180 | v1 = v2; | ||
181 | v2 = v3; | ||
182 | } | ||
183 | dsf[v1] += (dsf[v2] >> 2) << 2; | ||
184 | dsf[v2] = (v1 << 2) | !!inverse; | ||
185 | } | ||
186 | |||
187 | v2 = edsf_canonify(dsf, v2, &i2); | ||
188 | assert(v2 == v1); | ||
189 | assert(i2 == inverse); | ||
190 | |||
191 | /* fprintf(stderr, "dsf[%2d] = %2d\n", v2, dsf[v2]); */ | ||
192 | } | ||