package yi.ai.cluster;

/**
 * Class DistanceCluster implements the clustering algorithm from the c program:
 * /homes/rivers/yuyu/Law-Texture/cluster.c
 */
public class DistanceCluster {

  double SPLIT_THRESHOLD = 0.5;

  /**
   * Cluster the data
   * @param data the data vectors
   * @param data_dim data dimension
   * @param max_cluster_num the maximum cluster number
   * @return the resultant clusters
   */
  public Clusters clustering(int[][] data, int data_dim, int max_cluster_num) {
    int[] labels = new int[data.length];
    double[][] clusters = new double[max_cluster_num][data_dim];
    int cluster_num = clustering(data, data_dim, labels, max_cluster_num, clusters);
    return new Clusters(cluster_num, data_dim, clusters, data.length, labels);
  }

  /**
   * Cluster the data
   * @param data the data vectors
   * @param data_dim data dimension
   * @param labels to return the cluster result for each data vector.  Must
   *              be inited to get the result back.  Can be left as null.
   * @param max_cluster_num the maximum cluster number
   * @param clusters to return the cluster averages.  Must be inited to get
   *                 the result back.  Can be left as null
   * @return the cluster number
   */
  public int clustering(int[][] data, int data_dim, int[] labels,
               int max_cluster_num, double[][] clusters) {
    if (labels == null) labels = new int[data.length];
    if (clusters == null) clusters = new double[max_cluster_num][data_dim];

    // find a random data as a seed;
    // find the data has the longest distance to the seed
    // assign the data with the longest distance as the first cluster average
    int seed = (int)(Math.random() * data.length);

    int extreme = farest(data[seed], data, data.length);
//    System.out.println("max_dist_index = " + extreme +
//      ", max_dist = " + distance(data[extreme], data[seed]));

    for (int i=0; i<data_dim; i++) clusters[0][i] = data[extreme][i];

    // find the data farest from the first cluster as the second cluster average
    extreme = farest(clusters[0], data, data.length);
    for (int i=0; i<data_dim; i++) clusters[1][i] = data[extreme][i];

//    printVector("cluster[0]", clusters[0]);
//    printVector("cluster[1]", clusters[1]);

    // begin the loop
    // 1. assign each pixel to one of the existing and closest cluster
    // 2. calculate the average of each cluster avg(i) and the max distance a
    //    cluster member to the cluster average max_dist(i)
    // 3. calculate the average distance of each cluster to other clusters, avg_dist(i)
    // 4. If max_dist(i) > 1/2 * avg_dist(i), then split cluster i to two.  The
    //    vector with the longest distance to the average will be put into the
    //    new vector first; if any break happens, go to step 1
    int cluster_num = 2;
    double[] max_dists = new double[max_cluster_num];
    int[] max_dist_vectors = new int[max_cluster_num];
    boolean split;
    int loop = 0;
    do {
      loop ++;
//      System.out.println();
//      System.out.println();
//      System.out.println("LOOP" + loop);
//      // print out the averages
//      System.out.println("Average :");
//      for (int i=0; i<cluster_num; i++) printVector("c" + i, clusters[i]);
      // reassign the vectors to clusters
      assign2Cluster(clusters, cluster_num, data, labels,
                     max_dists, max_dist_vectors);
//      int[] demo = yi.util.ImageUtil.makeNewImageFromLabel(labels);
//      yi.util.io.OutputResult.outputGIFImage("assign." + loop +".1.gif",demo,640,435);
//      // print out the max distances
//      printVector("max dists 1: ", max_dists);
//      printVector("max dist vectors 1: ", max_dist_vectors);

      // find the average of each clusters
      average(data, labels, cluster_num, clusters);
//      // print out the averages
//      System.out.println("Average :");
//      for (int i=0; i<cluster_num; i++) printVector("c" + i, clusters[i]);

      // reassign the data to clusters again after calculate the averages
      assign2Cluster(clusters, cluster_num, data, labels,
                     max_dists, max_dist_vectors);
//      demo = yi.util.ImageUtil.makeNewImageFromLabel(labels);
//      yi.util.io.OutputResult.outputGIFImage("assign." + loop +".2.gif",demo,640,435);
      // print out the max distances
//      printVector("max dists 2: ", max_dists);
//      printVector("max dist vectors 2: ", max_dist_vectors);

      // split or not?
      if (cluster_num == max_cluster_num) break;
      split = false;

      int new_cluster_num = split(clusters, cluster_num, data_dim, max_dists, max_dist_vectors, data);
      if (new_cluster_num != cluster_num) {
        cluster_num = new_cluster_num;
        split = true;
      }

    } while (split);
    return cluster_num;
  }

  /**
   * Decide whether to split or not.  Have the maximum distance from a cluster
   * member to the cluster average for each cluster (max_dists[i]); calculate the
   * average distance from a cluster to other clusters for each clsuter
   * (avg_dists[i]).  The ratio ratio[i]=max_dists[i]/avg_dists[i] is used to decide
   * which cluster to split: a big ratio means some members of the cluster are
   * almost as far as other cluster average and it is hint to split it; on the
   * other hand, a small ratio means the cluster members are close to each other
   * compared to the data in other clusters.  SPLIT_THRESHOLD is a parameter to
   * decide whether or not to continue split: if the ratio of each cluster is
   * lower than this parameter, stop splitting.
   * @return the number of cluster after split.
   */
  int split (double[][] clusters, int cluster_num, int data_dim,
                 double[] max_dists, int[] max_dist_vectors, int[][] data) {

    double[] avg_dists = new double[cluster_num];
    double[] ratios = new double[cluster_num];
    for (int i=0; i<cluster_num; i++) {
      // calculate the average distance of the cluster to others.
      for (int j=0; j<cluster_num; j++) {
        if (j==i) continue;
        avg_dists[i] += distance(clusters[i], clusters[j]);
//        System.out.println("dist(" + i + "," + j + ")= " + distance(clusters[i], clusters[j]));
      }
      avg_dists[i] /= (cluster_num - 1);
      ratios[i] = max_dists[i]/avg_dists[i]; // the smaller the ratio, the more self-
                                            // contained of the cluster
//      System.out.println("average dist= " + avg_dists[i] + ", max_dist = " +
//        max_dists[i] + ", ratio= " + ratios[i]);
    }

    int worst = biggest(ratios);
//    System.out.println("split on : " + worst);
    if (ratios[worst] > SPLIT_THRESHOLD) {
        for (int j=0; j<data_dim; j++) {
          clusters[cluster_num][j] = data[max_dist_vectors[worst]][j];
        }
        return cluster_num + 1;
    }
    return cluster_num;
  }

  /**
   * Find the one farest from the target
   * @param target the target vector
   * @param data the data vectors
   * @param length the length of the data.  This allows user to use parts of
   *               the array "data" as the comparison instead of to use them all
   * @return the index of the farest (0 based)
   */
  int farest(int[] target, int[][] data, int length) {
    double longest_dist = distance(data[0], target);
    int    longest_dist_index = 0;
    for (int i=1; i<data.length; i++) {
      double distance = distance(data[i], target);
      if (distance > longest_dist) {
        longest_dist = distance;
        longest_dist_index = i;
      }
    }
    return longest_dist_index;
  }

  /**
   * Find the one farest from the target
   * @param target the target vector
   * @param data the data vectors
   * @param length the length of the data.  This allows user to use parts of
   *               the array "data" as the comparison instead of to use them all
   * @return the index of the farest (0 based)
   */
  int farest(double[] target, int[][] data, int length) {
    double longest_dist = distance(target, data[0]);
    int    longest_dist_index = 0;
    for (int i=1; i<data.length; i++) {
      double distance = distance(target, data[i]);
      if (distance > longest_dist) {
        longest_dist = distance;
        longest_dist_index = i;
      }
    }
    return longest_dist_index;
  }

  /**
   * Find the one closest from the target
   * @param target the target vector
   * @param data the data vectors
   * @param length the length of the data.  This allows user to use parts of
   *               the array "data" as the comparison instead of to use them all
   * @return the index of the closest (0 based)
   */
  int closest(int[] target, int[][] data, int length) {
    double closest_dist = distance(data[0], target);
    int    closest_dist_index = 0;
    for (int i=1; i<data.length; i++) {
      double distance = distance(data[i], target);
      if (distance < closest_dist) {
        closest_dist = distance;
        closest_dist_index = i;
      }
    }
    return closest_dist_index;
  }

  /**
   * Assign each data to its closes cluster
   * @param clusters the cluster averages
   * @param cluster_num the cluster number
   * @param data the data vectors
   * @param labels to return the cluster index for each data
   * @param max_dists to return the max distance a cluster member to its average
   *                  Must be inited as new double[cluster_num] before calling
   * @param max_dist_vectors to return the index of the vector with max distance to its cluster
   *                            (one per cluster).  Must be inited as
   *                            "new int[cluster_num]" before entering the method
   */
  void assign2Cluster(double[][] clusters, int cluster_num, int[][] data,
                      int[] labels, double[] max_dists, int[] max_dist_vectors) {
    java.util.Arrays.fill(max_dists, 0.0);
    // for each data, find the closest cluster
    for (int i=0; i<data.length; i++) {
      // find the closest cluster
      double closest_dist = distance(clusters[0], data[i]);
      int    closest = 0;
      for (int j=1; j<cluster_num; j++) {
        double distance = distance(clusters[j], data[i]);
        if (distance < closest_dist) {
          closest_dist = distance;
          closest = j;
        }
      }

      labels[i] = closest;  // record the closest cluster index (0-based)
      // also record the maximum distance of every cluster from its member data to its average
      if (closest_dist > max_dists[closest]) {
        max_dists[closest] = closest_dist;
        max_dist_vectors[closest] = i;
      }
    }
  }

  /**
   * Calculate the average of each cluster
   * @param data the data
   * @param labels the data->cluster_index map
   * @param cluster_num the number of clusters
   * @param averages to return the averages.  Must be inited as
   *                 [cluster_num][vector_elements] before calling
   */
  void average(int[][] data, int[] labels, int cluster_num, double[][] averages) {
    // clear averages
    for (int i=0; i<averages.length; i++) java.util.Arrays.fill(averages[i], 0.0);
    int[] count = new int[cluster_num];

    // sum
    for (int i=0; i<data.length; i++) {
      int label = labels[i];  // belongs to which cluster
      count[label] ++;
      for (int j=0; j<data[i].length; j++) {
        averages[label][j] += data[i][j];
      }
    }

    // average
    for (int i = 0 ; i < cluster_num ; i++) {
      for (int j=0; j<averages[i].length; j++) {
        averages[i][j] /= count[i];
      }
    }
  }

  /**
   * Return the distance of two vectors
   * @param v1
   * @param v2
   * @return the distance
   */
  double distance(double[] v1, double[] v2) {
    double dist = 0;
    for (int i=0; i<v1.length; i++) {
      double d= v1[i] - v2[i];
      dist += d*d;
    }
    return Math.sqrt(dist);
  }

  /**
   * Return the distance of two vectors
   * @param v1
   * @param v2
   * @return the distance
   */
  double distance(double[] v1, int[] v2) {
    double dist = 0;
    for (int i=0; i<v1.length; i++) {
      double d= v1[i] - v2[i];
      dist += d*d;
    }
    return Math.sqrt(dist);
  }

  /**
   * Return the distance of two vectors
   * @param v1
   * @param v2
   * @return the distance
   */
  double distance(int[] v1, int[] v2) {
    double dist = 0;
    for (int i=0; i<v1.length; i++) {
      double d= v1[i] - v2[i];
      dist += d*d;
    }
    return Math.sqrt(dist);
  }

  /**
   * Return the index of the biggest value in the given vector
   * @param v the vector
   * @return the biggest value index
   */
  int biggest(double[] v) {
    int index = 0;
    double biggest = v[0];
    for (int i=1; i<v.length; i++) {
      if (v[i]>biggest) {
        biggest = v[i];
        index = i;
      }
    }
    return index;
  }

  private void printVector(String s, int[] v) {
    if (s!=null) System.out.print(s + ": ");
    for (int i=0; i<v.length; i++) {
      System.out.print(v[i]);
      System.out.print(" ");
    }
    System.out.println();
  }

  private void printVector(String s,double[] v) {
    if (s!=null) System.out.print(s + ": ");
    for (int i=0; i<v.length; i++) {
      System.out.print(v[i]);
      System.out.print(" ");
    }
    System.out.println();
  }
}