Previous | Contents | Next

Chapter 5: Utility APIs

This chapter documents a variety of utility APIs provided for the general use of the rest of the Puzzles code.

5.1 Random number generation

Platforms' local random number generators vary widely in quality and seed size. Puzzles therefore supplies its own high-quality random number generator, with the additional advantage of giving the same results if fed the same seed data on different platforms. This allows game random seeds to be exchanged between different ports of Puzzles and still generate the same games.

Unlike the ANSI C rand() function, the Puzzles random number generator has an explicit state object called a random_state. One of these is managed by each mid-end, for example, and passed to the back end to generate a game with.

5.1.1 random_new()

random_state *random_new(char *seed, int len);

Allocates, initialises and returns a new random_state. The input data is used as the seed for the random number stream (i.e. using the same seed at a later time will generate the same stream).

The seed data can be any data at all; there is no requirement to use printable ASCII, or NUL-terminated strings, or anything like that.

5.1.2 random_copy()

random_state *random_copy(random_state *tocopy);

Allocates a new random_state, copies the contents of another random_state into it, and returns the new state. If exactly the same sequence of functions is subsequently called on both the copy and the original, the results will be identical. This may be useful for speculatively performing some operation using a given random state, and later replaying that operation precisely.

5.1.3 random_free()

void random_free(random_state *state);

Frees a random_state.

5.1.4 random_bits()

unsigned long random_bits(random_state *state, int bits);

Returns a random number from 0 to 2^bits-1 inclusive. bits should be between 1 and 32 inclusive.

5.1.5 random_upto()

unsigned long random_upto(random_state *state, unsigned long limit);

Returns a random number from 0 to limit-1 inclusive. limit may not be zero.

5.1.6 random_state_encode()

char *random_state_encode(random_state *state);

Encodes the entire contents of a random_state in printable ASCII. Returns a dynamically allocated string containing that encoding. This can subsequently be passed to random_state_decode() to reconstruct the same random_state.

5.1.7 random_state_decode()

random_state *random_state_decode(char *input);

Decodes a string generated by random_state_encode() and reconstructs an equivalent random_state to the one encoded, i.e. it should produce the same stream of random numbers.

This function has no error reporting; if you pass it an invalid string it will simply generate an arbitrary random state, which may turn out to be noticeably non-random.

5.1.8 shuffle()

void shuffle(void *array, int nelts, int eltsize, random_state *rs);

Shuffles an array into a random order. The interface is much like ANSI C qsort(), except that there's no need for a compare function.

array is a pointer to the first element of the array. nelts is the number of elements in the array; eltsize is the size of a single element (typically measured using sizeof). rs is a random_state used to generate all the random numbers for the shuffling process.

5.2 Presets menu management

The function midend_get_presets() (section 4.17) returns a data structure describing a menu hierarchy. Back ends can also choose to provide such a structure to the mid-end, if they want to group their presets hierarchically. To make this easy, there are a few utility functions to construct preset menu structures, and also one intended for front-end use.

5.2.1 preset_menu_new()

struct preset_menu *preset_menu_new(void);

Allocates a new struct preset_menu, and initialises it to hold no menu items.

5.2.2 preset_menu_add_submenu()

struct preset_menu *preset_menu_add_submenu
    (struct preset_menu *parent, char *title);

Adds a new submenu to the end of an existing preset menu, and returns a pointer to a newly allocated struct preset_menu describing the submenu.

The string parameter ‘title’ must be dynamically allocated by the caller. The preset-menu structure will take ownership of it, so the caller must not free it.

5.2.3 preset_menu_add_preset()

void preset_menu_add_preset
    (struct preset_menu *menu, char *title, game_params *params);

Adds a preset game configuration to the end of a preset menu.

Both the string parameter ‘title’ and the game parameter structure ‘params’ itself must be dynamically allocated by the caller. The preset-menu structure will take ownership of it, so the caller must not free it.

5.2.4 preset_menu_lookup_by_id()

game_params *preset_menu_lookup_by_id
    (struct preset_menu *menu, int id);

Given a numeric index, searches recursively through a preset menu hierarchy to find the corresponding menu entry, and returns a pointer to its existing game_params structure.

This function is intended for front end use (but front ends need not use it if they prefer to do things another way). If a front end finds it inconvenient to store anything more than a numeric index alongside each menu item, then this function provides an easy way for the front end to get back the actual game parameters corresponding to a menu item that the user has selected.

5.3 Memory allocation

Puzzles has some central wrappers on the standard memory allocation functions, which provide compile-time type checking, and run-time error checking by means of quitting the application if it runs out of memory. This doesn't provide the best possible recovery from memory shortage, but on the other hand it greatly simplifies the rest of the code, because nothing else anywhere needs to worry about NULL returns from allocation.

5.3.1 snew()

var = snew(type);

This macro takes a single argument which is a type name. It allocates space for one object of that type. If allocation fails it will call fatal() and not return; so if it does return, you can be confident that its return value is non-NULL.

The return value is cast to the specified type, so that the compiler will type-check it against the variable you assign it into. Thus, this ensures you don't accidentally allocate memory the size of the wrong type and assign it into a variable of the right one (or vice versa!).

5.3.2 snewn()

var = snewn(n, type);

This macro is the array form of snew(). It takes two arguments; the first is a number, and the second is a type name. It allocates space for that many objects of that type, and returns a type-checked non-NULL pointer just as snew() does.

5.3.3 sresize()

var = sresize(var, n, type);

This macro is a type-checked form of realloc(). It takes three arguments: an input memory block, a new size in elements, and a type. It re-sizes the input memory block to a size sufficient to contain that many elements of that type. It returns a type-checked non-NULL pointer, like snew() and snewn().

The input memory block can be NULL, in which case this function will behave exactly like snewn(). (In principle any ANSI-compliant realloc() implementation ought to cope with this, but I've never quite trusted it to work everywhere.)

5.3.4 sfree()

void sfree(void *p);

This function is pretty much equivalent to free(). It is provided with a dynamically allocated block, and frees it.

The input memory block can be NULL, in which case this function will do nothing. (In principle any ANSI-compliant free() implementation ought to cope with this, but I've never quite trusted it to work everywhere.)

5.3.5 dupstr()

char *dupstr(const char *s);

This function dynamically allocates a duplicate of a C string. Like the snew() functions, it guarantees to return non-NULL or not return at all.

(Many platforms provide the function strdup(). As well as guaranteeing never to return NULL, my version has the advantage of being defined everywhere, rather than inconveniently not quite everywhere.)

5.3.6 free_cfg()

void free_cfg(config_item *cfg);

This function correctly frees an array of config_items, including walking the array until it gets to the end and freeing any subsidiary data items in each u sub-union which are expected to be dynamically allocated.

(See section 2.3.9 for details of the config_item structure.)

5.3.7 free_keys()

void free_keys(key_label *keys, int nkeys);

This function correctly frees an array of key_labels, including the dynamically allocated label string for each key.

(See section 2.10.7 for details of the key_label structure.)

5.4 Sorted and counted tree functions

Many games require complex algorithms for generating random puzzles, and some require moderately complex algorithms even during play. A common requirement during these algorithms is for a means of maintaining sorted or unsorted lists of items, such that items can be removed and added conveniently.

For general use, Puzzles provides the following set of functions which maintain 2-3-4 trees in memory. (A 2-3-4 tree is a balanced tree structure, with the property that all lookups, insertions, deletions, splits and joins can be done in O(log N) time.)

All these functions expect you to be storing a tree of void * pointers. You can put anything you like in those pointers.

By the use of per-node element counts, these tree structures have the slightly unusual ability to look elements up by their numeric index within the list represented by the tree. This means that they can be used to store an unsorted list (in which case, every time you insert a new element, you must explicitly specify the position where you wish to insert it). They can also do numeric lookups in a sorted tree, which might be useful for (for example) tracking the median of a changing data set.

As well as storing sorted lists, these functions can be used for storing ‘maps’ (associative arrays), by defining each element of a tree to be a (key, value) pair.

5.4.1 newtree234()

tree234 *newtree234(cmpfn234 cmp);

Creates a new empty tree, and returns a pointer to it.

The parameter cmp determines the sorting criterion on the tree. Its prototype is 

typedef int (*cmpfn234)(void *, void *);

If you want a sorted tree, you should provide a function matching this prototype, which returns like strcmp() does (negative if the first argument is smaller than the second, positive if it is bigger, zero if they compare equal). In this case, the function addpos234() will not be usable on your tree (because all insertions must respect the sorting order).

If you want an unsorted tree, pass NULL. In this case you will not be able to use either add234() or del234(), or any other function such as find234() which depends on a sorting order. Your tree will become something more like an array, except that it will efficiently support insertion and deletion as well as lookups by numeric index.

5.4.2 freetree234()

void freetree234(tree234 *t);

Frees a tree. This function will not free the elements of the tree (because they might not be dynamically allocated, or you might be storing the same set of elements in more than one tree); it will just free the tree structure itself. If you want to free all the elements of a tree, you should empty it before passing it to freetree234(), by means of code along the lines of 

while ((element = delpos234(tree, 0)) != NULL)
    sfree(element); /* or some more complicated free function */

5.4.3 add234()

void *add234(tree234 *t, void *e);

Inserts a new element e into the tree t. This function expects the tree to be sorted; the new element is inserted according to the sort order.

If an element comparing equal to e is already in the tree, then the insertion will fail, and the return value will be the existing element. Otherwise, the insertion succeeds, and e is returned.

5.4.4 addpos234()

void *addpos234(tree234 *t, void *e, int index);

Inserts a new element into an unsorted tree. Since there is no sorting order to dictate where the new element goes, you must specify where you want it to go. Setting index to zero puts the new element right at the start of the list; setting index to the current number of elements in the tree puts the new element at the end.

Return value is e, in line with add234() (although this function cannot fail except by running out of memory, in which case it will bomb out and die rather than returning an error indication).

5.4.5 index234()

void *index234(tree234 *t, int index);

Returns a pointer to the indexth element of the tree, or NULL if index is out of range. Elements of the tree are numbered from zero.

5.4.6 find234()

void *find234(tree234 *t, void *e, cmpfn234 cmp);

Searches for an element comparing equal to e in a sorted tree.

If cmp is NULL, the tree's ordinary comparison function will be used to perform the search. However, sometimes you don't want that; suppose, for example, each of your elements is a big structure containing a char * name field, and you want to find the element with a given name. You could achieve this by constructing a fake element structure, setting its name field appropriately, and passing it to find234(), but you might find it more convenient to pass just a name string to find234(), supplying an alternative comparison function which expects one of its arguments to be a bare name and the other to be a large structure containing a name field.

Therefore, if cmp is not NULL, then it will be used to compare e to elements of the tree. The first argument passed to cmp will always be e; the second will be an element of the tree.

(See section 5.4.1 for the definition of the cmpfn234 function pointer type.)

The returned value is the element found, or NULL if the search is unsuccessful.

5.4.7 findrel234()

void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation);

This function is like find234(), but has the additional ability to do a relative search. The additional parameter relation can be one of the following values:

REL234_EQ
Find only an element that compares equal to e. This is exactly the behaviour of find234().
REL234_LT
Find the greatest element that compares strictly less than e. e may be NULL, in which case it finds the greatest element in the whole tree (which could also be done by index234(t, count234(t)-1)).
REL234_LE
Find the greatest element that compares less than or equal to e. (That is, find an element that compares equal to e if possible, but failing that settle for something just less than it.)
REL234_GT
Find the smallest element that compares strictly greater than e. e may be NULL, in which case it finds the smallest element in the whole tree (which could also be done by index234(t, 0)).
REL234_GE
Find the smallest element that compares greater than or equal to e. (That is, find an element that compares equal to e if possible, but failing that settle for something just bigger than it.)

Return value, as before, is the element found or NULL if no element satisfied the search criterion.

5.4.8 findpos234()

void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index);

This function is like find234(), but has the additional feature of returning the index of the element found in the tree; that index is written to *index in the event of a successful search (a non-NULL return value).

index may be NULL, in which case this function behaves exactly like find234().

5.4.9 findrelpos234()

void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp, int relation,
                    int *index);

This function combines all the features of findrel234() and findpos234().

5.4.10 del234()

void *del234(tree234 *t, void *e);

Finds an element comparing equal to e in the tree, deletes it, and returns it.

The input tree must be sorted.

The element found might be e itself, or might merely compare equal to it.

Return value is NULL if no such element is found.

5.4.11 delpos234()

void *delpos234(tree234 *t, int index);

Deletes the element at position index in the tree, and returns it.

Return value is NULL if the index is out of range.

5.4.12 count234()

int count234(tree234 *t);

Returns the number of elements currently in the tree.

5.4.13 splitpos234()

tree234 *splitpos234(tree234 *t, int index, bool before);

Splits the input tree into two pieces at a given position, and creates a new tree containing all the elements on one side of that position.

If before is true, then all the items at or after position index are left in the input tree, and the items before that point are returned in the new tree. Otherwise, the reverse happens: all the items at or after index are moved into the new tree, and those before that point are left in the old one.

If index is equal to 0 or to the number of elements in the input tree, then one of the two trees will end up empty (and this is not an error condition). If index is further out of range in either direction, the operation will fail completely and return NULL.

This operation completes in O(log N) time, no matter how large the tree or how balanced or unbalanced the split.

5.4.14 split234()

tree234 *split234(tree234 *t, void *e, cmpfn234 cmp, int rel);

Splits a sorted tree according to its sort order.

rel can be any of the relation constants described in section 5.4.7, except for REL234_EQ. All the elements having that relation to e will be transferred into the new tree; the rest will be left in the old one.

The parameter cmp has the same semantics as it does in find234(): if it is not NULL, it will be used in place of the tree's own comparison function when comparing elements to e, in such a way that e itself is always the first of its two operands.

Again, this operation completes in O(log N) time, no matter how large the tree or how balanced or unbalanced the split.

5.4.15 join234()

tree234 *join234(tree234 *t1, tree234 *t2);

Joins two trees together by concatenating the lists they represent. All the elements of t2 are moved into t1, in such a way that they appear after the elements of t1. The tree t2 is freed; the return value is t1.

If you apply this function to a sorted tree and it violates the sort order (i.e. the smallest element in t2 is smaller than or equal to the largest element in t1), the operation will fail and return NULL.

This operation completes in O(log N) time, no matter how large the trees being joined together.

5.4.16 join234r()

tree234 *join234r(tree234 *t1, tree234 *t2);

Joins two trees together in exactly the same way as join234(), but this time the combined tree is returned in t2, and t1 is destroyed. The elements in t1 still appear before those in t2.

Again, this operation completes in O(log N) time, no matter how large the trees being joined together.

5.4.17 copytree234()

tree234 *copytree234(tree234 *t, copyfn234 copyfn,
                     void *copyfnstate);

Makes a copy of an entire tree.

If copyfn is NULL, the tree will be copied but the elements will not be; i.e. the new tree will contain pointers to exactly the same physical elements as the old one.

If you want to copy each actual element during the operation, you can instead pass a function in copyfn which makes a copy of each element. That function has the prototype 

typedef void *(*copyfn234)(void *state, void *element);

and every time it is called, the state parameter will be set to the value you passed in as copyfnstate.

5.5 Disjoint set forests

This section describes a set of functions implementing the data structure variously known as ‘union-find’ or ‘Tarjan's disjoint set forest’. In this code base, it's universally abbreviated as a ‘dsf’.

A dsf represents a collection of elements partitioned into ‘equivalence classes’, in circumstances where equivalences are added incrementally. That is, all elements start off considered to be different, and you gradually declare more and more of them to be equal via the dsf_merge() operation, which says that two particular elements should be regarded as equal from now on.

For example, if I start off with A,B,U,V all distinct, and I merge A with B and merge U with V, then the structure will tell me that A and U are not equivalent. But if I then merge B with V, then after that, the structure will tell me that A and U are equivalent, by following the transitive chain of equivalences it knows about.

The dsf data structure is therefore ideal for tracking incremental connectivity in an undirected graph (again, ‘incremental’ meaning that you only ever add edges, never delete them), and other applications in which you gradually acquire knowledge you didn't previously have about what things are the same as each other. It's used extensively in puzzle solver and generator algorithms, and sometimes during gameplay as well.

The time complexity of dsf operations is not quite constant time, in theory, but it's so close to it as to make no difference in practice. In particular, any time a dsf has to do non-trivial work, it updates the structure so that that work won't be needed a second time. Use dsf operations without worrying about how long they take!

For some puzzle-game applications, it's useful to augment this data structure with extra information about how the elements of an equivalence class relate to each other. There's more than one way you might do this; the one supported here is useful in cases where the objects you're tracking are going to end up in one of two states (say, black/white, or on/off), and for any two objects you either know that they're in the same one of those states, or you know they're in opposite states, or you don't know which yet. Puzzles calls this a ‘flip dsf’: it tracks whether objects in the same equivalence class are flipped relative to each other.

As well as querying whether two elements are equivalent, this dsf implementation also allows you to ask for the number of elements in a given equivalence class, and the smallest element in the class. (The latter is used, for example, to decide which square to print the clue in each region of a Keen puzzle.)

5.5.1 dsf_new(), dsf_new_flip(), dsf_new_min()

DSF *dsf_new(int size);
DSF *dsf_new_flip(int size);
DSF *dsf_new_min(int size);

Each of these functions allocates space for a dsf describing size elements, and initialises it so that every element is in an equivalence class by itself.

The elements described by the dsf are represented by the integers from 0 to size-1 inclusive.

dsf_new_flip() will create a dsf which has the extra ability to track whether objects in the same equivalence class are flipped relative to each other.

dsf_new_min() will create a dsf which has the extra ability to track the smallest element of each equivalence class.

The returned object from any of these functions must be freed using dsf_free().

5.5.2 dsf_free()

void dsf_free(DSF *dsf);

Frees a dsf allocated by any of the dsf_new() functions.

5.5.3 dsf_reinit()

void dsf_reinit(DSF *dsf);

Reinitialises an existing dsf to the state in which all elements are distinct, without having to free and reallocate it.

5.5.4 dsf_copy()

void dsf_copy(DSF *to, DSF *from);

Copies the contents of one dsf over the top of another. Everything previously stored in to is overwritten.

The two dsfs must have been created with the same size, and the destination dsf may not have any extra information that the source dsf does not have.

5.5.5 dsf_merge()

void dsf_merge(DSF *dsf, int v1, int v2);

Updates a dsf so that elements v1 and v2 will now be considered to be in the same equivalence class. If they were already in the same class, this function will safely do nothing.

This function may not be called on a flip dsf. Use dsf_merge_flip instead.

5.5.6 dsf_canonify()

int dsf_canonify(DSF *dsf, int val);

Returns the ‘canonical’ element of the equivalence class in the dsf containing val. This will be some element of the same equivalence class. So in order to determine whether two elements are in the same equivalence class, you can call dsf_canonify on both of them, and compare the results.

Canonical elements don't necessarily stay the same if the dsf is mutated via dsf_merge. But between two calls to dsf_merge, they stay the same.

5.5.7 dsf_size()

int dsf_size(DSF *dsf, int val);

Returns the number of elements currently in the equivalence class containing val.

val itself counts, so in a newly created dsf, the return value will be 1.

5.5.8 dsf_merge_flip()

void edsf_merge(DSF *dsf, int v1, int v2, bool flip);

Updates a flip dsf so that elements v1 and v2 are in the same equivalence class. If flip is false, they will be regarded as in the same state as each other; if flip is true then they will be regarded as being in opposite states.

If v1 and v2 were already in the same equivalence class, then the new value of flip will be checked against what the edsf previously believed, and an assertion failure will occur if you contradict that.

For example, if you start from a blank flip dsf and do this: 

dsf_merge_flip(dsf, 0, 1, false);
dsf_merge_flip(dsf, 1, 2, true);

then it will create a dsf in which elements 0,1,2 are all in the same class, with 0,1 in the same state as each other and 2 in the opposite state from both. And then this call will do nothing, because it agrees with what the dsf already knew: 

dsf_merge_flip(dsf, 0, 2, true);

But this call will fail an assertion: 

dsf_merge_flip(dsf, 0, 2, false);

5.5.9 dsf_canonify_flip()

int dsf_canonify_flip(DSF *dsf, int val, bool *inverse);

Like dsf_canonify(), this returns the canonical element of the equivalence class of a dsf containing val.

However, it may only be called on a flip dsf, and it also fills in *flip with a flag indicating whether val and the canonical element are in opposite states: true if they are in opposite states, or false if they're in the same state.

So if you want to know the relationship between v1 and v2, you can do this: 

bool inv1, inv2;
int canon1 = dsf_canonify_flip(dsf, v1, &inv1);
int canon2 = dsf_canonify_flip(dsf, v2, &inv2);
if (canon1 != canon2) {
    // v1 and v2 have no known relation
} else if (inv1 == inv2) {
    // v1 and v2 are known to be in the same state as each other
} else {
    // v1 and v2 are known to be in opposite states
}

5.5.10 dsf_minimal()

int dsf_minimal(DSF *dsf, int val);

Returns the smallest element of the equivalence class in the dsf containing val.

For this function to work, the dsf must have been created using dsf_new_min().

5.6 To-do queues

This section describes a set of functions implementing a ‘to-do queue’, a simple de-duplicating to-do list mechanism. The code calls this a ‘tdq’.

A tdq can store integers up to a given size (specified at creation time). But it can't store the same integer more than once. So you can quickly make sure an integer is in the queue (which will do nothing if it's already there), and you can quickly pop an integer from the queue and return it, both in constant time.

The idea is that you might use this in a game solver, in the kind of game where updating your knowledge about one square of a grid means there's a specific other set of squares (such as its neighbours) where it's now worth attempting further deductions. So you keep a tdq of all the grid squares you plan to look at next, and every time you make a deduction in one square, you add the neighbouring squares to the tdq to make sure they get looked at again after that.

In solvers where deductions are mostly localised, this avoids the slowdown of having to find the next thing to do every time by looping over the whole grid: instead, you can keep checking the tdq for specific squares to look at, until you run out.

However, it's common to have games in which most deductions are localised, but not all. In that situation, when your tdq is empty, you can re-fill it with every square in the grid using tdq_fill(), which will force an iteration over everything again. And then if the tdq becomes empty again without you having made any progress, give up.

5.6.1 tdq_new()

tdq *tdq_new(int n);

Allocates space for a tdq that tracks items from 0 to size-1 inclusive.

5.6.2 tdq_free()

void tdq_free(tdq *tdq);

Frees a tdq.

5.6.3 tdq_add()

void tdq_add(tdq *tdq, int k);

Adds the value k to a tdq. If k was already in the to-do list, does nothing.

5.6.4 tdq_remove()

int tdq_remove(tdq *tdq);

Removes one item from the tdq, and returns it. If the tdq is empty, returns -1.

5.6.5 tdq_fill()

void tdq_fill(tdq *tdq);

Fills a tdq with every element it can possibly keep track of.

5.7 Finding loops in graphs and grids

Many puzzles played on grids or graphs have a common gameplay element of connecting things together into paths in such a way that you need to avoid making loops (or, perhaps, making the wrong kind of loop).

Just determining whether a loop exists in a graph is easy, using a dsf tracking connectivity between the vertices. Simply iterate over each edge of the graph, merging the two vertices at each end of the edge – but before you do that, check whether those vertices are already known to be connected to each other, and if they are, then the new edge is about to complete a loop.

But if you also want to identify exactly the set of edges that are part of any loop, e.g. to highlight the whole loop red during gameplay, then that's a harder problem. This API is provided here for all puzzles to use for that purpose.

5.7.1 findloop_new_state()

struct findloopstate *findloop_new_state(int nvertices);

Allocates a new state structure for the findloop algorithm, capable of handling a graph with up to nvertices vertices. The vertices will be represented by integers between 0 and nvertices-1 inclusive.

5.7.2 findloop_free_state()

void findloop_free_state(struct findloopstate *state);

Frees a state structure allocated by findloop_new_state().

5.7.3 findloop_run()

bool findloop_run(struct findloopstate *state, int nvertices,
                  neighbour_fn_t neighbour, void *ctx);

Runs the loop-finding algorithm, which will explore the graph and identify whether each edge is or is not part of any loop.

The algorithm will call the provided function neighbour to list the neighbouring vertices of each vertex. It should have this prototype: 

int neighbour(int vertex, void *ctx);

In this callback, vertex will be the index of a vertex when the algorithm first calls it for a given vertex. The function should return the index of one of that vertex's neighbours, or a negative number if there are none.

If the function returned a vertex, the algorithm will then call neighbour again with a negative number as the vertex parameter, which means ‘please give me another neighbour of the same vertex as last time’. Again, the function should return a vertex index, or a negative number to indicate that there are no more vertices.

The ctx parameter passed to findloop_run() is passed on unchanged to neighbour, so you can point that at your game state or solver state or whatever.

The return value is true if at least one loop exists in the graph, and false if no loop exists. Also, the algorithm state will have been filled in with information that the following query functions can use to ask about individual graph edges.

5.7.4 findloop_is_loop_edge()

bool findloop_is_loop_edge(struct findloopstate *state,
                           int u, int v);

Queries whether the graph edge between vertices u and v is part of a loop. If so, the return value is true, otherwise false.

5.7.5 findloop_is_bridge()

bool findloop_is_bridge(struct findloopstate *pv,
    int u, int v, int *u_vertices, int *v_vertices);

Queries whether the graph edge between vertices u and v is a ‘bridge’, i.e. an edge which would break the graph into (more) disconnected components if it were removed.

This is the exact inverse of the ‘loop edge’ criterion: a vertex returns true from findloop_is_loop_edge() if and only if it returns false from findloop_is_bridge(), and vice versa.

However, findloop_is_bridge() returns more information. If it returns true, then it also fills in *u_vertices and *v_vertices with the number of vertices connected to the u and v sides of the bridge respectively.

For example, if you have three vertices A,B,C all connected to each other, and four vertices U,V,W,X all connected to each other, and a single edge between A and V, then calling findloop_is_bridge() on the pair A,V will return true (removing that edge would separate the two sets from each other), and will report that there are three vertices on the A side and four on the V side.

5.8 Choosing r things out of n

This section describes a small API for iterating over all combinations of r things out of n.

For example, if you asked for all combinations of 3 things out of 5, you'd get back the sets {0,1,2}, {0,1,3}, {0,1,4}, {0,2,3}, {0,2,4}, {0,3,4}, {1,2,3}, {1,2,4}, {1,3,4}, and {2,3,4}.

These functions use a structure called a combi_ctx, which contains an element int *a holding each returned combination, plus other fields for implementation use only.

5.8.1 new_combi()

combi_ctx *new_combi(int r, int n);

Allocates a new combi_ctx structure for enumerating r things out of n.

5.8.2 free_combi()

void free_combi(combi_ctx *combi);

Frees a combi_ctx structure.

5.8.3 reset_combi()

void reset_combi(combi_ctx *combi);

Resets an existing combi_ctx structure to the start of its iteration

5.8.4 next_combi()

combi_ctx *next_combi(combi_ctx *combi);

Requests a combination from a combi_ctx.

If there are none left to return, the return value is NULL. Otherwise, it returns the input structure combi, indicating that it has filled in combi->a[0], combi->a[1], ..., combi->a[r-1] with an increasing sequence of distinct integers from 0 to n-1 inclusive.

5.9 Miscellaneous utility functions and macros

This section contains all the utility functions which didn't sensibly fit anywhere else.

5.9.1 max() and min()

The main Puzzles header file defines the pretty standard macros max() and min(), each of which is given two arguments and returns the one which compares greater or less respectively.

These macros may evaluate their arguments multiple times. Avoid side effects.

5.9.2 MAX_DIGITS()

The MAX_DIGITS() macro, defined in the main Puzzles header file, takes a type (or a variable of that type) and expands to an integer constant representing a reasonable upper bound on the number of characters that a number of that type could expand to when formatted as a decimal number using the %u or %d format of printf(). This is useful for allocating a fixed-size buffer that's guaranteed to be big enough to sprintf() a value into. Don't forget to add one for the trailing '\0'!

5.9.3 PI

The main Puzzles header file defines a macro PI which expands to a floating-point constant representing pi.

(I've never understood why ANSI's <math.h> doesn't define this. It'd be so useful!)

5.9.4 obfuscate_bitmap()

void obfuscate_bitmap(unsigned char *bmp, int bits, bool decode);

This function obscures the contents of a piece of data, by cryptographic methods. It is useful for games of hidden information (such as Mines, Guess or Black Box), in which the game ID theoretically reveals all the information the player is supposed to be trying to guess. So in order that players should be able to send game IDs to one another without accidentally spoiling the resulting game by looking at them, these games obfuscate their game IDs using this function.

Although the obfuscation function is cryptographic, it cannot properly be called encryption because it has no key. Therefore, anybody motivated enough can re-implement it, or hack it out of the Puzzles source, and strip the obfuscation off one of these game IDs to see what lies beneath. (Indeed, they could usually do it much more easily than that, by entering the game ID into their own copy of the puzzle and hitting Solve.) The aim is not to protect against a determined attacker; the aim is simply to protect people who wanted to play the game honestly from accidentally spoiling their own fun.

The input argument bmp points at a piece of memory to be obfuscated. bits gives the length of the data. Note that that length is in bits rather than bytes: if you ask for obfuscation of a partial number of bytes, then you will get it. Bytes are considered to be used from the top down: thus, for example, setting bits to 10 will cover the whole of bmp[0] and the top two bits of bmp[1]. The remainder of a partially used byte is undefined (i.e. it may be corrupted by the function).

The parameter decode is false for an encoding operation, and true for a decoding operation. Each is the inverse of the other. (There's no particular reason you shouldn't obfuscate by decoding and restore cleartext by encoding, if you really wanted to; it should still work.)

The input bitmap is processed in place.

5.9.5 bin2hex()

char *bin2hex(const unsigned char *in, int inlen);

This function takes an input byte array and converts it into an ASCII string encoding those bytes in (lower-case) hex. It returns a dynamically allocated string containing that encoding.

This function is useful for encoding the result of obfuscate_bitmap() in printable ASCII for use in game IDs.

5.9.6 hex2bin()

unsigned char *hex2bin(const char *in, int outlen);

This function takes an ASCII string containing hex digits, and converts it back into a byte array of length outlen. If there aren't enough hex digits in the string, the contents of the resulting array will be undefined.

This function is the inverse of bin2hex().

5.9.7 fgetline()

char *fgetline(FILE *fp);

This function reads a single line of text from a standard C input stream, and returns it as a dynamically allocated string. The returned string still has a newline on the end.

5.9.8 arraysort()

Sorts an array, with slightly more flexibility than the standard C qsort().

This function is really implemented as a macro, so it doesn't have a prototype as such. But you could imagine it having a prototype like this: 

void arraysort(element_t *array, size_t nmemb,
               arraysort_cmpfn_t cmp, void *ctx);

in which element_t is an unspecified type.

(Really, there's an underlying function that takes an extra parameter giving the size of each array element. But callers are encouraged to use this macro version, which fills that in automatically using sizeof.)

This function behaves essentially like qsort(): it expects array to point to an array of nmemb elements, and it will sort them in place into the order specified by the comparison function cmp.

The comparison function should have this prototype: 

int cmp(const void *a, const void *b, void *ctx);

in which a and b point at the two elements to be compared, and the return value is negative if a<b (that is, a should appear before b in the output array), positive if a>b, or zero if a=b.

The ctx parameter to arraysort() is passed directly to the comparison function. This is the feature that makes arraysort() more flexible than standard qsort(): it lets you vary the sorting criterion in a dynamic manner without having to write global variables in the caller for the compare function to read.

5.9.9 colour_mix()

void colour_mix(const float src1[3], const float src2[3], float p,
                float dst[3]);

This function mixes the colours src1 and src2 in specified proportions, producing dst. p is the proportion of src2 in the result. So if p is 1.0, dst will be the same as src2. If p is 0.0, dst will be the same as src1. And if p is somewhere in between, so will dst be. p is not restricted to the range 0.0 to 1.0. Values outside that range will produce extrapolated colours, which may be useful for some purposes, but may also produce impossible colours.

5.9.10 game_mkhighlight()

void game_mkhighlight(frontend *fe, float *ret,
                      int background, int highlight, int lowlight);

It's reasonably common for a puzzle game's graphics to use highlights and lowlights to indicate ‘raised’ or ‘lowered’ sections. Fifteen, Sixteen and Twiddle are good examples of this.

Puzzles using this graphical style are running a risk if they just use whatever background colour is supplied to them by the front end, because that background colour might be too light or dark to see any highlights on at all. (In particular, it's not unheard of for the front end to specify a default background colour of white.)

Therefore, such puzzles can call this utility function from their colours() routine (section 2.8.6). You pass it your front end handle, a pointer to the start of your return array, and three colour indices. It will:

Thus, ret[background*3] to ret[background*3+2] will be set to RGB values defining a sensible background colour, and similary highlight and lowlight will be set to sensible colours.

Either highlight or lowlight may be passed in as -1 to indicate that the back-end does not require a highlight or lowlight colour, respectively.

5.9.11 game_mkhighlight_specific()

void game_mkhighlight_specific(frontend *fe, float *ret,
    int background, int highlight, int lowlight);

This function behaves exactly like game_mkhighlight(), except that it expects the background colour to have been filled in already in the elements ret[background*3] to ret[background*3+2]. It will fill in the other two colours as brighter and darker versions of that.

This is useful if you want to show relief sections of a puzzle in more than one base colour.

5.9.12 button2label()

char *button2label(int button);

This function generates a descriptive text label for button, which should be a button code that can be passed to the midend. For example, calling this function with CURSOR_UP will result in the string "Up". This function should only be called when the key_label item returned by a backend's request_keys() (section 2.10.7) function has its label field set to NULL; in this case, the corresponding button field can be passed to this function to obtain an appropriate label. If, however, the field is not NULL, this function should not be called with the corresponding button field.

The returned string is dynamically allocated and should be sfree'd by the caller.

5.9.13 move_cursor()

char *move_cursor(int button, int *x, int *y, int w, int h,
                  bool wrap, bool *visible);

This function can be called by interpret_move() to implement the default keyboard API for moving a cursor around a grid.

button is the same value passed in to interpret_move(). If it's not any of CURSOR_UP, CURSOR_DOWN, CURSOR_LEFT or CURSOR_RIGHT, the function will do nothing.

x and y point to two integers which on input give the current location of a cursor in a square grid. w and h give the dimensions of the grid. On return, x and y are updated to give the cursor's new position according to which arrow key was pressed.

This function assumes that the grid coordinates run from 0 to w-1 inclusive (left to right), and from 0 to h-1 inclusive (top to bottom).

If wrap is true, then trying to move the cursor off any edge of the grid will result in it wrapping round to the corresponding square on the opposite edge. If wrap is false, such a move will have no effect.

If visible is not NULL, it points to a flag indicating whether the cursor is visible. This will be set to true if button represents a cursor-movement key.

The function returns one of the special constants that can be returned by interpret_move(). The return value is MOVE_UNUSED if button is unrecognised, MOVE_UI_UPDATE if x, y, or visible was updated, and MOVE_NO EFFECT otherwise.

5.9.14 divvy_rectangle()

int *divvy_rectangle(int w, int h, int k, random_state *rs);

Invents a random division of a rectangle into same-sized polyominoes, such as is found in the block layout of a Solo puzzle in jigsaw mode, or the solution to a Palisade puzzle.

w and h are the dimensions of the rectangle. k is the size of polyomino desired. It must be a factor of w*h.

rs is a random_state used to supply the random numbers to select a random division of the rectangle.

The return value is a dsf (see section 5.5) whose equivalence classes correspond to the polyominoes that the rectangle is divided into. The indices of the dsf are of the form y*w+x, for the cell with coordinates x,y.

5.9.15 domino_layout()

int *domino_layout(int w, int h, random_state *rs);

Invents a random tiling of a rectangle with dominoes.

w and h are the dimensions of the rectangle. If they are both odd, then one square will be left untiled.

rs is a random_state used to supply the random numbers to select a random division of the rectangle.

The return value is an array in which element y*w+x represents the cell with coordinates x,y. Each element of the array gives the index (in the same representation) of the other end of its domino. If there's a left-over square, then that element contains its own index.

5.9.16 domino_layout_prealloc()

void domino_layout_prealloc(int w, int h, random_state *rs,
                            int *grid, int *grid2, int *list);

Just like domino_layout(), but does no memory allocation. You can use this to save allocator overhead if you expect to need to generate many domino tilings of the same grid.

grid and grid2 should each have space for w*h ints. list should have space for 2*w*h ints.

The returned array is delivered in grid.

[Simon Tatham's Portable Puzzle Collection, version 20240330.fd304c5]