//  @(#)floodfill.cxx 1.4 93/03/12 
//
// 		      Robot Vision Group
// 		Dept. of Artificial Intelligence
// 		    University of Edinburgh
// 
// Author: Andrew Fitzgibbon 
// Description: Generic floodfill routine.
//

typedef int (*ArrayReadFunc)(const void * client_data,int x, int y);
typedef void (*ArraySetFunc)(void * client_data,int x, int y);

int STACKLIM = 65536;
int floodfill(int sx, int sy,		// Start point
	      void * client_data,	// Pointer to structure holding array
	      ArrayReadFunc array_read, // Array reading function
	      ArraySetFunc array_set,   // Array setting function
	      int num_neighbours,	// Number of neighbors (4 or 8)
	      int max_distance)		// Max. distance for connectedness
{
  int max_stackpointer = 0;
  int * stx = new int[STACKLIM];
  int * sty = new int[STACKLIM];
  if (!stx || !sty)
    {
      error("floodfill(): out of memory\n");
      return 0;
    }
  
  printf("[floodfill(%d,%d)",sx,sy);
  static int dx[8] = {1,0,-1,0,-1,1,1,-1};
  static int dy[8] = {0,1,0,-1,-1,-1,1,1};
  
  stx[0] = sx;
  sty[0] = sy;
  int stkptr = 1;
  int numfilled = 0;
  int reported = 0;
  
  do {
    // Try 4-connected neighbours
    stkptr--;
    int x0 = stx[stkptr];
    int y0 = sty[stkptr];
    for (int scale = 1; scale <= max_distance; scale++)
      for (int i=0; i<num_neighbours; i++) {
	int x = x0 + dx[i] * scale;
	int y = y0 + dy[i] * scale;
	
	if (array_read(client_data,x,y))
	  {
	    array_set(client_data,x,y);
	    numfilled++;
	    
	    stx[stkptr] = x;
	    sty[stkptr] = y;
	    if (stkptr > max_stackpointer)
	      max_stackpointer = stkptr;
	    if (++stkptr >= STACKLIM) {
	      --stkptr;
	      if (!reported++)
		warning("floodfill: Out of stack space\n");
	    }
	  }
      }
  } while (stkptr > 0);
  
  delete stx;
  delete sty;
  printf("ed %d points] ",numfilled);
  printf("max_stackpointer == %d\n",max_stackpointer);
  if (reported) warning("maybe %d points not filled that should have been\n", reported);
  return numfilled;
}