// Copyright (c) 2016 - Patrick Schäfer (patrick.schaefer@hu-berlin.de)
// Distributed under the GLP 3.0 (See accompanying file LICENSE)

//modified by shifaz 2018

package dotnet54.classifiers.tschief.splitters.boss;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import dotnet54.tscore.data.MTimeSeries;
import dotnet54.tscore.data.TimeSeries;

/**
 * Symbolic Fourier Approximation as published in Schäfer, P., Högqvist, M.:
 * SFA: a symbolic fourier approximation and index for similarity search in high
 * dimensional datasets. In: EDBT, ACM (2012)
 */
public class SFA implements Serializable {
	private static final long serialVersionUID = -3903361341617350743L;

	// distribution of Fourier values
	public transient ArrayList<ValueLabel>[] orderLine;

	public HistogramType histogramType = HistogramType.EQUI_DEPTH;

	public int alphabetSize = 256;
	public byte neededBits = (byte) Words.binlog(this.alphabetSize);
	public int wordLength = 0;
	public boolean initialized = false;
	public boolean lowerBounding = true;

	public int maxWordLength;

	// The Momentary Fourier Transform
	public MFT transformation;

	// use binning / bucketing
	public double[][] bins;

	public enum HistogramType {
		EQUI_FREQUENCY, EQUI_DEPTH, INFORMATION_GAIN
	}

	// for the MFT classifier
	private boolean mftUseMaxOrMin = false;

	static class ValueLabel implements Serializable {
		private static final long serialVersionUID = 4392333771929261697L;

		public double value;
		public double label;

		public ValueLabel() {
		}

		public ValueLabel(double key, Double label) {
			this.value = key;
			this.label = label != null ? label : 0;
		}

		@Override
		public String toString() {
			return "" + this.value + ":" + this.label;
		}
	}

	public static class Words {
		public static int binlog(int bits) {
			int log = 0;
			if ((bits & 0xffff0000) != 0) {
				bits >>>= 16;
				log = 16;
			}
			if (bits >= 256) {
				bits >>>= 8;
				log += 8;
			}
			if (bits >= 16) {
				bits >>>= 4;
				log += 4;
			}
			if (bits >= 4) {
				bits >>>= 2;
				log += 2;
			}
			return log + (bits >>> 1);
		}

		public static long createWord(short[] words, int features, byte usedBits) {
			return fromByteArrayOne(words, features, usedBits);
		}

		/**
		 * Returns a long containing the values in bytes.
		 *
		 * @param bytes
		 * @param to
		 * @param usedBits
		 * @return
		 */
		public static long fromByteArrayOne(short[] bytes, int to, byte usedBits) {
			int shortsPerLong = 60 / usedBits;
			to = Math.min(bytes.length, to);

			long bits = 0;
			int start = 0;
			long shiftOffset = 1;
			for (int i = start, end = Math.min(to, shortsPerLong + start); i < end; i++) {
				for (int j = 0, shift = 1; j < usedBits; j++, shift <<= 1) {
					if ((bytes[i] & shift) != 0) {
						bits |= shiftOffset;
					}
					shiftOffset <<= 1;
				}
			}

			return bits;
		}
	}

	public SFA() {
	}

	public SFA(HistogramType histogramType) {
		this(histogramType, false);
	}

	public SFA(HistogramType histogramType, boolean mftUseMaxOrMin) {
		reset();
		this.histogramType = histogramType;
		this.mftUseMaxOrMin = mftUseMaxOrMin;
	}

	public void reset() {
		this.initialized = false;
		this.orderLine = null;
		this.bins = null;
	}

	@SuppressWarnings("unchecked")
	private void init(int l, int alphabetSize) {
		this.wordLength = l;
		this.maxWordLength = l;
		this.alphabetSize = alphabetSize;
		this.initialized = true;

		// l-dimensional bins
		this.alphabetSize = alphabetSize;
		this.neededBits = (byte) Words.binlog(alphabetSize);

		this.bins = new double[l][alphabetSize - 1];
		for (double[] row : this.bins) {
			Arrays.fill(row, Double.MAX_VALUE);
		}

		this.orderLine = new ArrayList[l];
		for (int i = 0; i < this.orderLine.length; i++) {
			this.orderLine[i] = new ArrayList<>();
		}
	}

	/**
	 * Transforms a single time series to its SFA word
	 *
	 * @param UTimeSeries a sample
	 * @return
	 */
	public short[] transform(TimeSeries UTimeSeries) {
		return transform(UTimeSeries, null);
	}

	/**
	 * Transforms a single time series to its SFA word
	 *
	 * @param UTimeSeries    a sample
	 * @param approximation the DFT approximation, if available, else pass 'null'
	 * @return
	 */
	public short[] transform(TimeSeries UTimeSeries, double[] approximation) {
		if (!this.initialized) {
			throw new RuntimeException("Please call fitTransform() first.");
		}
		if (approximation == null) {
			// get approximation of the time series
			approximation = this.transformation.transform(UTimeSeries, this.maxWordLength);
		}

		// use lookup table (bins) to get the word from the approximation
		return quantization(approximation);
	}

	/**
	 * Transforms a set of samples to SFA words
	 *
	 * @param samples a set of samples
	 * @return
	 */
	public short[][] transform(TimeSeries[] samples) {
		if (!this.initialized) {
			throw new RuntimeException("Please call fitTransform() first.");
		}
		short[][] transform = new short[samples.length][];
		for (int i = 0; i < transform.length; i++) {
			transform[i] = transform(samples[i], null);
		}

		return transform;
	}

	/**
	 * Transforms a set of time series to SFA words.
	 *
	 * @param samples       a set of samples
	 * @param approximation the DFT approximations, if available, else pass 'null'
	 * @return
	 */
	public short[][] transform(TimeSeries[] samples, double[][] approximation) {
		if (!this.initialized) {
			throw new RuntimeException("Please call fitTransform() first.");
		}
		short[][] transform = new short[samples.length][];
		for (int i = 0; i < transform.length; i++) {
			transform[i] = transform(samples[i], approximation[i]);
		}

		return transform;
	}

	/**
	 * Quantization of a DFT approximation to its SFA word
	 *
	 * @param approximation the DFT approximation of a time series
	 * @return
	 */
	public short[] quantization(double[] approximation) {
		int i = 0;
		short[] word = new short[approximation.length];
		for (double value : approximation) {
			// lookup character:
			short c = 0;
			for (; c < this.bins[i].length; c++) {
				if (value < this.bins[i][c]) {
					break;
				}
			}
			word[i++] = c;
		}
		return word;
	}

	/**
	 * Quantization of a DFT approximation to its SFA word (using bytes for each
	 * character)
	 *
	 * @param approximation the DFT approximation of a time series
	 * @return
	 */
	public byte[] quantizationByte(double[] approximation) {
		int i = 0;
		byte[] word = new byte[approximation.length];
		for (double value : approximation) {
			// lookup character:
			byte c = 0;
			for (; c < this.bins[i].length; c++) {
				if (value < this.bins[i][c]) {
					break;
				}
			}
			word[i++] = c;
		}
		return word;
	}

	protected void sortOrderLine() {
		for (List<ValueLabel> element : this.orderLine) {
			Collections.sort(element, new Comparator<ValueLabel>() {
				@Override
				public int compare(ValueLabel o1, ValueLabel o2) {
					int comp = Double.compare(o1.value, o2.value);
					if (comp != 0) {
						return comp;
					}
					return Double.compare(o1.label, o2.label);
				}
			});
		}
	}


	/**
	 * Extracts sliding windows from the time series and trains SFA based on the
	 * sliding windows. At the end of this call, the quantization bins are set.
	 *
	 * @param series   A set of samples
	 * @param windowLength The queryLength of each sliding window
	 * @param wordLength   the SFA word-queryLength
	 * @param symbols      the SFA alphabet size
	 * @param normMean     if set, the mean is subtracted from each sliding window
	 */
	public void fitWindowing(TimeSeries[] series, int windowLength, int wordLength, int symbols, boolean normMean,
							 boolean lowerBounding) {
		this.transformation = new MFT(windowLength, normMean, lowerBounding, this.mftUseMaxOrMin);

		ArrayList<TimeSeries> sa = new ArrayList<>(series.length * series[0].length() / windowLength);

		for (TimeSeries t : series) {
			sa.addAll(Arrays.asList(t.getDisjointSequences(windowLength, normMean)));
		}
		fitTransform(sa.toArray(new MTimeSeries[] {}), wordLength, symbols, normMean);
	}

	/**
	 * Extracts sliding windows from a time series and transforms it to its SFA
	 * word.
	 * <p>
	 * Returns the SFA words as short[] (from Fourier transformed windows). Each
	 * short corresponds to one character.
	 *
	 * @param series a sample
	 * @return
	 */
	public short[][] transformWindowing(TimeSeries series) {
		double[][] mft = this.transformation.transformWindowing(series, this.maxWordLength);

		short[][] words = new short[mft.length][];
		for (int i = 0; i < mft.length; i++) {
			words[i] = quantization(mft[i]);
		}

		return words;
	}

	/**
	 * Extracts sliding windows from a time series and applies the Fourier
	 * Transform.
	 * <p>
	 * Returns the Fourier transformed windows.
	 *
	 * @param series a sample
	 * @return
	 */
	public double[][] transformWindowingDouble(TimeSeries series) {
		return this.transformation.transformWindowing(series, this.maxWordLength);
	}

	/**
	 * Extracts sliding windows from a time series and transforms it to its SFA
	 * word.
	 * <p>
	 * Returns the SFA words as a single int (compacts the characters into one int).
	 *
	 * @param ts
	 * @param wordLength
	 * @return
	 */
	public int[] transformWindowingInt(TimeSeries ts, int wordLength) {
		short[][] words = transformWindowing(ts);
		int[] intWords = new int[words.length];
		for (int i = 0; i < words.length; i++) {
			intWords[i] = (int) Words.createWord(words[i], wordLength, this.neededBits);
		}
		return intWords;
	}

	/**
	 * Trains the SFA boss based on a set of samples. At the end of this call, the
	 * quantization bins are set.
	 *
	 * @param samples    the samples to use for training.
	 * @param wordLength Length of the resulting SFA words. Each character of a word
	 *                   corresponds to one Fourier value. Even characters (starting
	 *                   with 0) are real values and uneven characters are imaginary
	 *                   values. A shorter word queryLength corresponds to a
	 *                   stronger low-pass filtering of the time series.
	 * @param symbols    the alphabet size, i.e. number of quantization bins to use
	 * @param normMean   true: sets mean to 0 for each time series.
	 * @return the Fourier transformation of the time series.
	 */
	public double[][] fitTransformDouble(TimeSeries[] samples, int wordLength, int symbols, boolean normMean) {
		if (!this.initialized) {
			init(wordLength, symbols);

			if (this.transformation == null) {
				this.transformation = new MFT(samples[0].length(), normMean, this.lowerBounding,
						this.mftUseMaxOrMin);
			}
		}

		double[][] transformedSamples = fillOrderline(samples, wordLength);

		if (this.histogramType == HistogramType.EQUI_DEPTH) {
			divideEquiDepthHistogram();
		} else if (this.histogramType == HistogramType.EQUI_FREQUENCY) {
			divideEquiWidthHistogram();
		} else if (this.histogramType == HistogramType.INFORMATION_GAIN) {
//			divideHistogramInformationGain();
		}

		this.orderLine = null;

		return transformedSamples;
	}

	/**
	 * Same as fitTransformDouble but returns the SFA words instead of the Fourier
	 * transformed time series.
	 */
	public short[][] fitTransform(TimeSeries[] samples, int wordLength, int symbols, boolean normMean) {
		return transform(samples, fitTransformDouble(samples, wordLength, symbols, normMean));
	}

	/**
	 * Fills  in the orderline
	 *
	 * @param samples A set of samples
	 */
	protected double[][] fillOrderline(TimeSeries[] samples, int l) {
		double[][] transformedSamples = new double[samples.length][];

		for (int i = 0; i < samples.length; i++) {
			// z-normalization
			samples[i].normalize();

			// approximation
			transformedSamples[i] = this.transformation.transform(samples[i], l);

			for (int j = 0; j < transformedSamples[i].length; j++) {
				// round to 2 decimal places to reduce noise
				double value = Math.round(transformedSamples[i][j] * 100.0) / 100.0;
				this.orderLine[j].add(new ValueLabel(value, samples[i].label().doubleValue()));	//TODO int to dbl convt
			}
		}

		// Sort ascending by value
		sortOrderLine();

		return transformedSamples;
	}

	/**
	 * Use equi-width binning to divide the orderline
	 */
	protected void divideEquiWidthHistogram() {
		int i = 0;
		for (List<ValueLabel> elements : this.orderLine) {
			if (!elements.isEmpty()) {
				// apply the split
				double first = elements.get(0).value;
				double last = elements.get(elements.size() - 1).value;
				double intervalWidth = (last - first) / (this.alphabetSize);

				for (int c = 0; c < this.alphabetSize - 1; c++) {
					this.bins[i][c] = intervalWidth * (c + 1) + first;
				}
			}
			i++;
		}
	}

	/**
	 * Use equi-depth binning to divide the orderline
	 */
	protected void divideEquiDepthHistogram() {
		// For each real and imaginary part
		for (int i = 0; i < this.bins.length; i++) {
			// Divide into equi-depth intervals
			double depth = this.orderLine[i].size() / (double) (this.alphabetSize);

			int pos = 0;
			long count = 0;
			for (ValueLabel value : this.orderLine[i]) {
				if (++count > Math.ceil(depth * (pos + 1)) && (pos == 0 || this.bins[i][pos - 1] != value.value)) {
					this.bins[i][pos++] = value.value;
				}
			}
		}
	}

//	/**
//	 * Use information-gain to divide the orderline
//	 */
//	protected void divideHistogramInformationGain() {
//		// for each Fourier coefficient: split using maximal information gain
//		for (int i = 0; i < this.orderLine.length; i++) {
//			List<ValueLabel> element = this.orderLine[i];
//			if (!element.isEmpty()) {
//				ArrayList<Integer> splitPoints = new ArrayList<>();
//				findBestSplit(element, 0, element.size(), this.alphabetSize, splitPoints);
//
//				Collections.sort(splitPoints);
//
//				// apply the split
//				for (int j = 0; j < splitPoints.size(); j++) {
//					double value = element.get(splitPoints.get(j) + 1).value;
//					// double value = (element.get(splitPoints.get(j)).value +
//					// element.get(splitPoints.get(j)+1).value)/2.0;
//					this.bins[i][j] = value;
//				}
//			}
//		}
//	}
//
//	protected static double entropy(TObjectIntHashMap<Double> frequency, double total) {
//		double entropy = 0;
//		double log2 = 1.0 / Math.log(2.0);
//		for (int element : frequency.values()) {
//			double p = element / total;
//			if (p > 0) {
//				entropy -= p * Math.log(p) * log2;
//			}
//		}
//		return entropy;
//	}
//
//	protected static double calculateInformationGain(TObjectIntHashMap<Double> cIn, TObjectIntHashMap<Double> cOut,
//			double class_entropy, double total_c_in, double total) {
//		double total_c_out = (total - total_c_in);
//		return class_entropy - total_c_in / total * entropy(cIn, total_c_in)
//				- total_c_out / total * entropy(cOut, total_c_out);
//	}
//
//	protected void findBestSplit(List<ValueLabel> element, int start, int end, int remainingSymbols,
//			List<Integer> splitPoints) {
//
//		double bestGain = -1;
//		int bestPos = -1;
//
//		// class entropy
//		int total = end - start;
//		TObjectIntHashMap<Double> cIn = new TObjectIntHashMap<>();
//		TObjectIntHashMap<Double> cOut = new TObjectIntHashMap<>();
//		for (int pos = start; pos < end; pos++) {
//			cOut.putOrAdd(element.get(pos).label, 1, 1);
//		}
//		double class_entropy = entropy(cOut, total);
//
//		int i = start;
//		Double lastLabel = element.get(i).label;
//		i += moveElement(element, cIn, cOut, start);
//
//		for (int split = start + 1; split < end - 1; split++) {
//			Double label = element.get(i).label;
//			i += moveElement(element, cIn, cOut, split);
//
//			// only inspect changes of the label
//			if (!label.equals(lastLabel)) {
//				double gain = calculateInformationGain(cIn, cOut, class_entropy, i, total);
//
//				if (gain >= bestGain) {
//					bestPos = split;
//					bestGain = gain;
//				}
//			}
//			lastLabel = label;
//		}
//
//		if (bestPos > -1) {
//			splitPoints.add(bestPos);
//
//			// recursive split
//			remainingSymbols = remainingSymbols / 2;
//			if (remainingSymbols > 1) {
//				if (bestPos - start > 2 && end - bestPos > 2) { // enough  points?
//					findBestSplit(element, start, bestPos, remainingSymbols, splitPoints);
//					findBestSplit(element, bestPos, end, remainingSymbols, splitPoints);
//				} else if (end - bestPos > 4) { // enough  points?
//					findBestSplit(element, bestPos, (end - bestPos) / 2, remainingSymbols, splitPoints);
//					findBestSplit(element, (end - bestPos) / 2, end, remainingSymbols, splitPoints);
//				} else if (bestPos - start > 4) { // enough  points?
//					findBestSplit(element, start, (bestPos - start) / 2, remainingSymbols, splitPoints);
//					findBestSplit(element, (bestPos - start) / 2, end, remainingSymbols, splitPoints);
//				}
//			}
//		}
//	}
//
//	protected int moveElement(List<ValueLabel> element, TObjectIntHashMap<Double> cIn, TObjectIntHashMap<Double> cOut,
//			int pos) {
//		cIn.putOrAdd(element.get(pos).label, 1, 1);
//		cOut.putOrAdd(element.get(pos).label, -1, -1);
//		return 1;
//	}

	public void printBins() {
		System.out.print("[");
		for (double[] element : this.bins) {
			System.out.print("-Inf\t");
			for (double element2 : element) {
				String e = element2 != Double.MAX_VALUE ? ("" + element2) : "Inf";
				System.out.print("," + e + "\t");
			}
			System.out.println(";");
		}
		System.out.println("]");
	}

}
