package dataStructures;

import java.util.ArrayList;
import java.util.TreeSet;

public class DecisionTree {
	public ArrayList< Factor<String> > fctrs;
	public int trainLen;
	
	/**
	 * If tree is trained, prints factors by their decision impact
	 * 	- level of decision impact decreases from first to last
	 * 	- next to factors, their pure branches are also printed
	 * If tree is untrained, you basically get an object dump
	 */
	public void printTree() {
		for (Factor<String> fct : fctrs) {
			System.out.print( "\n" + fct.getName() );
			for (Bucket<String> brnch : fct.branches)
				System.out.printf("\t|%s-%s", brnch.type, 
					( (brnch.cntn == -1) ? "mix": ((brnch.cntn == 0) ? "pos":"neg") )
				);
		}
	}
	
	public DecisionTree() { }

	/**
	 * removes excess data to construct a learning tree
	 */
	public void trainTree() {
		int m = 0;
		TreeSet<Integer> exports;
		Factor<String> fct;
		ArrayList< Factor<String> > trained = new ArrayList< Factor<String> >();

		while (fctrs.size() > 0) { //keep training until all the factors have been cleansed
			fct = computeGain(); //identify factor with most gain
			exports = fct.getPures(); //export pure data, and define factor pure
			trained.add(fct); //save trained factor

			//if we have removed all the training examples, training is complete
			m += exports.size();
			if (m > trainLen)
				break;

			for(int i = 0; i < fctrs.size(); i++) { //remove already trained examples
				fctrs.get(i).removeExamples(exports);

				if (fctrs.get(i).getN() + fctrs.get(i).getP() == 0) { //remove useless factors
					fctrs.remove(fctrs.get(i));
					i--;
				}
			}
		}
		fctrs = trained;
	}
	
	/**
	 * @param datum - example to test against decision tree
	 * @return - if true, predicts a positive decision, otherwise a negative decision
	 */
	public boolean predictPos(String[] datum) {
		
		for (Factor<String> fct : fctrs)
			for (Bucket<String> brnch : fct.branches) {
				//System.out.printf("\n%s==%s\t|%b", datum[fct.index], brnch.type, datum[fct.index].equals(brnch.type));
				//check if any of the pure branches can decide a positive prediction or negative one
				if (datum[fct.index].equals(brnch.type) ) {
					return (brnch.cntn == 0 && brnch.cntn != -1) ? true:false;
				}
			}
		//none of the branches could predict, leave it to chance
		return (Math.random() > .5) ? true: false;
	}
	
	/**
	 * @return factor with the most information gain
	 */
	public Factor<String> computeGain() {
		Factor<String> max = fctrs.get(0);
		double cntP, cntN;
		
		for (Factor<String> tmpFct : fctrs) {
			cntP = (double) tmpFct.getP(); cntN = (double) tmpFct.getN();	
			tmpFct.setGain( entropy(cntP/(cntP+cntN), cntN/(cntP+cntN)) -  remainder(tmpFct) );
			//System.out.printf("\n****** factor: %s\t|information gain: %f\n", tmpFct.getName(), tmpFct.getGain() );
			if ( max.getGain() < tmpFct.getGain() )
				max = tmpFct;
		}
		fctrs.remove(max);
		//System.out.printf("\n****** factor: %s\t|information gain: %f\n", max.getName(), max.getGain() );
		return max;
	}

	/**
	 * Computes local entropy for each of a factor's branch
	 * @param fctr
	 * @return cumulative local entropy from each branch
	 */
	public double remainder(Factor<String> fctr) {
		int bgP = fctr.getP(), bgN = fctr.getN();
		double sum = 0, smP, smN;
		
		for (Bucket<String> branch : fctr.branches) {
			smP = (double) branch.cntp; smN = (double) branch.cntn;	
			sum += (smP + smN) / (bgP + bgN) * entropy( smP / (smP + smN), smN / (smP + smN) );
		}
		return sum;
	}

	/**
	 * Returns the entropy for given ratios corresponding
	 * the positive and negative values. In the case of either one
	 * (NOTE: ONLY ONE) being 0, the method excludes it form the calculation.
	 * This is because log_base2(0) = -infinity. 
	 * 
	 * @param p = p / (n+p)
	 * @param n = n / (n+p)
	 * @return entropy value
	 */
	public double entropy(double p, double n) {
		if (p == 0) {
			return - n * ( Math.log(n)/Math.log(2) );
		} else if (n == 0) {
			return - p * ( Math.log(p)/Math.log(2) );
		} else {
			return - ( p * ( Math.log(p)/Math.log(2) )
				+ n * ( Math.log(n)/Math.log(2) ) );
		}
	}

	/**
	 * Takes data and represents it as a set of "trees",
	 * 	where a factor (columns 1 to n-1) are the root.
	 * 	The possible values a factor could poses are then mapped
	 * 	as branches of the tree. Each branch has two numerical counters.
	 *  counters keep track of positive and negative outcomes (column n) 
	 *  for a given branch.
	 *  
	 * @param data - data to map
	 * @param posDec - representation of a positive value in column n
	 * @return set of trees
	 */
	public void mapData(String[][] data, String posDec) {
		fctrs = new ArrayList< Factor<String> >( );
		Factor<String> fact;
		boolean outcome;
		trainLen = data.length;
		int cols = data[0].length;
		
		for (int i = 0; i < cols-1; i++) {
			fact = new Factor<String>( data[0][i], i );
			
			for (int j = 1; j < trainLen; j++) {	
				//remove comment for debugging 
				//System.out.printf(">%d) %s %s \n", j, data[j][cols-1].trim(), data[j][cols-1]);
				if ( data[j][cols-1].trim().equals(posDec) ) outcome = true;
				else outcome = false;
				//remove comment for debugging
				//System.out.printf("f:%s\t|d:%s\t|%b\n", data[j][i], data[j][cols-1].trim(), data[j][cols-1].trim().equals(posDec) );
				//System.out.printf("pos:%s\t|dec:%s\t|%b\n", posDec, data[j][cols-1].trim(), data[j][cols-1].trim().equals(posDec) );
				fact.addExample(data[j][i], outcome, new Integer(j) );
			}			
			fctrs.add(fact);
		}	
	}
}
