/*********************************************************************
 * 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 _BSAS_H
#define _BSAS_H

#include <values.h>
#include <string.h>
#include "ClusteringAlgorithm.h"

namespace prapi { namespace clustering {

	/**
	 * Basic Sequential Algorithmic Scheme.
	 **/
	template <class T, class I, class C> class BSAS : public ClusteringAlgorithm<T,I,C>
	{
	public:
		BSAS(int clusters, double threshold) : _iClusters(clusters), _dThreshold(threshold) {}

		/**
		 * @complexity O(N), where N is the number of samples in <i>samples</i>
		 **/
		List<Cluster<T,I,C> > getClustering(const List<Sample<T,I,C> >& samples, const ProximityMeasure<T>& measure);

		void setThreshold(double threshold) { _dThreshold = threshold; }
		double getThreshold(void) const { return _dThreshold; }
		double& threshold(void) { return _dThreshold; }

		void setClusters(int clusters) { _iClusters = clusters; }
		int getClusters(void) const { return _iClusters; }
		int& clusters(void) { return _iClusters; }

	protected:
		int _iClusters;
		double _dThreshold;
	};

	template <class T, class I, class C> List<Cluster<T,I,C> > BSAS<T,I,C>::getClustering(const List<Sample<T,I,C> >& samples, const ProximityMeasure<T>& measure)
	{
		List<Cluster<T,I,C> > result;
		
		Cluster<T,I,C> cluster;
		cluster += samples[0];
		cluster.representative() = samples[0];
		if (measure.usesRepresentatives())
			updateRepresentative(cluster);
		result += cluster;

		//Go through all samples once
		for (int i=1;i<samples.getLength();i++)
			{
				double minDist = MAXDOUBLE;
				int minIndex = 0;

				//Find the closest cluster
				for (int j=result.getLength();j--;)
					{
						double dist = measure.getProximity(samples[i],result[j]);
						if (dist < minDist)
							{
								minDist = dist;
								minIndex = j;
							}
					}
				//Form a new cluster, if threshold value is exceeded
				if (minDist > _dThreshold && result.getLength() < _iClusters)
					{
						cluster = samples[i];
						if (measure.usesRepresentatives())
							updateRepresentative(cluster);
						result += cluster;
					}
				else //add to an existing one
					{
						result[minIndex] += samples[i];
						if (measure.usesRepresentatives())
							updateRepresentative(result[minIndex]);
					}
			}
		return result;
	}
	
	/**
	 * Modified Basic Sequential Algorithmic Scheme.
	 **/
	template <class T, class I, class C> class MBSAS : public BSAS<T,I,C>
	{
	public:
		MBSAS(int clusters, double threshold) : BSAS<T,I,C>(clusters,threshold) {}
		
		List<Cluster<T,I,C> > getClustering(const List<Sample<T,I,C> >& samples, const ProximityMeasure<T>& measure);
	};

	template <class T, class I, class C> List<Cluster<T,I,C> > MBSAS<T,I,C>::getClustering(const List<Sample<T,I,C> >& samples,
																																									const ProximityMeasure<T>& measure)
	{
		List<Cluster<T,I,C> > result;
		char used[samples.getLength()];
		memset(used,0,samples.getLength());
		
		Cluster<T,I,C> cluster;
		cluster += samples[0];
		cluster.representative() = samples[0];
		if (measure.usesRepresentatives())
			updateRepresentative(cluster);
		result += cluster;
		used[0] = -1;

		//Phase 1: go through all samples and form new clusters as necessary
		for (int i=1;i<samples.getLength();i++)
			{
				double minDist = MAXDOUBLE;
				int minIndex = 0;

				//Find the closest cluster
				for (int j=result.getLength();j--;)
					{
						double dist = measure.getProximity(samples[i],result[j]);
						if (dist < minDist)
							{
								minDist = dist;
								minIndex = j;
							}
					}
				//Form a new cluster, if threshold value is exceeded
				if (minDist > _dThreshold && result.getLength() < _iClusters)
					{
						cluster = samples[i];
						if (measure.usesRepresentatives())
							updateRepresentative(cluster);
						result += cluster;
						used[i] = -1;
					}
			}
		//Phase 2: assign all unassigned samples to their closest clusters
		for (int i=1;i<samples.getLength();i++)
			{
				if (used[i]) continue;

				double minDist = MAXDOUBLE;
				int minIndex = 0;

				//Find the closest cluster
				for (int j=result.getLength();j--;)
					{
						double dist = measure.getProximity(samples[i],result[j]);
						if (dist < minDist)
							{
								minDist = dist;
								minIndex = j;
							}
					}
				result[minIndex] += samples[i];
				if (measure.usesRepresentatives())
					updateRepresentative(result[minIndex]);
			}
		
		return result;
	}
}}

#endif