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

#ifndef _TREECLASSIFIER_H
#define _TREECLASSIFIER_H

#include <List.h>
#include <Serialization.h>
#include "Classifier.h"
#include "Sample.h"
#include <Math.h>
#include <Event.h>

using namespace util;

namespace prapi
{
	class TreeClassificationException : public ClassificationException
	{
	public:
		TreeClassificationException(string message) : ClassificationException(message) {}
	};

	template <class T, class I, class C> class TreeClassifier;
	
	/**
	 * An event for informing interested listeners of the state of the
	 * Tree Classification.
	 **/
	template <class T, class I=string, class C=int> class TreeClassificationEvent
	{
	public:
		/**
		 * Create a new TreeClassificationEvent.
		 * @param treee a reference to the TreeClassifier that was just classified/made.
		 * @param index the index of root number of the TreeClassifier.
		 **/
		TreeClassificationEvent(TreeClassifier<T,I,C>* tree, int index) : _iIndex(index) {_treeClassifier = tree;}

		/**
		 * Get a copy of the TreeClassifier that was just classified/made.
		 **/
		TreeClassifier<T,I,C>* getTreeClassifier(void) const { return _treeClassifier; }

		/**
		 * Get the TreeClassifier's index.
		 * @return how many TreeClassifiers have been classified/made this far? The first
		 *         TreeClassifier will be accompanied with index 0.
		 **/
		int getIndex(void) const { return _iIndex; }
		
	private:
		TreeClassifier<T,I,C>* _treeClassifier;
		int _iIndex;
	};
	
	/**
	 * TreeClassifier is made to help Building a treeclassifier. It Classifies
	 * root's given with function addChild. Every root have to give a Classifier
	 * which contains the information how the specified root should be classified.
	 * Remember that the template parameter T is spesified for List<T>, that means
	 * you have to give a list of Features for TreeClassifier.
	 **/
	template <class T, class I=string, class C=int> class TreeClassifier  : public EventSource<TreeClassificationEvent<T,I,C> >
	{
	public:
		/**
		 * Create a new TreeClassifier node.
		 * NOTE you must do every child TreeClassifier with new operator
		 *      therefor that the deleting of those pointers will be done right.
		 *
		 * @param classifier is the Classifier which will be used
		 *        in tree classification.
		 * @param classes is the list which includes the information
		 *        about used classes.
		 **/
		TreeClassifier(Classifier<List<T>,I,C>* classifier, IntegerList classes);
		/**
		 * NOTE destructor deletes all the children when it is deleted.
		 **/
		virtual ~TreeClassifier();

		/**
		 * AddChild funtion adds the childer for TreeClassifier.
		 * Remember that the first root index is zero.
		 * @param child new TreeClassifier which will be used in
     *        classifing child.
		 * @param rootIndex is the index of the root wanted to
		 *        classify again.
		 **/
		void addChild(TreeClassifier<T,I,C>* child, int rootIndex) throw (TreeClassificationException&);
		/**
		 * Get the child node of this TreeClassifier from rootNumber given.
		 *
		 * @param rootIndex the index of child node.
		 **/
		TreeClassifier<T,I,C>* getChild(int rootIndex)throw (TreeClassificationException&); 

		/**
		 * Perform a holdout test using the given samples as testing data for
		 * all of the roots.
		 * @param lst testing samples
		 **/
		void holdOut(List<Sample<List<T>,I,C> >& lst) throw (TreeClassificationException&);
		/**
		 * Perform a leave-one-out test on the training data for all of the
		 * roots.
		 **/
		void leaveOneOut(void) throw (TreeClassificationException&);

		/** Funktion which collects the classification from samples
		 * @param resultList sample list where wanted to add result samples.
		 **/
		void collectClassification(List<Sample<List<T>,I,C> >& resultList);

		/** Funktion which prints the TreeCalssifier.
		 * @param out the output stream
		 * @param lst list of names for features.
		 **/
		void print(ostream& out, List<string>& lst, int depth=0);

		/**
		 * Function buildTreeClassifier
		 * @param trainingSamples samples that are used at training of the tree.
		 * @param classifier which is used in building.
		 *        Remember: You should give classifier which DO NOT have any training samples.
		 * @param limitValue the value which is used to determine if some class is
		 *        so good that there is no use to divide it anymore.
		 * @param numberOfDividingTests tell how many compinations are used in every level
		 *                              (max amount).
		 * @param changeOfLimitValue tell how much the limitValue will be rised if it's too low
		 *        to build a tree.
		 **/
		void buildTreeClassifier(List<Sample<List<T>,I,C> >& trainingSamples,
														 int classCount, double limitValue,int numberOfDividingTests=10,double changeOfLimitValue=0.01)
		throw (TreeClassificationException&);

		/**
		 * Set the training samples for TreeClassifier.
		 **/ 
		void setTrainingSamples(List<Sample<List<T>,I,C> >& sampleList){_lstTrainingSamples = sampleList;}
		/**
		 * Get the Training samples from TreeClassifier.
		 **/
		List<Sample<List<T>,I,C> >& getTrainingSamples(){return &_lstTrainingSamples;}
		
		//	template <class U, class V, class W> friend ostream& operator<< (ostream& sout, TreeClassifier<U,V,W>& tree);
		//  template <class U, class V, class W> friend istream& operator>> (istream& sin, TreeClassifier<U,V,W>& tree);
		
		/**
		 * How to use TreeClassifier.<p>
		 * Example:<br>
		 * <pre>
		 *
		 *
		 * // make the first Classifier
		 * kNNClassifier<List<double> > knn(&wholeSet, &measure, 2);
		 * // make the second classifier for first root/child
		 * // remember that if you want to use same Proximity measure and
		 * // disable at the same time some fatures you have to take copy
		 * // of the ProximityMeasure.
		 * kNNClassifier<List<double> > knn1(&emptySet, &measureColour, 3);
		 *
		 * // make the list which contains information how to divide the result
		 * // of classification
		 * IntegerList classes;
		 * classes.addElements(17,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0);
		 *
		 * // make the first TreeClassifier and give the Classifier and
		 * // the divide information
		 * TreeClassifier<double> tree(&knn,&classes);
		 *
		 * // make the secon classes for the child
		 * IntegerList classes1;
		 * classes1.addElements(17,0,0,0,0,0,0,0,0,0,0,1,1,1,0,2,2,2);
		 *
		 * // make the first child TreeClassifier
		 * TreeClassifier<double>* tree1 = new TreeClassifier<double>(&knn1,&classes1);
		 *
		 * // add the child to main tree. Give the child tree and the index of root.
		 * tree.addChild(&tree1,0);
		 *
		 * // and so on...
		 * // then Classify the tree by giving
		 * tree.leaveOneOut();
		 *
		 * // If you want you can collect Classification result by
		 * List<Sample<List<double> > > resultSamples
		 * tree.collectClassification(resultSamples);
		 *
		 * // and the do ConfusionMatrix and print the results.
		 * ConfusionMatrix cm1(resultSamples,17);
		 * cm1.print(cerr,classNames);
		 *
		 * </pre>
		 **/
		
	private:
		/**
		 * Gives list of random integer numbers.
		 **/
		static IntegerList selectRandomly(int classCount);
		/**
		 * Pointer to Parent TreeClassifier.
		 **/
		TreeClassifier<T,I,C>* _pTreeClassifierParent;
		/**
		 * Pointer to List which contains all the Children what
		 * the classfier have.
		 **/
		List<TreeClassifier<T,I,C>* > _lstpTreeClassifierChildren;
		/**
		 * Pointer to IntegerList which contains information about
		 * classes for dividing.
		 **/
		IntegerList _lstClasses;
		/**
		 * Pointer to Classifier which is used to classifing the samples.
		 **/
		Classifier<List<T>,I,C>* _pClassifier;
		/**
		 * List which contains Holdout Samples
		 **/
		List<Sample<List<T>,I,C> >  _lstHoldOutList;
		/**
		 * This are the training samples of the tree.
		 **/
		List<Sample<List<T>,I,C> >  _lstTrainingSamples;
		/**
		 * Every TreeClassifiers own MultiFeatureProximity
		 **/
		MultiFeatureProximity<T> _multiFeatureProximity;
		bool _boolIsAutoldeleteUsed;
		/**
		 * integer for root Number
		 **/
		int _iRootNumber;
		/**
		 * This is the old measure for _pClassifier.
		 * And it will be returned when TreeClassifier is
		 * deleteed.
		 **/
		MultiFeatureProximity<T>* _pOldMultiFeatureProximity;
		
		/**
		 * This is therefor that there might be classification where
		 * some roots does not have any samples and there for is
		 * needeed to inform which classification is used.
		 **/
		bool _boolIsHoldOutUsed;
	};
	
  
	template <class T,class I,class C> TreeClassifier<T,I,C>::TreeClassifier(Classifier<List<T>,I,C>* classifier, IntegerList classes) :
		_pClassifier(classifier),_lstClasses(classes),_iRootNumber(-1),_boolIsHoldOutUsed(false)
	{
		_pOldMultiFeatureProximity = (MultiFeatureProximity<T>*)classifier->getProximityMeasure(); // save the oldmeasure
		_multiFeatureProximity = *_pOldMultiFeatureProximity; // get the measure
		_lstTrainingSamples = *classifier->getTrainingSamples(); // save the tarining samples of this node
		_boolIsAutoldeleteUsed = _pClassifier->getAutodeleteMeasure(); // get the information about autodelete
		_pClassifier->setAutodeleteMeasure(false);// set the autodelete of therefor that measure does not be deleted
		_pClassifier->setProximityMeasure(_multiFeatureProximity);// set the proximity measure for the classifier
	}

	template <class T,class I,class C> TreeClassifier<T,I,C>::~TreeClassifier() 
	{ // return the state of _pClassifier before treeClassifier
		_pClassifier->setProximityMeasure(_pOldMultiFeatureProximity);
		_pClassifier->setAutodeleteMeasure(_boolIsAutoldeleteUsed);
		for(int i=0;i<_lstpTreeClassifierChildren.getLength();i++)
						delete _lstpTreeClassifierChildren[i];
	}

	template <class T,class I,class C> TreeClassifier<T,I,C>* TreeClassifier<T,I,C>::getChild(int rootIndex)
		throw (TreeClassificationException&)
	{
		if(rootIndex >= _lstpTreeClassifierChildren.getLength())
			throw TreeClassificationException("TreeClassifier<T,I,C>::getChild(int) : index given is bigger than amount of childs.");

		return _lstpTreeClassifierChildren[rootIndex];
	}
	
	template <class T,class I,class C> void  TreeClassifier<T,I,C>::addChild(TreeClassifier<T,I,C>* child,int rootIndex)
		throw (TreeClassificationException&)
	{	
		_lstpTreeClassifierChildren.addElement(child);//remember to add child
		child->_pTreeClassifierParent = this;// remember to add this to parent
		child->_iRootNumber = rootIndex;
	}//addChildren

	template <class T,class I,class C> void TreeClassifier<T,I,C>::leaveOneOut(void) throw (TreeClassificationException&)
	{
		// remember to set flag _boolIsHoldOutUsed to false
		_boolIsHoldOutUsed = false;
		int len = _lstpTreeClassifierChildren.getLength();
	
		if(_lstTrainingSamples.getLength() != 0)
			{
				_pClassifier->setTrainingSamples(&_lstTrainingSamples);
				_pClassifier->leaveOneOut();// classifing first this one
			}

		if(len > 0)//testing if list have children
			{
				// dividing the classifier test set to classing the classifier test set to classes given in IntegerList _lstpClasses
				// checking first if there is need to divide
				List<List<Sample<List<T>,I,C> > > lstSampleList;
				lstSampleList = _pClassifier->divide(_lstTrainingSamples,_lstClasses);

				for(int i=0;i<len;i++)
					{ // setting the right trining samples
						_lstpTreeClassifierChildren[i]->setTrainingSamples(lstSampleList[_lstpTreeClassifierChildren[i]->_iRootNumber]);
						_lstpTreeClassifierChildren[i]->leaveOneOut(); // classifing every child
						// fire the event that tell the root ha been classified
						fireEvent(new TreeClassificationEvent<T,I,C>(_lstpTreeClassifierChildren[i],i));
					}//for
			}//if
	}//leaveOneOut

	
	template <class T,class I,class C> void TreeClassifier<T,I,C>::holdOut(List<Sample<List<T>,I,C> >& lst) throw (TreeClassificationException&)
	{
		// remember to set flag _boolIsHoldOutUsed to true
		_boolIsHoldOutUsed = true;
		int len = _lstpTreeClassifierChildren.getLength();
		
		if(lst.getLength() != 0)
			{ // first set the right training samples for classifier
				_pClassifier->setTrainingSamples(&_lstTrainingSamples);
				_pClassifier->holdOut(lst);
				_lstHoldOutList=lst;
			}
		
		if(len > 0)//testing if list have children
			{
				// make the list needeed
				List<List<Sample<List<T>,I,C> > > lstTestList;
				List<List<Sample<List<T>,I,C> > > trainingSetList;
				// dividing the lst to classes given in IntegerList _lstpClasses if needeed
				lstTestList = _pClassifier->divide(lst,_lstClasses);
				// remember to get samples out from trainingSet too
				trainingSetList = _pClassifier->divideByTrueClass(_lstTrainingSamples,_lstClasses);
		
				for(int i=0;i<len;i++)
					{ // first set the right training samples for the Children, which comes from its parents
						// traininSamples (and then classifing all)
						int index = _lstpTreeClassifierChildren[i]->_iRootNumber;
						_lstpTreeClassifierChildren[i]->setTrainingSamples(trainingSetList[index]);
						// set the samples from divide funktion (saved in List<List<Sample<T> > >)			
						_lstpTreeClassifierChildren[i]->holdOut(lstTestList[index]); // classifing every chilld
						// fire the event that tell the root ha been classified
						fireEvent(new TreeClassificationEvent<T,I,C>(_lstpTreeClassifierChildren[i],i));
					}//for
			}//if
	}//holdOut

	template <class T,class I,class C> void TreeClassifier<T,I,C>::collectClassification(List<Sample<List<T>,I,C> >& resultList)
	{
		int len = _lstpTreeClassifierChildren.getLength(); 
	
		//this one mans that leaveOneOut is used
		if(!_boolIsHoldOutUsed)
			{ //first remove old ones from the list and then add new ones
				for(int i=_lstTrainingSamples.getLength();i--;)
					{
						int index = resultList.indexOf(_lstTrainingSamples[i]);
						if(index != -1)resultList[index].setClassification(_lstTrainingSamples[i].getClassification());
						else resultList += _lstTrainingSamples[i];
					}
			}
		// if its used then add _lstHoldOutList to resultList
		else
			{ //first remove old ones from the list and then add new ones
				for(int i=_lstHoldOutList.getLength();i--;)
					{
						int index = resultList.indexOf(_lstHoldOutList[i]);
						if(index != -1)resultList[index].setClassification(_lstHoldOutList[i].getClassification());
						else resultList +=  _lstHoldOutList[i];
					}
			}
		// asking for every child their results.
		if(len > 0)
			for(int i=0;i<len;i++)
				_lstpTreeClassifierChildren[i]->collectClassification(resultList);
	}//collectClassification

	template <class T,class I,class C> void  TreeClassifier<T,I,C>::print(ostream& out, List<string>& lst,int depth)
	{
		// print first own information
		string emptySpace = "";
		for(int i=0; i< depth;i++)emptySpace += "   ";

		out << emptySpace;
		for(int i=0;i< _multiFeatureProximity.getFeatureCount();i++)
			if(_multiFeatureProximity.isFeatureEnabled(i)) out << lst[i] << " : ";
		out << "samples: "<<_lstTrainingSamples.getLength()<<endl;
		
		int len = _lstpTreeClassifierChildren.getLength(); 
		// asking for every child their results.
		if(len > 0)
			for(int i=0;i<len;i++)
				_lstpTreeClassifierChildren[i]->print(out,lst,depth+1);
	}//print

	template <class T,class I,class C> void TreeClassifier<T,I,C>::buildTreeClassifier(List<Sample<List<T>,I,C> >& trainingSamples,
																																										 int classCount,double limitValue,
																																										 int numberOfDividingTests,double changeOfLimitValue)
		throw (TreeClassificationException&)
	{
		// set the sanmples to triningsamples for classsifier
		// and save the old ones
		int oldClassCount = _pClassifier->getClassCount();
		_pClassifier->setTrainingSamples(&trainingSamples);
		_pClassifier->setClassCount(classCount);
		// first make leave one out classification for every combine of features
		// and save the result to List<ConfisionMatrix>...
		int numberOfFeatureVectors =  _multiFeatureProximity.getFeatureCount();
		List<ConfusionMatrix*> confusionMatrixes(numberOfFeatureVectors);
		double limitValueInUse = limitValue;
		// first making sure that every feature is disabled
		
		for(int i=0;i< numberOfFeatureVectors;i++)_multiFeatureProximity.setFeatureEnabled(i,false);

		// making the all combination needeed for all kinds of classifications
		List<IntegerList> combinations(Math::findAllCombinations(numberOfFeatureVectors-1));
		// then classifying the samples for every posible combination
		for(int i=0;i< combinations.getLength();i++)
			{ // activate features which are wanted
				for(int j=0; j< combinations[i].getLength();j++) 
					_multiFeatureProximity.setFeatureEnabled(combinations[i].getElementAt(j),true);
				_pClassifier->leaveOneOut();
				confusionMatrixes.addElement(new ConfusionMatrix(trainingSamples,classCount));
				// remember to deactivate  features
				for(int j=0; j< combinations[i].getLength();j++) 
					_multiFeatureProximity.setFeatureEnabled(combinations[i].getElementAt(j),false);
			}//for
		
		//////////////////////////////////// CALCULATING THE BEST FEATURES /////////////////////////////////////////////////////
		// this is for every feature and it makes list were it put's
		// it's proposal to new class division
		// numberOfSamples tells how many samples we can divide 
		int combLen = combinations.getLength();
		List<IntegerList> parametersForDivide(combLen);
		IntegerList numberOfSamples(combLen);
		parametersForDivide.setLength(combLen);
		numberOfSamples.setLength(combLen);
		bool needToRiseLimit = true;
		
		// go throw every matrix in the list
		do
			{
				needToRiseLimit = true;
				for(int i=0;i<confusionMatrixes.getLength();i++)
					{
						// go throw every line in this confusion matrix
						int classIndex = 1; // this gives the right index for every class
						parametersForDivide[i].setLength(classCount);// set the length therfor that we can use operator []
						for(int j=0;j<classCount;j++)parametersForDivide[i][j] = 0; // remember to format variables
						numberOfSamples[i] = 0;
						
						for(int j=0;j<confusionMatrixes[i]->getRows();j++)
							{
								// test if the line error is less than limitValue
								// then add the value of classIndex to place j and
								// increment the value of classIndex at the same time
								if(confusionMatrixes[i]->getError(j) < 	limitValueInUse )
									{
										parametersForDivide[i][j] = classIndex++;
										numberOfSamples[i] += Math::sum(confusionMatrixes[i]->getRow(j));
									}
							}//for confu[i]
				
						// then make the random classes
						for(int j=0;j<numberOfDividingTests;j++)
							{
								IntegerList randomClasses(selectRandomly(classCount));
								
								double error = 0;
								int amountOfClasses = 0; //tells how many classes is accepted
								int randomLen = randomClasses.getLength(); 
								for(int k=0; k< randomLen;k++)
									{ // check that class is not in use allready
										// if it is not put the value from confusion list to error
										int index = randomClasses[k];
										if(parametersForDivide[i].getElementAt(index) == 0)
											{
												error += confusionMatrixes[i]->getError(index);
												amountOfClasses++;
											}
									}// for random
								// check that there are classes  
								if(amountOfClasses != 0)
									{ // first calculate the mean error and check if its less than the limit
										if(double(error/amountOfClasses) < limitValueInUse)
											{ // set the right value for new classes
												for(int k=0; k<randomLen;k++)
													{
														parametersForDivide[i][randomClasses[k]] = classIndex;
														numberOfSamples[i] += Math::sum(confusionMatrixes[i]->getRow(randomClasses[k]));
													}
												classIndex++;//remember to increment class index
											}//if error
									}//if amountOf
							}//for numberOfDividing
						// check if there aro no classes to divide
						if(Math::max(parametersForDivide[i])!=0 && numberOfSamples[i] !=0)needToRiseLimit = false;
					}//for confu
				// if need to rise value lets do it
				if(needToRiseLimit)limitValueInUse +=  changeOfLimitValue;
				//be in loop while needToRiseLimit is false or the Limit value is smaller than 1
			}while(needToRiseLimit && (limitValueInUse  < 1));

		// for memory reasons lets make same good things
		confusionMatrixes.setLength(0);
		
		// now make the decicion which is the best feature
		int bestFeature = numberOfSamples.indexOf(Math::max(numberOfSamples));
		//int maxClassIndex = Math::max(parametersForDivide[bestFeature]);

		// in these centences you can decide by the division which is the best
		// feature
		//int maxClassIndex = Math::max(parametersForDivide[0]);

		//for(int i=1; i<parametersForDivide.getLength();i++)
		//  { 
		//		int temp = Math::max(parametersForDivide[i]);
		//		if(maxClassIndex < temp)
		//			{
		//				maxClassIndex = temp;
		//				bestFeature = i;
		//		}
		//}
	
		// set the divide information for this root and the information about features Used
		_lstClasses = parametersForDivide[bestFeature];
		
		for(int i=0; i< combinations[bestFeature].getLength();i++)  
					_multiFeatureProximity.setFeatureEnabled(combinations[bestFeature].getElementAt(i),true);		

		// divide the trainingSet
		List<List<Sample<List<T>,I,C> > > dividedSamples(Classifier<List<T>,I,C>::divideByTrueClass(trainingSamples,parametersForDivide[bestFeature]));
		//delete parametersForDivide;
		parametersForDivide.setLength(0);
		numberOfSamples.setLength(0);
		
		for(int i=0,rootIndex=0;i<dividedSamples.getLength();i++,rootIndex++)
			{ //check that thera are samples left and there are more than one class to divide
				if(dividedSamples[i].getLength() != 0 && (Math::numberOf(_lstClasses,rootIndex) > 1) && (Math::numberOf(_lstClasses,rootIndex) != classCount))
					{
						TreeClassifier* temp = new TreeClassifier(_pClassifier,*(new IntegerList(0)));
						temp->setTrainingSamples(dividedSamples[i]);
						this->addChild(temp,rootIndex);
						temp->buildTreeClassifier(dividedSamples[i],classCount,limitValue,numberOfDividingTests);
 					}
			}
		
		// set back the values which were there before we do anything
		_pClassifier->setClassCount(oldClassCount);
		// fire the event that tell the root has been made
		fireEvent(new TreeClassificationEvent<T,I,C>(this,_iRootNumber));
							
	}//buildTreeClassifier

	template <class T,class I,class C> IntegerList TreeClassifier<T,I,C>::selectRandomly(int classCount)
	{ //give the length one becauce this function can not return list which do not have any members
		IntegerList result(1);
		srand48(time(NULL));

		int numberOfClasses = int(drand48()*classCount);
		// make sure that there is not posibility have list whis length is zero
		if(numberOfClasses == 0) numberOfClasses = 1;
		for(int i=0; i<numberOfClasses ;i++)
			{
				int rnumber = int(drand48()*numberOfClasses);

				int j,len = result.getLength();
				// check than there are not the same number all ready
				for(j=0;j<len;j++)
					if(rnumber == result.getElementAt(j))break;
				// check if there were not the same number in the list
				if(j == len)result.addElement(rnumber);
			}
		return result;
	}


	template <class T, class I, class C> ostream& operator<< (ostream& sout, const TreeClassifier<T,I,C>& tree)
	{
		// first put the integerList to stream
		//	sout << IntegerList _lstClasses << endl;
		//ut << _pClassifier << endl;
		//ut << _lstTrainingSamples << endl;
		//sout << _multiFeatureProximity << endl;
		//sout << _iRootNumber << endl;
	}
	
	template <class T, class I, class C> istream& operator>> (istream& sin, TreeClassifier<T,I,C>& tree){}
	
}
#endif