diff options
| -rw-r--r-- | grid.c | 391 | ||||
| -rw-r--r-- | grid.h | 15 | ||||
| -rw-r--r-- | loopgen.c | 10 | ||||
| -rw-r--r-- | loopgen.h | 2 | ||||
| -rw-r--r-- | loopy.c | 185 | ||||
| -rw-r--r-- | pearl.c | 22 |
6 files changed, 251 insertions, 374 deletions
@@ -43,12 +43,17 @@ void grid_free(grid *g) if (g->refcount == 0) { int i; for (i = 0; i < g->num_faces; i++) { - sfree(g->faces[i].dots); - sfree(g->faces[i].edges); + sfree(g->faces[i]->dots); + sfree(g->faces[i]->edges); + sfree(g->faces[i]); } for (i = 0; i < g->num_dots; i++) { - sfree(g->dots[i].faces); - sfree(g->dots[i].edges); + sfree(g->dots[i]->faces); + sfree(g->dots[i]->edges); + sfree(g->dots[i]); + } + for (i = 0; i < g->num_edges; i++) { + sfree(g->edges[i]); } sfree(g->faces); sfree(g->edges); @@ -66,6 +71,7 @@ static grid *grid_empty(void) g->edges = NULL; g->dots = NULL; g->num_faces = g->num_edges = g->num_dots = 0; + g->size_faces = g->size_edges = g->size_dots = 0; g->refcount = 1; g->lowest_x = g->lowest_y = g->highest_x = g->highest_y = 0; return g; @@ -123,7 +129,7 @@ grid_edge *grid_nearest_edge(grid *g, int x, int y) best_edge = NULL; for (i = 0; i < g->num_edges; i++) { - grid_edge *e = &g->edges[i]; + grid_edge *e = g->edges[i]; long e2; /* squared length of edge */ long a2, b2; /* squared lengths of other sides */ double dist; @@ -192,7 +198,7 @@ xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n\n"); if (which & SVG_FACES) { fprintf(fp, "<g>\n"); for (i = 0; i < g->num_faces; i++) { - grid_face *f = g->faces + i; + grid_face *f = g->faces[i]; fprintf(fp, "<polygon points=\""); for (j = 0; j < f->order; j++) { grid_dot *d = f->dots[j]; @@ -207,7 +213,7 @@ xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n\n"); if (which & SVG_EDGES) { fprintf(fp, "<g>\n"); for (i = 0; i < g->num_edges; i++) { - grid_edge *e = g->edges + i; + grid_edge *e = g->edges[i]; grid_dot *d1 = e->dot1, *d2 = e->dot2; fprintf(fp, "<line x1=\"%d\" y1=\"%d\" x2=\"%d\" y2=\"%d\" " @@ -220,7 +226,7 @@ xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n\n"); if (which & SVG_DOTS) { fprintf(fp, "<g>\n"); for (i = 0; i < g->num_dots; i++) { - grid_dot *d = g->dots + i; + grid_dot *d = g->dots[i]; fprintf(fp, "<ellipse cx=\"%d\" cy=\"%d\" rx=\"%d\" ry=\"%d\" fill=\"%s\" />", d->x, d->y, g->tilesize/20, g->tilesize/20, DOT_COLOUR); } @@ -259,12 +265,12 @@ static void grid_debug_basic(grid *g) int i; printf("--- Basic Grid Data ---\n"); for (i = 0; i < g->num_faces; i++) { - grid_face *f = g->faces + i; + grid_face *f = g->faces[i]; printf("Face %d: dots[", i); int j; for (j = 0; j < f->order; j++) { grid_dot *d = f->dots[j]; - printf("%s%d", j ? "," : "", (int)(d - g->dots)); + printf("%s%d", j ? "," : "", (int)(d->index)); } printf("]\n"); } @@ -282,38 +288,38 @@ static void grid_debug_derived(grid *g) int i; printf("--- Derived Grid Data ---\n"); for (i = 0; i < g->num_edges; i++) { - grid_edge *e = g->edges + i; + grid_edge *e = g->edges[i]; printf("Edge %d: dots[%d,%d] faces[%d,%d]\n", - i, (int)(e->dot1 - g->dots), (int)(e->dot2 - g->dots), - e->face1 ? (int)(e->face1 - g->faces) : -1, - e->face2 ? (int)(e->face2 - g->faces) : -1); + i, (int)(e->dot1->index), (int)(e->dot2->index), + e->face1 ? (int)(e->face1->index) : -1, + e->face2 ? (int)(e->face2->index) : -1); } /* faces */ for (i = 0; i < g->num_faces; i++) { - grid_face *f = g->faces + i; + grid_face *f = g->faces[i]; int j; printf("Face %d: faces[", i); for (j = 0; j < f->order; j++) { grid_edge *e = f->edges[j]; grid_face *f2 = (e->face1 == f) ? e->face2 : e->face1; - printf("%s%d", j ? "," : "", f2 ? (int)(f2 - g->faces) : -1); + printf("%s%d", j ? "," : "", f2 ? f2->index : -1); } printf("]\n"); } /* dots */ for (i = 0; i < g->num_dots; i++) { - grid_dot *d = g->dots + i; + grid_dot *d = g->dots[i]; int j; printf("Dot %d: dots[", i); for (j = 0; j < d->order; j++) { grid_edge *e = d->edges[j]; grid_dot *d2 = (e->dot1 == d) ? e->dot2 : e->dot1; - printf("%s%d", j ? "," : "", (int)(d2 - g->dots)); + printf("%s%d", j ? "," : "", d2->index); } printf("] faces["); for (j = 0; j < d->order; j++) { grid_face *f = d->faces[j]; - printf("%s%d", j ? "," : "", f ? (int)(f - g->faces) : -1); + printf("%s%d", j ? "," : "", f ? f->index : -1); } printf("]\n"); } @@ -378,10 +384,10 @@ static void grid_trim_vigorously(grid *g) for (j = 0; j < g->num_dots; j++) dotpairs[i*g->num_dots+j] = -1; for (i = 0; i < g->num_faces; i++) { - grid_face *f = g->faces + i; - int dot0 = f->dots[f->order-1] - g->dots; + grid_face *f = g->faces[i]; + int dot0 = f->dots[f->order-1]->index; for (j = 0; j < f->order; j++) { - int dot1 = f->dots[j] - g->dots; + int dot1 = f->dots[j]->index; dotpairs[dot0 * g->num_dots + dot1] = i; dot0 = dot1; } @@ -441,56 +447,48 @@ static void grid_trim_vigorously(grid *g) for (i = 0; i < g->num_dots; i++) dots[i] = 0; for (i = 0; i < g->num_faces; i++) { - grid_face *f = g->faces + i; + grid_face *f = g->faces[i]; bool keep = false; for (k = 0; k < f->order; k++) - if (dsf_canonify(dsf, f->dots[k] - g->dots) == j) + if (dsf_canonify(dsf, f->dots[k]->index) == j) keep = true; if (keep) { faces[i] = 1; for (k = 0; k < f->order; k++) - dots[f->dots[k]-g->dots] = 1; + dots[f->dots[k]->index] = 1; } } /* - * Work out the new indices of those faces and dots, when we - * compact the arrays containing them. + * Compact the faces array, rewriting the faces' indices and + * freeing the unwanted ones. */ - for (i = newfaces = 0; i < g->num_faces; i++) - faces[i] = (faces[i] ? newfaces++ : -1); - for (i = newdots = 0; i < g->num_dots; i++) - dots[i] = (dots[i] ? newdots++ : -1); - - /* - * Free the dynamically allocated 'dots' pointer lists in faces - * we're going to discard. - */ - for (i = 0; i < g->num_faces; i++) - if (faces[i] < 0) - sfree(g->faces[i].dots); + for (i = newfaces = 0; i < g->num_faces; i++) { + grid_face *f = g->faces[i]; + if (faces[i]) { + f->index = newfaces++; + g->faces[f->index] = f; + } else { + sfree(f->dots); + sfree(f); + } + } + g->num_faces = newfaces; /* - * Go through and compact the arrays. + * Compact the dots array, similarly. */ - for (i = 0; i < g->num_dots; i++) - if (dots[i] >= 0) { - grid_dot *dnew = g->dots + dots[i], *dold = g->dots + i; - *dnew = *dold; /* structure copy */ - } - for (i = 0; i < g->num_faces; i++) - if (faces[i] >= 0) { - grid_face *fnew = g->faces + faces[i], *fold = g->faces + i; - *fnew = *fold; /* structure copy */ - for (j = 0; j < fnew->order; j++) { - /* - * Reindex the dots in this face. - */ - k = fnew->dots[j] - g->dots; - fnew->dots[j] = g->dots + dots[k]; - } + for (i = newdots = 0; i < g->num_dots; i++) { + grid_dot *d = g->dots[i]; + if (dots[i]) { + d->index = newdots++; + g->dots[d->index] = d; + } else { + sfree(d->edges); + sfree(d->faces); + sfree(d); } - g->num_faces = newfaces; + } g->num_dots = newdots; sfree(dotpairs); @@ -512,7 +510,6 @@ static void grid_make_consistent(grid *g) { int i; tree234 *incomplete_edges; - grid_edge *next_new_edge; /* Where new edge will go into g->edges */ grid_debug_basic(g); @@ -520,14 +517,6 @@ static void grid_make_consistent(grid *g) * Generate edges */ - /* We know how many dots and faces there are, so we can find the exact - * number of edges from Euler's polyhedral formula: F + V = E + 2 . - * We use "-1", not "-2" here, because Euler's formula includes the - * infinite face, which we don't count. */ - g->num_edges = g->num_faces + g->num_dots - 1; - g->edges = snewn(g->num_edges, grid_edge); - next_new_edge = g->edges; - /* Iterate over faces, and over each face's dots, generating edges as we * go. As we find each new edge, we can immediately fill in the edge's * dots, but only one of the edge's faces. Later on in the iteration, we @@ -537,7 +526,7 @@ static void grid_make_consistent(grid *g) * their dots. */ incomplete_edges = newtree234(grid_edge_bydots_cmpfn); for (i = 0; i < g->num_faces; i++) { - grid_face *f = g->faces + i; + grid_face *f = g->faces[i]; int j; for (j = 0; j < f->order; j++) { grid_edge e; /* fake edge for searching */ @@ -555,18 +544,28 @@ static void grid_make_consistent(grid *g) * Edge is already removed from incomplete_edges. */ edge_found->face2 = f; } else { - assert(next_new_edge - g->edges < g->num_edges); - next_new_edge->dot1 = e.dot1; - next_new_edge->dot2 = e.dot2; - next_new_edge->face1 = f; - next_new_edge->face2 = NULL; /* potentially infinite face */ - add234(incomplete_edges, next_new_edge); - ++next_new_edge; + grid_edge *new_edge = snew(grid_edge); + new_edge->dot1 = e.dot1; + new_edge->dot2 = e.dot2; + new_edge->face1 = f; + new_edge->face2 = NULL; /* potentially infinite face */ + add234(incomplete_edges, new_edge); + + /* And add it to g->edges. */ + if (g->num_edges >= g->size_edges) { + int increment = g->num_edges / 4 + 128; + g->size_edges = (increment < INT_MAX - g->num_edges ? + g->num_edges + increment : INT_MAX); + g->edges = sresize(g->edges, g->size_edges, grid_edge *); + } + assert(g->num_edges < INT_MAX); + new_edge->index = g->num_edges++; + g->edges[new_edge->index] = new_edge; } } } freetree234(incomplete_edges); - + /* ====== Stage 2 ====== * For each face, build its edge list. */ @@ -574,7 +573,7 @@ static void grid_make_consistent(grid *g) /* Allocate space for each edge list. Can do this, because each face's * edge-list is the same size as its dot-list. */ for (i = 0; i < g->num_faces; i++) { - grid_face *f = g->faces + i; + grid_face *f = g->faces[i]; int j; f->edges = snewn(f->order, grid_edge*); /* Preload with NULLs, to help detect potential bugs. */ @@ -586,7 +585,7 @@ static void grid_make_consistent(grid *g) * the face's edge-list, after finding where it should go in the * sequence. */ for (i = 0; i < g->num_edges; i++) { - grid_edge *e = g->edges + i; + grid_edge *e = g->edges[i]; int j; for (j = 0; j < 2; j++) { grid_face *f = j ? e->face2 : e->face1; @@ -648,16 +647,16 @@ static void grid_make_consistent(grid *g) * allocate the right space for these lists. Pre-compute the sizes by * iterating over each edge and recording a tally against each dot. */ for (i = 0; i < g->num_dots; i++) { - g->dots[i].order = 0; + g->dots[i]->order = 0; } for (i = 0; i < g->num_edges; i++) { - grid_edge *e = g->edges + i; + grid_edge *e = g->edges[i]; ++(e->dot1->order); ++(e->dot2->order); } /* Now we have the sizes, pre-allocate the edge and face lists. */ for (i = 0; i < g->num_dots; i++) { - grid_dot *d = g->dots + i; + grid_dot *d = g->dots[i]; int j; assert(d->order >= 2); /* sanity check */ d->edges = snewn(d->order, grid_edge*); @@ -670,7 +669,7 @@ static void grid_make_consistent(grid *g) /* For each dot, need to find a face that touches it, so we can seed * the edge-face-edge-face process around each dot. */ for (i = 0; i < g->num_faces; i++) { - grid_face *f = g->faces + i; + grid_face *f = g->faces[i]; int j; for (j = 0; j < f->order; j++) { grid_dot *d = f->dots[j]; @@ -684,7 +683,7 @@ static void grid_make_consistent(grid *g) * blocks progress. But there's only one such face, so we will * succeed in finding every edge and face this way. */ for (i = 0; i < g->num_dots; i++) { - grid_dot *d = g->dots + i; + grid_dot *d = g->dots[i]; int current_face1 = 0; /* ascends clockwise */ int current_face2 = 0; /* descends anticlockwise */ @@ -781,7 +780,7 @@ static void grid_make_consistent(grid *g) /* Bounding rectangle */ for (i = 0; i < g->num_dots; i++) { - grid_dot *d = g->dots + i; + grid_dot *d = g->dots[i]; if (i == 0) { g->lowest_x = g->highest_x = d->x; g->lowest_y = g->highest_y = d->y; @@ -809,36 +808,52 @@ static int grid_point_cmp_fn(void *v1, void *v2) else return p2->x - p1->x; } -/* Add a new face to the grid, with its dot list allocated. - * Assumes there's enough space allocated for the new face in grid->faces */ +/* Add a new face to the grid, with its dot list allocated. */ static void grid_face_add_new(grid *g, int face_size) { int i; - grid_face *new_face = g->faces + g->num_faces; + grid_face *new_face = snew(grid_face); + assert(g->num_faces < INT_MAX); + if (g->num_faces >= g->size_faces) { + int increment = g->num_faces / 4 + 128; + g->size_faces = (increment < INT_MAX - g->num_faces ? + g->num_faces + increment : INT_MAX); + g->faces = sresize(g->faces, g->size_faces, grid_face *); + } + new_face->index = g->num_faces++; + g->faces[new_face->index] = new_face; + new_face->order = face_size; new_face->dots = snewn(face_size, grid_dot*); for (i = 0; i < face_size; i++) new_face->dots[i] = NULL; new_face->edges = NULL; new_face->has_incentre = false; - g->num_faces++; } -/* Assumes dot list has enough space */ static grid_dot *grid_dot_add_new(grid *g, int x, int y) { - grid_dot *new_dot = g->dots + g->num_dots; + grid_dot *new_dot = snew(grid_dot); + if (g->num_dots >= g->size_dots) { + int increment = g->num_dots / 4 + 128; + g->size_dots = (increment < INT_MAX - g->num_dots ? + g->num_dots + increment : INT_MAX); + g->dots = sresize(g->dots, g->size_dots, grid_dot *); + } + assert(g->num_dots < INT_MAX); + new_dot->index = g->num_dots++; + g->dots[new_dot->index] = new_dot; + new_dot->order = 0; new_dot->edges = NULL; new_dot->faces = NULL; new_dot->x = x; new_dot->y = y; - g->num_dots++; + return new_dot; } /* Retrieve a dot with these (x,y) coordinates. Either return an existing dot * in the dot_list, or add a new dot to the grid (and the dot_list) and - * return that. - * Assumes g->dots has enough capacity allocated */ + * return that. */ static grid_dot *grid_get_dot(grid *g, tree234 *dot_list, int x, int y) { grid_dot test, *ret; @@ -862,7 +877,7 @@ static grid_dot *grid_get_dot(grid *g, tree234 *dot_list, int x, int y) * previously been added, with the required number of dots allocated) */ static void grid_face_set_dot(grid *g, grid_dot *d, int position) { - grid_face *last_face = g->faces + g->num_faces - 1; + grid_face *last_face = g->faces[g->num_faces - 1]; last_face->dots[position] = d; } @@ -1420,16 +1435,10 @@ static grid *grid_new_square(int width, int height, const char *desc) /* Side length */ int a = SQUARE_TILESIZE; - /* Upper bounds - don't have to be exact */ - int max_faces = width * height; - int max_dots = (width + 1) * (height + 1); - tree234 *points; grid *g = grid_empty(); g->tilesize = a; - g->faces = snewn(max_faces, grid_face); - g->dots = snewn(max_dots, grid_dot); points = newtree234(grid_point_cmp_fn); @@ -1454,8 +1463,6 @@ static grid *grid_new_square(int width, int height, const char *desc) } freetree234(points); - assert(g->num_faces <= max_faces); - assert(g->num_dots <= max_dots); grid_make_consistent(g); return g; @@ -1495,16 +1502,10 @@ static grid *grid_new_honeycomb(int width, int height, const char *desc) int a = HONEY_A; int b = HONEY_B; - /* Upper bounds - don't have to be exact */ - int max_faces = width * height; - int max_dots = 2 * (width + 1) * (height + 1); - tree234 *points; grid *g = grid_empty(); g->tilesize = HONEY_TILESIZE; - g->faces = snewn(max_faces, grid_face); - g->dots = snewn(max_dots, grid_dot); points = newtree234(grid_point_cmp_fn); @@ -1535,8 +1536,6 @@ static grid *grid_new_honeycomb(int width, int height, const char *desc) } freetree234(points); - assert(g->num_faces <= max_faces); - assert(g->num_dots <= max_dots); grid_make_consistent(g); return g; @@ -1622,16 +1621,18 @@ static grid *grid_new_triangular(int width, int height, const char *desc) * 5x6t1:a022a212h1a1d1a12c2b11a012b1a20d1a0a12e */ - g->num_faces = width * height * 2; - g->num_dots = (width + 1) * (height + 1); - g->faces = snewn(g->num_faces, grid_face); - g->dots = snewn(g->num_dots, grid_dot); + g->num_faces = g->size_faces = width * height * 2; + g->num_dots = g->size_dots = (width + 1) * (height + 1); + g->faces = snewn(g->size_faces, grid_face *); + g->dots = snewn(g->size_dots, grid_dot *); /* generate dots */ index = 0; for (y = 0; y <= height; y++) { for (x = 0; x <= width; x++) { - grid_dot *d = g->dots + index; + grid_dot *d = snew(grid_dot); + d->index = index; + g->dots[d->index] = d; /* odd rows are offset to the right */ d->order = 0; d->edges = NULL; @@ -1647,8 +1648,11 @@ static grid *grid_new_triangular(int width, int height, const char *desc) for (y = 0; y < height; y++) { for (x = 0; x < width; x++) { /* initialise two faces for this (x,y) */ - grid_face *f1 = g->faces + index; - grid_face *f2 = f1 + 1; + grid_face *f1 = snew(grid_face), *f2 = snew(grid_face); + f1->index = index; + f2->index = index + 1; + g->faces[f1->index] = f1; + g->faces[f2->index] = f2; f1->edges = NULL; f1->order = 3; f1->dots = snewn(f1->order, grid_dot*); @@ -1661,19 +1665,19 @@ static grid *grid_new_triangular(int width, int height, const char *desc) /* face descriptions depend on whether the row-number is * odd or even */ if (y % 2) { - f1->dots[0] = g->dots + y * w + x; - f1->dots[1] = g->dots + (y + 1) * w + x + 1; - f1->dots[2] = g->dots + (y + 1) * w + x; - f2->dots[0] = g->dots + y * w + x; - f2->dots[1] = g->dots + y * w + x + 1; - f2->dots[2] = g->dots + (y + 1) * w + x + 1; + f1->dots[0] = g->dots[y * w + x]; + f1->dots[1] = g->dots[(y + 1) * w + x + 1]; + f1->dots[2] = g->dots[(y + 1) * w + x]; + f2->dots[0] = g->dots[y * w + x]; + f2->dots[1] = g->dots[y * w + x + 1]; + f2->dots[2] = g->dots[(y + 1) * w + x + 1]; } else { - f1->dots[0] = g->dots + y * w + x; - f1->dots[1] = g->dots + y * w + x + 1; - f1->dots[2] = g->dots + (y + 1) * w + x; - f2->dots[0] = g->dots + y * w + x + 1; - f2->dots[1] = g->dots + (y + 1) * w + x + 1; - f2->dots[2] = g->dots + (y + 1) * w + x; + f1->dots[0] = g->dots[y * w + x]; + f1->dots[1] = g->dots[y * w + x + 1]; + f1->dots[2] = g->dots[(y + 1) * w + x]; + f2->dots[0] = g->dots[y * w + x + 1]; + f2->dots[1] = g->dots[(y + 1) * w + x + 1]; + f2->dots[2] = g->dots[(y + 1) * w + x]; } index += 2; } @@ -1690,12 +1694,6 @@ static grid *grid_new_triangular(int width, int height, const char *desc) * 5x6t1:0_a1212c22c2a02a2f22a0c12a110d0e1c0c0a101121a1 */ tree234 *points = newtree234(grid_point_cmp_fn); - /* Upper bounds - don't have to be exact */ - int max_faces = height * (2*width+1); - int max_dots = (height+1) * (width+1) * 4; - - g->faces = snewn(max_faces, grid_face); - g->dots = snewn(max_dots, grid_dot); for (y = 0; y < height; y++) { /* @@ -1743,8 +1741,6 @@ static grid *grid_new_triangular(int width, int height, const char *desc) } freetree234(points); - assert(g->num_faces <= max_faces); - assert(g->num_dots <= max_dots); } grid_make_consistent(g); @@ -1786,16 +1782,10 @@ static grid *grid_new_snubsquare(int width, int height, const char *desc) int a = SNUBSQUARE_A; int b = SNUBSQUARE_B; - /* Upper bounds - don't have to be exact */ - int max_faces = 3 * width * height; - int max_dots = 2 * (width + 1) * (height + 1); - tree234 *points; grid *g = grid_empty(); g->tilesize = SNUBSQUARE_TILESIZE; - g->faces = snewn(max_faces, grid_face); - g->dots = snewn(max_dots, grid_dot); points = newtree234(grid_point_cmp_fn); @@ -1871,8 +1861,6 @@ static grid *grid_new_snubsquare(int width, int height, const char *desc) } freetree234(points); - assert(g->num_faces <= max_faces); - assert(g->num_dots <= max_dots); grid_make_consistent(g); return g; @@ -1911,16 +1899,10 @@ static grid *grid_new_cairo(int width, int height, const char *desc) int a = CAIRO_A; int b = CAIRO_B; - /* Upper bounds - don't have to be exact */ - int max_faces = 2 * width * height; - int max_dots = 3 * (width + 1) * (height + 1); - tree234 *points; grid *g = grid_empty(); g->tilesize = CAIRO_TILESIZE; - g->faces = snewn(max_faces, grid_face); - g->dots = snewn(max_dots, grid_dot); points = newtree234(grid_point_cmp_fn); @@ -1989,8 +1971,6 @@ static grid *grid_new_cairo(int width, int height, const char *desc) } freetree234(points); - assert(g->num_faces <= max_faces); - assert(g->num_dots <= max_dots); grid_make_consistent(g); return g; @@ -2030,16 +2010,10 @@ static grid *grid_new_greathexagonal(int width, int height, const char *desc) int a = GREATHEX_A; int b = GREATHEX_B; - /* Upper bounds - don't have to be exact */ - int max_faces = 6 * (width + 1) * (height + 1); - int max_dots = 6 * width * height; - tree234 *points; grid *g = grid_empty(); g->tilesize = GREATHEX_TILESIZE; - g->faces = snewn(max_faces, grid_face); - g->dots = snewn(max_dots, grid_dot); points = newtree234(grid_point_cmp_fn); @@ -2131,8 +2105,6 @@ static grid *grid_new_greathexagonal(int width, int height, const char *desc) } freetree234(points); - assert(g->num_faces <= max_faces); - assert(g->num_dots <= max_dots); grid_make_consistent(g); return g; @@ -2172,16 +2144,10 @@ static grid *grid_new_kagome(int width, int height, const char *desc) int a = KAGOME_A; int b = KAGOME_B; - /* Upper bounds - don't have to be exact */ - int max_faces = 6 * (width + 1) * (height + 1); - int max_dots = 6 * width * height; - tree234 *points; grid *g = grid_empty(); g->tilesize = KAGOME_TILESIZE; - g->faces = snewn(max_faces, grid_face); - g->dots = snewn(max_dots, grid_dot); points = newtree234(grid_point_cmp_fn); @@ -2239,8 +2205,6 @@ static grid *grid_new_kagome(int width, int height, const char *desc) } freetree234(points); - assert(g->num_faces <= max_faces); - assert(g->num_dots <= max_dots); grid_make_consistent(g); return g; @@ -2280,16 +2244,10 @@ static grid *grid_new_octagonal(int width, int height, const char *desc) int a = OCTAGONAL_A; int b = OCTAGONAL_B; - /* Upper bounds - don't have to be exact */ - int max_faces = 2 * width * height; - int max_dots = 4 * (width + 1) * (height + 1); - tree234 *points; grid *g = grid_empty(); g->tilesize = OCTAGONAL_TILESIZE; - g->faces = snewn(max_faces, grid_face); - g->dots = snewn(max_dots, grid_dot); points = newtree234(grid_point_cmp_fn); @@ -2334,8 +2292,6 @@ static grid *grid_new_octagonal(int width, int height, const char *desc) } freetree234(points); - assert(g->num_faces <= max_faces); - assert(g->num_dots <= max_dots); grid_make_consistent(g); return g; @@ -2375,16 +2331,10 @@ static grid *grid_new_kites(int width, int height, const char *desc) int a = KITE_A; int b = KITE_B; - /* Upper bounds - don't have to be exact */ - int max_faces = 6 * width * height; - int max_dots = 6 * (width + 1) * (height + 1); - tree234 *points; grid *g = grid_empty(); g->tilesize = KITE_TILESIZE; - g->faces = snewn(max_faces, grid_face); - g->dots = snewn(max_dots, grid_dot); points = newtree234(grid_point_cmp_fn); @@ -2466,8 +2416,6 @@ static grid *grid_new_kites(int width, int height, const char *desc) } freetree234(points); - assert(g->num_faces <= max_faces); - assert(g->num_dots <= max_dots); grid_make_consistent(g); return g; @@ -2520,16 +2468,10 @@ static grid *grid_new_floret(int width, int height, const char *desc) int qx = 4*px/5, qy = -py*2; /* |( 60, 52)| = 79.40 */ int rx = qx-px, ry = qy-py; /* |(-15, 78)| = 79.38 */ - /* Upper bounds - don't have to be exact */ - int max_faces = 6 * width * height; - int max_dots = 9 * (width + 1) * (height + 1); - tree234 *points; grid *g = grid_empty(); g->tilesize = FLORET_TILESIZE; - g->faces = snewn(max_faces, grid_face); - g->dots = snewn(max_dots, grid_dot); points = newtree234(grid_point_cmp_fn); @@ -2590,8 +2532,6 @@ static grid *grid_new_floret(int width, int height, const char *desc) } freetree234(points); - assert(g->num_faces <= max_faces); - assert(g->num_dots <= max_dots); grid_make_consistent(g); return g; @@ -2632,16 +2572,10 @@ static grid *grid_new_dodecagonal(int width, int height, const char *desc) int a = DODEC_A; int b = DODEC_B; - /* Upper bounds - don't have to be exact */ - int max_faces = 3 * width * height; - int max_dots = 14 * width * height; - tree234 *points; grid *g = grid_empty(); g->tilesize = DODEC_TILESIZE; - g->faces = snewn(max_faces, grid_face); - g->dots = snewn(max_dots, grid_dot); points = newtree234(grid_point_cmp_fn); @@ -2688,8 +2622,6 @@ static grid *grid_new_dodecagonal(int width, int height, const char *desc) } freetree234(points); - assert(g->num_faces <= max_faces); - assert(g->num_dots <= max_dots); grid_make_consistent(g); return g; @@ -2725,16 +2657,10 @@ static grid *grid_new_greatdodecagonal(int width, int height, const char *desc) int a = DODEC_A; int b = DODEC_B; - /* Upper bounds - don't have to be exact */ - int max_faces = 30 * width * height; - int max_dots = 200 * width * height; - tree234 *points; grid *g = grid_empty(); g->tilesize = DODEC_TILESIZE; - g->faces = snewn(max_faces, grid_face); - g->dots = snewn(max_dots, grid_dot); points = newtree234(grid_point_cmp_fn); @@ -2814,8 +2740,6 @@ static grid *grid_new_greatdodecagonal(int width, int height, const char *desc) } freetree234(points); - assert(g->num_faces <= max_faces); - assert(g->num_dots <= max_dots); grid_make_consistent(g); return g; @@ -2852,16 +2776,10 @@ static grid *grid_new_greatgreatdodecagonal(int width, int height, const char *d int a = DODEC_A; int b = DODEC_B; - /* Upper bounds - don't have to be exact */ - int max_faces = 50 * width * height; - int max_dots = 300 * width * height; - tree234 *points; grid *g = grid_empty(); g->tilesize = DODEC_TILESIZE; - g->faces = snewn(max_faces, grid_face); - g->dots = snewn(max_dots, grid_dot); points = newtree234(grid_point_cmp_fn); @@ -2996,8 +2914,6 @@ static grid *grid_new_greatgreatdodecagonal(int width, int height, const char *d } freetree234(points); - assert(g->num_faces <= max_faces); - assert(g->num_dots <= max_dots); grid_make_consistent(g); return g; @@ -3034,16 +2950,10 @@ static grid *grid_new_compassdodecagonal(int width, int height, const char *desc int a = DODEC_A; int b = DODEC_B; - /* Upper bounds - don't have to be exact */ - int max_faces = 6 * width * height; - int max_dots = 18 * width * height; - tree234 *points; grid *g = grid_empty(); g->tilesize = DODEC_TILESIZE; - g->faces = snewn(max_faces, grid_face); - g->dots = snewn(max_dots, grid_dot); points = newtree234(grid_point_cmp_fn); @@ -3105,8 +3015,6 @@ static grid *grid_new_compassdodecagonal(int width, int height, const char *desc } freetree234(points); - assert(g->num_faces <= max_faces); - assert(g->num_dots <= max_dots); grid_make_consistent(g); return g; @@ -3282,7 +3190,7 @@ static const char *grid_validate_desc_penrose(grid_type type, static grid *grid_new_penrose(int width, int height, int which, const char *desc) { - int max_faces, max_dots, tilesize = PENROSE_TILESIZE; + int tilesize = PENROSE_TILESIZE; int xsz, ysz, xoff, yoff, aoff; double rradius; @@ -3301,13 +3209,8 @@ static grid *grid_new_penrose(int width, int height, int which, const char *desc ps.new_tile = set_faces; ps.ctx = &sf_ctx; - max_faces = (width*3) * (height*3); /* somewhat paranoid... */ - max_dots = max_faces * 4; /* ditto... */ - g = grid_empty(); g->tilesize = tilesize; - g->faces = snewn(max_faces, grid_face); - g->dots = snewn(max_dots, grid_dot); points = newtree234(grid_point_cmp_fn); @@ -3338,8 +3241,6 @@ static grid *grid_new_penrose(int width, int height, int which, const char *desc penrose(&ps, which, aoff); freetree234(points); - assert(g->num_faces <= max_faces); - assert(g->num_dots <= max_dots); debug(("penrose: %d faces total (equivalent to %d wide by %d high)", g->num_faces, g->num_faces/height, g->num_faces/width)); @@ -3540,16 +3441,10 @@ static grid *grid_new_hats(int width, int height, const char *desc) error = grid_desc_to_hat_params(desc, &hp); assert(error == NULL && "grid_validate_desc_hats should have failed"); - /* Upper bounds - don't have to be exact */ - int max_faces = (width * height * 6 + 7) / 8; - int max_dots = width * height * 6 + width * 2 + height * 2 + 1; - struct hatcontext ctx[1]; ctx->g = grid_empty(); ctx->g->tilesize = HATS_TILESIZE; - ctx->g->faces = snewn(max_faces, grid_face); - ctx->g->dots = snewn(max_dots, grid_dot); ctx->points = newtree234(grid_point_cmp_fn); @@ -3696,30 +3591,10 @@ static grid *grid_new_spectres(int width, int height, const char *desc) error = grid_desc_to_spectre_params(desc, &sp); assert(error == NULL && "grid_validate_desc_spectres should have failed"); - /* - * Bound on the number of faces: the area of a single face in the - * output coordinates is 24 + 24 rt3, which is between 65 and 66. - * Every face fits strictly inside the target rectangle, so the - * number of faces times a lower bound on their area can't exceed - * the area of the rectangle we give to spectre_tiling_generate. - */ - int max_faces = width2 * height2 / 65; - - /* - * Bound on number of dots: 14*faces is certainly enough, but - * quite wasteful given that _most_ dots are shared between at - * least two faces. But to get a better estimate we'd have to - * figure out a bound for the number of dots on the perimeter, - * which is the number by which the count exceeds 14*faces/2. - */ - int max_dots = 14 * max_faces; - struct spectrecontext ctx[1]; ctx->g = grid_empty(); ctx->g->tilesize = SPECTRE_TILESIZE; - ctx->g->faces = snewn(max_faces, grid_face); - ctx->g->dots = snewn(max_dots, grid_dot); ctx->points = newtree234(grid_point_cmp_fn); @@ -33,6 +33,7 @@ typedef struct grid_edge grid_edge; typedef struct grid_dot grid_dot; struct grid_face { + int index; /* index in grid->faces[] where this face appears */ int order; /* Number of edges, also the number of dots */ grid_edge **edges; /* edges around this face */ grid_dot **dots; /* corners of this face */ @@ -56,8 +57,10 @@ struct grid_face { struct grid_edge { grid_dot *dot1, *dot2; grid_face *face1, *face2; /* Use NULL for the infinite outside face */ + int index; /* index in grid->edges[] where this edge appears */ }; struct grid_dot { + int index; /* index in grid->dots[] where this dot appears */ int order; grid_edge **edges; grid_face **faces; /* A NULL grid_face* means infinite outside face */ @@ -69,11 +72,13 @@ struct grid_dot { int x, y; }; typedef struct grid { - /* These are (dynamically allocated) arrays of all the - * faces, edges, dots that are in the grid. */ - int num_faces; grid_face *faces; - int num_edges; grid_edge *edges; - int num_dots; grid_dot *dots; + /* Arrays of all the faces, edges, dots that are in the grid. + * The arrays themselves are dynamically allocated, and so is each object + * inside them. num_foo indicates the number of things actually stored, + * and size_foo indicates the allocated size of the array. */ + int num_faces, size_faces; grid_face **faces; + int num_edges, size_edges; grid_edge **edges; + int num_dots, size_dots; grid_dot **dots; /* Cache the bounding-box of the grid, so the drawing-code can quickly * figure out the proper scaling to draw onto a given area. */ @@ -83,7 +83,7 @@ static bool can_colour_face(grid *g, char* board, int face_index, enum face_colour colour) { int i, j; - grid_face *test_face = g->faces + face_index; + grid_face *test_face = g->faces[face_index]; grid_face *starting_face, *current_face; grid_dot *starting_dot; int transitions; @@ -348,7 +348,7 @@ void generate_loop(grid *g, char *board, random_state *rs, * to check every face of the board (the grid structure does not keep a * list of the infinite face's neighbours). */ for (i = 0; i < num_faces; i++) { - grid_face *f = g->faces + i; + grid_face *f = g->faces[i]; struct face_score *fs = face_scores + i; if (board[i] != FACE_GREY) continue; /* We need the full colourability check here, it's not enough simply @@ -430,7 +430,7 @@ void generate_loop(grid *g, char *board, random_state *rs, del234(darkable_faces_sorted, fs); /* Remember which face we've just coloured */ - cur_face = g->faces + i; + cur_face = g->faces[i]; /* The face we've just coloured potentially affects the colourability * and the scores of any neighbouring faces (touching at a corner or @@ -456,7 +456,7 @@ void generate_loop(grid *g, char *board, random_state *rs, if (FACE_COLOUR(f) != FACE_GREY) continue; /* Find the face index and face_score* corresponding to f */ - fi = f - g->faces; + fi = f->index; fs = face_scores + fi; /* Remove from lightable list if it's in there. We do this, @@ -517,7 +517,7 @@ void generate_loop(grid *g, char *board, random_state *rs, enum face_colour opp = (board[j] == FACE_WHITE) ? FACE_BLACK : FACE_WHITE; if (can_colour_face(g, board, j, opp)) { - grid_face *face = g->faces +j; + grid_face *face = g->faces[j]; if (do_random_pass) { /* final random pass */ if (!random_upto(rs, 10)) @@ -13,7 +13,7 @@ enum face_colour { FACE_WHITE, FACE_GREY, FACE_BLACK }; /* face should be of type grid_face* here. */ #define FACE_COLOUR(face) \ ( (face) == NULL ? FACE_BLACK : \ - board[(face) - g->faces] ) + board[(face)->index] ) typedef int (*loopgen_bias_fn_t)(void *ctx, char *board, int face); @@ -1097,7 +1097,7 @@ static char *game_text_format(const game_state *state) assert(state->grid_type == 0); /* Work out the basic size unit */ - f = g->faces; /* first face */ + f = g->faces[0]; /* first face */ assert(f->order == 4); /* The dots are ordered clockwise, so the two opposite * corners are guaranteed to span the square */ @@ -1120,7 +1120,7 @@ static char *game_text_format(const game_state *state) /* Fill in edge info */ for (i = 0; i < g->num_edges; i++) { - grid_edge *e = g->edges + i; + grid_edge *e = g->edges[i]; /* Cell coordinates, from (0,0) to (w-1,h-1) */ int x1 = (e->dot1->x - g->lowest_x) / cell_size; int x2 = (e->dot2->x - g->lowest_x) / cell_size; @@ -1148,7 +1148,7 @@ static char *game_text_format(const game_state *state) for (i = 0; i < g->num_faces; i++) { int x1, x2, y1, y2; - f = g->faces + i; + f = g->faces[i]; assert(f->order == 4); /* Cell coordinates, from (0,0) to (w-1,h-1) */ x1 = (f->dots[0]->x - g->lowest_x) / cell_size; @@ -1228,26 +1228,26 @@ static bool solver_set_line(solver_state *sstate, int i, #endif g = state->game_grid; - e = g->edges + i; + e = g->edges[i]; /* Update the cache for both dots and both faces affected by this. */ if (line_new == LINE_YES) { - sstate->dot_yes_count[e->dot1 - g->dots]++; - sstate->dot_yes_count[e->dot2 - g->dots]++; + sstate->dot_yes_count[e->dot1->index]++; + sstate->dot_yes_count[e->dot2->index]++; if (e->face1) { - sstate->face_yes_count[e->face1 - g->faces]++; + sstate->face_yes_count[e->face1->index]++; } if (e->face2) { - sstate->face_yes_count[e->face2 - g->faces]++; + sstate->face_yes_count[e->face2->index]++; } } else { - sstate->dot_no_count[e->dot1 - g->dots]++; - sstate->dot_no_count[e->dot2 - g->dots]++; + sstate->dot_no_count[e->dot1->index]++; + sstate->dot_no_count[e->dot2->index]++; if (e->face1) { - sstate->face_no_count[e->face1 - g->faces]++; + sstate->face_no_count[e->face1->index]++; } if (e->face2) { - sstate->face_no_count[e->face2 - g->faces]++; + sstate->face_no_count[e->face2->index]++; } } @@ -1271,10 +1271,10 @@ static bool merge_dots(solver_state *sstate, int edge_index) { int i, j, len; grid *g = sstate->state->game_grid; - grid_edge *e = g->edges + edge_index; + grid_edge *e = g->edges[edge_index]; - i = e->dot1 - g->dots; - j = e->dot2 - g->dots; + i = e->dot1->index; + j = e->dot2->index; i = dsf_canonify(sstate->dotdsf, i); j = dsf_canonify(sstate->dotdsf, j); @@ -1332,12 +1332,12 @@ static int dot_order(const game_state* state, int dot, char line_type) { int n = 0; grid *g = state->game_grid; - grid_dot *d = g->dots + dot; + grid_dot *d = g->dots[dot]; int i; for (i = 0; i < d->order; i++) { grid_edge *e = d->edges[i]; - if (state->lines[e - g->edges] == line_type) + if (state->lines[e->index] == line_type) ++n; } return n; @@ -1349,12 +1349,12 @@ static int face_order(const game_state* state, int face, char line_type) { int n = 0; grid *g = state->game_grid; - grid_face *f = g->faces + face; + grid_face *f = g->faces[face]; int i; for (i = 0; i < f->order; i++) { grid_edge *e = f->edges[i]; - if (state->lines[e - g->edges] == line_type) + if (state->lines[e->index] == line_type) ++n; } return n; @@ -1375,10 +1375,10 @@ static bool dot_setall(solver_state *sstate, int dot, return false; g = state->game_grid; - d = g->dots + dot; + d = g->dots[dot]; for (i = 0; i < d->order; i++) { - int line_index = d->edges[i] - g->edges; + int line_index = d->edges[i]->index; if (state->lines[line_index] == old_type) { r = solver_set_line(sstate, line_index, new_type); assert(r); @@ -1402,10 +1402,10 @@ static bool face_setall(solver_state *sstate, int face, return false; g = state->game_grid; - f = g->faces + face; + f = g->faces[face]; for (i = 0; i < f->order; i++) { - int line_index = f->edges[i] - g->edges; + int line_index = f->edges[i]->index; if (state->lines[line_index] == old_type) { r = solver_set_line(sstate, line_index, new_type); assert(r); @@ -1434,7 +1434,7 @@ static void add_full_clues(game_state *state, random_state *rs) * algorithm does work, and there aren't any GREY faces still there. */ memset(clues, 0, g->num_faces); for (i = 0; i < g->num_edges; i++) { - grid_edge *e = g->edges + i; + grid_edge *e = g->edges[i]; grid_face *f1 = e->face1; grid_face *f2 = e->face2; enum face_colour c1 = FACE_COLOUR(f1); @@ -1442,8 +1442,8 @@ static void add_full_clues(game_state *state, random_state *rs) assert(c1 != FACE_GREY); assert(c2 != FACE_GREY); if (c1 != c2) { - if (f1) clues[f1 - g->faces]++; - if (f2) clues[f2 - g->faces]++; + if (f1) clues[f1->index]++; + if (f2) clues[f2->index]++; } } sfree(board); @@ -1725,8 +1725,8 @@ static bool check_completion(game_state *state) /* Build the dsf. */ for (i = 0; i < g->num_edges; i++) { if (state->lines[i] == LINE_YES) { - grid_edge *e = g->edges + i; - int d1 = e->dot1 - g->dots, d2 = e->dot2 - g->dots; + grid_edge *e = g->edges[i]; + int d1 = e->dot1->index, d2 = e->dot2->index; dsf_merge(dsf, d1, d2); } } @@ -1751,10 +1751,10 @@ static bool check_completion(game_state *state) int unknown = dot_order(state, i, LINE_UNKNOWN); if ((yes == 1 && unknown == 0) || (yes >= 3)) { /* violation, so mark all YES edges as errors */ - grid_dot *d = g->dots + i; + grid_dot *d = g->dots[i]; int j; for (j = 0; j < d->order; j++) { - int e = d->edges[j] - g->edges; + int e = d->edges[j]->index; if (state->lines[e] == LINE_YES) state->line_errors[e] = true; } @@ -1817,8 +1817,8 @@ static bool check_completion(game_state *state) */ for (i = 0; i < g->num_edges; i++) { if (state->lines[i] == LINE_YES) { - grid_edge *e = g->edges + i; - int d1 = e->dot1 - g->dots; /* either endpoint is good enough */ + grid_edge *e = g->edges[i]; + int d1 = e->dot1->index; /* either endpoint is good enough */ int comp = dsf_canonify(dsf, d1); if ((component_state[comp] == COMP_PATH && -1 != largest_comp) || @@ -1916,11 +1916,10 @@ static int dline_index_from_dot(grid *g, grid_dot *d, int i) if (i2 == d->order) i2 = 0; e2 = d->edges[i2]; #endif - ret = 2 * (e - g->edges) + ((e->dot1 == d) ? 1 : 0); + ret = 2 * (e->index) + ((e->dot1 == d) ? 1 : 0); #ifdef DEBUG_DLINES printf("dline_index_from_dot: d=%d,i=%d, edges [%d,%d] - %d\n", - (int)(d - g->dots), i, (int)(e - g->edges), - (int)(e2 - g->edges), ret); + (int)(d->index), i, (int)(e->index), (int)(e2 ->index), ret); #endif return ret; } @@ -1939,11 +1938,10 @@ static int dline_index_from_face(grid *g, grid_face *f, int i) if (i2 < 0) i2 += f->order; e2 = f->edges[i2]; #endif - ret = 2 * (e - g->edges) + ((e->dot1 == d) ? 1 : 0); + ret = 2 * (e->index) + ((e->dot1 == d) ? 1 : 0); #ifdef DEBUG_DLINES printf("dline_index_from_face: f=%d,i=%d, edges [%d,%d] - %d\n", - (int)(f - g->faces), i, (int)(e - g->edges), - (int)(e2 - g->edges), ret); + (int)(f->index), i, (int)(e->index), (int)(e2->index), ret); #endif return ret; } @@ -2001,9 +1999,9 @@ static bool dline_set_opp_atleastone(solver_state *sstate, opp2 = opp + 1; if (opp2 == N) opp2 = 0; /* Check if opp, opp2 point to LINE_UNKNOWNs */ - if (state->lines[d->edges[opp] - g->edges] != LINE_UNKNOWN) + if (state->lines[d->edges[opp]->index] != LINE_UNKNOWN) continue; - if (state->lines[d->edges[opp2] - g->edges] != LINE_UNKNOWN) + if (state->lines[d->edges[opp2]->index] != LINE_UNKNOWN) continue; /* Found opposite UNKNOWNS and they're next to each other */ opp_dline_index = dline_index_from_dot(g, d, opp); @@ -2025,18 +2023,18 @@ static bool face_setall_identical(solver_state *sstate, int face_index, bool retval = false; game_state *state = sstate->state; grid *g = state->game_grid; - grid_face *f = g->faces + face_index; + grid_face *f = g->faces[face_index]; int N = f->order; int i, j; int can1, can2; bool inv1, inv2; for (i = 0; i < N; i++) { - int line1_index = f->edges[i] - g->edges; + int line1_index = f->edges[i]->index; if (state->lines[line1_index] != LINE_UNKNOWN) continue; for (j = i + 1; j < N; j++) { - int line2_index = f->edges[j] - g->edges; + int line2_index = f->edges[j]->index; if (state->lines[line2_index] != LINE_UNKNOWN) continue; @@ -2060,9 +2058,8 @@ static void find_unknowns(game_state *state, int *e /* Returned edge indices */) { int c = 0; - grid *g = state->game_grid; while (c < expected_count) { - int line_index = *edge_list - g->edges; + int line_index = (*edge_list)->index; if (state->lines[line_index] == LINE_UNKNOWN) { e[c] = line_index; c++; @@ -2191,7 +2188,7 @@ static int trivial_deductions(solver_state *sstate) /* Per-face deductions */ for (i = 0; i < g->num_faces; i++) { - grid_face *f = g->faces + i; + grid_face *f = g->faces[i]; if (sstate->face_solved[i]) continue; @@ -2249,22 +2246,22 @@ static int trivial_deductions(solver_state *sstate) int j, k, e1, e2, e, d; for (j = 0; j < f->order; j++) { - e1 = f->edges[j] - g->edges; - e2 = f->edges[j+1 < f->order ? j+1 : 0] - g->edges; + e1 = f->edges[j]->index; + e2 = f->edges[j+1 < f->order ? j+1 : 0]->index; - if (g->edges[e1].dot1 == g->edges[e2].dot1 || - g->edges[e1].dot1 == g->edges[e2].dot2) { - d = g->edges[e1].dot1 - g->dots; + if (g->edges[e1]->dot1 == g->edges[e2]->dot1 || + g->edges[e1]->dot1 == g->edges[e2]->dot2) { + d = g->edges[e1]->dot1->index; } else { - assert(g->edges[e1].dot2 == g->edges[e2].dot1 || - g->edges[e1].dot2 == g->edges[e2].dot2); - d = g->edges[e1].dot2 - g->dots; + assert(g->edges[e1]->dot2 == g->edges[e2]->dot1 || + g->edges[e1]->dot2 == g->edges[e2]->dot2); + d = g->edges[e1]->dot2->index; } if (state->lines[e1] == LINE_UNKNOWN && state->lines[e2] == LINE_UNKNOWN) { - for (k = 0; k < g->dots[d].order; k++) { - int e = g->dots[d].edges[k] - g->edges; + for (k = 0; k < g->dots[d]->order; k++) { + int e = g->dots[d]->edges[k]->index; if (state->lines[e] == LINE_YES) goto found; /* multi-level break */ } @@ -2278,7 +2275,7 @@ static int trivial_deductions(solver_state *sstate) * they're e1 and e2. */ for (j = 0; j < f->order; j++) { - e = f->edges[j] - g->edges; + e = f->edges[j]->index; if (state->lines[e] == LINE_UNKNOWN && e != e1 && e != e2) { bool r = solver_set_line(sstate, e, LINE_YES); assert(r); @@ -2292,7 +2289,7 @@ static int trivial_deductions(solver_state *sstate) /* Per-dot deductions */ for (i = 0; i < g->num_dots; i++) { - grid_dot *d = g->dots + i; + grid_dot *d = g->dots[i]; int yes, no, unknown; if (sstate->dot_solved[i]) @@ -2389,7 +2386,7 @@ static int dline_deductions(solver_state *sstate) for (i = 0; i < g->num_faces; i++) { int maxs[MAX_FACE_SIZE][MAX_FACE_SIZE]; int mins[MAX_FACE_SIZE][MAX_FACE_SIZE]; - grid_face *f = g->faces + i; + grid_face *f = g->faces[i]; int N = f->order; int j,m; int clue = state->clues[i]; @@ -2400,7 +2397,7 @@ static int dline_deductions(solver_state *sstate) /* Calculate the (j,j+1) entries */ for (j = 0; j < N; j++) { - int edge_index = f->edges[j] - g->edges; + int edge_index = f->edges[j]->index; int dline_index; enum line_state line1 = state->lines[edge_index]; enum line_state line2; @@ -2411,7 +2408,7 @@ static int dline_deductions(solver_state *sstate) mins[j][k] = (line1 == LINE_YES) ? 1 : 0; /* Calculate the (j,j+2) entries */ dline_index = dline_index_from_face(g, f, k); - edge_index = f->edges[k] - g->edges; + edge_index = f->edges[k]->index; line2 = state->lines[edge_index]; k++; if (k >= N) k = 0; @@ -2456,7 +2453,7 @@ static int dline_deductions(solver_state *sstate) for (j = 0; j < N; j++) { int k; grid_edge *e = f->edges[j]; - int line_index = e - g->edges; + int line_index = e->index; int dline_index; if (state->lines[line_index] != LINE_UNKNOWN) @@ -2491,7 +2488,7 @@ static int dline_deductions(solver_state *sstate) if (sstate->diff >= DIFF_TRICKY) { /* Now see if we can make dline deduction for edges{j,j+1} */ e = f->edges[k]; - if (state->lines[e - g->edges] != LINE_UNKNOWN) + if (state->lines[e->index] != LINE_UNKNOWN) /* Only worth doing this for an UNKNOWN,UNKNOWN pair. * Dlines where one of the edges is known, are handled in the * dot-deductions */ @@ -2523,7 +2520,7 @@ static int dline_deductions(solver_state *sstate) /* ------ Dot deductions ------ */ for (i = 0; i < g->num_dots; i++) { - grid_dot *d = g->dots + i; + grid_dot *d = g->dots[i]; int N = d->order; int yes, no, unknown; int j; @@ -2541,8 +2538,8 @@ static int dline_deductions(solver_state *sstate) k = j + 1; if (k >= N) k = 0; dline_index = dline_index_from_dot(g, d, j); - line1_index = d->edges[j] - g->edges; - line2_index = d->edges[k] - g->edges; + line1_index = d->edges[j]->index; + line2_index = d->edges[k] ->index; line1 = state->lines[line1_index]; line2 = state->lines[line2_index]; @@ -2639,7 +2636,7 @@ static int dline_deductions(solver_state *sstate) int opp_index; if (opp == j || opp == k) continue; - opp_index = d->edges[opp] - g->edges; + opp_index = d->edges[opp]->index; if (state->lines[opp_index] == LINE_UNKNOWN) { solver_set_line(sstate, opp_index, LINE_YES); @@ -2690,7 +2687,7 @@ static int linedsf_deductions(solver_state *sstate) if (clue < 0) continue; - N = g->faces[i].order; + N = g->faces[i]->order; yes = sstate->face_yes_count[i]; if (yes + 1 == clue) { if (face_setall_identical(sstate, i, LINE_NO)) @@ -2708,14 +2705,14 @@ static int linedsf_deductions(solver_state *sstate) /* Deductions with small number of LINE_UNKNOWNs, based on overall * parity of lines. */ - diff_tmp = parity_deductions(sstate, g->faces[i].edges, + diff_tmp = parity_deductions(sstate, g->faces[i]->edges, (clue - yes) % 2, unknown); diff = min(diff, diff_tmp); } /* ------ Dot deductions ------ */ for (i = 0; i < g->num_dots; i++) { - grid_dot *d = g->dots + i; + grid_dot *d = g->dots[i]; int N = d->order; int j; int yes, no, unknown; @@ -2728,12 +2725,12 @@ static int linedsf_deductions(solver_state *sstate) int can1, can2; bool inv1, inv2; int j2; - line1_index = d->edges[j] - g->edges; + line1_index = d->edges[j]->index; if (state->lines[line1_index] != LINE_UNKNOWN) continue; j2 = j + 1; if (j2 == N) j2 = 0; - line2_index = d->edges[j2] - g->edges; + line2_index = d->edges[j2]->index; if (state->lines[line2_index] != LINE_UNKNOWN) continue; /* Infer dline flags from linedsf */ @@ -2855,9 +2852,9 @@ static int loop_deductions(solver_state *sstate) * loop it would create is a solution. */ for (i = 0; i < g->num_edges; i++) { - grid_edge *e = g->edges + i; - int d1 = e->dot1 - g->dots; - int d2 = e->dot2 - g->dots; + grid_edge *e = g->edges[i]; + int d1 = e->dot1->index; + int d2 = e->dot2->index; int eqclass, val; if (state->lines[i] != LINE_UNKNOWN) continue; @@ -2894,13 +2891,13 @@ static int loop_deductions(solver_state *sstate) */ sm1_nearby = 0; if (e->face1) { - int f = e->face1 - g->faces; + int f = e->face1->index; int c = state->clues[f]; if (c >= 0 && sstate->face_yes_count[f] == c - 1) sm1_nearby++; } if (e->face2) { - int f = e->face2 - g->faces; + int f = e->face2->index; int c = state->clues[f]; if (c >= 0 && sstate->face_yes_count[f] == c - 1) sm1_nearby++; @@ -3065,7 +3062,7 @@ static char *interpret_move(const game_state *state, game_ui *ui, if (e == NULL) return NULL; - i = e - g->edges; + i = e->index; /* I think it's only possible to play this game with mouse clicks, sorry */ /* Maybe will add mouse drag support some time */ @@ -3126,7 +3123,7 @@ static char *interpret_move(const game_state *state, game_ui *ui, for (j = n_found = 0; j < dot->order; j++) { grid_edge *e_candidate = dot->edges[j]; - int i_candidate = e_candidate - g->edges; + int i_candidate = e_candidate->index; if (e_candidate != e_this && (ui->autofollow == AF_FIXED || state->lines[i] == LINE_NO || @@ -3137,7 +3134,7 @@ static char *interpret_move(const game_state *state, game_ui *ui, } if (n_found != 1 || - state->lines[e_next - g->edges] != state->lines[i]) + state->lines[e_next->index] != state->lines[i]) break; if (e_next == e) { @@ -3164,7 +3161,7 @@ static char *interpret_move(const game_state *state, game_ui *ui, } e_this = e_next; movelen += sprintf(movebuf+movelen, "%d%c", - (int)(e_this - g->edges), button_char); + (int)(e_this->index), button_char); } autofollow_done:; } @@ -3237,7 +3234,7 @@ static void grid_to_screen(const game_drawstate *ds, const grid *g, static void face_text_pos(const game_drawstate *ds, const grid *g, grid_face *f, int *xret, int *yret) { - int faceindex = f - g->faces; + int faceindex = f->index; /* * Return the cached position for this face, if we've already @@ -3280,7 +3277,7 @@ static void game_redraw_clue(drawing *dr, game_drawstate *ds, const game_state *state, int i) { grid *g = state->game_grid; - grid_face *f = g->faces + i; + grid_face *f = g->faces[i]; int x, y; char c[20]; @@ -3345,7 +3342,7 @@ static void game_redraw_line(drawing *dr, game_drawstate *ds,const game_ui *ui, const game_state *state, int i, int phase) { grid *g = state->game_grid; - grid_edge *e = g->edges + i; + grid_edge *e = g->edges[i]; int x1, x2, y1, y2; int line_colour; @@ -3384,7 +3381,7 @@ static void game_redraw_dot(drawing *dr, game_drawstate *ds, const game_state *state, int i) { grid *g = state->game_grid; - grid_dot *d = g->dots + i; + grid_dot *d = g->dots[i]; int x, y; grid_to_screen(ds, g, d->x, d->y, &x, &y); @@ -3415,20 +3412,20 @@ static void game_redraw_in_rect(drawing *dr, game_drawstate *ds, for (i = 0; i < g->num_faces; i++) { if (state->clues[i] >= 0) { - face_text_bbox(ds, g, &g->faces[i], &bx, &by, &bw, &bh); + face_text_bbox(ds, g, g->faces[i], &bx, &by, &bw, &bh); if (boxes_intersect(x, y, w, h, bx, by, bw, bh)) game_redraw_clue(dr, ds, state, i); } } for (phase = 0; phase < NPHASES; phase++) { for (i = 0; i < g->num_edges; i++) { - edge_bbox(ds, g, &g->edges[i], &bx, &by, &bw, &bh); + edge_bbox(ds, g, g->edges[i], &bx, &by, &bw, &bh); if (boxes_intersect(x, y, w, h, bx, by, bw, bh)) game_redraw_line(dr, ds, ui, state, i, phase); } } for (i = 0; i < g->num_dots; i++) { - dot_bbox(ds, g, &g->dots[i], &bx, &by, &bw, &bh); + dot_bbox(ds, g, g->dots[i], &bx, &by, &bw, &bh); if (boxes_intersect(x, y, w, h, bx, by, bw, bh)) game_redraw_dot(dr, ds, state, i); } @@ -3488,7 +3485,7 @@ static void game_redraw(drawing *dr, game_drawstate *ds, /* First, trundle through the faces. */ for (i = 0; i < g->num_faces; i++) { - grid_face *f = g->faces + i; + grid_face *f = g->faces[i]; int sides = f->order; int yes_order, no_order; bool clue_mistake; @@ -3588,7 +3585,7 @@ static void game_redraw(drawing *dr, game_drawstate *ds, /* Right. Now we roll up our sleeves. */ for (i = 0; i < nfaces; i++) { - grid_face *f = g->faces + faces[i]; + grid_face *f = g->faces[faces[i]]; int x, y, w, h; face_text_bbox(ds, g, f, &x, &y, &w, &h); @@ -3596,7 +3593,7 @@ static void game_redraw(drawing *dr, game_drawstate *ds, } for (i = 0; i < nedges; i++) { - grid_edge *e = g->edges + edges[i]; + grid_edge *e = g->edges[edges[i]]; int x, y, w, h; edge_bbox(ds, g, e, &x, &y, &w, &h); @@ -3660,7 +3657,7 @@ static void game_print(drawing *dr, const game_state *state, const game_ui *ui, for (i = 0; i < g->num_dots; i++) { int x, y; - grid_to_screen(ds, g, g->dots[i].x, g->dots[i].y, &x, &y); + grid_to_screen(ds, g, g->dots[i]->x, g->dots[i]->y, &x, &y); draw_circle(dr, x, y, ds->tilesize / 15, ink, ink); } @@ -3668,7 +3665,7 @@ static void game_print(drawing *dr, const game_state *state, const game_ui *ui, * Clues. */ for (i = 0; i < g->num_faces; i++) { - grid_face *f = g->faces + i; + grid_face *f = g->faces[i]; int clue = state->clues[i]; if (clue >= 0) { char c[20]; @@ -3686,7 +3683,7 @@ static void game_print(drawing *dr, const game_state *state, const game_ui *ui, */ for (i = 0; i < g->num_edges; i++) { int thickness = (state->lines[i] == LINE_YES) ? 30 : 150; - grid_edge *e = g->edges + i; + grid_edge *e = g->edges[i]; int x1, y1, x2, y2; grid_to_screen(ds, g, e->dot1->x, e->dot1->y, &x1, &y1); grid_to_screen(ds, g, e->dot2->x, e->dot2->y, &x2, &y2); @@ -980,9 +980,9 @@ static int pearl_loopgen_bias(void *vctx, char *board, int face) * to reprocess the edges for this boundary. */ if (oldface == c || newface == c) { - grid_face *f = &g->faces[face]; + grid_face *f = g->faces[face]; for (k = 0; k < f->order; k++) - tdq_add(b->edges_todo, f->edges[k] - g->edges); + tdq_add(b->edges_todo, f->edges[k]->index); } } } @@ -998,15 +998,15 @@ static int pearl_loopgen_bias(void *vctx, char *board, int face) * the vertextypes_todo list. */ while ((j = tdq_remove(b->edges_todo)) >= 0) { - grid_edge *e = &g->edges[j]; - int fc1 = e->face1 ? board[e->face1 - g->faces] : FACE_BLACK; - int fc2 = e->face2 ? board[e->face2 - g->faces] : FACE_BLACK; + grid_edge *e = g->edges[j]; + int fc1 = e->face1 ? board[e->face1->index] : FACE_BLACK; + int fc2 = e->face2 ? board[e->face2->index] : FACE_BLACK; bool oldedge = b->edges[j]; bool newedge = (fc1==c) ^ (fc2==c); if (oldedge != newedge) { b->edges[j] = newedge; - tdq_add(b->vertextypes_todo, e->dot1 - g->dots); - tdq_add(b->vertextypes_todo, e->dot2 - g->dots); + tdq_add(b->vertextypes_todo, e->dot1->index); + tdq_add(b->vertextypes_todo, e->dot2->index); } } @@ -1021,7 +1021,7 @@ static int pearl_loopgen_bias(void *vctx, char *board, int face) * old neighbours. */ while ((j = tdq_remove(b->vertextypes_todo)) >= 0) { - grid_dot *d = &g->dots[j]; + grid_dot *d = g->dots[j]; int neighbours[2], type = 0, n = 0; for (k = 0; k < d->order; k++) { @@ -1029,10 +1029,10 @@ static int pearl_loopgen_bias(void *vctx, char *board, int face) grid_dot *d2 = (e->dot1 == d ? e->dot2 : e->dot1); /* dir == 0,1,2,3 for an edge going L,U,R,D */ int dir = (d->y == d2->y) + 2*(d->x+d->y > d2->x+d2->y); - int ei = e - g->edges; + int ei = e->index; if (b->edges[ei]) { type |= 1 << dir; - neighbours[n] = d2 - g->dots; + neighbours[n] = d2->index; n++; } } @@ -1141,7 +1141,7 @@ static void pearl_loopgen(int w, int h, char *lines, random_state *rs) } for (i = 0; i < g->num_edges; i++) { - grid_edge *e = g->edges + i; + grid_edge *e = g->edges[i]; enum face_colour c1 = FACE_COLOUR(e->face1); enum face_colour c2 = FACE_COLOUR(e->face2); assert(c1 != FACE_GREY); |