#pragma ident "@(#)conn-cpt.cxx 1.2 94/02/03"

//
// File: conn-cpt.cxx
//
// Function: mark_connected_components
// Author: andrewfg
// Date: 21/1/94
//
//    Marks connected components in a multiple-valued image.
//    Uses a translation-table approach to equivalences.
//    Seems to be quite fast (0.5s on 400x400 with 59 very
//    wiggly regions).
//

#include <stdio.h>
#include "Arrays.H"

int mark_connected_components(const Short2D & labels, Short2D & cc, int maxregions)
{
  int w = labels.get_width();
  int h = labels.get_height();
  cc.resize(w,h);
  cc.fill(0);

  intarray translations(maxregions);
  translations.fill(-1); 

#define N x,y-1
#define S x,y+1
#define E x-1,y
#define W x+1,y

  int x,y,here;
  int BIGGUN = maxregions + 2;

  // Top left corner is region 0
  int nregions = 0;
  cc.set(0,0,nregions++);

  // Do remaining rows.
  for ( y = 1; y < h; y++ ) {
    for ( x = 1; x < w; x++ ) {
      here = labels(x,y);
      if (here == 0)
	{
	  cc.set(x,y,0);
	  continue;
	}

      int le = BIGGUN;
      if (here == labels(E))
	{
	  le = cc(E);
	  while (translations[le] != -1)
	    le = translations[le];
	}

      int ln = BIGGUN;
      if (here == labels(N))
	{
	  ln = cc(N);
	  while (translations[ln] != -1)
	    ln = translations[ln];
	}

      int min = le<ln?le:ln;
      if (min == BIGGUN)
	{
	  // New label
	  if (nregions == maxregions)
	    {
	      error("Number of regions [%d] exceeds maximum [%d]\n", nregions, maxregions);
	      --nregions;
	    }
	  cc.set(x,y,nregions++);
	  continue;
	}
      cc.set(x,y,min);

      int max = ln + le - min;
      if (max == BIGGUN)
	continue;

      if (le != ln) {
	// Have a labelling error.
	
	while (translations[min] != -1)
	  min = translations[min];
	
	while (translations[max] != -1)
	  max = translations[max];
	
	if (max != min)
	  translations[max] = min;
	
      } // end le != ln
    } // end for x
    
  } // end for y

  SCAN(cc) {
    int i = cc(x,y);
    int t = translations[i];
    if (t != -1)
      {
	while (translations[t] != -1)
	  t = translations[t];
	cc.set(x,y,t);
      }
  }

  return nregions;
}


int relabel(Short2D & cc, int nregions)
//
// Take a multivalued image, and renumber pixels so
// values form a contiguous set.
//
//       7 2 1 8     1 2 3 4
// E.g.  7 7 8 8 --> 1 1 4 4
//       7 7 7 8     1 1 1 4
//
{
  intarray translations(nregions+1);
  translations.fill(-1);
  
  nregions = 0;
  SCANxy(cc) {
    int o = cc(x,y);
    int *t = &translations[o];
    if (*t == -1) *t = nregions++;
    cc.set(x,y,*t);
  }
  
  return nregions;
}


main(int argc, char ** argv)
{
  Short2D input("Input");
  Short2D output("Output");

  {
    HIPS_Header h;
    UChar2D ucharin("UChar2D");
    ucharin.read_hip("-",&h);
    input.assign(ucharin);
  }

  int n = mark_connected_components(input,output, 65536);
  //info ("cclabel: n = %d\n", n);
  n = relabel(output, n);
  info ("cclabel: found %d regions\n", n);

  UChar2D ucharout("ucharout", output.get_width(), output.get_height());
  ucharout.assign(output);
  ucharout.write_hip("-");
}