package com.yahoo.labs.samoa.evaluation.measures;

/*
 * #%L
 * SAMOA
 * %%
 * Copyright (C) 2014 - 2015 Apache Software Foundation
 * %%
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *      http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * #L%
 */

import com.yahoo.labs.samoa.evaluation.measures.CMM_GTAnalysis.CMMPoint;
import com.yahoo.labs.samoa.moa.cluster.Cluster;
import com.yahoo.labs.samoa.moa.cluster.Clustering;
import com.yahoo.labs.samoa.moa.cluster.SphereCluster;
import com.yahoo.labs.samoa.moa.evaluation.MeasureCollection;
import com.yahoo.labs.samoa.moa.core.DataPoint;
import java.util.ArrayList;

/**
 * [CMM.java]
 * 
 * CMM: Main class
 * 
 * Reference: Kremer et al., "An Effective Evaluation Measure for Clustering on Evolving Data Streams", KDD, 2011
 * 
 * @author Timm jansen Data Management and Data Exploration Group, RWTH Aachen University
 */

public class CMM extends MeasureCollection {

  private static final long serialVersionUID = 1L;

  /**
   * found clustering
   */
  private Clustering clustering;

  /**
   * the ground truth analysis
   */
  private CMM_GTAnalysis gtAnalysis;

  /**
   * number of points within the horizon
   */
  private int numPoints;

  /**
   * number of clusters in the found clustering
   */
  private int numFClusters;

  /**
   * number of cluster in the adjusted groundtruth clustering that was calculated through the groundtruth analysis
   */
  private int numGT0Classes;

  /**
   * match found clusters to GT clusters
   */
  private int matchMap[];

  /**
   * pointInclusionProbFC[p][C] contains the probability of point p being included in cluster C
   */
  private double[][] pointInclusionProbFC;

  /**
   * threshold that defines when a point is being considered belonging to a cluster
   */
  private double pointInclusionProbThreshold = 0.5;

  /**
   * parameterize the error weight of missed points (default 1)
   */
  private double lamdaMissed = 1;

  /**
   * enable/disable debug mode
   */
  public boolean debug = false;

  /**
   * enable/disable class merge (main feature of ground truth analysis)
   */
  public boolean enableClassMerge = true;

  /**
   * enable/disable model error when enabled errors that are caused by the underling cluster model will not be counted
   */
  public boolean enableModelError = true;

  @Override
  protected String[] getNames() {
    String[] names = { "CMM", "CMM Basic", "CMM Missed", "CMM Misplaced", "CMM Noise",
        "CA Seperability", "CA Noise", "CA Modell" };
    return names;
  }

  @Override
  protected boolean[] getDefaultEnabled() {
    boolean[] defaults = { false, false, false, false, false, false, false, false };
    return defaults;
  }

  @Override
  public void evaluateClustering(Clustering clustering, Clustering trueClustering, ArrayList<DataPoint> points)
      throws Exception {
    this.clustering = clustering;

    numPoints = points.size();
    numFClusters = clustering.size();

    gtAnalysis = new CMM_GTAnalysis(trueClustering, points, enableClassMerge);

    numGT0Classes = gtAnalysis.getNumberOfGT0Classes();

    addValue("CA Seperability", gtAnalysis.getClassSeparability());
    addValue("CA Noise", gtAnalysis.getNoiseSeparability());
    addValue("CA Modell", gtAnalysis.getModelQuality());

    /* init the matching and point distances */
    calculateMatching();

    /* calculate the actual error */
    calculateError();
  }

  /**
   * calculates the CMM specific matching between found clusters and ground truth clusters
   */
  private void calculateMatching() {

    /**
     * found cluster frequencies
     */
    int[][] mapFC = new int[numFClusters][numGT0Classes];

    /**
     * ground truth cluster frequencies
     */
    int[][] mapGT = new int[numGT0Classes][numGT0Classes];
    int[] sumsFC = new int[numFClusters];

    // calculate fuzzy mapping from
    pointInclusionProbFC = new double[numPoints][numFClusters];
    for (int p = 0; p < numPoints; p++) {
      CMMPoint cmdp = gtAnalysis.getPoint(p);
      // found cluster frequencies
      for (int fc = 0; fc < numFClusters; fc++) {
        Cluster cl = clustering.get(fc);
        pointInclusionProbFC[p][fc] = cl.getInclusionProbability(cmdp);
        if (pointInclusionProbFC[p][fc] >= pointInclusionProbThreshold) {
          // make sure we don't count points twice that are contained in two
          // merged clusters
          if (cmdp.isNoise())
            continue;
          mapFC[fc][cmdp.workclass()]++;
          sumsFC[fc]++;
        }
      }

      // ground truth cluster frequencies
      if (!cmdp.isNoise()) {
        for (int hc = 0; hc < numGT0Classes; hc++) {
          if (hc == cmdp.workclass()) {
            mapGT[hc][hc]++;
          }
          else {
            if (gtAnalysis.getGT0Cluster(hc).getInclusionProbability(cmdp) >= 1) {
              mapGT[hc][cmdp.workclass()]++;
            }
          }
        }
      }
    }

    // assign each found cluster to a hidden cluster
    matchMap = new int[numFClusters];
    for (int fc = 0; fc < numFClusters; fc++) {
      int matchIndex = -1;
      // check if we only have one entry anyway
      for (int hc0 = 0; hc0 < numGT0Classes; hc0++) {
        if (mapFC[fc][hc0] != 0) {
          if (matchIndex == -1)
            matchIndex = hc0;
          else {
            matchIndex = -1;
            break;
          }
        }
      }

      // more then one entry, so look for most similar frequency profile
      int minDiff = Integer.MAX_VALUE;
      if (sumsFC[fc] != 0 && matchIndex == -1) {
        ArrayList<Integer> fitCandidates = new ArrayList<Integer>();
        for (int hc0 = 0; hc0 < numGT0Classes; hc0++) {
          int errDiff = 0;
          for (int hc1 = 0; hc1 < numGT0Classes; hc1++) {
            // fc profile doesn't fit into current hc profile
            double freq_diff = mapFC[fc][hc1] - mapGT[hc0][hc1];
            if (freq_diff > 0) {
              errDiff += freq_diff;
            }
          }
          if (errDiff == 0) {
            fitCandidates.add(hc0);
          }
          if (errDiff < minDiff) {
            minDiff = errDiff;
            matchIndex = hc0;
          }
          if (debug) {
            // System.out.println("FC"+fc+"("+Arrays.toString(mapFC[fc])+") - HC0_"+hc0+"("+Arrays.toString(mapGT[hc0])+"):"+errDiff);
          }
        }
        // if we have a fitting profile overwrite the min error choice
        // if we have multiple fit candidates, use majority vote of
        // corresponding classes
        if (fitCandidates.size() != 0) {
          int bestGTfit = fitCandidates.get(0);
          for (int i = 1; i < fitCandidates.size(); i++) {
            int GTfit = fitCandidates.get(i);
            if (mapFC[fc][GTfit] > mapFC[fc][bestGTfit])
              bestGTfit = fitCandidates.get(i);
          }
          matchIndex = bestGTfit;
        }
      }

      matchMap[fc] = matchIndex;
      int realMatch = -1;
      if (matchIndex == -1) {
        if (debug)
          System.out.println("No cluster match: needs to be implemented?");
      }
      else {
        realMatch = gtAnalysis.getGT0Cluster(matchMap[fc]).getLabel();
      }
      clustering.get(fc).setMeasureValue("CMM Match", "C" + realMatch);
      clustering.get(fc).setMeasureValue("CMM Workclass", "C" + matchMap[fc]);
    }

    // print matching table
    if (debug) {
      for (int i = 0; i < numFClusters; i++) {
        System.out.print("C" + ((int) clustering.get(i).getId()) + " N:" + ((int) clustering.get(i).getWeight())
            + "  |  ");
        for (int j = 0; j < numGT0Classes; j++) {
          System.out.print(mapFC[i][j] + " ");
        }
        System.out.print(" = " + sumsFC[i] + " | ");
        String match = "-";
        if (matchMap[i] != -1) {
          match = Integer.toString(gtAnalysis.getGT0Cluster(matchMap[i]).getLabel());
        }
        System.out.println(" --> " + match + "(work:" + matchMap[i] + ")");
      }
    }
  }

  /**
   * Calculate the actual error values
   */
  private void calculateError() {
    int totalErrorCount = 0;
    int totalRedundancy = 0;
    int trueCoverage = 0;
    int totalCoverage = 0;

    int numNoise = 0;
    double errorNoise = 0;
    double errorNoiseMax = 0;

    double errorMissed = 0;
    double errorMissedMax = 0;

    double errorMisplaced = 0;
    double errorMisplacedMax = 0;

    double totalError = 0.0;
    double totalErrorMax = 0.0;

    /**
     * mainly iterate over all points and find the right error value for the point. within the same run calculate
     * various other stuff like coverage etc...
     */
    for (int p = 0; p < numPoints; p++) {
      CMMPoint cmdp = gtAnalysis.getPoint(p);
      double weight = cmdp.weight();
      // noise counter
      if (cmdp.isNoise()) {
        numNoise++;
        // this is always 1
        errorNoiseMax += cmdp.connectivity * weight;
      }
      else {
        errorMissedMax += cmdp.connectivity * weight;
        errorMisplacedMax += cmdp.connectivity * weight;
      }
      // sum up maxError as the individual errors are the quality weighted
      // between 0-1
      totalErrorMax += cmdp.connectivity * weight;

      double err = 0;
      int coverage = 0;

      // check every FCluster
      for (int c = 0; c < numFClusters; c++) {
        // contained in cluster c?
        if (pointInclusionProbFC[p][c] >= pointInclusionProbThreshold) {
          coverage++;

          if (!cmdp.isNoise()) {
            // PLACED CORRECTLY
            if (matchMap[c] == cmdp.workclass()) {
            }
            // MISPLACED
            else {
              double errvalue = misplacedError(cmdp, c);
              if (errvalue > err)
                err = errvalue;
            }
          }
          else {
            // NOISE
            double errvalue = noiseError(cmdp, c);
            if (errvalue > err)
              err = errvalue;
          }
        }
      }
      // not in any cluster
      if (coverage == 0) {
        // MISSED
        if (!cmdp.isNoise()) {
          err = missedError(cmdp, true);
          errorMissed += weight * err;
        }
        // NOISE
        else {
        }
      }
      else {
        if (!cmdp.isNoise()) {
          errorMisplaced += err * weight;
        }
        else {
          errorNoise += err * weight;
        }
      }

      /* processing of other evaluation values */
      totalError += err * weight;
      if (err != 0)
        totalErrorCount++;
      if (coverage > 0)
        totalCoverage++; // points covered by clustering (incl. noise)
      if (coverage > 0 && !cmdp.isNoise())
        trueCoverage++; // points covered by clustering, don't count noise
      if (coverage > 1)
        totalRedundancy++; // include noise

      cmdp.p.setMeasureValue("CMM", err);
      cmdp.p.setMeasureValue("Redundancy", coverage);
    }

    addValue("CMM", (totalErrorMax != 0) ? 1 - totalError / totalErrorMax : 1);
    addValue("CMM Missed", (errorMissedMax != 0) ? 1 - errorMissed / errorMissedMax : 1);
    addValue("CMM Misplaced", (errorMisplacedMax != 0) ? 1 - errorMisplaced / errorMisplacedMax : 1);
    addValue("CMM Noise", (errorNoiseMax != 0) ? 1 - errorNoise / errorNoiseMax : 1);
    addValue("CMM Basic", 1 - ((double) totalErrorCount / (double) numPoints));

    if (debug) {
      System.out.println("-------------");
    }
  }

  private double noiseError(CMMPoint cmdp, int assignedClusterID) {
    int gtAssignedID = matchMap[assignedClusterID];
    double error;

    // Cluster wasn't matched, so just contains noise
    // TODO: Noiscluster?
    // also happens when we decrease the radius and there is only a noise point
    // in the center
    if (gtAssignedID == -1) {
      error = 1;
      cmdp.p.setMeasureValue("CMM Type", "noise - cluster");
    }
    else {
      if (enableModelError
          && gtAnalysis.getGT0Cluster(gtAssignedID).getInclusionProbability(cmdp) >= pointInclusionProbThreshold) {
        // set to MIN_ERROR so we can still track the error
        error = 0.00001;
        cmdp.p.setMeasureValue("CMM Type", "noise - byModel");
      }
      else {
        error = 1 - gtAnalysis.getConnectionValue(cmdp, gtAssignedID);
        cmdp.p.setMeasureValue("CMM Type", "noise");
      }
    }

    return error;
  }

  private double missedError(CMMPoint cmdp, boolean useHullDistance) {
    cmdp.p.setMeasureValue("CMM Type", "missed");
    if (!useHullDistance) {
      return cmdp.connectivity;
    }
    else {
      // main idea: look at relative distance of missed point to cluster
      double minHullDist = 1;
      for (int fc = 0; fc < numFClusters; fc++) {
        // if fc is mappend onto the class of the point, check it for its
        // hulldist
        if (matchMap[fc] != -1 && matchMap[fc] == cmdp.workclass()) {
          if (clustering.get(fc) instanceof SphereCluster) {
            SphereCluster sc = (SphereCluster) clustering.get(fc);
            double distanceFC = sc.getCenterDistance(cmdp);
            double radius = sc.getRadius();
            double hullDist = (distanceFC - radius) / (distanceFC + radius);
            if (hullDist < minHullDist)
              minHullDist = hullDist;
          }
          else {
            double min = 1;
            double max = 1;

            // TODO: distance for random shape
            // generate X points from the cluster with
            // clustering.get(fc).sample(null)
            // and find Min and Max values

            double hullDist = min / max;
            if (hullDist < minHullDist)
              minHullDist = hullDist;
          }
        }
      }

      // use distance as weight
      if (minHullDist > 1)
        minHullDist = 1;

      double weight = (1 - Math.exp(-lamdaMissed * minHullDist));
      cmdp.p.setMeasureValue("HullDistWeight", weight);

      return weight * cmdp.connectivity;
    }
  }

  private double misplacedError(CMMPoint cmdp, int assignedClusterID) {
    double weight = 0;

    int gtAssignedID = matchMap[assignedClusterID];
    // TODO take care of noise cluster?
    if (gtAssignedID == -1) {
      System.out.println("Point " + cmdp.getTimestamp() + " from gtcluster " + cmdp.trueClass
          + " assigned to noise cluster " + assignedClusterID);
      return 1;
    }

    if (gtAssignedID == cmdp.workclass())
      return 0;
    else {
      // assigned and real GT0 cluster are not connected, but does the model
      // have the
      // chance of separating this point after all?
      if (enableModelError
          && gtAnalysis.getGT0Cluster(gtAssignedID).getInclusionProbability(cmdp) >= pointInclusionProbThreshold) {
        weight = 0;
        cmdp.p.setMeasureValue("CMM Type", "missplaced - byModel");
      }
      else {
        // point was mapped onto wrong cluster (assigned), so check how far away
        // the nearest point is within the wrongly assigned cluster
        weight = 1 - gtAnalysis.getConnectionValue(cmdp, gtAssignedID);
      }
    }
    double err_value;
    // set to MIN_ERROR so we can still track the error
    if (weight == 0) {
      err_value = 0.00001;
    }
    else {
      err_value = weight * cmdp.connectivity;
      cmdp.p.setMeasureValue("CMM Type", "missplaced");
    }

    return err_value;
  }

  public String getParameterString() {
    String para = gtAnalysis.getParameterString();
    para += "lambdaMissed=" + lamdaMissed + ";";
    return para;
  }

}