#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "inc/floodfill.h"

struct node {
  int x;
  int y;
  struct node *next;
};

/* Implement floodfill using queue
 * Basically:
 *  1. Add first node to the queue
 *  2. While the queue is not empty,
 *    2a. Scan left and right, filling as we go
 *    2b. Also, add available above/below squares to the queue
 */
int floodfill(int x, int y, int w, int h, char **data) {
  int count = 0;
  struct node *head = NULL;
  struct node *tail = NULL;
  struct node *tmp  = NULL;

  assert(data != NULL);
  assert(w > 0);
  assert(h > 0);
  assert(y < h);
  assert(x < w);

  if(data[y][x] < 1)
    return 0;

  head = malloc(sizeof *head);
  if(head == NULL)
    return 0;
  head->x = x;
  head->y = y;
  head->next = NULL;
  tail = head;

 /* Foreach item in read queue... */
  while(head != NULL) {
    int scanx = head->x;
   /* Mark non-zero (white) squares as read in an undoable way.
    * If puzzle is connected, _every_ square will end up <= 0. */
    if(data[head->y][head->x] > 0)
      data[head->y][head->x] -= 10;

   /* Scan left */
    while(data[head->y][scanx - 1])
      --scanx;
   /* Scan right */
    while(scanx < w && data[head->y][scanx] != 0) {
      if(head->y > 0 && data[head->y - 1][scanx] > 0) {
       /* Add to queue */
        struct node *new = malloc(sizeof *new);
        if(new != NULL) {
          new->x = scanx;
          new->y = head->y - 1;
          new->next = NULL;
          tail->next = new;
          tail = new;
          data[new->y][scanx] -= 10;
        }
      }
      if(head->y < h - 1 && data[head->y + 1][scanx] > 0) {
       /* Add to queue */
        struct node *new = malloc(sizeof *new);
        if(new != NULL) {
          new->x = scanx;
          new->y = head->y + 1;
          new->next = NULL;
          tail->next = new;
          tail = new;
          data[new->y][scanx] -= 10;
        }
      }
      ++scanx;
    }
   /* Cleanup */
    tmp  = head;
    head = head->next;
    free(tmp);
    ++count;
  }
  return count;
}