/**
    * Copyright (c) 2011, The University of Southampton and the individual contributors.
    * All rights reserved.
    *
    * Redistribution and use in source and binary forms, with or without modification,
    * are permitted provided that the following conditions are met:
    *
    *   * 	Redistributions of source code must retain the above copyright notice,
    * 	this list of conditions and the following disclaimer.
   *
   *   *	Redistributions in binary form must reproduce the above copyright notice,
   * 	this list of conditions and the following disclaimer in the documentation
   * 	and/or other materials provided with the distribution.
   *
   *   *	Neither the name of the University of Southampton nor the names of its
   * 	contributors may be used to endorse or promote products derived from this
   * 	software without specific prior written permission.
   *
   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
   * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
   * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
   * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
   * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
   * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
   * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
   * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
   * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   */
  package org.openimaj.ml.clustering.rforest;
  
  import java.io.DataInput;
  import java.io.DataOutput;
  import java.io.IOException;
  import java.io.PrintWriter;
  import java.util.HashMap;
  import java.util.LinkedList;
  import java.util.List;
  import java.util.Map;
  import java.util.Map.Entry;
  import java.util.Random;
  import java.util.Scanner;
  
  import org.openimaj.citation.annotation.Reference;
  import org.openimaj.citation.annotation.ReferenceType;
  import org.openimaj.data.DataSource;
  import org.openimaj.ml.clustering.IndexClusters;
  import org.openimaj.ml.clustering.SpatialClusterer;
  import org.openimaj.ml.clustering.SpatialClusters;
  import org.openimaj.ml.clustering.assignment.HardAssigner;
  import org.openimaj.util.hash.HashCodeUtil;
  import org.openimaj.util.pair.IntFloatPair;
  
  /**
   * An implementation of the RandomForest clustering algorithm proposed by <a
   * href
   * ="http://users.info.unicaen.fr/~jurie/papers/moosman-nowak-jurie-pami08.pdf"
   * >Jurie et al</a>.
   * <p>
   * In this implementation the training phase is used to identify the limits of
   * the data (for which a very small subset may be provided). Once this is known
   * N decision trees are constructed each with M decisions (see
   * {@link RandomDecisionTree}). In the clustering phase each feature projected
   * is assigned a letter for each decision tree.
   * 
   * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
   * @author Sina Samangooei (ss@ecs.soton.ac.uk)
   */
  @Reference(
  		type = ReferenceType.Article,
  		author = { "Frank Moosmann", "Eric Nowak", "Fr{\'e}d{\'e}ric Jurie" },
  		title = "Randomized Clustering Forests for Image Classification",
  		year = "2008",
  		journal = "IEEE PAMI",
  		url = "http://dx.doi.org/10.1109/TPAMI.2007.70822")
  public class IntRandomForest
  		implements
  		SpatialClusters<int[]>,
  		SpatialClusterer<IntRandomForest, int[]>,
  		HardAssigner<int[], float[], IntFloatPair>
  {
  	private static final String HEADER = SpatialClusters.CLUSTER_HEADER + "RFIC";
  	int nDecisions;
  	int nTrees;
  	int featureLength;
  	List<RandomDecisionTree> trees;
  	int[] maxVal;
  	int[] minVal;
  	Map<Letter, Integer> letterToInt;
  	private int currentInt = 0;
  	private HashMap<Word, Integer> wordToInt;
  	private int currentWordInt = 0;
  	private int randomSeed = -1;
  
  	private Word wordFromString(String str) {
  		final String[] values = str.split("_");
  		final Letter[] intValues = new Letter[values.length];
  		int i = 0;
  		for (final String s : values) {
 			intValues[i++] = letterFromString(s);
 		}
 		return new Word(intValues);
 	}
 
 	private Letter letterFromString(String str) {
 		final String[] values = str.split("-");
 		final boolean[] intValues = new boolean[values.length];
 		int i = 0;
 		for (int j = 0; j < values.length - 1; j++) {
 			intValues[i++] = Boolean.parseBoolean(values[j]);
 		}
 		return new Letter(intValues, Integer.parseInt(values[values.length - 1]));
 	}
 
 	class Word {
 		private Letter[] letters;
 
 		Word(Letter[] value) {
 			letters = value;
 		}
 
 		@Override
 		public int hashCode() {
 			int result = HashCodeUtil.SEED;
 			for (final Letter l : letters) {
 				result = HashCodeUtil.hash(result, l);
 			}
 			return result;
 		}
 
 		@Override
 		public boolean equals(Object obj) {
 			if (!(obj instanceof Word))
 				return false;
 
 			final Word that = (Word) obj;
 			boolean same = true;
 			for (int i = 0; i < letters.length; i++) {
 				same &= letters[i].equals(that.letters[i]);
 
 				if (!same)
 					return false;
 			}
 
 			return same;
 		}
 
 		@Override
 		public String toString() {
 			String outString = "";
 			for (int i = 0; i < this.letters.length; i++) {
 				outString += "_" + letters[i];
 			}
 			return outString.substring(1);
 		}
 
 		public int hashedWord() {
 			if (!wordToInt.containsKey(this)) {
 				wordToInt.put(this, currentWordInt++);
 				if (currentWordInt == Integer.MAX_VALUE) {
 					System.err.println("Too many words!");
 					currentWordInt = 0;
 				}
 			}
 			return wordToInt.get(this);
 		}
 	}
 
 	class Letter {
 		boolean[] value;
 		int treeIndex;
 
 		public Letter(boolean[] value, int treeIndex) {
 			this.value = value;
 			this.treeIndex = treeIndex;
 		}
 
 		@Override
 		public int hashCode() {
 			int result = HashCodeUtil.SEED;
 			result = HashCodeUtil.hash(result, this.value);
 			result = HashCodeUtil.hash(result, this.treeIndex);
 			return result;
 		}
 
 		public int getTreeIndex() {
 			return this.treeIndex;
 		}
 
 		@Override
 		public boolean equals(Object obj) {
 			if (!(obj instanceof Letter))
 				return false;
 			final Letter that = (Letter) obj;
 			boolean same = true;
 			for (int i = 0; i < this.value.length; i++) {
 				same &= this.value[i] == that.value[i];
 				if (!same)
 					return false;
 			}
 			same &= this.treeIndex == that.treeIndex;
 			return same;
 		}
 
 		@Override
 		public String toString() {
 			String outString = "";
 			for (int i = 0; i < this.value.length; i++) {
 				outString += "-" + (value[i] ? 1 : 0);
 			}
 			return outString.substring(1) + "-" + this.treeIndex;
 		}
 
 		public int hashedLetter() {
 			if (!letterToInt.containsKey(this)) {
 				letterToInt.put(this, currentInt++);
 				if (currentInt == Integer.MAX_VALUE) {
 					System.err.println("... too many letters!");
 					currentInt = 0;
 				}
 			}
 			return letterToInt.get(this);
 		}
 	}
 
 	/**
 	 * Makes a default random forest with 32 trees each with 32 decisions. This
 	 * results in 10^47 potential words.
 	 */
 	public IntRandomForest() {
 		this(32, 32);
 	}
 
 	/**
 	 * Makes a random forest with nTrees each with nDecisions. This will result
 	 * in nTrees ^ nDecisions potential words
 	 * 
 	 * @param nTrees
 	 *            number of trees
 	 * @param nDecisions
 	 *            number of decisions per tree
 	 */
 	public IntRandomForest(int nTrees, int nDecisions) {
 		this.nTrees = nTrees;
 		this.nDecisions = nDecisions;
 		this.letterToInt = new HashMap<Letter, Integer>();
 		this.wordToInt = new HashMap<Word, Integer>();
 	}
 
 	private void initMinMax(int[][] data) {
 		final int[] min = new int[this.featureLength];
 		final int[] max = new int[this.featureLength];
 		boolean isSet = false;
 		for (int i = 0; i < data.length; i++) {
 			for (int j = 0; j < this.featureLength; j++) {
 				final int val = data[i][j];
 				if (!isSet) {
 					min[j] = val;
 					max[j] = val;
 				} else {
 					if (max[j] < val)
 						max[j] = val;
 					else if (min[j] > val)
 						min[j] = val;
 				}
 			}
 			isSet = true;
 		}
 		setMinMax(min, max);
 	}
 
 	/**
 	 * The maximum and minimum values for the various dimentions against which
 	 * random decisions will be based.
 	 * 
 	 * @param min
 	 * @param max
 	 */
 	public void setMinMax(int[] min, int[] max) {
 		this.minVal = min;
 		this.maxVal = max;
 
 	}
 
 	private void initTrees() {
 		this.trees = new LinkedList<RandomDecisionTree>();
 		Random r = new Random();
 		if (this.randomSeed != -1)
 			r = new Random(this.randomSeed);
 		for (int i = 0; i < nTrees; i++) {
 			final RandomDecisionTree tree = new RandomDecisionTree(this.nDecisions, this.featureLength, this.minVal,
 					this.maxVal, r);
 			this.trees.add(tree);
 		}
 	}
 
 	@Override
 	public IntRandomForest cluster(int[][] data) {
 		this.featureLength = data[0].length;
 
 		initMinMax(data);
 		initTrees();
 
 		return this;
 	}
 
 	@Override
 	public IntRandomForest cluster(DataSource<int[]> data) {
 		final int[][] dataArr = new int[data.size()][data.numDimensions()];
 
 		return cluster(dataArr);
 	}
 
 	@Override
 	public int numClusters() {
 		return this.currentInt;
 	}
 
 	@Override
 	public int numDimensions() {
 		return featureLength;
 	}
 
 	@Override
 	public int[] assign(int[][] data) {
 		final int[] proj = new int[data.length];
 
 		for (int i = 0; i < data.length; i++) {
 			proj[i] = this.assign(data[i]);
 		}
 		return proj;
 	}
 
 	/**
 	 * Push each data point provided to a set of letters, i.e. a word. Each
 	 * letter represents a set of decisions made in a single decision tree.
 	 * 
 	 * @param data
 	 * @return A word per data point
 	 */
 	public Word[] assignLetters(int[][] data) {
 		final Word[] pushedLetters = new Word[data.length];
 
 		int i = 0;
 		for (final int[] k : data) {
 			pushedLetters[i++] = this.assignWord(k);
 		}
 
 		return pushedLetters;
 	}
 
 	/**
 	 * Push a single data point to a set of letters, return the letters as word.
 	 * This is achieved by pushing the data point down each decision tree. This
 	 * returns the result of the n decisions made for that tree, this is a
 	 * single letter. As a letter is seen for the first time, it is assigned a
 	 * number. The letters are combined in sequence to construct a word.
 	 * 
 	 * @param data
 	 *            to be projected
 	 * @return A single word containing the letters containing the decisions
 	 *         made on each tree
 	 */
 	public Word assignWord(int[] data) {
 		final Letter[] pushed = new Letter[this.nTrees];
 		for (int i = 0; i < this.nTrees; i++) {
 			final boolean[] justLetter = this.trees.get(i).getLetter(data);
 			final Letter letter = new Letter(justLetter, i);
 			letter.hashedLetter();
 			pushed[i] = letter;
 		}
 		return new Word(pushed);
 	}
 
 	/**
 	 * Uses the {@link #assignWord(int[])} function to construct the word
 	 * representing this data point. If this exact word has been seen before
 	 * (i.e. these letters in this order) the same int is used. If not, a new
 	 * int is assigned for this word.
 	 * 
 	 * @param data
 	 *            a data point to be clustered to a word
 	 * @return a cluster centroid from a word
 	 */
 	@Override
 	public int assign(int[] data) {
 		final Word word = this.assignWord(data);
 		return word.hashedWord();
 	}
 
 	/**
 	 * @return The number of decision trees
 	 */
 	public int getNTrees() {
 		return this.nTrees;
 	}
 
 	/**
 	 * @return the number of decisions per tree
 	 */
 	public int getNDecisions() {
 		return this.nDecisions;
 	}
 
 	/**
 	 * @return the decision trees
 	 */
 	public List<RandomDecisionTree> getTrees() {
 		return this.trees;
 	}
 
 	@Override
 	public boolean equals(Object r) {
 		if (!(r instanceof IntRandomForest))
 			return false;
 
 		final IntRandomForest that = (IntRandomForest) r;
 
 		boolean same = true;
 
 		same &= this.numDimensions() == that.numDimensions();
 		same &= this.getNTrees() == that.getNTrees();
 		same &= this.getNDecisions() == that.getNDecisions();
 
 		for (int i = 0; i < that.trees.size(); i++) {
 			this.trees.get(i).equals(that.trees.get(i));
 		}
 
 		for (final Entry<Letter, Integer> a : that.letterToInt.entrySet()) {
 			same &= that.letterToInt.get(a.getKey()).equals(this.letterToInt.get(a.getKey()));
 		}
 
 		for (final Entry<Word, Integer> a : that.wordToInt.entrySet()) {
 			same &= that.wordToInt.get(a.getKey()).equals(this.wordToInt.get(a.getKey()));
 		}
 
 		return same;
 	}
 
 	@Override
 	public String asciiHeader() {
 		return "ASCII" + HEADER;
 	}
 
 	@Override
 	public byte[] binaryHeader() {
 		return HEADER.getBytes();
 	}
 
 	@Override
 	public void readASCII(Scanner br) throws IOException {
 		nDecisions = Integer.parseInt(br.nextLine());
 		nTrees = Integer.parseInt(br.nextLine());
 		this.letterToInt = new HashMap<Letter, Integer>();
 		featureLength = Integer.parseInt(br.nextLine());
 
 		if (this.trees == null || this.trees.size() != nTrees) {
 			trees = new LinkedList<RandomDecisionTree>();
 			for (int i = 0; i < nTrees; i++)
 				trees.add(new RandomDecisionTree().readASCII(br));
 		} else {
 			// We have an existing tree, try to read it!
 			for (final RandomDecisionTree rt : trees) {
 				rt.readASCII(br);
 			}
 		}
 
 		// Only rebuild an array of the wrong size
 		String[] line = br.nextLine().split(" ");
 		if (maxVal == null || maxVal.length != featureLength)
 			maxVal = new int[featureLength];
 		for (int i = 0; i < featureLength; i++)
 			maxVal[i] = Integer.parseInt(line[i]);
 		if (minVal == null || minVal.length != featureLength)
 			minVal = new int[featureLength];
 		line = br.nextLine().split(" ");
 		for (int i = 0; i < featureLength; i++)
 			minVal[i] = Integer.parseInt(line[i]);
 		currentInt = Integer.parseInt(br.nextLine());
 
 		line = br.nextLine().split(" ");
 		assert ((line.length - 1) == currentInt);
 		for (int i = 0; i < currentInt; i++) {
 			final String[] part = line[i].split(",");
 
 			letterToInt.put(letterFromString(part[0]), Integer.parseInt(part[1]));
 		}
 		currentWordInt = Integer.parseInt(br.nextLine());
 		if (currentWordInt != 0) {
 			line = br.nextLine().split(" ");
 			assert ((line.length - 1) == currentWordInt);
 			for (int i = 0; i < currentWordInt; i++) {
 				final String[] part = line[i].split(",");
 
 				wordToInt.put(wordFromString(part[0]), Integer.parseInt(part[1]));
 			}
 		}
 	}
 
 	@Override
 	public void readBinary(DataInput dis) throws IOException {
 		nDecisions = dis.readInt();
 		nTrees = dis.readInt();
 		this.letterToInt = new HashMap<Letter, Integer>();
 		featureLength = dis.readInt();
 		if (this.trees == null || this.trees.size() != nTrees) {
 			trees = new LinkedList<RandomDecisionTree>();
 			for (int i = 0; i < nTrees; i++)
 				trees.add(new RandomDecisionTree().readBinary(dis));
 		} else {
 			// We have an existing tree, try to read it!
 			for (final RandomDecisionTree rt : trees) {
 				rt.readBinary(dis);
 			}
 		}
 
 		if (maxVal == null || maxVal.length != featureLength)
 			maxVal = new int[featureLength];
 		for (int i = 0; i < featureLength; i++)
 			maxVal[i] = dis.readInt();
 
 		if (minVal == null || minVal.length != featureLength)
 			minVal = new int[featureLength];
 		for (int i = 0; i < featureLength; i++)
 			minVal[i] = dis.readInt();
 
 		currentInt = dis.readInt();
 		for (int i = 0; i < currentInt; i++) {
 			final int letterLen = dis.readInt();
 			final boolean[] stringBytes = new boolean[letterLen];
 			// dis.read(stringBytes, 0, stringBytes .length); // Entry key
 			for (int j = 0; j < letterLen; j++)
 				stringBytes[j] = dis.readBoolean();
 			letterToInt.put(new Letter(stringBytes, dis.readInt()), dis.readInt());
 		}
 
 		currentWordInt = dis.readInt();
 		if (currentWordInt != 0) {
 			for (int i = 0; i < currentWordInt; i++) {
 				final Letter[] letters = new Letter[dis.readInt()];
 				// dis.read(stringBytes, 0, stringBytes .length); // Entry key
 				for (int j = 0; j < letters.length; j++) {
 					final int letterLen = dis.readInt();
 					final boolean[] stringBytes = new boolean[letterLen];
 					for (int k = 0; k < stringBytes.length; k++) {
 						stringBytes[k] = dis.readBoolean();
 					}
 					letters[j] = new Letter(stringBytes, dis.readInt());
 				}
 				wordToInt.put(new Word(letters), dis.readInt());
 			}
 		}
 	}
 
 	@Override
 	public void writeASCII(PrintWriter writer) throws IOException {
 		writer.println(this.nDecisions);
 		writer.println(this.nTrees);
 		writer.println(this.featureLength);
 		for (final RandomDecisionTree tree : trees) {
 			tree.writeASCII(writer);
 			writer.println();
 		}
 		for (int i = 0; i < maxVal.length; i++)
 			writer.print(maxVal[i] + " ");
 		writer.println();
 		for (int i = 0; i < minVal.length; i++)
 			writer.print(minVal[i] + " ");
 		writer.println();
 		writer.println(currentInt);
 		for (final Entry<Letter, Integer> p : letterToInt.entrySet()) {
 			writer.print(p.getKey() + "," + p.getValue() + " ");
 		}
 		writer.println();
 		writer.println(currentWordInt);
 		for (final Entry<Word, Integer> p : wordToInt.entrySet()) {
 			writer.print(p.getKey() + "," + p.getValue() + " ");
 		}
 		writer.println();
 		writer.flush();
 	}
 
 	@Override
 	public void writeBinary(DataOutput o) throws IOException {
 		o.writeInt(nDecisions);
 		o.writeInt(nTrees);
 		o.writeInt(featureLength);
 		for (final RandomDecisionTree tree : trees) {
 			tree.write(o);
 		}
 
 		for (int i = 0; i < maxVal.length; i++)
 			o.writeInt(maxVal[i]);
 		for (int i = 0; i < minVal.length; i++)
 			o.writeInt(minVal[i]);
 
 		o.writeInt(currentInt);
 		for (final Entry<Letter, Integer> p : letterToInt.entrySet()) {
 			o.writeInt(p.getKey().value.length);
 			for (final boolean i : p.getKey().value)
 				o.writeBoolean(i);
 			o.writeInt(p.getKey().treeIndex);
 			o.writeInt(p.getValue());
 		}
 		o.writeInt(currentWordInt);
 		for (final Entry<Word, Integer> p : wordToInt.entrySet()) {
 			o.writeInt(p.getKey().letters.length);
 			for (final Letter i : p.getKey().letters) {
 				o.writeInt(i.value.length);
 				for (final boolean j : i.value)
 					o.writeBoolean(j);
 				o.writeInt(i.treeIndex);
 			}
 			o.writeInt(p.getValue());
 		}
 	}
 
 	/**
 	 * @param random
 	 *            the seed of the java {@link Random} instance used by the
 	 *            decision trees
 	 */
 	public void setRandomSeed(int random) {
 		this.randomSeed = random;
 	}
 
 	Letter newLetter(boolean[] bs, int i) {
 		return new Letter(bs, i);
 	}
 
 	Word newWord(Letter[] letters) {
 		return new Word(letters);
 	}
 
 	@Override
 	public void assignDistance(int[][] data, int[] indices, float[] distances) {
 		throw new UnsupportedOperationException("Not implemented");
 	}
 
 	@Override
 	public IntFloatPair assignDistance(int[] data) {
 		throw new UnsupportedOperationException("Not implemented");
 	}
 
 	@Override
 	public HardAssigner<int[], ?, ?> defaultHardAssigner() {
 		return this;
 	}
 
 	@Override
 	public int size() {
 		return this.currentInt;
 	}
 
 	@Override
 	public int[][] performClustering(int[][] data) {
 		return new IndexClusters(this.cluster(data).defaultHardAssigner().assign(data)).clusters();
 	}
 }