/*********************************************************************
 * 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.5 $
 *********************************************************************/

#ifndef _CLUSTERINGALGORITHM_H
#define _CLUSTERINGALGORITHM_H

#include <List.h>
#include <string>
#include "../Distribution.h"
#include "../Sample.h"
#include "../ProximityMeasure.h"
#include "../Cluster.h"

namespace prapi { namespace clustering {

	/**
	 * ClusteringAlgorithm is a common interface for different types of
	 * clustering schemes. It also provides some useful methods for
	 * updating cluster representatives, refining the clustering result
	 * etc.
	 **/
	template <class T, class I=string, class C=int> class ClusteringAlgorithm
	{
	public:
		virtual List<Cluster<T,I,C> > getClustering(const List<Sample<T,I,C> >& samples, const ProximityMeasure<T>& measure) = 0;

		/**
		 * Update the representative for a cluster. The default
		 * implementation calculates the mean of each feature vector
		 * component.
		 **/
		virtual void updateRepresentative(Cluster<T,I,C>& cluster);

		/**
		 * Perform a merging procedure after the clusters have been
		 * formed.
		 *
		 * @param clusters the produces clusters
		 * @param threshold a threshold for merging clusters that are
		 * "close" to each other
		 **/
		void merge(List<Cluster<T,I,C> >& clusters, ProximityMeasure<T>* measure, double threshold);
	};

	template <class T, class I, class C> void ClusteringAlgorithm<T,I,C>::merge(List<Cluster<T,I,C> >& clusters,
																																							ProximityMeasure<T>* measure,
																																							double threshold)
	{
		int minI = 0, minJ = 0;
		bool merged = false;
		do
			{
				double minDist = MAXDOUBLE;
				for (int i=clusters.getLength();i--;)
					for (int j=clusters.getLength();j--;)
						{
							if (j == i) continue;
							double dist = measure->getProximity(clusters[i],clusters[j]);
							if (dist < minDist)
								{
									minI = i;
									minJ = j;
									minDist = dist;
								}
						}
				if (minDist <= threshold)
					{
						int min = minI <? minJ;
						int max = minI >? minJ;
						clusters[min] += clusters[max];
						clusters.removeElementAt(max);
						if (measure->usesRepresentatives())
							updateRepresentative(clusters[min]);
						merged = true;
					}
			} while (merged);
	}

	template <class T, class I, class C> void ClusteringAlgorithm<T,I,C>::updateRepresentative(Cluster<T,I,C>& cluster)
	{
		Distribution dist;
		for (int i=cluster.getLength();i--;)
			dist += cluster[i];
		dist /= cluster.getLength();
		cluster.representative() = dist;
	}
}}


#endif