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
|
/* Equivalence Class Implementation */
/* Implements simple single-depth union */
/* Simpler than Union-Find and better running time (constant) */
/* 0 indicates that a member is not part of a union (singleton);
otherwise, the number indicates the class to which the member belongs
*/
#include <stdlib.h>
#include "glotski.h"
void eq_init(level *mylevel) {
mylevel->equiv = (int *)calloc(mylevel->nextid, sizeof(int));
}
int eq_equiv(int *eq, int node1, int node2) { /* Are they equivalent? */
if (node1 == node2) return 1;
if (eq[node1] == 0 || eq[node2] == 0) return 0;
else return eq[node1] == eq[node2];
}
int eq_unite(int *eq, int *id, int parent, int node) { /* Make equiv:
0 fail, 1 succ */
if (eq[node] != 0) return 0;
if (eq[parent] == 0) eq[parent] = *id++;
eq[node] = eq[parent];
return 1;
}
|
