/*********************************************************************
 * This file is part of the PRAPI library.
 *
 * Copyright (C) 2001 Topi Mäenpää and Jaakko Viertola
 * All rights reserved.
 *
 * This program is free software. You can redistribute and/or modify
 * it under the terms of the free software licence found in the
 * accompanying file "COPYING". The licence terms must always be
 * redistributed with this source file. The above copyright notice
 * must be reproduced in all modified and unmodified copies of this
 * source file.
 *
 * $Revision: 1.8 $
 *********************************************************************/

#ifndef _LABELING_H
#define _LABELING_H

#include "../ImageTransform.h"
#include "../Image.h"
#include <SortedList.h>
#include <Math.h>
#include <ListUtils.h>

namespace prapi { namespace binary {

	/**
	 * Connectivity types:
	 * <ul>
	 * <li>CONNECT_4 - 4-connectivity</li>
	 * <li>CONNECT_8 - 8-connectivity</li>
	 * </ul>
	 **/
	enum ConnectivityType { CONNECT_4, CONNECT_8 };

	/**
	 * Label all connected components in a (binary) image. The first
	 * component found is given the label one, the second one the label
	 * two and so on. Background is marked with zeros.
	 **/
  template <class T=bool> class Labeling : public ImageTransform<int,T>
	{
	public:
		/**
		 * Create a new Labeling instance that inspects neighbors with the
		 * given connectivity type.
		 **/
		Labeling(ConnectivityType cType = CONNECT_4) : _cType(cType) {}

		/**
		 * Set the connectivity type used for labeling.
		 **/
		void setConnectivityType(ConnectivityType cType) { _cType = cType; }

		/**
		 * Get the connectivity type.
		 **/
		ConnectivityType getConnectivityType() const { return _cType; }
		
		/**
		 * Label an image using either 4- or 8-neighbors.
		 *
		 * @param mat The matrix wanted to make labeling.
		 **/
		util::Matrix<int> getTransformedImage(const util::Matrix<T>& mat)throw (ImageTransformException&);

	private:
		ConnectivityType _cType;

		util::Matrix<int> transform4(const util::Matrix<T>& mat) throw (ImageTransformException&);
		util::Matrix<int> transform8(const util::Matrix<T>& mat) throw (ImageTransformException&);
		
		/**
		 * The fuction finds the minimum value of the list.
		 **/
		int findMinimum(int index,util::List<int>& labels);
	};

	
	template <class T> util::Matrix<int> Labeling<T>::getTransformedImage(const util::Matrix<T>& mat)
		throw (ImageTransformException&)
	{
		if (_cType == CONNECT_4)
			return transform4(mat);
		else
			return transform8(mat);
	}

	template <class T> util::Matrix<int> Labeling<T>::transform4(const util::Matrix<T>& mat)
		throw (ImageTransformException&)
	{
		int cols = mat.getColumns();
		int rows = mat.getRows();
		int labelIndex = 1;
		// make the label list and set the first member to zero.
		util::List<int> labels(256,256);
		labels.addElement(0);
		
		util::Matrix<int> result(rows,cols);

		const T	*data = mat.getData();
		int
			*current = result.getData(),
			*up = current - cols,
			*left = current - 1;

		for(int r=0; r<rows; r++)
			for(int c=0; c<cols; c++, data++, current++, left++, up++)
				{
					//If there is no object at this pixel, do nothing
					if (!*data)
						continue;

					int iLeft = c ? *left : 0;
					int iUp = r ? *up : 0;

					//No connected label -> form a new one
					if (!iLeft && !iUp)
						{
							*current = labelIndex;
							labels += labelIndex++;
							continue;
						}

					//If left and up agree take, say, left
					if (labels[iLeft] == labels[iUp])
						{
							*current = labels[iLeft];
							continue;
						}

					int larger, smaller;
					//Labels are different -> must mark equal
					if (iLeft > labels[iUp])
						{
							larger = iLeft;
							smaller = labels[iUp];
						}
					else
						{
							larger = labels[iUp];
							smaller = iLeft;
						}
					//smaller is not background
					if (smaller)
						{
							labels[larger] = smaller;
							*current = smaller;
						}
					//smaller is background
					else 
						*current = larger;
				}

		//Move labels so that objects are numbered sequentially
		labelIndex = 2;
		for (int i=2; i<labels.getLength(); i++)
			if (labels[i] == i)
				{
					for (int j=i; j<labels.getLength(); j++)
						if (labels[j] == i)
							labels[j] = labelIndex;
					labelIndex++;
				}
		
		//Finally, alter mapped labels
		for (int i=rows*cols, *data = result.getData(); i--; data++)
			*data = labels[*data];
		
		return result;
	}

	
	template <class T> util::Matrix<int> Labeling<T>::transform8(const util::Matrix<T>& mat)
		throw (ImageTransformException&)
	{
		int matColumns = mat.getColumns();
		int matRows = mat.getRows();
		int tmpRows = matRows+2;
		int tmpColumns = matColumns+2;
		// make the label list and set the first member to zero.
		util::List<int> labels(256);
		labels.addElement(0);
		
		util::Matrix<int> tmp(tmpRows,tmpColumns);

		// do not even try to understand what this does
		for(int r=0,i=1; r<matRows;r++,i++)
			{
				for(int c=0,j=1; c<matColumns;c++,j++)
					{
						if(mat(r,c) != T(0))
							{
								util::SortedList<int> values(4);
								values.addElements(4,findMinimum(tmp(i,j-1),labels),findMinimum(tmp(i-1,j-1),labels),
																		 findMinimum(tmp(i-1,j),labels),findMinimum(tmp(i-1,j+1),labels));
								int min=util::ListUtils::findFirstNotOf(values,0);
								// if everything were not zeros
								if(min != -1)
									{
										min = values[min];
										labels[tmp(i,j-1)]=min;//check left
										labels[tmp(i-1,j-1)]=min;//check northwest
										labels[tmp(i-1,j)]=min;//check up
										labels[tmp(i-1,j+1)]=min;//check northeast
										tmp(i,j)=min;//set the right value
									}
								else
									{
										// add the lists length to next label 
										tmp(i,j)=labels.getLength();
										labels.addElement(labels.getLength());
									}
							}//if
					}
			}
		
		// go throw the labels
		int labelIndex = 1;
		for(int i=0;i<labels.getLength();i++)
			{
				if(labels[i] != i)labels[i]=labels[labels[i]];		
				else
					{
						labels[i] = labelIndex;
						labelIndex++;
					}
			}
		
		util::Matrix<int> result(matRows,matColumns);
		// and then go throw the whole Matrix again and change the labels.
		for(int i=1,r=0; r<matRows;i++,r++)
			for(int j=1,c=0; c< matColumns;j++,c++)
				{
					if((tmp(i,j)) && (labels[tmp(i,j)]))result(r,c)=labels[tmp(i,j)];
					else result(r,c)=tmp(i,j); 
		 		}

		return result;
	}
	
	template <class T> int Labeling<T>::findMinimum(int index, util::List<int>& labels)
	{
		int tmp=labels[index];
		int before=index;
		while(tmp < before && before > 1 && tmp >= 1)
			{
				before=tmp;
				tmp=labels[tmp];
			}
		return before;
	}
	
}}
#endif