EDIT

import java.util.ArrayList;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Iterator;

import java.util.Set;

import eu.etaxonomy.cdm.model.common.Language;

import eu.etaxonomy.cdm.model.description.Feature;

import eu.etaxonomy.cdm.model.description.KeyStatement;

import eu.etaxonomy.cdm.model.description.PolytomousKey;

import eu.etaxonomy.cdm.model.description.PolytomousKeyNode;

import eu.etaxonomy.cdm.model.description.QuantitativeData;

import eu.etaxonomy.cdm.model.description.State;

import eu.etaxonomy.cdm.model.description.StatisticalMeasure;

import eu.etaxonomy.cdm.model.description.TaxonDescription;

import eu.etaxonomy.cdm.model.term.TermTreeNode;

import eu.etaxonomy.cdm.model.term.TermTree;

/**

public class PolytomousKeyGenerator {

	static int level=-1; // global variable needed by the printTree function in order to store the level which is being printed

	private boolean merge=true; // if this boolean is set to true, branches of the tree will be merged if the corresponding states can be used together without decreasing their score

	private TermTree dependenciesTree; // the tree containing the dependencies between states and features (InapplicableIf and OnlyApplicableIf)

	private Map<State,Set<Feature>> iIdependencies = new HashMap<>(); // map of a set of Features (value) inapplicables if a State (key) is present

	private boolean dependenciesON = true; // if this boolean is true, the dependencies are taken into account

	private String before="<";

	private String separator = " or ";

	/**

	 * Sets the features used to generate the key.

	 *

	 * @param featuresList

	public void setFeatures(List<Feature> featuresList){

		this.features = featuresList;

	/**

	 * Sets the base of taxa.

	 *

	 * @param featuresList

	public void setTaxa(Set<TaxonDescription> taxaSet){

	}

	/**

	 * Sets the tree containing the dependencies between states and features.

	 *

	 * @param tree

	public void setDependencies(TermTree tree){

		this.dependenciesTree = tree;

	/**

	 * Initializes the function buildBranches() with the starting parameters in order to build the key

	 */

	private void loop(){

		polytomousKey = PolytomousKey.NewInstance();

		PolytomousKeyNode root = polytomousKey.getRoot();

		buildBranches(root,features,taxa,true);

	}

	/**

	public PolytomousKey invoke(){

		List<PolytomousKeyNode> rootlist = new ArrayList<PolytomousKeyNode>();

		rootlist.add(polytomousKey.getRoot());

		//		String spaces = new String();

		return polytomousKey;

	}

	/**

	 *

	 * @param father the node considered

	 * @param taxaAreTheSame if in the previous level the taxa discriminated are the same, this boolean is set to true, thus if the taxa, again, are not discriminated at this level the function stops

	 */

	private void buildBranches(PolytomousKeyNode father, List<Feature> featuresLeft, Set<TaxonDescription> taxaCovered, boolean taxaDiscriminated){

		Set<Feature> innapplicables = new HashSet<Feature>();

		if (taxaCovered.size()>1) {

			Map<Feature,Float> scoreMap = featureScores(featuresLeft, taxaCovered, quantitativeFeaturesThresholds);

			dependenciesScores(scoreMap,featuresLeft, taxaCovered, quantitativeFeaturesThresholds);

			// the feature with the best score becomes the one corresponding to the current node

			Feature winnerFeature = lessStatesWinner(scoreMap, taxaCovered);

			// the feature is removed from the list of features available to build the next level of the tree

			int i;

			if (winnerFeature!=null && winnerFeature.isSupportsQuantitativeData()) {

				// first, get the threshold

				// thus the list contains two sets of TaxonDescription, the first corresponding to those before, the second to those after the threshold

				for (i=0;i<2;i++) {

					if (i==0){

					if (newTaxaCovered.size()>0 && !((newTaxaCovered.size()==taxaCovered.size()) && !taxaDiscriminated)){ // if the taxa are discriminated compared to those of the father node, a child is created

						childrenExist = true;

						PolytomousKeyNode son = PolytomousKeyNode.NewInstance();

						son.setFeature(winnerFeature);

						// old code used when PolytomousKey extended FeatureTree

						//						Representation question = new Representation(null, " " + sign + " " + threshold +unit,null, Language.DEFAULT()); // the question attribute is used to store the state of the feature

						son.setStatement(statement);

						father.addChild(son);

						boolean areTheTaxaDiscriminated;

						if (newTaxaCovered.size()==taxaCovered.size()) {

						buildBranches(son,featuresLeft, newTaxaCovered,areTheTaxaDiscriminated);

					}

				}

			List<State> statesDone = new ArrayList<State>(); // the list of states already used

			int numberOfStates;

			if (winnerFeature!=null && winnerFeature.isSupportsCategoricalData()) {

				for (TaxonDescription td : taxaCovered){

					for (DescriptionElementBase deb : td.getElements()) {

						if (deb.getFeature().equals(winnerFeature)) {

					}

					if (debConcerned!=null) {

						// a map is created, the key being the set of taxa that present the state(s) stored in the corresponding value

						Map<Set<TaxonDescription>,List<State>> taxonStatesMap = determineCategoricalStates(statesDone,(CategoricalData)debConcerned,winnerFeature,taxaCovered);

							// creates a map between the different states of the winnerFeature and the sets of states "incompatible" with them

							Map<State,Set<State>> exclusions = new HashMap<State,Set<State>>();

							featureScoreAndMerge(winnerFeature,taxaCovered,exclusions);

								// looks for the largest clique, i.e. the state with less exclusions

								List<State> clique = returnBestClique(exclusions);

								// then merges the corresponding branches

								mergeBranches(clique,taxonStatesMap);

							}

						}

						if (taxonStatesMap!=null && !taxonStatesMap.isEmpty()) {

							for (Map.Entry<Set<TaxonDescription>,List<State>> entry : taxonStatesMap.entrySet()){

									childrenExist = true;

									PolytomousKeyNode son = PolytomousKeyNode.NewInstance();

									StringBuilder questionLabel = new StringBuilder();

									for (State state : listOfStates) {

										if (dependenciesON){

											// if the dependencies are considered, removes and adds the right features from/to the list of features left

											if (iIdependencies.get(state)!= null) {

										}

										questionLabel.append(state.getLabel());

										if (listOfStates.lastIndexOf(state)!=numberOfStates)

									}

									// old code used when PolytomousKey extended FeatureTree

									KeyStatement statement = KeyStatement.NewInstance(questionLabel.toString());

									son.setFeature(winnerFeature);

									featuresLeft.remove(winnerFeature); // unlike for quantitative features, once a categorical one has been used, it cannot be reused in the same branch

									if (newTaxaCovered.size()==taxaCovered.size()) {

									buildBranches(son,featuresLeft, newTaxaCovered,areTheTaxaDiscriminated);

								}

						}

					}

			}

			// the features depending on other features are added/removed to/from the features left once the branch is done

			if (dependenciesON){

				for (Feature feature : innapplicables) {

			}

			// the winner features are put back to the features left once the branch is done

			featuresLeft.add(winnerFeature);

		}

		// if the node is a leaf, the statement contains the list of taxa to which the current leaf leads.

		if (!childrenExist){

			KeyStatement fatherStatement = father.getStatement();

			if (fatherStatement!=null){

					fatherStatement.putLabel(Language.DEFAULT(), label);

				}

			}

		}

	 *

	 * @param scoreMap

	private void dependenciesScores(Map<Feature,Float> scoreMap, List<Feature> featuresLeft,Set<TaxonDescription> coveredTaxa, Map<Feature,Float> quantitativeFeaturesThresholds){

		// first copies the list of features left

		List<Feature> pseudoFeaturesLeft = featuresLeft.subList(0, featuresLeft.size()-1);

		// then adds all the features which depend on features contained in the list

		for (Feature feature : pseudoFeaturesLeft){

		// then calculates the scores of all features that have been added

		Map<Feature,Float> newScoreMap = featureScores(pseudoFeaturesLeft, coveredTaxa, quantitativeFeaturesThresholds);

		for (Feature feature : featureDependencies.keySet()){

						// if a feature has a better than the "father" feature it depends on

						if (newScoreMap.get(feature2)>newScoreMap.get(feature)){

							// the "father" feature gets its score

						}

		}

	 *

	 * @param clique the list of States linked together (i.e. if merged have the same score)

		boolean stateFound;

		Map.Entry<Set<TaxonDescription>,List<State>> firstBranch=null;

		List<Set<TaxonDescription>> tdToDelete = new ArrayList<Set<TaxonDescription>>();

		if (clique.size()>1){

			Iterator<Map.Entry<Set<TaxonDescription>, List<State>>> it1 = taxonStatesMap.entrySet().iterator();

			while (it1.hasNext()){

				Map.Entry<Set<TaxonDescription>,List<State>> branch = it1.next();

				Iterator<State> stateIterator = clique.iterator();

				// looks for one state of the clique in this branch

				while(stateIterator.hasNext() && stateFound!=true) {

					if (branch.getValue().contains(state)) {

						stateFound=true;

				// if one state is found...

				if (stateFound==true){

					// ...for the first time, the branch becomes the one to which the others will be merged

					}

					// ... else the branch is merged to the first one.

					else {

						firstBranch.getKey().addAll(branch.getKey());

					}

			// once this is done, the branches merged to the first one are deleted

			for (Set<TaxonDescription> td : tdToDelete){

	 *

	 * @param exclusions map a state (key) to the set of states (value) which can not be merged with it without decreasing its score.

	private List<State> returnBestClique (Map<State,Set<State>> exclusions){

		int bestNumberOfExclusions=-1;;

		List<State> clique = new ArrayList<State>();

		// looks for the largest clique, i.e. the state with less exclusions

		for (Iterator<Map.Entry<State,Set<State>>> it1 = exclusions.entrySet().iterator() ; it1.hasNext();){

			Map.Entry<State,Set<State>> pair = it1.next();

			numberOfExclusions = pair.getValue().size();

				bestState = pair.getKey();

		clique.add(bestState);

			Map.Entry<State,Set<State>> pair = iterator.next();

			isNotExcluded = true;

			for (State state : clique) {

				if (pair.getValue().contains(state)) {

			}

			if (isNotExcluded){

				clique.add(pair.getKey());

	/**

	 *

	 * @param statesDone the list of states already done for this feature

		Map<Set<TaxonDescription>,List<State>> childrenStatesMap = new HashMap<Set<TaxonDescription>,List<State>>();

		List<StateData> stateDatas = categoricalData.getStateData();

		for (StateData sd : stateDatas){

		}

				statesDone.add(featureState);

				Set<TaxonDescription> newTaxaCovered = whichTaxa(feature,featureState,taxaCovered); //gets which taxa present this state

				List<State> newStates = childrenStatesMap.get(newTaxaCovered);

				if (newStates==null) { // if no states are associated to these taxa, create a new list

					newStates = new ArrayList<State>();

				newStates.add(featureState); // then add the state to the list

			}

		}

		return childrenStatesMap;

	}

	 *

	 * @param feature

	private Set<TaxonDescription> whichTaxa(Feature feature, State featureState, Set<TaxonDescription> taxaCovered){

						List<StateData> stateDatas = ((CategoricalData)deb).getStateData();

						for (StateData sd : stateDatas) {

							if (sd.getState().equals(featureState)){

								newCoveredTaxa.add(td);

							}

						}

				}

			}

	 *

	 * @param nTaxa

		if (nTaxa==1) {

		float bestScore = nTaxa*nTaxa;

		List<Feature> bestFeatures = new ArrayList<Feature>(); // if ever different features have the best score, they are put in this list

		Feature bestFeature = null;

		Iterator<Map.Entry<Feature,Float>> it = scores.entrySet().iterator();

		float newScore;

			Map.Entry<Feature,Float> pair = it.next();

			if (pair.getValue()!=null){

				newScore = Math.abs(pair.getValue()-meanScore);// the best score is the closest to the score (meanScore here)

				// a feature would have if it divided the taxa in two equal parts

				if (newScore < bestScore){

					bestFeatures.add(pair.getKey());

					bestScore = newScore;

				}else if (newScore==bestScore){

					bestFeatures.add(pair.getKey());

				}

		if (bestFeatures.size()==1) { // if there is only one feature with the best score, pick it

			return bestFeatures.get(0);

		else { // else choose the one with less states

			int lessStates=-1;

					Set<State> differentStates = new HashSet<State>();

									List<StateData> stateDatas = catdat.getStateData();

									for (StateData sd : stateDatas) {

						}

					}

					numberOfDifferentStates=differentStates.size();

					numberOfDifferentStates=2;

			}

			return bestFeature;

	 *

	 * @param nTaxa

		int i;

		for (i=1;i<nTaxa;i++){

			score = score + Math.round(i+1/2);

		}

	 *

	 * @param featuresLeft

	private Map<Feature,Float> featureScores(List<Feature> featuresLeft, Set<TaxonDescription> coveredTaxa, Map<Feature,Float> quantitativeFeaturesThresholds){

		Map<Feature,Float> scoreMap = new HashMap<Feature,Float>();

			if (feature.isSupportsCategoricalData()) {

				scoreMap.put(feature, categoricalFeatureScore(feature,coveredTaxa));

			}

				scoreMap.put(feature, quantitativeFeatureScore(feature,coveredTaxa, quantitativeFeaturesThresholds));

			}

		}

	 *

	 * @param threshold

	private List<Set<TaxonDescription>> determineQuantitativeStates (Float threshold, Feature feature, Set<TaxonDescription> taxa, StringBuilder unit){

		List<Set<TaxonDescription>> list = new ArrayList<Set<TaxonDescription>>();