tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
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 <assert.h>
8#include <limits.h>
9#include <string.h>
10
11#include "puzzles.h"
12
13#define DSF_INDEX_MASK (UINT_MAX >> 1)
14#define DSF_FLAG_CANONICAL (UINT_MAX & ~(UINT_MAX >> 1))
15#define DSF_MAX (DSF_INDEX_MASK + 1)
16
17struct DSF {
18 /*
19 * Size of the dsf.
20 */
21 size_t size;
22
23 /*
24 * Main array storing the data structure.
25 *
26 * If n is the canonical element of an equivalence class,
27 * parent_or_size[n] holds the number of elements in that class,
28 * bitwise-ORed with DSF_FLAG_CANONICAL.
29 *
30 * If n is not the canonical element, parent_or_size[n] holds the
31 * index of another element nearer to the root of the tree for
32 * that class.
33 */
34 unsigned *parent_or_size;
35
36 /*
37 * Extra storage for flip tracking.
38 *
39 * If n is not a canonical element, flip[n] indicates whether the
40 * sense of this element is flipped relative to parent_or_size[n].
41 *
42 * If n is a canonical element, flip[n] is unused.
43 */
44 unsigned char *flip;
45
46 /*
47 * Extra storage for minimal-element tracking.
48 *
49 * If n is a canonical element, min[n] holds the index of the
50 * smallest value in n's equivalence class.
51 *
52 * If n is not a canonical element, min[n] is unused.
53 */
54 unsigned *min;
55};
56
57static DSF *dsf_new_internal(int size, bool flip, bool min)
58{
59 DSF *dsf;
60
61 assert(0 < size && size <= DSF_MAX && "Bad dsf size");
62
63 dsf = snew(DSF);
64 dsf->size = size;
65 dsf->parent_or_size = snewn(size, unsigned);
66 dsf->flip = flip ? snewn(size, unsigned char) : NULL;
67 dsf->min = min ? snewn(size, unsigned) : NULL;
68
69 dsf_reinit(dsf);
70
71 return dsf;
72}
73
74DSF *dsf_new(int size)
75{
76 return dsf_new_internal(size, false, false);
77}
78
79DSF *dsf_new_flip(int size)
80{
81 return dsf_new_internal(size, true, false);
82}
83
84DSF *dsf_new_min(int size)
85{
86 return dsf_new_internal(size, false, true);
87}
88
89void dsf_reinit(DSF *dsf)
90{
91 size_t i;
92
93 /* Every element starts as the root of an equivalence class of size 1 */
94 for (i = 0; i < dsf->size; i++)
95 dsf->parent_or_size[i] = DSF_FLAG_CANONICAL | 1;
96
97 /* If we're tracking minima then every element is also its own min */
98 if (dsf->min)
99 for (i = 0; i < dsf->size; i++)
100 dsf->min[i] = i;
101
102 /* No need to initialise dsf->flip, even if it exists, because
103 * only the entries for non-root elements are meaningful, and
104 * currently there are none. */
105}
106
107void dsf_copy(DSF *to, DSF *from)
108{
109 assert(to->size == from->size && "Mismatch in dsf_copy");
110 memcpy(to->parent_or_size, from->parent_or_size,
111 to->size * sizeof(*to->parent_or_size));
112 if (to->flip) {
113 assert(from->flip && "Copying a non-flip dsf to a flip one");
114 memcpy(to->flip, from->flip, to->size * sizeof(*to->flip));
115 }
116 if (to->min) {
117 assert(from->min && "Copying a non-min dsf to a min one");
118 memcpy(to->min, from->min, to->size * sizeof(*to->min));
119 }
120}
121
122
123void dsf_free(DSF *dsf)
124{
125 if (dsf) {
126 sfree(dsf->parent_or_size);
127 sfree(dsf->flip);
128 sfree(dsf->min);
129 sfree(dsf);
130 }
131}
132
133static inline size_t dsf_find_root(DSF *dsf, size_t n)
134{
135 while (!(dsf->parent_or_size[n] & DSF_FLAG_CANONICAL))
136 n = dsf->parent_or_size[n];
137 return n;
138}
139
140static inline void dsf_path_compress(DSF *dsf, size_t n, size_t root)
141{
142 while (!(dsf->parent_or_size[n] & DSF_FLAG_CANONICAL)) {
143 size_t prev = n;
144 n = dsf->parent_or_size[n];
145 dsf->parent_or_size[prev] = root;
146 }
147 assert(n == root);
148}
149
150int dsf_canonify(DSF *dsf, int n)
151{
152 size_t root;
153
154 assert(0 <= n && n < dsf->size && "Overrun in dsf_canonify");
155
156 root = dsf_find_root(dsf, n);
157 dsf_path_compress(dsf, n, root);
158 return root;
159}
160
161void dsf_merge(DSF *dsf, int n1, int n2)
162{
163 size_t r1, r2, s1, s2, root;
164
165 assert(0 <= n1 && n1 < dsf->size && "Overrun in dsf_merge");
166 assert(0 <= n2 && n2 < dsf->size && "Overrun in dsf_merge");
167 assert(!dsf->flip && "dsf_merge on a flip dsf");
168
169 /* Find the root elements */
170 r1 = dsf_find_root(dsf, n1);
171 r2 = dsf_find_root(dsf, n2);
172
173 if (r1 == r2) {
174 /* Classes are already the same, so we have a common root */
175 root = r1;
176 } else {
177 /* Classes must be merged */
178
179 /* Decide which one to use as the overall root, based on size */
180 s1 = dsf->parent_or_size[r1] & DSF_INDEX_MASK;
181 s2 = dsf->parent_or_size[r2] & DSF_INDEX_MASK;
182 if (s1 > s2) {
183 dsf->parent_or_size[r2] = root = r1;
184 } else {
185 dsf->parent_or_size[r1] = root = r2;
186 }
187 dsf->parent_or_size[root] = (s1 + s2) | DSF_FLAG_CANONICAL;
188
189 if (dsf->min) {
190 /* Update the min of the merged class */
191 unsigned m1 = dsf->min[r1], m2 = dsf->min[r2];
192 dsf->min[root] = m1 < m2 ? m1 : m2;
193 }
194 }
195
196 /* Path-compress both paths from n1 and n2 so they point at the new root */
197 dsf_path_compress(dsf, n1, root);
198 dsf_path_compress(dsf, n2, root);
199}
200
201bool dsf_equivalent(DSF *dsf, int n1, int n2)
202{
203 return dsf_canonify(dsf, n1) == dsf_canonify(dsf, n2);
204}
205
206int dsf_size(DSF *dsf, int n)
207{
208 size_t root = dsf_canonify(dsf, n);
209 return dsf->parent_or_size[root] & DSF_INDEX_MASK;
210}
211
212static inline size_t dsf_find_root_flip(DSF *dsf, size_t n, unsigned *flip)
213{
214 *flip = 0;
215 while (!(dsf->parent_or_size[n] & DSF_FLAG_CANONICAL)) {
216 *flip ^= dsf->flip[n];
217 n = dsf->parent_or_size[n];
218 }
219 return n;
220}
221
222static inline void dsf_path_compress_flip(DSF *dsf, size_t n, size_t root,
223 unsigned flip)
224{
225 while (!(dsf->parent_or_size[n] & DSF_FLAG_CANONICAL)) {
226 size_t prev = n;
227 unsigned flip_prev = flip;
228 n = dsf->parent_or_size[n];
229 flip ^= dsf->flip[prev];
230 dsf->flip[prev] = flip_prev;
231 dsf->parent_or_size[prev] = root;
232 }
233 assert(n == root);
234}
235
236int dsf_canonify_flip(DSF *dsf, int n, bool *inverse)
237{
238 size_t root;
239 unsigned flip;
240
241 assert(0 <= n && n < dsf->size && "Overrun in dsf_canonify_flip");
242 assert(dsf->flip && "dsf_canonify_flip on a non-flip dsf");
243
244 root = dsf_find_root_flip(dsf, n, &flip);
245 dsf_path_compress_flip(dsf, n, root, flip);
246 *inverse = flip;
247 return root;
248}
249
250void dsf_merge_flip(DSF *dsf, int n1, int n2, bool inverse)
251{
252 size_t r1, r2, s1, s2, root;
253 unsigned f1, f2;
254
255 assert(0 <= n1 && n1 < dsf->size && "Overrun in dsf_merge_flip");
256 assert(0 <= n2 && n2 < dsf->size && "Overrun in dsf_merge_flip");
257 assert(dsf->flip && "dsf_merge_flip on a non-flip dsf");
258
259 /* Find the root elements */
260 r1 = dsf_find_root_flip(dsf, n1, &f1);
261 r2 = dsf_find_root_flip(dsf, n2, &f2);
262
263 if (r1 == r2) {
264 /* Classes are already the same, so we have a common root */
265 assert((f1 ^ f2 ^ inverse) == 0 && "Inconsistency in dsf_merge_flip");
266 root = r1;
267 } else {
268 /* Classes must be merged */
269
270 /* Decide which one to use as the overall root, based on size */
271 s1 = dsf->parent_or_size[r1] & DSF_INDEX_MASK;
272 s2 = dsf->parent_or_size[r2] & DSF_INDEX_MASK;
273 if (s1 > s2) {
274 dsf->parent_or_size[r2] = root = r1;
275 dsf->flip[r2] = f1 ^ f2 ^ inverse;
276 f2 ^= dsf->flip[r2];
277 } else {
278 root = r2;
279 dsf->parent_or_size[r1] = root = r2;
280 dsf->flip[r1] = f1 ^ f2 ^ inverse;
281 f1 ^= dsf->flip[r1];
282 }
283 dsf->parent_or_size[root] = (s1 + s2) | DSF_FLAG_CANONICAL;
284
285 if (dsf->min) {
286 /* Update the min of the merged class */
287 unsigned m1 = dsf->min[r1], m2 = dsf->min[r2];
288 dsf->min[root] = m1 < m2 ? m1 : m2;
289 }
290 }
291
292 /* Path-compress both paths from n1 and n2 so they point at the new root */
293 dsf_path_compress_flip(dsf, n1, root, f1);
294 dsf_path_compress_flip(dsf, n2, root, f2);
295}
296
297int dsf_minimal(DSF *dsf, int n)
298{
299 size_t root;
300
301 assert(dsf->min && "dsf_minimal on a non-min dsf");
302
303 root = dsf_canonify(dsf, n);
304 return dsf->min[root];
305}