package yi.ai.cluster;

import yi.math.*;
import yi.ds.*;

/**
 * ClosestMerger merges the clusters if their distance is less than the
 * threshold.  The mean of each cluster is given.  The merger merges from the
 * closest distance.  After merging two clusters, the means of the merged
 * cluster is re-calculate and the closest distance between clusters is
 * re-searched.  If the new closest distance is again less than the threshold,
 * those two clusters will be merged.  Going on ...
 */

public class ClosestMerger {
  /**
   * Merge from the closest distance
   * @param means
   * @param sizes the size of each cluster
   * @param threshold
   * @param ignorezero whether leave the label 0 untouched.
   * @return the map from old label to new label
   */
  public static int[] merge(double[][] means, double[] sizes, double threshold, boolean ignorezero) {
    // number of labels (clusters), don't change after merging
    int num_label = means.length;

    Merge merge = new Merge(num_label);

    // save the size of merged clusters
    double[] s = (double[])sizes.clone();
    // make the size of cluster 0 to 0 to skip label 0
    if (ignorezero) s[0] = 0;

    // save the means
    double[][] m = new double[num_label][];
    for (int i=0; i<num_label; i++) {
      if (means[i] != null) {
        m[i] = (double[])means[i].clone();
      }
    }

    // number of cluster can be merged.  changed after merging
    int num_cluster = 0;
    for (int i=0; i<num_label; i++) if (s[i] > 0) num_cluster++;

    // loop until the closest distance is greater than the specified threshold
    while (num_cluster > 1) {

      // find the closest distance
      int closest_i = 0, closest_j = 0;
      double closest_dist = threshold;

      for (int i= 0; i< num_label; i++) {
        if (s[i] == 0) continue; // cluster[i] is merged to others
        for (int j= i+1; j< num_label; j++) {
          if (s[j] == 0) continue;
          double d = VectorUtil.EuclideanDistance(m[i], m[j]);
          if (d < closest_dist) {
            closest_dist = d;
            closest_i = i; closest_j = j;
          }
        }
      }

      // if the cloest distance is not less than the threshold, just quit
      if (closest_dist >= threshold) break;

      System.out.println("merge: " + closest_dist);

      // merge those two closest ones
      for (int i=0; i<m[closest_i].length; i++) {
        m[closest_i][i] = (m[closest_i][i] * s[closest_i] + m[closest_j][i] * s[closest_j]) /
            (s[closest_i] + s[closest_j]);
      }
      s[closest_i] += s[closest_j];
      s[closest_j] = 0;
      merge.merge(closest_j, closest_i);
    }

    return merge.decentResult();
  }

}