package ie.dcu.image;

import ie.dcu.matrix.*;
import ie.dcu.matrix.Matrix.Type;

import java.util.Stack;

/**
 * Class to perform connected component analysis on a binary object mask and
 * create a labeled map of connected components.
 * 
 * Connected component analysis is performed using the 8-neighborhood rule.
 * 
 * 
 * @author Kevin McGuinness
 */
public class ObjectLabeler implements MatrixProvider {
	
	/**
	 * Value of the background label in the label maps produced.
	 */
	public static final int BACKGROUND_LABEL = 0;
	
	/**
	 * Offsets of the row indices for each of the 8-neighbors
	 */
	private static final int[] Ni = { -1, -1, -1,  0,  0,  1,  1,  1 };
	
	/**
	 * Offsets of the column values for each of the 8-neighbors
	 */
	private static final int[] Nj = { -1,  0,  1, -1,  1, -1,  0,  1 };
	
	/**
	 * The label matrix.
	 */
	private IntMatrix labels;
	
	/**
	 * The number of objects found in the last labeling.
	 */
	private int objectCount;
	
	/**
	 * The value used to identify foreground pixels in the object mask.
	 */
	private byte foregroundValue;
	
	/**
	 * Construct an object labeler with a default foreground label value of 1.
	 */
	public ObjectLabeler() {
		this((byte) 1);
	}
	
	/**
	 * Construct an object labeler that identifies foreground pixels using the
	 * given value.
	 * 
	 * @param foregroundValue
	 *            The value used to identify foreground pixels in the mask.
	 */
	public ObjectLabeler(byte foregroundValue) {
		this.objectCount = 0;
		this.foregroundValue = foregroundValue;
	}
	
	/**
	 * Get the foreground value used to identify foreground pixels in the mask.
	 */
	public byte getForegroundValue() {
		return foregroundValue;
	}

	/**
	 * Set the foreground value used to identify foreground pixels in the mask.
	 */
	public void setForegroundValue(byte value) {
		foregroundValue = value;
	}
	
	/**
	 * Return the number of objects found in the last labeling.
	 */
	public int getObjectCount() {
		return objectCount;
	}
	
	/**
	 * Returns the label map computed in the last labeling. This will be null
	 * if no labeling has been performed with this labeler.
	 */
	public IntMatrix getLabelMap() {
		return labels;
	}

	/**
	 * Compute the connected component labeling of the given binary mask.
	 * 
	 * @param mask
	 *            A binary matrix (non null).
	 * @return The number of objects found.
	 */
	public int label(ByteMatrix mask) {
		labels = new IntMatrix(mask.rows, mask.cols);
		
		// Fill the object with the background label
		labels.fill(BACKGROUND_LABEL);
		
		// Current label
		int label = 0;
		
		// Labeling loop
		for (int i = 0, k = 0; i < mask.rows; i++) {
			for (int j = 0; j < mask.cols; j++, k++) {
			
				if (mask.values[k] == foregroundValue &&
					labels.values[k] == BACKGROUND_LABEL) 
				{
					label++;
					
					// Unlabeled foreground pixel
					doLabel(mask, i, j, label);
				} 
			}
		}
		
		// Set and return label count
		return (objectCount = label);
	}

	/**
	 * Internal routine for label propagation.
	 */
	private void doLabel(ByteMatrix mask, int i, int j, int label) {
		
		// Stack of indices to process
		Stack<Index2D> stack = new Stack<Index2D>();
		stack.add(new Index2D(i, j));
		
		// Processing loop
		while (!stack.isEmpty()) {
			
			Index2D idx = stack.pop();
			
			if (labels.intAt(idx) != BACKGROUND_LABEL) {
				// Already labeled
				continue;
			}
			
			labels.setIntAt(idx, label);
			
			// iterate over neighbors
			for (int k = 0; k < Ni.length; k++) {
				i = idx.i + Ni[k];
				j = idx.j + Nj[k];
				
				// Check in range
				if (labels.hasIndex(i, j)) {
					
					int offset = labels.offsetOf(i, j);
					
					if (labels.values[offset] == BACKGROUND_LABEL && 
						mask.values[offset] == foregroundValue) 
					{
						stack.push(new Index2D(i, j));
					}	
				}
			}
		}
	}

	/**
	 * Implementation of matrix provider.
	 */
	public Matrix getMatrix(boolean alwaysCopy) {
		return getMatrix(null, alwaysCopy);
	}

	/**
	 * Implementation of matrix provider.
	 */
	public Matrix getMatrix(Type type, boolean alwaysCopy) {
		if (labels == null) {
			throw new IllegalStateException();
		}
		
		return labels.getMatrix(type, alwaysCopy);
	}

	/**
	 * Implementation of matrix provider.
	 */
	public Type getDefaultMatrixType() {
		return labels.getDefaultMatrixType();
	}
}