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

#ifndef _CLASSIFIER_H
#define _CLASSIFIER_H

#include <SortedList.h>
#include <Event.h>
#include <Exception.h>
#include "Sample.h"
#include "ProximityMeasure.h"
#include "ValueHolder.h"
#include <values.h>
#include <ListUtils.h>
#include <Heap.h>
#include <Pair.h>

namespace prapi
{
	/**
	 * An event for informing interested listeners of the state of the
	 * classification.
	 **/
	template <class T, class I=std::string, class C=int> class ClassificationEvent : virtual public util::Object
	{
	public:
		/**
		 * Create a new ClassificationEvent.
		 * @param sample a reference to the sample that was just classified
		 * @param index the index of the sample
		 **/
		ClassificationEvent(Sample<T,I,C>& sample, int index) : _sample(sample), _iIndex(index) {}

		/**
		 * Get a copy of the sample that was just classified.
		 **/
		Sample<T,I,C> getSample(void) const { return _sample; }

		/**
		 * Get the sample's index.
		 * @return how many samples have been classified this far? The first
		 *         sample will be accompanied with index 0.
		 **/
		int getIndex(void) const { return _iIndex; }
		
	private:
		Sample<T,I,C>& _sample;
		int _iIndex;
	};
	
	/**
	 * Classifier is the common base class for all types of classifiers.
	 * Classifier modifies the testing samples by setting their
	 * classification field to a new value.<p>
	 *
	 * Classifier stores a pointer to the training samples and proximity
	 * measure for memory saving purposes. Take care that the training
	 * samples won't be deleted before the Classifier has done its due.<p>
	 *
	 * If you want to keep track of the state of the classification, you
	 * might want to add some EventListeners to a classifier. After each
	 * classified sample, all registered event listeners are notified.<p>
	 *
	 * The purpose of a classifier is just to set the classification for
	 * a set of samples. When you want to get more information of the
	 * classification result, use a confusion matrix for the classified
	 * sample set.
	 *
	 * @see ConfusionMatrix
	 **/
	template <class T, class I=std::string, class C=int> class Classifier : public util::EventSource<ClassificationEvent<T,I,C> >
	{
	public:
		/**
		 * Create a new classifier. The memory pointed by <i>measure</i>
		 * is automatically released upon the deletion of the classifier.
		 * Training samples are not deleted automatically. That is, you
		 * can create a Classifier like the following:<br>
		 * <pre>
		 * MyClassifier classifier(&trainingSamples, new MyProximityMeasure, classes);
		 * </pre>
		 * One does not need to store a pointer to "new
		 * MyProximityMeasure" as the memory is released automatically.
		 *
		 * @param trainingSamples a pointer to a list of samples to be
		 *        used in training
		 * @param measure a proximity measure for classification (autodelete)
		 * @param classCount total number of classes in the data
		 **/
		Classifier(util::List<Sample<T,I,C> >* trainingSamples = NULL, ProximityMeasure<T>* measure = NULL, int classCount = -1);
		/**
		 * Create a new classifier. The memory pointed by <i>measure</i>
		 * is automatically released upon the deletion of the classifier.
		 * Training samples are not deleted automatically.
		 *
		 * @param trainingSamples a reference to a list of samples to be
		 *        used in training
		 * @param measure a proximity measure for classification (autodelete)
		 * @param classCount total number of classes in the data
		 **/
		Classifier(util::List<Sample<T,I,C> >& trainingSamples, ProximityMeasure<T>* measure, int classCount);
		/**
		 * Create a new classifier.
		 *
		 * @param trainingSamples a reference to a list of samples to be
		 *        used in training
		 * @param measure a proximity measure for classification
		 * @param classCount total number of classes in the data
		 **/
		Classifier(util::List<Sample<T,I,C> >& trainingSamples, ProximityMeasure<T>& measure, int classCount);
		/**
		 * The Destructor of Classifier. If Autodelete mesure is on the measure
		 * will be deleted.
		 **/
		virtual ~Classifier() { if (_bDeleteMeasure) delete _proximityMeasure; }

		/**
		 * Perform a holdout test using the given samples as testing data.
		 * @param lst testing samples
		 **/
		virtual void holdOut(util::List<Sample<T,I,C> >& lst) throw (ClassificationException&);
		/**
		 * Perform a leave-one-out test on the training data.
		 **/
		virtual void leaveOneOut(void) throw (ClassificationException&);
		/**
		 * Get the classification for a single sample. This method is used
		 * by holdOut and leaveOneOut to classify each sample. Subclasses
		 * must override this method.
		 *
		 * @param sample the sample to be classified
		 * @return the classification. Simple classfiers (like NN or kNN) use
		 * integers. More sophisticated ones may use any classification type.
		 * @see Sample for more information.
		 **/
		virtual C getClassification(Sample<T,I,C>& sample) throw (ClassificationException&) = 0;

		/**
		 * Sort all classes according to their proximity to a given test
		 * sample. The default implementation loops through all training
		 * samples and finds the closest match from each class using the
		 * internal proximity measure. It then ranks the classes according
		 * to the obtained proximities. The larger the rank, the worse the
		 * match.
		 *
		 * @param sample the sample for which class ranks are to be obtained
		 * @return the rank number for each class. The length of the
		 * returned list is equal to the number classes, and each slot in
		 * the list represents the rank of the corresponding class. Note
		 * that some classifiers may be unable to produce rankings. In
		 * this case, this list contains a zero in the slot of the winning
		 * class and ones elsewhere.
		 **/
		virtual util::List<int> getRanks(Sample<T,I,C>& sample) throw (ClassificationException&);
		
		/**
		 * Change the training samples held by this classifier.
		 * @param lst the new samples
		 **/
		virtual void setTrainingSamples(util::List<Sample<T,I,C> >* lst) { _lstpTrainingSamples = lst; }
		/**
		 * Get the training samples held by this classifier.
		 **/
		util::List<Sample<T,I,C> >* getTrainingSamples(void) { return _lstpTrainingSamples; }
		/**
		 * Get the training samples held by this classifier.
		 **/
		const util::List<Sample<T,I,C> >* getTrainingSamples(void) const { return _lstpTrainingSamples; }
		/**
		 * Get the training samples held by this classifier.
		 **/
		util::List<Sample<T,I,C> >*& trainingSamples(void) { return _lstpTrainingSamples; }

		/**
		 * Set the proximity (distance) measure used in classification. If
		 * Classifier is initialized using a pointer to a proximity
		 * measure (autodelete mode), then the memory allocated by the old
		 * measure is automatically released. Autodelete mode will be
		 * turned on upon the exit of this method.
		 *
		 * @param measure the new proximity measure
		 **/
		void setProximityMeasure(ProximityMeasure<T>* measure);

		/**
		 * Set the proximity (distance) measure used in classification. If
		 * Classifier is initialized using a pointer to a proximity
		 * measure (autodelete mode), then the memory allocated by the old
		 * measure is automatically released. Autodelete mode will be
		 * turned off upon the exit of this method.
		 *
		 * @param measure the new proximity measure
		 **/
		void setProximityMeasure(ProximityMeasure<T>& measure);

		/**
		 * Get a pointer to the proximity measure.
		 **/
		ProximityMeasure<T>* getProximityMeasure(void) const { return _proximityMeasure; }
		//ProximityMeasure<T>*& proximityMeasure(void) { return _proximityMeasure; }

		/**
		 * Set the class count for this classifier. The number does not
		 * actually matter for some classifiers, but you might want to
		 * keep it correct in any case.
		 **/
		void setClassCount(int count) { _iClassCount = count; }
		/**
		 * Get the class count.
		 **/
		int getClassCount(void) const { return _iClassCount; }
		/**
		 * Get the class count.
		 **/
		int& classCount(void) { return _iClassCount; }

		/**
		 * Enable or disable the automatic deletion of the proximity
		 * measure. You will probably not need this method, but if you do,
		 * take enormous care that memory is not released twice.
		 *
		 * @param del if true, memory allocated by the proximity measure
		 *        is automatically released on deletion of the Classifier
		 *        and in setProximityMeasure().
		 **/
		void setAutodeleteMeasure(bool del) { _bDeleteMeasure = del; }
		/**
		 * See whether the classifier is going to automatically delete its
		 * proximity measure.
		 **/
		bool getAutodeleteMeasure(void) const { return _bDeleteMeasure; }
		/**
		 * Directly access the autorelease mode flag.
		 **/
		bool& autodeleteMeasure(void) { return _bDeleteMeasure; }

		/**
		 * Randomly select <i>n</i> samples from <i>samples</i>.
		 * @param samples the samples from which samples are to be selected
		 * @param n the number of samples to select
		 * @return the selected samples
		 **/
		static util::List<Sample<T,I,C> > selectRandomly(const util::List<Sample<T,I,C> >& samples,
																										 int n) throw (InvalidArgumentException&);
		
		/**
		 * Divide the given sample list into two disjoint sets, one
		 * containing the correctly classified samples and the other
		 * containing the rest.
		 * @param samples a list of samples to be divided
		 * @param corret a list for storing correctly classified samples
		 * @param corret a list for storing incorrectly classified samples
		 **/
		static void divide(const util::List<Sample<T,I,C> >& samples, util::List<Sample<T,I,C> >& correct, util::List<Sample<T,I,C> >& wrong);
		
		/**
		 * Divide the given sample list into disjoint sets. The number of
		 * disjoint sets depends on the number of classes given from the
		 * IntegerList classes. (Example: if <i>classes</i> has number 3
		 * at the index 2, then all samples that have been classified to
		 * class 2 are added to the list index 3).
		 * Return List contain classes from 0 to max integer given in classes. 
		 * @param samples a list of samples to be divided
		 * @param classes a list which tell where to put specified sample
		 * @return the List of different classes in List&lt;Sample&lt;T,I,C&gt; &gt; format 
		 **/
		static util::List<util::List<Sample<T,I,C> > > divide(const util::List<Sample<T,I,C> >& samples,
																													util::List<int>& classes) throw (ClassificationException&);

		/**
		 * DivideByTrueClass divides a sample set according to the true
		 * class of a sample (divide(samples,classes) divides by the
		 * classification).
		 *
		 * @param samples a list of samples to be divided
		 * @param classes a list of mappings for placing samples
		 * @return the List of different classes in List&lt;Sample&lt;T,I,C&gt; &gt; format
		 **/
		static util::List<util::List<Sample<T,I,C> > > divideByTrueClass(const util::List<Sample<T,I,C> >& samples,
																																		 util::List<int>& classes) throw (ClassificationException&);
		
	protected:
		/**
		 * A pointer to the list of training samples.
		 **/
		util::List<Sample<T,I,C> >* _lstpTrainingSamples;
		/**
		 * A pointer to the code used to measure proximities between samples.
		 **/
		ProximityMeasure<T>* _proximityMeasure;
		/**
		 * The number of classes.
		 **/
		int _iClassCount;

	private:
		bool _bDeleteMeasure;
	};


	template <class T, class I, class C> Classifier<T,I,C>::Classifier(util::List<Sample<T,I,C> >* samples, ProximityMeasure<T>* meas, int classes) :
		_lstpTrainingSamples(samples), _proximityMeasure(meas), _iClassCount(classes), _bDeleteMeasure(true) {}

	template <class T, class I, class C> Classifier<T,I,C>::Classifier(util::List<Sample<T,I,C> >& samples, ProximityMeasure<T>* meas, int classes) :
		_lstpTrainingSamples(&samples), _proximityMeasure(meas), _iClassCount(classes), _bDeleteMeasure(false) {}

	template <class T, class I, class C> Classifier<T,I,C>::Classifier(util::List<Sample<T,I,C> >& samples, ProximityMeasure<T>& meas, int classes) :
		_lstpTrainingSamples(&samples), _proximityMeasure(&meas), _iClassCount(classes), _bDeleteMeasure(false) {}

	template <class T, class I, class C> void Classifier<T,I,C>::setProximityMeasure(ProximityMeasure<T>* measure)
	{
		if (_bDeleteMeasure)
			delete _proximityMeasure;
		_proximityMeasure = measure;
		_bDeleteMeasure = true;
	}

	template <class T, class I, class C> void Classifier<T,I,C>::setProximityMeasure(ProximityMeasure<T>& measure)
	{
		if (_bDeleteMeasure)
			delete _proximityMeasure;
		_proximityMeasure = &measure;
		_bDeleteMeasure = false;
	}

	template <class T, class I, class C> void Classifier<T,I,C>::holdOut(util::List<Sample<T,I,C> >& testingSamples) throw (ClassificationException&)
	{
		for (int i=0;i<testingSamples.getLength();i++)
			{
				testingSamples[i].setClassification(getClassification(testingSamples[i]));
				fireEvent(new ClassificationEvent<T,I,C>(testingSamples[i],i));
			}
	}

	template <class T, class I, class C> void Classifier<T,I,C>::leaveOneOut(void) throw (ClassificationException&)
	{
		if (!_lstpTrainingSamples)
			throw ClassificationException("Classifier<T,I,C>::leaveOneOut(): No training samples.");			
		int trainSetSize = _lstpTrainingSamples->getLength();
		if (trainSetSize < 2)
			throw ClassificationException("Classifier<T,I,C>::leaveOneOut(): Cannot classify less than two samples.");
		Sample<T,I,C> last(_lstpTrainingSamples->removeElementAt(trainSetSize-1));
		for (int i=0;i<trainSetSize-1;i++) //classify all but the last sample
			{
				//We do not use removeElementAt to avoid time-consuming list shifts
				Sample<T,I,C> tmp(_lstpTrainingSamples->elementAt(i)); //store the current sample
				_lstpTrainingSamples->elementAt(i) = last; //replace it with the last sample

				tmp.setClassification(getClassification(tmp));

				_lstpTrainingSamples->elementAt(i) = tmp; //restore the current sample

				fireEvent(new ClassificationEvent<T,I,C>(tmp,i));

				//cerr << "Classified sample no. " << i << endl;
			}

		//classify the last sample
		last.setClassification(getClassification(last));
		_lstpTrainingSamples->addElement(last);
	}

	template <class T, class I, class C> util::List<int> Classifier<T,I,C>::getRanks(Sample<T,I,C>& sample) throw (ClassificationException&)
	{
		using namespace util;
		if (!_lstpTrainingSamples)
			throw ClassificationException("Classifier<T,I,C>::getRanks(Sample<T,I,C>&): No training samples.");
		if (!_proximityMeasure)
			throw ClassificationException("Classifier<T,I,C>::getRanks(Sample<T,I,C>&): No proximity measure.");
		
		List<double> minProximities(_iClassCount);
		minProximities.setLength(_iClassCount,MAXDOUBLE);
		
		for (int i=0;i<_lstpTrainingSamples->getLength();i++)
			{
				Sample<T,I,C>& model = _lstpTrainingSamples->elementAt(i);
				int trueClass = model.trueClass();
				double proximity = _proximityMeasure->getProximity(sample,model,minProximities[trueClass]);
				if (proximity < minProximities[trueClass])
					minProximities[trueClass] = proximity;
			}

		Heap<Pair<double,int>, std::less<Pair<double,int> > > heap(_iClassCount);
		for (int i=0;i<_iClassCount;i++)
			heap += Pair<double,int>(minProximities[i],i);
		List<int> ranks(_iClassCount);
		ranks.setLength(_iClassCount);
		for (int i=0;i<_iClassCount;i++)
			ranks[heap.removeElementAt(0).second()] = i;

		return ranks;
	}

	template <class T, class I, class C> util::List<Sample<T,I,C> > Classifier<T,I,C>::selectRandomly(const util::List<Sample<T,I,C> >& samples, int n)
		throw (InvalidArgumentException&)
	{
		return util::ListUtils::selectRandomly(samples,n);
	}
	
	template <class T, class I, class C> void Classifier<T,I,C>::divide(const util::List<Sample<T,I,C> >& samples,
																																			util::List<Sample<T,I,C> >& correct,
																																			util::List<Sample<T,I,C> >& wrong)
	{
		for (int i=0;i<samples.getLength();i++)
			{
				if (samples[i].getTrueClass() == samples[i].getClassification())
					correct += samples[i];
				else
					wrong += samples[i];
			}
	}

	template <class T, class I, class C>
	util::List<util::List<Sample<T,I,C> > > Classifier<T,I,C>::divide(const util::List<Sample<T,I,C> >& samples,
																																		util::List<int>& classes)
		throw (ClassificationException&)
	{
	  // we will put in list place witch is same as Classification the sample in list samples
	  // this helps when building trees.
		int len = classes.getLength();
		int maxIndex = 0;
		for (int i=classes.getLength();i--;)
			{ 
				if (classes[i] < 0)
					throw ClassificationException("Classifier<T,I,C>::divide(const util::List<Sample<T,I,C> >&, util::List<int>&): Invalid new class index.");
				if (classes[i] > maxIndex)
					maxIndex = classes[i];
			} // for loop

		// for loop couts the max index of classes we have to rise it by one
		// because we put it to length of list and we must remember that
		// list is allways one bigger if we take the number zero in count
		// thath's why we
		++maxIndex;
		
		util::List<util::List<Sample<T,I,C> > > sampleClasses(maxIndex);
		sampleClasses.setLength(maxIndex);
		
	  for (int i=0;i<samples.getLength();i++)
	    {
				//putting the sample to sampleClasses at point which we get on classes
				int classification = (int)samples[i].getClassification();
				if (classification >= len || classification < 0)
					throw ClassificationException("Classifier<T,I,C>::divide(const util::List<Sample<T,I,C> >&, util::List<int>&): Invalid classification index.");
			
				sampleClasses[classes[classification]].addElement(samples[i]);
			}//for loop
		return sampleClasses;
	}//divide funtion

	template <class T, class I, class C>
	util::List<util::List<Sample<T,I,C> > > Classifier<T,I,C>::divideByTrueClass(const util::List<Sample<T,I,C> >& samples,
																																							 util::List<int>& classes)
		throw (ClassificationException&)
	{
		// first calculating the number of classses
		int len = classes.getLength();
		int maxIndex = 0;
		for (int i=classes.getLength();i--;)
			{ 
				if (classes[i] < 0)
					throw ClassificationException("Classifier<T,I,C>::divideByTrueClass(const util::List<Sample<T,I,C> >&,"
																				"util::List<int>&): Invalid new class index.");
				if (classes[i] > maxIndex)
					maxIndex = classes[i];
			} // for loop

		// for loop couts the max index of classes we have to rise it by one
		// because we put it to length of list and we must remember that
		// list is allways one bigger if we take the number zero in count
		// thath's why we
		++maxIndex;
		
		util::List<util::List<Sample<T,I,C> > > sampleClasses(maxIndex);
		sampleClasses.setLength(maxIndex);
		
	  for (int i=0;i<samples.getLength();i++)
	    {
				//putting the sample to sampleClasses at point which we get on classes
				int trueClass = (int)samples[i].getTrueClass();
				if (trueClass >= len || trueClass < 0)
					throw ClassificationException("Classifier<T,I,C>::divideByTrueClass(const util::List<Sample<T,I,C> >&,"
																				"util::List<int>&): Invalid classification index.");
			
				sampleClasses[classes[trueClass]].addElement(samples[i]);
			}//for loop
		return sampleClasses;
		
	}//divideByTrueClass

	/**
	 * An implementation of the nearest neighbor classifier. Each
	 * unknown sample is classified according to the class of the sample
	 * that has the smallest proximity measure between it.
	 **/
	template <class T, class I=std::string, class C=int> class NNClassifier : public Classifier<T,I,C>
	{
	public:
		/**
		 * Create a new NN classifier with the given training samples,
		 * proximity measure and class count. (Autorelease measure.)
		 **/
		NNClassifier(util::List<Sample<T,I,C> >* trainingSamples, ProximityMeasure<T>* measure, int classCount) :
			Classifier<T,I,C>(trainingSamples, measure, classCount) {}
		/**
		 * Create a new NN classifier with the given training samples,
		 * proximity measure and class count. (Autorelease measure.)
		 **/
		NNClassifier(util::List<Sample<T,I,C> >& trainingSamples, ProximityMeasure<T>* measure, int classCount) :
			Classifier<T,I,C>(trainingSamples, measure, classCount) {}
		/**
		 * Create a new NN classifier with the given training samples,
		 * proximity measure and class count.
		 **/
		NNClassifier(util::List<Sample<T,I,C> >& trainingSamples, ProximityMeasure<T>& measure, int classCount) :
			Classifier<T,I,C>(trainingSamples, measure, classCount) {}
		
		C getClassification(Sample<T,I,C>& sample) throw (ClassificationException&);
	};


	template <class T, class I, class C> C NNClassifier<T,I,C>::getClassification(Sample<T,I,C>& sample) throw (ClassificationException&)
	{
		if (!_lstpTrainingSamples)
			throw ClassificationException("NNClassifier<T,I,C>::getClassification(Sample<T,I,C>&): No training samples.");
		if (!_proximityMeasure)
			throw ClassificationException("NNClassifier<T,I,C>::getClassification(Sample<T,I,C>&): No proximity measure.");

		double minProximity = MAXDOUBLE;
		C classification = 0;
		for (int i=0;i<_lstpTrainingSamples->getLength();i++)
			{
				double proximity = _proximityMeasure->getProximity(sample, _lstpTrainingSamples->elementAt(i), minProximity);
				if (proximity < minProximity)
					{
						minProximity = proximity;
						classification = _lstpTrainingSamples->elementAt(i).getTrueClass();
					}
			}
		return classification;
	}

	/**
	 * A k nearest neighbors classifier. This classifier takes k nearest
	 * neighbors to a sample, according to a given proximity measure.
	 * The classification result is the class that has the majority in
	 * the k nearest neighbors. If there is a draw between two classes,
	 * then the closest one wins. If k equals to one, the classifier
	 * functions exactly as a nearest neighbor classifier does.
	 **/
	template <class T, class I=std::string, class C=int> class kNNClassifier : public Classifier<T,I,C>
	{
	public:
		/**
		 * Create a new kNN classifier with the given training samples,
		 * proximity measure, class count and k. (Autorelease measure.)
		 **/
		kNNClassifier(util::List<Sample<T,I,C> >* trainingSamples, ProximityMeasure<T>* measure, int classCount, int k=1);
		/**
		 * Create a new kNN classifier with the given training samples,
		 * proximity measure, class count and k. (Autorelease measure.)
		 **/
		kNNClassifier(util::List<Sample<T,I,C> >& trainingSamples, ProximityMeasure<T>* measure, int classCount, int k=1);
		/**
		 * Create a new kNN classifier with the given training samples,
		 * proximity measure, class count and k.
		 **/
		kNNClassifier(util::List<Sample<T,I,C> >& trainingSamples, ProximityMeasure<T>& measure, int classCount, int k=1);
		
		C getClassification(Sample<T,I,C>& sample) throw (ClassificationException&);

		/**
		 * Set a new value for k. K is always ensured to be odd. That is,
		 * the least significant bit of k will always be turned on.
		 **/
		void setk(int newk);
		/**
		 * Get the value of k.
		 **/
		int getk(void) { return _iK; }

	private:
		util::SortedList<ValueHolder<C> > _lstProximities;
		int _iK;
	};

	
	template <class T, class I, class C> kNNClassifier<T,I,C>::kNNClassifier(util::List<Sample<T,I,C> >* trainingSamples,
																																					 ProximityMeasure<T>* measure,
																																					 int classCount,
																																					 int k) :
		Classifier<T,I,C>(trainingSamples, measure, classCount)
	{
		setk(k);
	}
	template <class T, class I, class C> kNNClassifier<T,I,C>::kNNClassifier(util::List<Sample<T,I,C> >& trainingSamples,
																																					 ProximityMeasure<T>* measure,
																																					 int classCount,
																																					 int k) :
		Classifier<T,I,C>(trainingSamples, measure, classCount)
	{
		setk(k);
	}
	template <class T, class I, class C> kNNClassifier<T,I,C>::kNNClassifier(util::List<Sample<T,I,C> >& trainingSamples,
																																					 ProximityMeasure<T>& measure,
																																					 int classCount,
																																					 int k) :
		Classifier<T,I,C>(trainingSamples, measure, classCount)
	{
		setk(k);
	}

	template <class T, class I, class C> void kNNClassifier<T,I,C>::setk(int newk)
	{
		_iK = newk | 1; //make sure k will be odd
		_lstProximities.setMaximumSize(_iK);
	}

	template <class T, class I, class C> C kNNClassifier<T,I,C>::getClassification(Sample<T,I,C>& sample) throw (ClassificationException&)
	{
		if (!_lstpTrainingSamples)
			throw ClassificationException("kNNClassifier<T,I,C>::getClassification(Sample<T,I,C>&): No training samples.");
		if (!_proximityMeasure)
			throw ClassificationException("kNNClassifier<T,I,C>::getClassification(Sample<T,I,C>&): No proximity measure.");
		_lstProximities.clear();
		_lstProximities.setLength(_iK,ValueHolder<C>(MAXDOUBLE,C(-1))); //fill with extreme distances
		for (int i=0;i<_lstpTrainingSamples->getLength();i++)
			{
				//cerr << "_lstpTrainingSamples->elementAt(i): " << _lstpTrainingSamples->elementAt(i) << endl;
				double proximity = _proximityMeasure->getProximity(sample, _lstpTrainingSamples->elementAt(i),_lstProximities[_iK-1].getValue());
				ValueHolder<C> holder(proximity,_lstpTrainingSamples->elementAt(i).getTrueClass());
				_lstProximities.addElement(holder);
			}
		if (_iK>1)
			{
				int votes[_iClassCount];
				memset(votes,0,_iClassCount*sizeof(int));
				
				for (int i=0;i<_iK;i++)
					votes[_lstProximities[i].getObject()]++;

				int votedClass = 0;
				util::List<int> winners(_iK);

				//find the winner
				for (int i=0;i<_iClassCount;i++)
					{
						if (votes[i] > votes[votedClass])
							{
								winners.clear();
								winners += i;
								votedClass = i;
							}
						else if (votes[i] == votes[votedClass])
							winners += i;
					}
				//only one winner
				if (winners.getLength() == 1)
					return votedClass;
				//many winners -> find the closest one
				else
					{
						//Go through the proximity list and find the first occurrence of
						//a winning class
						for (int i=0;i<_lstProximities.getLength();i++)
							if (winners.contains(_lstProximities[i].getObject()))
								return _lstProximities[i].getObject();
					}
			}
		return _lstProximities[0].getObject();
	}

	/**
	 * An implementation of the minimum distance classifier. Each
	 * unknown sample is classified according to the class of the
	 * prototype sample that has the smallest proximity measure
	 * between it.
	 **/
	template <class T, class I=std::string, class C=int> class MinimumDistanceClassifier : public Classifier<T,I,C>
	{
	public:
		/**
		 * Create a new MinimumDistance classifier with the given training samples,
		 * proximity measure and class count. (Autorelease measure.)
		 **/
		MinimumDistanceClassifier(util::List<Sample<T,I,C> >* trainingSamples, ProximityMeasure<T>* measure, int classCount) :
			Classifier<T,I,C>(trainingSamples, measure, classCount),_lstPrototypeVectors(classCount),_lstTrueClasses(classCount)
		{
			if (trainingSamples) initialize();
		}
		/**
		 * Create a new MinimumDistance classifier with the given training samples,
		 * proximity measure and class count. (Autorelease measure.)
		 **/
		MinimumDistanceClassifier(util::List<Sample<T,I,C> >& trainingSamples, ProximityMeasure<T>* measure, int classCount) :
			Classifier<T,I,C>(trainingSamples, measure, classCount),_lstPrototypeVectors(classCount),_lstTrueClasses(classCount) {}
		/**
		 * Create a new MinimumDistance classifier with the given training samples,
		 * proximity measure and class count.
		 **/
		MinimumDistanceClassifier(util::List<Sample<T,I,C> >& trainingSamples, ProximityMeasure<T>& measure, int classCount) :
			Classifier<T,I,C>(trainingSamples, measure, classCount),_lstPrototypeVectors(classCount),_lstTrueClasses(classCount) {}

		void setTrainingSamples(util::List<Sample<T,I,C> >* lst) { _lstpTrainingSamples = lst; if (lst) initialize(); }

		C getClassification(Sample<T,I,C>& sample) throw (ClassificationException&);

	private:
		/**
		 * Initialize function calculates the prototype vectors for every class
		 * and calculates the stdev at the same time. The vector will be calculated
		 * from the training samples.
		 **/
		void initialize() throw (ClassificationException&);

		/**
		 * Includes classes<mean|stdev<features<double> > >
		 *
		 * classes - The amount of classes in classifier.
		 * mean|stdev - List which length is 2 and which conatins the mean and stdev.
		 * features - The list which conatins the features (mean/stdev).
		 **/
		util::List<util::List<util::List<T> > > _lstPrototypeVectors;
		/**
		 * Includes the true classes
		 **/
		util::List<C> _lstTrueClasses;
	};

	template <class T,class I,class C> void MinimumDistanceClassifier<T,I,C>::initialize()
		throw (ClassificationException&)
	{
		if (!_lstpTrainingSamples)
			throw ClassificationException("MinimumDistanceClassifier<T,I,C>::initialize(): No training samples.");
		// first divide training samples for own groups.
		util::List<int> classes(_iClassCount);
		for(int i=0;i<_iClassCount;i++)classes+=i;
		util::List<util::List<Sample<T,I,C> > > trainData(divideByTrueClass(*_lstpTrainingSamples,classes));

		if(_iClassCount != trainData.getLength())
			throw ClassificationException("MinimumDistanceClassifier<T,I,C>::initialize(): Class counts differ.");

		// calculate mean and stdev for all classes in trainData.
		for(int i=0;i<trainData.getLength();i++)
			{
				_lstPrototypeVectors[i].setLength(2); // set the length for mean and variance.
				_lstTrueClasses += trainData[i][0].getTrueClass(); // get the true class
				int len = trainData[i].getLength();
				util::List<T> sum;
				util::List<T> aSum;
				for(int j=0;j<len;j++)
					{
						util::List<T> tmp(trainData[i][j].featureVector());
						sum.add(tmp);
						tmp.multiply(tmp);
						aSum += tmp;
					}
				_lstPrototypeVectors[i][0] = sum/T(len); //(mean)
				sum.multiply(_lstPrototypeVectors[i][0]); //(sum*mean)
				aSum.subtract(sum); // aSum - sum*mean
				_lstPrototypeVectors[i][1] = aSum/T(len);//and here are the variance
				_lstPrototypeVectors[i][0].divide(_lstPrototypeVectors[i][1]);// scale mean to variance.
			}
	}

	template <class T, class I, class C> C MinimumDistanceClassifier<T,I,C>::getClassification(Sample<T,I,C>& sample)
		throw (ClassificationException&)
	{
		if (!_proximityMeasure)
			throw ClassificationException("MinimumDistanceClassifier<T,I,C>::getClassification(Sample<T,I,C>&): No proximity measure.");

		double minProximity = MAXDOUBLE;
		C classification = 0;
		for (int i=0;i<_iClassCount;i++)
			{
				util::List<T> feature(sample.featureVector());
				feature.divide(_lstPrototypeVectors[i][1]);
				double proximity = _proximityMeasure->getProximity(feature, _lstPrototypeVectors[i][0], minProximity);
				if (proximity < minProximity)
					{
						minProximity = proximity;
						classification = _lstTrueClasses[i];
					}
			}
		return classification;
	}
}

#endif