// Simple Binary Connected components 
// (c) Andrew Senior 2006  http://www.andrewsenior.com 
// Preserve this header when redistributing. 

class pconcomps
{
  int [] m_piLabels;
  int m_lIndex;
  int [] m_plEquivalent;
  int [] m_plAreas;
  int m_lIndicesAllocated;
  int m_iHeight, m_iWidth; 
  
  // Take an image and label the components in it internally 
  void Compute(PImage Im)
    {
      m_iWidth=Im.width; 
      m_iHeight=Im.height;
      m_piLabels=new int[Im.width * Im.height];
      m_lIndex=1;
      m_lIndicesAllocated=10;
      m_plEquivalent= new int [m_lIndicesAllocated];
      m_plEquivalent[0]=0;
      int iIndex=0;
      for(int j=0; j<Im.height; j++)
      {
	for(int i=0; i<Im.width; i++, iIndex++)
	{
	  if (i>0 && Im.pixels[iIndex]!=0)  // Same colour as the left pixel
	    if (red(Im.pixels[iIndex])==0)
	      m_piLabels[iIndex]=0;
	    else
	    {
	      if (i>0 && (red(Im.pixels[iIndex-1])!=0))  // Same colour as the left pixel
	      {
		m_piLabels[iIndex]=m_piLabels[iIndex-1];
		if (j>0 
		    && (red(Im.pixels[iIndex-Im.width])!=0) 
		    && m_piLabels[iIndex]!=m_piLabels[iIndex-Im.width])  // Two regions  different label adjoin
		  MarkEquivalent(m_piLabels[iIndex], m_piLabels[iIndex-Im.width]);
	      }
	      else   // Same colour as the  pixel below
		if (j>0 && (red(Im.pixels[iIndex-Im.width])!=0))
		  m_piLabels[iIndex]=m_piLabels[iIndex-Im.width];
		else  // No neighbours - start a new component
		{
		  m_piLabels[iIndex]=m_lIndex;  // The new component will have this label
		  NewComponent(); // All non BG components are considered same colour ie 1
		}
	    }
	}
      }
      RelabelEquivalents();       
    }

  void MarkEquivalent(int i, int j)
    {
      // Find the ultimate parent (equivalency) of each component
      int iT=m_plEquivalent[i];
      int iS=m_plEquivalent[j];
      // sort them 
      if (iT>iS) 
      {
	int l=iT;
	iT=iS;
	iS=l;
      }
      for( int k=iS; k<m_lIndex; k++)  // Overwrite the highest (iS) with the lowest (iT)
	if (m_plEquivalent[k]==iS)
	  m_plEquivalent[k]=iT;
    }
  void ReallocIndices()
    {
      int [] pTemp=new int[m_lIndicesAllocated+10];
      for(int i=0; i<m_lIndicesAllocated; i++)
	pTemp[i]=m_plEquivalent[i];
      m_plEquivalent=pTemp;
      m_lIndicesAllocated+=10;
    }

  void NewComponent()
    {
      if (m_lIndex>=m_lIndicesAllocated)
	ReallocIndices();
      m_plEquivalent[m_lIndex]=m_lIndex;  // itself later it might get relabelled to a lower numbered component when they're found to touch
      m_lIndex++; // total number === Next component to allocate 
    }
  void RelabelEquivalents()
    {
      // First go through and find the active components
      // iUsed keeps track of which ones are a "root" of equivalence
      // Everything, including the root is now mapped into an index so that 
      // only the first iUsed indices are used. 
      int lOldMax=m_lIndex;
      int k=0;
      int iUsed=0;
      for(k=0; k<m_lIndex; k++)
	if (m_plEquivalent[k]==k) // A "root" 
	{
	  if (iUsed!=k)  // We need to relabel all equivalents to point to this now too
	  {
	    for( int l=k; l<m_lIndex; l++)
	      if (m_plEquivalent[l]==k)                // this is safe because iUsed<k
		m_plEquivalent[l]=iUsed;  
	  }
	  iUsed++;
	}
      m_lIndex=iUsed;

      m_plAreas=new int [m_lIndex];
//println(" in Relable components="+m_lIndex);
      if (m_lIndex==0)
	return;
      int iIndex=0;
      for(int  y=0; y<m_iHeight; y++)
	for(int  x=0; x<m_iWidth; x++, iIndex++)
	{
	  int lNewClass=m_plEquivalent[m_piLabels[iIndex]];
	  m_plAreas[lNewClass]++;
	  m_piLabels[iIndex]=lNewClass;
	}
    }

  // Remove components with area less than lSize
  void RemoveSmall(int lSize)
    {
      int k;
      int iDeleted=0;
      if (m_lIndex==0)
	return;

      // Go through components in reverse order
      for(k=m_lIndex-1; k>=1; k--)
	if (m_plAreas[k]<lSize ) // a non-background region not touching tbe main background component
	{
	  DeleteComponent(k);
	  iDeleted++;
	}
      //   println("Deleted "+iDeleted+" componnents leaving "+m_lIndex);
    }

  // Delete a given component
  void DeleteComponent(int k)
    {
      int iIndex=0;
      for(int  y=0; y<m_iHeight; y++)
	for(int  x=0; x<m_iWidth; x++, iIndex++)
	{
	  if (m_piLabels[iIndex]==k)
	    m_piLabels[iIndex]=0;
	  else if (m_piLabels[iIndex]>k)
	    m_piLabels[iIndex]=m_piLabels[iIndex]-1;
	}
      for(int k2=k; k2<m_lIndex-1; k2++)
	m_plAreas[k2]=m_plAreas[k2+1];
      m_lIndex--;
    }

  // Copy the current appearance (remaining components) to an image
  void SetImage(PImage Im)
    {
      int iIndex=0;
      for(int  y=0; y<m_iHeight; y++)
	for(int  x=0; x<m_iWidth; x++, iIndex++)
	{
	  if (m_piLabels[iIndex]==0)
	    Im.pixels[iIndex]=color(0,0,0);
	  else 
	    Im.pixels[iIndex]=color(255,255,255);
	}
    }
} // End of pconcomps