/*
       connect.c

       Connected component transforms

       cocoImage:   connected component transform of a discrete binary image
                   (8-connected topology)

       cocoGraph: connected component labels for a discrete graph
                   specified by a list of edges
       
       $Revision: 1.8 $ $Date: 2013/05/27 02:09:10 $

       
*/

#include <math.h>
#include <R.h>
#include <Rdefines.h>
#include <R_ext/Utils.h>

#include "raster.h"
void   shape_raster();

#include "yesno.h"


/* workhorse function for cocoImage */

void
comcommer(im)
     Raster  *im;            
     /* raster must have been dimensioned by shape_raster() */
     /* Pixel values assumed to be 0 in background, and 
        distinct nonzero integers in foreground */
{
  int	j,k;
  int rmin, rmax, cmin, cmax;
  int label, curlabel, minlabel;
  int nchanged;

  /* image boundaries */
  rmin = im->rmin;
  rmax = im->rmax;
  cmin = im->cmin;
  cmax = im->cmax;

#define ENTRY(ROW, COL) Entry(*im, ROW, COL, int)

#define UPDATE(ROW,COL,BEST,NEW) \
     NEW = ENTRY(ROW, COL); \
     if(NEW != 0 && NEW < BEST) \
       BEST = NEW

  nchanged = 1;

  while(nchanged >0) {
    nchanged = 0;
    R_CheckUserInterrupt();
    for(j = rmin; j <= rmax; j++) {
      for(k = cmin; k <= cmax; k++) {
	curlabel = ENTRY(j, k);
	if(curlabel != 0) {
	  minlabel = curlabel;
	  UPDATE(j-1, k-1, minlabel, label);
	  UPDATE(j-1, k,   minlabel, label);
	  UPDATE(j-1, k+1, minlabel, label);
	  UPDATE(j,   k-1, minlabel, label);
	  UPDATE(j,   k,   minlabel, label);
	  UPDATE(j,   k+1, minlabel, label);
	  UPDATE(j+1, k-1, minlabel, label);
	  UPDATE(j+1, k,   minlabel, label);
	  UPDATE(j+1, k+1, minlabel, label);
	  if(minlabel < curlabel) {
	    ENTRY(j, k) = minlabel;
	    nchanged++;
	  }
	}
      }
    }
  }
}

void cocoImage(mat, nr, nc)
     int   *mat;        /* input:  binary image */
     int *nr, *nc;      /* raster dimensions
			   EXCLUDING margin of 1 on each side */
{
  Raster im;

  shape_raster( &im, (void *) mat, 
		(double) 1, (double) 1,
		(double) *nc, (double) *nr, 
		*nr+2, *nc+2, 1, 1);
  comcommer(&im);
}	

void cocoGraph(nv, ne, ie, je, label, status)
     /* inputs */
     int *nv;         /* number of graph vertices */
     int *ne;         /* number of edges */
     int *ie, *je;    /* vectors of indices of ends of each edge */ 
     /* output */
     int *label;      /* vector of component labels for each vertex */
                      /* Component label is lowest serial number of
			 any vertex in the connected component */
     int *status;          /* 0 if OK, 1 if overflow */
{
  int Nv, Ne, i, j, k, niter, labi, labj, changed;
  
  Nv = *nv;
  Ne = *ne;

  /* initialise labels */
  for(k = 0; k < Nv; k++)
    label[k] = k;

  for(niter = 0; niter < Nv; niter++) {
    R_CheckUserInterrupt();
    changed = NO;
    for(k = 0; k < Ne; k++) {
      i = ie[k];
      j = je[k];
      labi = label[i];
      labj = label[j];
      if(labi < labj) {
	label[j] = labi;
	changed = YES;
      } else if(labj < labi) {
	label[i] = labj;
	changed = YES;
      } 
    }
    if(!changed) {
      /* algorithm has converged */
      *status = 0;
      return;
    }
  }
  /* error exit */   
  *status = 1;
  return;
}