import java.awt.color.ColorSpace;
import java.awt.image.BufferedImage;
import java.util.ArrayList;
import java.util.List;


public class CCLabeling {
	List<Integer> intList = null;
	public int tabv []= null;
	// relabel the root
	 public int label=0;
	// original component image/array
	private int[][] image;
	private int width,height;
 
	// graph of nodes
	private int[] roots = null;
	private final int NOROOT=-1;
 
	
	public CCLabeling (int[][] im, int width, int height) {
		this.image = im;
		this.width = width;
		this.height = height;
		this.roots = new int[width*height];
	}
 
	// find the root of the node at position pos 
	private int find(int pos) {
		while(roots[pos]!=pos) pos=roots[pos];
		return pos;
	}
 
	// union of the 2 path formed by the 2 roots
	private int union(int root0, int root1) {
		if (root0==root1) return root0;
		if (root0==NOROOT) return root1;
		if (root1==NOROOT) return root0;
		if (root0<root1) {
			roots[root1]=root0;
			return root0;
		} else {
			roots[root0]=root1;
			return root1;
		}
	}
 
	// set the root of the node at position pos  
	private void add(int pos, int root) {
		if (root==NOROOT) 
			roots[pos]=pos;
		else 
			roots[pos]=root;
	}
 
	// build the connected component labels array
	private int[][] buildLabelArray() {
		
		// remove indirections
		for(int pos=0;pos<(width*height);pos++)
			roots[pos] = find(pos);
 
		
		for(int pos=0;pos<(width*height);pos++)
			if (roots[pos]==pos)
				roots[pos] = label++;
			else
				roots[pos] = roots[roots[pos]];
 
 
		// copy label to new array
		int[][] labels = new int[width][height];
		for(int y=0,pos=0;y<height;y++)
			for(int x=0;x<width;x++,pos++)
				if(image[x][y] !=0)
				labels[x][y]=roots[pos];

		return labels;
	}
 

	public int[][] compute() {
		int root;
		for(int y=0,pos=0;y<height;y++) {
			for(int x=0;x<width;x++,pos++) {
				
				//if(image[x][y] !=0){
					root = NOROOT;
				if ( (x>0) && (image[x-1][y]==image[x][y]) )
					root = union( find(pos-1) , root);
 
				if ( (x>0 && y>0) && (image[x-1][y-1]==image[x][y]) )
					root = union( find(pos-1-width) , root);
 
				if ( (y>0) && (image[x][y-1]==image[x][y]) )
					root = union( find(pos-width) , root);
 
				if ( (x<(width-1) && y>0) && (image[x+1][y-1]==image[x][y]) )
					root = union( find(pos+1-width) , root);
				
				add( pos, root );
			}}
 
		return buildLabelArray();
	}
	

	public int [][] elimin_surface(int [][] mat , int etq,int l ,int h){
		int ss = l*h;
		int surf [] = getsurfaces(mat,etq, l ,h);
		intList = new ArrayList<Integer>();
	for(int k = 1 ; k< surf.length; k++){
	
		if((surf[k] <(ss/21.2))||(surf[k]>(ss/0.9) )){//////<(ss/21.2)> (ss/0.9)
			
		for(int i=0 ;i<l ;i++){
			for(int j=0 ;j<h ;j++){
				
				if(mat[i][j] == k){
					mat[i][j] = 0 ;}
				}}
		} 
		else {
			
			intList.add(k);
			}	
	}
	tabv = new int [intList.size()];
	for (int i =0 ; i<intList.size();i++){		
		tabv [i] = (int) intList.get(i);
	}
		return mat;
		
	}
	
	public int [] getsurfaces(int [][] mat_img, int nbr_etq ,int l, int h){
		
		int tab_surf[]= new int [nbr_etq];
		
			for(int k = 1 ; k< nbr_etq; k++){
				int s =0;	
			for(int i=0 ;i<l ;i++){
				for(int j=0 ;j<h ;j++)
					
					if(mat_img[i][j] == k){
						s++;
					}
		}
			tab_surf[k] = s;//(max_j - min_j)*(max_i - min_i);
			}
		return tab_surf;
		}
	
}