java-topology/defects/freeciv-0001/test/test_continent_flood.c

/*
 * Unit test for freeciv-0001: assign_continent_flood() BFS uses O(N)
 * tile_list_search() as visited check, making continent assignment O(T^2).
 *
 * Fix: mark tiles with continent number at enqueue time, replacing
 * the O(N) linked-list membership check with an O(1) integer check.
 *
 * We simulate a grid-based BFS flood fill on a square map and count
 * the number of "search operations" (comparisons) performed by each
 * approach.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/* Simulated tile: just needs a continent number and terrain type */
struct tile {
    int continent;
    int is_land; /* 1 = land, 0 = ocean */
};

/* Simple linked list node for worklist */
struct node {
    int tile_idx;
    struct node *next;
};

struct worklist {
    struct node *head;
    struct node *tail;
    int size;
};

static struct worklist *wl_new(void) {
    struct worklist *wl = calloc(1, sizeof(*wl));
    return wl;
}

static void wl_append(struct worklist *wl, int idx) {
    struct node *n = malloc(sizeof(*n));
    n->tile_idx = idx;
    n->next = NULL;
    if (wl->tail) {
        wl->tail->next = n;
    } else {
        wl->head = n;
    }
    wl->tail = n;
    wl->size++;
}

static int wl_pop_front(struct worklist *wl) {
    struct node *n = wl->head;
    int idx = n->tile_idx;
    wl->head = n->next;
    if (!wl->head) wl->tail = NULL;
    free(n);
    wl->size--;
    return idx;
}

/* O(N) linear search through linked list, counting comparisons */
static int wl_search(struct worklist *wl, int idx, long *ops) {
    struct node *n = wl->head;
    while (n) {
        (*ops)++;
        if (n->tile_idx == idx) return 1;
        n = n->next;
    }
    return 0;
}

static void wl_destroy(struct worklist *wl) {
    while (wl->head) {
        struct node *n = wl->head;
        wl->head = n->next;
        free(n);
    }
    free(wl);
}

/* Get adjacent tile indices for a grid position (4-connected) */
static int get_adjacent(int idx, int width, int height, int *adj) {
    int x = idx % width;
    int y = idx / width;
    int count = 0;

    if (x > 0)          adj[count++] = idx - 1;
    if (x < width - 1)  adj[count++] = idx + 1;
    if (y > 0)          adj[count++] = idx - width;
    if (y < height - 1) adj[count++] = idx + width;

    return count;
}

/*
 * DEFECTIVE: Uses tile_list_search (O(N) linked list scan) to check
 * if a tile is already in our worklist before adding it.
 */
static long flood_defective(struct tile *tiles, int width, int height,
                            int start, int nr) {
    long ops = 0;
    struct worklist *wl = wl_new();
    int adj[4];

    wl_append(wl, start);

    while (wl->size > 0) {
        int current = wl_pop_front(wl);
        int nadj = get_adjacent(current, width, height, adj);

        for (int i = 0; i < nadj; i++) {
            int neighbor = adj[i];
            if (tiles[neighbor].continent != 0 || !tiles[neighbor].is_land)
                continue;

            /* DEFECT: O(N) search through linked list worklist */
            if (!wl_search(wl, neighbor, &ops)) {
                wl_append(wl, neighbor);
            }
        }

        tiles[current].continent = nr;
    }

    wl_destroy(wl);
    return ops;
}

/*
 * PATCHED: Mark tiles with continent number at enqueue time.
 * The continent field itself serves as our visited set (O(1) check).
 */
static long flood_patched(struct tile *tiles, int width, int height,
                          int start, int nr) {
    long ops = 0;
    struct worklist *wl = wl_new();
    int adj[4];

    /* Mark immediately at enqueue */
    tiles[start].continent = nr;
    wl_append(wl, start);

    while (wl->size > 0) {
        int current = wl_pop_front(wl);
        int nadj = get_adjacent(current, width, height, adj);

        for (int i = 0; i < nadj; i++) {
            int neighbor = adj[i];
            ops++; /* O(1) integer comparison */
            if (tiles[neighbor].continent != 0 || !tiles[neighbor].is_land)
                continue;

            /* PATCHED: O(1) mark-and-enqueue */
            tiles[neighbor].continent = nr;
            wl_append(wl, neighbor);
        }

        /* No tile_list_remove needed, just popped from front */
    }

    wl_destroy(wl);
    return ops;
}

int main(void) {
    /* Test with increasing continent sizes */
    int sizes[] = {10, 20, 40, 80, 160};
    int nsizes = sizeof(sizes) / sizeof(sizes[0]);
    int all_pass = 1;

    printf("freeciv-0001: assign_continent_flood() tile_list_search O(T^2)\n");
    printf("%-8s %-10s %-12s %-12s %-8s %s\n",
           "Size", "Tiles", "Defective", "Patched", "Ratio", "Status");
    printf("%-8s %-10s %-12s %-12s %-8s %s\n",
           "----", "-----", "---------", "-------", "-----", "------");

    for (int s = 0; s < nsizes; s++) {
        int width = sizes[s];
        int height = sizes[s];
        int total = width * height;

        /* Create an all-land map */
        struct tile *tiles_def = calloc(total, sizeof(struct tile));
        struct tile *tiles_pat = calloc(total, sizeof(struct tile));

        for (int i = 0; i < total; i++) {
            tiles_def[i].is_land = 1;
            tiles_def[i].continent = 0;
            tiles_pat[i].is_land = 1;
            tiles_pat[i].continent = 0;
        }

        long ops_def = flood_defective(tiles_def, width, height, 0, 1);
        long ops_pat = flood_patched(tiles_pat, width, height, 0, 1);

        /* Verify all tiles were assigned */
        int assigned_def = 0, assigned_pat = 0;
        for (int i = 0; i < total; i++) {
            if (tiles_def[i].continent == 1) assigned_def++;
            if (tiles_pat[i].continent == 1) assigned_pat++;
        }

        double ratio = (ops_pat > 0) ? (double)ops_def / ops_pat : 0;
        int pass = (assigned_def == total && assigned_pat == total
                    && ops_pat < ops_def);

        printf("%-8d %-10d %-12ld %-12ld %-8.1fx %s\n",
               width, total, ops_def, ops_pat, ratio,
               pass ? "PASS" : "FAIL");

        if (!pass) all_pass = 0;

        free(tiles_def);
        free(tiles_pat);
    }

    printf("\n%s\n", all_pass ? "ALL PASS" : "SOME FAILED");
    return all_pass ? 0 : 1;
}