diff options
| -rw-r--r-- | dsf.c | 356 |
1 files changed, 250 insertions, 106 deletions
@@ -5,157 +5,301 @@ */ #include <assert.h> +#include <limits.h> #include <string.h> #include "puzzles.h" +#define DSF_INDEX_MASK (UINT_MAX >> 1) +#define DSF_FLAG_CANONICAL (UINT_MAX & ~(UINT_MAX >> 1)) +#define DSF_MAX (DSF_INDEX_MASK + 1) + struct DSF { - int size; - int *p; + /* + * Size of the dsf. + */ + size_t size; + + /* + * Main array storing the data structure. + * + * If n is the canonical element of an equivalence class, + * parent_or_size[n] holds the number of elements in that class, + * bitwise-ORed with DSF_FLAG_CANONICAL. + * + * If n is not the canonical element, parent_or_size[n] holds the + * index of another element nearer to the root of the tree for + * that class. + */ + unsigned *parent_or_size; + + /* + * Extra storage for flip tracking. + * + * If n is not a canonical element, flip[n] indicates whether the + * sense of this element is flipped relative to parent_or_size[n]. + * + * If n is a canonical element, flip[n] is unused. + */ + unsigned char *flip; + + /* + * Extra storage for minimal-element tracking. + * + * If n is a canonical element, min[n] holds the index of the + * smallest value in n's equivalence class. + * + * If n is not a canonical element, min[n] is unused. + */ + unsigned *min; }; -void dsf_reinit(DSF *dsf) +static DSF *dsf_new_internal(int size, bool flip, bool min) { - int i; + DSF *dsf; - for (i = 0; i < dsf->size; i++) - dsf->p[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. */ + assert(0 < size && size <= DSF_MAX && "Bad dsf size"); + + dsf = snew(DSF); + dsf->size = size; + dsf->parent_or_size = snewn(size, unsigned); + dsf->flip = flip ? snewn(size, unsigned char) : NULL; + dsf->min = min ? snewn(size, unsigned) : NULL; + + dsf_reinit(dsf); + + return dsf; } -void dsf_copy(DSF *to, DSF *from) +DSF *dsf_new(int size) { - assert(to->size == from->size && "Mismatch in dsf_copy"); - memcpy(to->p, from->p, to->size * sizeof(int)); + return dsf_new_internal(size, false, false); } -DSF *dsf_new(int size) +DSF *dsf_new_flip(int size) +{ + return dsf_new_internal(size, true, false); +} + +DSF *dsf_new_min(int size) { - DSF *ret = snew(DSF); - ret->size = size; - ret->p = snewn(size, int); + return dsf_new_internal(size, false, true); +} + +void dsf_reinit(DSF *dsf) +{ + size_t i; - dsf_reinit(ret); + /* Every element starts as the root of an equivalence class of size 1 */ + for (i = 0; i < dsf->size; i++) + dsf->parent_or_size[i] = DSF_FLAG_CANONICAL | 1; + + /* If we're tracking minima then every element is also its own min */ + if (dsf->min) + for (i = 0; i < dsf->size; i++) + dsf->min[i] = i; + + /* No need to initialise dsf->flip, even if it exists, because + * only the entries for non-root elements are meaningful, and + * currently there are none. */ +} - return ret; +void dsf_copy(DSF *to, DSF *from) +{ + assert(to->size == from->size && "Mismatch in dsf_copy"); + memcpy(to->parent_or_size, from->parent_or_size, + to->size * sizeof(*to->parent_or_size)); + if (to->flip) { + assert(from->flip && "Copying a non-flip dsf to a flip one"); + memcpy(to->flip, from->flip, to->size * sizeof(*to->flip)); + } + if (to->min) { + assert(from->min && "Copying a non-min dsf to a min one"); + memcpy(to->min, from->min, to->size * sizeof(*to->min)); + } } -DSF *dsf_new_min(int size) { return dsf_new(size); } -DSF *dsf_new_flip(int size) { return dsf_new(size); } void dsf_free(DSF *dsf) { if (dsf) { - sfree(dsf->p); + sfree(dsf->parent_or_size); + sfree(dsf->flip); + sfree(dsf->min); sfree(dsf); } } -int dsf_canonify(DSF *dsf, int index) +static inline size_t dsf_find_root(DSF *dsf, size_t n) { - return dsf_canonify_flip(dsf, index, NULL); + while (!(dsf->parent_or_size[n] & DSF_FLAG_CANONICAL)) + n = dsf->parent_or_size[n]; + return n; } -int dsf_minimal(DSF *dsf, int index) +static inline void dsf_path_compress(DSF *dsf, size_t n, size_t root) { - return dsf_canonify_flip(dsf, index, NULL); + while (!(dsf->parent_or_size[n] & DSF_FLAG_CANONICAL)) { + size_t prev = n; + n = dsf->parent_or_size[n]; + dsf->parent_or_size[prev] = root; + } + assert(n == root); } -bool dsf_equivalent(DSF *dsf, int i1, int i2) +int dsf_canonify(DSF *dsf, int n) { - return dsf_canonify(dsf, i1) == dsf_canonify(dsf, i2); + size_t root; + + assert(0 <= n && n < dsf->size && "Overrun in dsf_canonify"); + + root = dsf_find_root(dsf, n); + dsf_path_compress(dsf, n, root); + return root; } -void dsf_merge(DSF *dsf, int v1, int v2) +void dsf_merge(DSF *dsf, int n1, int n2) { - dsf_merge_flip(dsf, v1, v2, false); -} + size_t r1, r2, s1, s2, root; + + assert(0 <= n1 && n1 < dsf->size && "Overrun in dsf_merge"); + assert(0 <= n2 && n2 < dsf->size && "Overrun in dsf_merge"); + assert(!dsf->flip && "dsf_merge on a flip dsf"); + + /* Find the root elements */ + r1 = dsf_find_root(dsf, n1); + r2 = dsf_find_root(dsf, n2); + + if (r1 == r2) { + /* Classes are already the same, so we have a common root */ + root = r1; + } else { + /* Classes must be merged */ -int dsf_size(DSF *dsf, int index) { - return dsf->p[dsf_canonify(dsf, index)] >> 2; + /* Decide which one to use as the overall root, based on size */ + s1 = dsf->parent_or_size[r1] & DSF_INDEX_MASK; + s2 = dsf->parent_or_size[r2] & DSF_INDEX_MASK; + if (s1 > s2) { + dsf->parent_or_size[r2] = root = r1; + } else { + dsf->parent_or_size[r1] = root = r2; + } + dsf->parent_or_size[root] = (s1 + s2) | DSF_FLAG_CANONICAL; + + if (dsf->min) { + /* Update the min of the merged class */ + unsigned m1 = dsf->min[r1], m2 = dsf->min[r2]; + dsf->min[root] = m1 < m2 ? m1 : m2; + } + } + + /* Path-compress both paths from n1 and n2 so they point at the new root */ + dsf_path_compress(dsf, n1, root); + dsf_path_compress(dsf, n2, root); } -int dsf_canonify_flip(DSF *dsf, int index, bool *inverse_return) +bool dsf_equivalent(DSF *dsf, int n1, int n2) { - int start_index = index, canonical_index; - bool inverse = false; + return dsf_canonify(dsf, n1) == dsf_canonify(dsf, n2); +} - assert(0 <= index && index < dsf->size && "Overrun in edsf_canonify"); +int dsf_size(DSF *dsf, int n) +{ + size_t root = dsf_canonify(dsf, n); + return dsf->parent_or_size[root] & DSF_INDEX_MASK; +} - /* 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->p[index] & 2) == 0) { - inverse ^= (dsf->p[index] & 1); - index = dsf->p[index] >> 2; +static inline size_t dsf_find_root_flip(DSF *dsf, size_t n, unsigned *flip) +{ + *flip = 0; + while (!(dsf->parent_or_size[n] & DSF_FLAG_CANONICAL)) { + *flip ^= dsf->flip[n]; + n = dsf->parent_or_size[n]; } - 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->p[index] >> 2; - bool nextinverse = inverse ^ (dsf->p[index] & 1); - dsf->p[index] = (canonical_index << 2) | inverse; - inverse = nextinverse; - index = nextindex; + return n; +} + +static inline void dsf_path_compress_flip(DSF *dsf, size_t n, size_t root, + unsigned flip) +{ + while (!(dsf->parent_or_size[n] & DSF_FLAG_CANONICAL)) { + size_t prev = n; + unsigned flip_prev = flip; + n = dsf->parent_or_size[n]; + flip ^= dsf->flip[prev]; + dsf->flip[prev] = flip_prev; + dsf->parent_or_size[prev] = root; } + assert(n == root); +} + +int dsf_canonify_flip(DSF *dsf, int n, bool *inverse) +{ + size_t root; + unsigned flip; + + assert(0 <= n && n < dsf->size && "Overrun in dsf_canonify_flip"); + assert(dsf->flip && "dsf_canonify_flip on a non-flip dsf"); + + root = dsf_find_root_flip(dsf, n, &flip); + dsf_path_compress_flip(dsf, n, root, flip); + *inverse = flip; + return root; +} + +void dsf_merge_flip(DSF *dsf, int n1, int n2, bool inverse) +{ + size_t r1, r2, s1, s2, root; + unsigned f1, f2; + + assert(0 <= n1 && n1 < dsf->size && "Overrun in dsf_merge_flip"); + assert(0 <= n2 && n2 < dsf->size && "Overrun in dsf_merge_flip"); + assert(dsf->flip && "dsf_merge_flip on a non-flip dsf"); + + /* Find the root elements */ + r1 = dsf_find_root_flip(dsf, n1, &f1); + r2 = dsf_find_root_flip(dsf, n2, &f2); - assert(!inverse); - - return index; -} - -void dsf_merge_flip(DSF *dsf, int v1, int v2, bool inverse) -{ - bool i1, i2; - - assert(0 <= v1 && v1 < dsf->size && "Overrun in edsf_merge"); - assert(0 <= v2 && v2 < dsf->size && "Overrun in edsf_merge"); - - v1 = dsf_canonify_flip(dsf, v1, &i1); - assert(dsf->p[v1] & 2); - inverse ^= i1; - v2 = dsf_canonify_flip(dsf, v2, &i2); - assert(dsf->p[v2] & 2); - inverse ^= i2; - - 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->p[v1] += (dsf->p[v2] >> 2) << 2; - dsf->p[v2] = (v1 << 2) | inverse; + if (r1 == r2) { + /* Classes are already the same, so we have a common root */ + assert((f1 ^ f2 ^ inverse) == 0 && "Inconsistency in dsf_merge_flip"); + root = r1; + } else { + /* Classes must be merged */ + + /* Decide which one to use as the overall root, based on size */ + s1 = dsf->parent_or_size[r1] & DSF_INDEX_MASK; + s2 = dsf->parent_or_size[r2] & DSF_INDEX_MASK; + if (s1 > s2) { + dsf->parent_or_size[r2] = root = r1; + dsf->flip[r2] = f1 ^ f2 ^ inverse; + f2 ^= dsf->flip[r2]; + } else { + root = r2; + dsf->parent_or_size[r1] = root = r2; + dsf->flip[r1] = f1 ^ f2 ^ inverse; + f1 ^= dsf->flip[r1]; + } + dsf->parent_or_size[root] = (s1 + s2) | DSF_FLAG_CANONICAL; + + if (dsf->min) { + /* Update the min of the merged class */ + unsigned m1 = dsf->min[r1], m2 = dsf->min[r2]; + dsf->min[root] = m1 < m2 ? m1 : m2; + } } - - v2 = dsf_canonify_flip(dsf, v2, &i2); - assert(v2 == v1); - assert(i2 == inverse); + + /* Path-compress both paths from n1 and n2 so they point at the new root */ + dsf_path_compress_flip(dsf, n1, root, f1); + dsf_path_compress_flip(dsf, n2, root, f2); +} + +int dsf_minimal(DSF *dsf, int n) +{ + size_t root; + + assert(dsf->min && "dsf_minimal on a non-min dsf"); + + root = dsf_canonify(dsf, n); + return dsf->min[root]; } |