348
348
void dsf_init(int *dsf, int len);
355
* Data structure implementing a 'to-do queue', a simple
356
* de-duplicating to-do list mechanism.
358
* Specification: a tdq is a queue which can hold integers from 0 to
359
* n-1, where n was some constant specified at tdq creation time. No
360
* integer may appear in the queue's current contents more than once;
361
* an attempt to add an already-present integer again will do nothing,
362
* so that that integer is removed from the queue at the position
363
* where it was _first_ inserted. The add and remove operations take
366
* The idea is that you might use this in applications like solvers:
367
* keep a tdq listing the indices of grid squares that you currently
368
* need to process in some way. Whenever you modify a square in a way
369
* that will require you to re-scan its neighbours, add them to the
370
* list with tdq_add; meanwhile you're constantly taking elements off
371
* the list when you need another square to process. In solvers where
372
* deductions are mostly localised, this should prevent repeated
373
* O(N^2) loops over the whole grid looking for something to do. (But
374
* if only _most_ of the deductions are localised, then you should
375
* respond to an empty to-do list by re-adding everything using
376
* tdq_fill, so _then_ you rescan the whole grid looking for newly
377
* enabled non-local deductions. Only if you've done that and emptied
378
* the list again finding nothing new to do are you actually done.)
380
typedef struct tdq tdq;
382
void tdq_free(tdq *tdq);
383
void tdq_add(tdq *tdq, int k);
384
int tdq_remove(tdq *tdq); /* returns -1 if nothing available */
385
void tdq_fill(tdq *tdq); /* add everything to the tdq at once */
353
390
int *domino_layout(int w, int h, random_state *rs);
added
removed
puzzles.h
