diff options
Diffstat (limited to 'puzzles.h')
| -rw-r--r-- | puzzles.h | 44 |
1 files changed, 24 insertions, 20 deletions
@@ -427,30 +427,34 @@ char *button2label(int button); * dsf.c */ typedef struct DSF DSF; -DSF *snew_dsf(int size); +DSF *dsf_new(int size); void dsf_free(DSF *dsf); void dsf_copy(DSF *to, DSF *from); -/* Return the canonical element of the equivalence class containing element - * val. If 'inverse' is non-NULL, this function will put into it a flag - * indicating whether the canonical element is inverse to val. */ -int edsf_canonify(DSF *dsf, int val, bool *inverse); -int dsf_canonify(DSF *dsf, int val); -int dsf_size(DSF *dsf, int val); - -/* Check whether two elements are in the same equivalence class. - * Equivalent to, but less verbose than, calling dsf_canonify twice - * and seeing if their two canonical elements are the same. */ -bool dsf_equivalent(DSF *dsf, int v1, int v2); - -/* Allow the caller to specify that two elements should be in the same - * equivalence class. If 'inverse' is true, the elements are actually opposite - * to one another in some sense. This function will fail an assertion if the - * caller gives it self-contradictory data, ie if two elements are claimed to - * be both opposite and non-opposite. */ -void edsf_merge(DSF *dsf, int v1, int v2, bool inverse); -void dsf_merge(DSF *dsf, int v1, int v2); +/* Basic dsf operations, return the canonical element of a class, + * check if two elements are in the same class, and return the size of + * a class. These work on all types of dsf. */ +int dsf_canonify(DSF *dsf, int n); +bool dsf_equivalent(DSF *dsf, int n1, int n2); +int dsf_size(DSF *dsf, int n); + +/* Merge two elements and their classes. Not legal on a flip dsf. */ +void dsf_merge(DSF *dsf, int n1, int n2); + +/* Special dsf that tracks the minimal element of every equivalence + * class, and a function to query it. */ +DSF *dsf_new_min(int size); +int dsf_minimal(DSF *dsf, int n); + +/* Special dsf that tracks whether pairs of elements in the same class + * have flipped sense relative to each other. Merge function takes an + * argument saying whether n1 and n2 are opposite to each other; + * canonify function will report whether n is opposite to the returned + * element. */ +DSF *dsf_new_flip(int size); +void dsf_merge_flip(DSF *dsf, int n1, int n2, bool flip); +int dsf_canonify_flip(DSF *dsf, int n, bool *flip); /* Reinitialise a dsf to the starting 'all elements distinct' state. */ void dsf_reinit(DSF *dsf); |