/**
 * 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.incremental;

import gnu.trove.list.array.TIntArrayList;
import gnu.trove.set.TIntSet;
import gnu.trove.set.hash.TIntHashSet;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

import org.apache.logging.log4j.Logger;
import org.apache.logging.log4j.LogManager;

import org.openimaj.experiment.evaluation.cluster.analyser.FScoreClusterAnalyser;
import org.openimaj.math.matrix.MatlibMatrixUtils;
import org.openimaj.ml.clustering.IndexClusters;
import org.openimaj.ml.clustering.SparseMatrixClusterer;
import org.openimaj.util.pair.IntDoublePair;

import ch.akuhn.matrix.SparseMatrix;

/**
 *
 * An incremental clusterer which holds old {@link SparseMatrix} instances internally, 
 * only forgetting rows once they have been clustered and are relatively stable.
 * 
 * The criteria for row removal is cluster stability.
 * The defenition of cluster stability is maximum f1-score achieving a threshold between
 * clusters in the previous round and the current round. Once one round of stability is achieved
 * the cluster is stable and its elements are removed.
 * 
 * @author Sina Samangooei (ss@ecs.soton.ac.uk)
 */
public class IncrementalSparseClusterer implements SparseMatrixClusterer<IndexClusters>{
	
	private SparseMatrixClusterer<? extends IndexClusters> clusterer;
	private int window;
	protected double threshold;
	private int maxwindow = -1;
	private final static Logger logger = LogManager.getLogger(IncrementalSparseClusterer.class);
	

	/**
	 * @param clusterer the underlying clusterer
	 * @param window 
	 */
	public IncrementalSparseClusterer(SparseMatrixClusterer<? extends IndexClusters> clusterer, int window) {
		this.clusterer = clusterer;
		this.window = window;
		this.threshold = 1.;
	}
	
	/**
	 * @param clusterer the underlying clusterer
	 * @param window 
	 * @param threshold 
	 */
	public IncrementalSparseClusterer(SparseMatrixClusterer<? extends IndexClusters> clusterer, int window, double threshold) {
		this.clusterer = clusterer;
		this.window = window;
		this.threshold = threshold;
	}
	
	/**
	 * @param clusterer the underlying clusterer
	 * @param window 
	 * @param maxwindow 
	 */
	@SuppressWarnings("unused")
	private IncrementalSparseClusterer(SparseMatrixClusterer<? extends IndexClusters> clusterer, int window, int maxwindow) {
		this.clusterer = clusterer;
		this.window = window;
		if(maxwindow>0 ){
			if(maxwindow < window * 2)
				maxwindow = window * 2;
		}
		if(maxwindow <= 0){
			maxwindow = -1;
		}
		this.maxwindow  = maxwindow;
		this.threshold = 1.;
	}
	
	class WindowedSparseMatrix{
		SparseMatrix window;
		Map<Integer,Integer> indexCorrection;
		
		public WindowedSparseMatrix(SparseMatrix sm, int nextwindow, TIntSet inactive) {
			TIntArrayList active = new TIntArrayList(nextwindow);
			indexCorrection = new HashMap<Integer, Integer>();
			for (int i = 0; i < nextwindow; i++) {
				if(!inactive.contains(i)){
					indexCorrection.put(active.size(), i);
					active.add(i);
				}
			}
			window = MatlibMatrixUtils.subMatrix(sm, active, active);
		}
		
		public void correctClusters(IndexClusters clstrs){
			int[][] clusters = clstrs.clusters();
			for (int i = 0; i < clusters.length; i++) {
				int[] cluster = clusters[i];
				for (int j = 0; j < cluster.length; j++) {
					cluster[j] = indexCorrection.get(cluster[j]);
				}
			}
		}
	}

	@Override
	public IndexClusters cluster(SparseMatrix data) {
		if(window >= data.rowCount()) window = data.rowCount();
		SparseMatrix seen = MatlibMatrixUtils.subMatrix(data, 0, window, 0, window);
		int seenrows = window;
		TIntSet inactiveRows = new TIntHashSet(window);
		logger.debug("First clustering!: " + seen.rowCount() + "x" + seen.columnCount());
		IndexClusters oldClusters = clusterer.cluster(seen);
		logger.debug("First clusters:\n" + oldClusters);
		List<int[]> completedClusters = new ArrayList<int[]>();
		while(seenrows < data.rowCount()){
			int nextwindow = seenrows + window;
			if(nextwindow >= data.rowCount()) nextwindow = data.rowCount();
			if(this.maxwindow > 0 && nextwindow - inactiveRows.size() > this.maxwindow){
				logger.debug(String.format("Window size (%d) without inactive (%d) = (%d), greater than maximum (%d)",nextwindow, inactiveRows.size(), nextwindow - inactiveRows.size(), this.maxwindow));
				deactiveOldItemsAsNoise(nextwindow,inactiveRows,completedClusters);
			}
			WindowedSparseMatrix wsp = new WindowedSparseMatrix(data, nextwindow, inactiveRows);
			logger.debug("Clustering: " + wsp.window.rowCount() + "x" + wsp.window.columnCount());
			IndexClusters newClusters = clusterer.cluster(wsp.window);
			wsp.correctClusters(newClusters);
			logger.debug("New clusters:\n" + newClusters);
			// if stability == 1 for any cluster, it was the same last window, we should not include those items next round
			detectInactive(oldClusters, newClusters, inactiveRows, completedClusters);
			
			oldClusters = newClusters;
			seenrows += window;
			logger.debug("Seen rows: " + seenrows);
			logger.debug("Inactive rows: " + inactiveRows.size());
		}
		for (int i = 0; i < oldClusters.clusters().length; i++) {
			int[] cluster = oldClusters.clusters()[i];
			if(cluster.length!=0) 
				completedClusters.add(cluster);
		}
		
		return new IndexClusters(completedClusters);
	}

	private void deactiveOldItemsAsNoise(int nextwindow, TIntSet inactiveRows, List<int[]> completedClusters) {
		int toDeactivate = 0;
		while(nextwindow - inactiveRows.size() > this.maxwindow){
			if(!inactiveRows.contains(toDeactivate)){
				logger.debug("Forcing the deactivation of: " + toDeactivate);
				inactiveRows.add(toDeactivate);
				completedClusters.add(new int[]{toDeactivate});
			}
			toDeactivate++;
		}
	}

	/**
	 * Given the old and new clusters, make a decision as to which rows are now inactive,
	 * and therefore which clusters are now completed
	 * @param oldClusters
	 * @param newClusters
	 * @param inactiveRows
	 * @param completedClusters
	 */
	protected void detectInactive(IndexClusters oldClusters, IndexClusters newClusters, TIntSet inactiveRows, List<int[]> completedClusters) {
		Map<Integer, IntDoublePair> stability = calculateStability(oldClusters,newClusters,inactiveRows);
		for (Entry<Integer, IntDoublePair> e : stability.entrySet()) {
			if(e.getValue().second >= threshold){
				int[] completedCluster = oldClusters.clusters()[e.getKey()];
				inactiveRows.addAll(completedCluster);
				completedClusters.add(completedCluster);
				if(threshold == 1){
					newClusters.clusters()[e.getValue().first] = new int[0];
				}
			}
		}
	}

	protected Map<Integer, IntDoublePair> calculateStability(IndexClusters c1, IndexClusters c2, TIntSet inactiveRows) {
		
		Map<Integer, IntDoublePair> stability = new HashMap<Integer, IntDoublePair>();
		int[][] clusters1 = c1.clusters();
		int[][] clusters2 = c2.clusters();
		for (int i = 0; i < clusters1.length; i++) {
			if(clusters1[i].length == 0) continue;
			double maxnmi = 0;
			int maxj = -1;
			TIntArrayList cluster = new TIntArrayList(clusters1[i].length);
			for (int j = 0; j < clusters1[i].length; j++) {
				if(inactiveRows.contains(clusters1[i][j]))
					continue;
				cluster.add(clusters1[i][j]);
			}
			int[][] correct = new int[][]{cluster.toArray()};
			for (int j = 0; j < clusters2.length; j++) {
				int[][] estimated = new int[][]{clusters2[j]};
//				NMIAnalysis nmi = new NMIClusterAnalyser().analyse(correct, estimated);
				double score = 0;
				if(correct[0].length == 1 && estimated[0].length == 1){
					// BOTH 1, either they are the same or not!
					score = correct[0][0] == estimated[0][0] ? 1 : 0;
				}
				else{					
					score = new FScoreClusterAnalyser().analyse(correct, estimated).score();
				}
				if(!Double.isNaN(score))
				{
					if(score > maxnmi){
						maxnmi = score;
						maxj = j;
					}
				}
			}
			stability.put(i, IntDoublePair.pair(maxj, maxnmi));
		}
		logger.debug(String.format("The stability is:\n%s",stability));
		return stability;
	}

	@Override
	public int[][] performClustering(SparseMatrix data) {
		return this.cluster(data).clusters();
	}

	
}
