package yi.ai.cluster;

import java.util.*;

/**
 * Class KMCluster implements K-means cluster algorithm
 * <P>
 * There are several different init method could be use:
 * random, linear, cube, statistical, possbility, predefined
 * (possibility is not finished yet)
 * </P>
 * <P>
 * [REQUIRES]<BR/>
 *   values of data are integer [0, 255]
 * </P>
 * <P>
 * [EXAMPLE]<BR/>
 *   KMCluster c  = new KMCluster(k, KMCluster.RANDOM, data);<BR/>
 *   Clusters clusters = c.clustering();<BR/>
 * </P>
 *
 * <P>
 * [EXAMPLE] (Expired on Aug 23, 2002<BR/>
 *   KMCluster c  = new KMCluster(k, KMCluster.RANDOM, data);<BR/>
 *   int[] labels = c.clustering();<BR/>
 *   int[][] means  = c.getMeans();<BR/>
 *   int num_clusters = c.clusterNum();<BR/>
 * </P>
 * <P>
 * [REFERENCE]<BR/>
 *   A. R. Weeks, Color segmentation in the HSI color space using the K-means
 *   algorithm
 * </P>
 * @deprecated replaced by yi.stat.kmeans.KMeans
 */
public class KMCluster implements java.io.Serializable
{
    //possible method to generate the initial means
    public final static int RANDOM=0;
    public final static int LINEAR=1;
    public final static int CUBE=2;
    public final static int STAT=3;
    public final static int POSS=4;
    public final static int DEFAULT=5;
    public final static int PREDEFINED=6;

    int BINNUM=16;              // when do the possibility based initialization,
                                // need to quantilize on every dimension
    int USEBINRATIO=8;          // when a bin is considered as useful, the pixel
                                // number in that bin must more than a certain
                                // times of the average (used in possibilty init)

    protected int initMethod = RANDOM;    // initial method for the means
    protected int K = 16;                 // as in K means
    protected int m_clusterNumber = K;    // resultant cluster number.  May be smaller than
                                // K after removing the empty clusters
    protected int[][] init_means = null;  // initial means
    transient protected int[][] data = null;        // data to clusterize
    protected int info_len;               // the vector length of every data
    protected int[] label = null;         // cluster result for every data
    protected int[][] means = null;       // resultant cluster meas
    /**
     * The maximum value on each dimension of the data vector.  It is useful,
     * say, when generating the random init means.
     */
    int[] m_maximums = null;

    protected KMCluster() {

    }

    /**
     * constuct k means clustering algorithm with specified K and init type
     * @param k k as in k means
     * @param init_type the init method used to init k means
     * @param data data to cluster
     * @param maximums the maximum value on each dimension of the data vector.
     *                 If it is null, then 255 is set for each dimension
     */
    public KMCluster(int k, int init_type, int[][] data, int[] maximums) {
        K = k;
        initMethod=init_type;
        this.data = data;
        info_len = data[0].length;
        m_maximums = maximums;
        init_means = getInitMeans(initMethod, K, info_len, data, maximums);
    }

    /**
     * Construct k means using predefined means
     * @param init_means predefined means
     * @param data data to be classified
     */
    public KMCluster(int[][] init_means, int[][] data) {
        K = init_means.length;
        initMethod = PREDEFINED;
        this.data = data;
        info_len = data[0].length;
        this.init_means = init_means;
    }

    /**
     * Init a KMCluster instance using POSS (possibility) as the initialization
     * method.
     * @param data data vector to be clustered
     * @param bin_num bin number for each dimension
     * @param use_bin_ratio the threshold to decide whether a bin is qualified
     *                      as a inited mean
     */
    public KMCluster(int[][] data, int bin_num, int use_bin_ratio) {
        initMethod = POSS;
        this.data = data;
        info_len = data[0].length;
        BINNUM = bin_num;
        USEBINRATIO = use_bin_ratio;
        init_means =  getInitMeans(initMethod, K, info_len, data, null);
    }

    /**
     * Return k-means clustering result.  Every data is given a label
     * @return the data->cluster index map
     */
    public int[] getLabels() {
        return this.label;
    }

    /**
     * Return the resultant k means
     * @return the means for each cluster
     */
    public int[][] getMeans() {
        return this.means;
    }

    /**
     * Return the resultant cluster number
     * @return the resultant cluster number
     */
    public int clusterNum() {
      return m_clusterNumber;
    }

//    /**
//     * Aug 23th, 2002
//     * This interface is no longer supported and it is replace by
//     *
//     *
//     * Clustering with an option to compact the result.  The init means can be
//     * useless (no data belongs to it anymore).  Passing in compact = true will
//     * eliminate those empty clusters and relabel each data
//     * @param no_empty whether to eliminate empty clusters
//     * @return the data -> cluster index map
//     */
//    public int[] clustering(boolean no_empty) {
//        means = (int[][])init_means.clone();
//        return clustering(data, means, no_empty);
//    }

    /*
     * Clustering with an option to compact the result.  The init means can be
     * useless (no data belongs to it anymore).  Passing in compact = true will
     * eliminate those empty clusters and relabel each data
     * @param no_empty whether to eliminate empty clusters
     * @return the data -> cluster index map
     */
    public Clusters clustering(boolean no_empty) {
        means = (int[][])init_means.clone();
        clustering(data, means, 0, no_empty);
        return new Clusters(m_clusterNumber, info_len, means, data.length, label);
    }

    /**
     * Clustering with an option to compact the result (eliminate empty
     * clusters) and another option to stop the iterations earlier (by giving
     * a max step threshold)
     * @param max_step if this number > 0, then the iteration steps will not
     *                 be greater than it.
     * @param no_empty set it to true, if want to remove the empty clusters
     * @return
     */
    public Clusters clustering(int max_step, boolean no_empty) {
        means = (int[][])init_means.clone();
        clustering(data, means, max_step, no_empty);
        return new Clusters(m_clusterNumber, info_len, means, data.length, label);
    }

//    /**
//     * Aug 23th, 2002
//     * This interface is no longer supported and it is replace by
//     *
//     *
//     * Clustering.  The resultant means will be examined to elminate empty
//     * clusters.  This interface is kept for backward compatible.
//     * @return the data -> cluster index map
//     * @see public int[] clustering(boolean no_empty)
//     */
//    public int[] clustering() {
//        return clustering(true);
//    }

    /**
     * Clustering.  The resultant means will be examined to elminate empty
     * clusters.  This interface is kept for backward compatible.
     * @return the data -> cluster index map
     * @see public int[] clustering(boolean no_empty)
     */
    public Clusters clustering() {
        return clustering(true);
    }

    /**
     * Method clusteringWithPick is for random init means.  Run clustering
     * multiple times and pick the one with highest score.
     * @param times how many times to run.  Should no less than 1
     * @param no_empty only keep the no empty clusters
     * @return the resultant clusters
     */
    public Clusters clusteringWithPick(int times, boolean no_empty) {
      // only useful when using random initialized means
      if (initMethod != RANDOM) {
        System.err.println("clusteringWithPick is only useful when using random initialized means: "
          + "change running times to 1 now");
        times = 1;
      }

      // first run
      clustering(no_empty);
      long score = clusteringScore();
//      System.out.println("score = " + score);

      // run several times and pick up the one with the minmum score (best one)
      for (int i=2; i<=times; i++) {
        KMCluster cluster = new KMCluster(K, RANDOM, data, m_maximums);
        cluster.clustering(no_empty);
        long current_score = cluster.clusteringScore();
        if (current_score < score) { // copy the current (better) one
          score = current_score;
          init_means = cluster.means;
          label = cluster.label;
          m_clusterNumber = cluster.m_clusterNumber;
          means = cluster.means;
        }
//        System.out.println("current_score = " + current_score + " score = " + score);
      }
      return new Clusters(m_clusterNumber, info_len, means, data.length, label);
    }

    /**
     * Give the clustering score.  The lower the number, the better the result.
     * The score is the summary of the distance of each data vector to its cluster
     * mean.
     * @return the clustering score
     */
    public long clusteringScore() {
      long sum = 0;
      for (int i=0; i<data.length; i++) {
        sum += distance(data[i], means[label[i]], info_len);
      }
      return sum;
    }

    /**
     * K-means clustering.
     * <P>
     * requires: <BR/>
     *   values of info are [0,255] <BR/>
     *   k means have been initialized <BR/>
     * </P>
     * <P>
     * modifies: <BR/>
     *   this.label <BR/>
     *   this.means <BR/>
     * </P>
     * <P>
     * effects: <BR/>
     *   return a label array with the values indicate which mean the pixel
     *   is belong to. <BR/>
     *   if return type is mean-color, then rgb color will be returned in
     *   4-bytes format <BR/>
     * </P>
     * @param info the data vectors to be classified
     * @param means the means of the clusters (inited before calling, changed
     *              in the clustering process.
     * @param max_step if this number is greater than 0, then the k-means will
     *                 not carry on after "max_step" steps.
     * @param no_empty eliminate those means corresponding to the empty clusters
     * @return the data -> cluster index map
     */
    int[] clustering(int[][] info, int[][] means, int max_step, boolean no_empty)
    {
        int k= means.length;        //number of cluster
        int size=info.length;       //size of image
        int info_len= info[0].length;   //number of elements of the information vector (hsi, =3)

        label= new int[info.length];      //store the result of labeling
        int i,j,m,n,temp;
        int ic=1;
        boolean changed=true;

        //used when re-calculate the means before the iteration step
        long[][] sum= new long[k][info_len];
        int[] num= new int[k];

        int steps = 0;
        while (changed && (max_step <= 0 || steps < max_step)) {
            steps ++;
            System.out.println("step #" + steps);

            //find the minimum distance for each vector
            for (i=0;i<size;i++) {
                int min_dist = distance(info[i], means[0], info_len);
                int min_dist_index = 0; //remember the index of the mean with the minimum distance
                for (m=1; m<k; m++) {
                    int d = distance(info[i], means[m], info_len);
                    if (min_dist > d) {
                      min_dist = d;
                      min_dist_index = m;
                    }
                }
                // assign the data to the closest cluster
                label[i]= min_dist_index;
            }
            //recalculate the means
            for (m=0;m<k;m++) java.util.Arrays.fill(sum[m], 0);
            java.util.Arrays.fill(num, 0);
            for (i=0;i<size;i++) {
              temp=label[i];
              for (n=0;n<info_len;n++) sum[temp][n]+=info[i][n];
              num[temp]++;
            }

            changed=false;
            for (m=0;m<k;m++) {
                for (n=0;n<info_len;n++) {
                    if (num[m]==0) continue;
                    int new_mean = (int)Math.round((double)sum[m][n]/num[m]);
                    if (means[m][n]==new_mean) continue;
                    changed=true;
                    means[m][n] = new_mean;
                }
            }
        }

        // eliminate empty cluster
//        System.out.println("cluster_number before eliminate empty cluster = " + m_clusterNumber);
        if (no_empty) m_clusterNumber = eliminateEmptyCluster(label, means);
//        System.out.println("cluster_number after = " + m_clusterNumber);
        return label;
    }

    /**
     * This method is used after clustering to remove empty clusters
     * @param label the data->cluster map before removing empty clusters.  It
     *              may be changed after the invokation.
     * @param means the means. It may be changed after the invokation.
     * @return the new mean number after removing the empty clusters.
     */
    protected int eliminateEmptyCluster(int[] label, int[][] means) {
      boolean[] empty = new boolean[means.length];
      java.util.Arrays.fill(empty, true);

      // find out which clusters are empty
      for (int i=0; i<label.length; i++) {
        empty[label[i]] = false;
      }

      // set up the old-label -> new-label map
      int[] map = new int[means.length];
      int count = 0;
      for (int i=0; i<empty.length; i++) {
        if (!empty[i]) {
          map[i] = count ++;
        }
      }

//      System.out.println("no empty cluster #= "+ count);

      // relabel the result
      for (int i=0; i<label.length; i++) label[i] = map[label[i]];

      // compact means
      count = 0;
      for (int i=0; i<means.length; i++) {
        if (!empty[i]) {
          means[count] = means[i];
          count++;
        }
      }
      return count;
    }

    /**
     * Calculate the distance between two vectors
     * @param v1 vector 1
     * @param v2 vector 2
     * @param info_len the dimension of the vectors
     * @return the distance
     */
    int distance (int[] v1, int[] v2, int info_len) {
      int dist = 0;
      for (int n = 0 ; n < info_len ; n++) {
        int d = v1[n] - v2[n];
        dist += d * d;
      }
      return dist;
    }

    /**
     * Set means initialized
     * @param initmethod init method, one of RANDOM, LINEAR, CUBE, STAT, POSS
     *                   and PREDEFINED.
     * @param k the number of means
     * @param info_len dimension of data vectors
     * @param info data vectors
     * @param maximums the maximum value on each dimension of the data vector.
     *                 If it is null, then 255 is set for each dimension
     * @return the inited means
     */
    int[][] getInitMeans(int initmethod, int k, int info_len, int[][] info, int[] maximums)
    {
        int[][] means = null;
        switch (initmethod) {
            case RANDOM: means= random(k,info_len, maximums);break;
            case LINEAR: means= linear(k,info_len);break;
            case CUBE: means= cube(k,info_len);break;
            case STAT: means= statistical(info,k,info_len);break;
            case POSS: means= possibility(info,info_len,BINNUM, USEBINRATIO);break;
            case PREDEFINED: means= init_means;break;
            default:
                System.err.println("mean init method not supported");
                System.exit(1);
        }
        return means;
    }

    /**
     * Randomly init the K means
     * @param k number of means
     * @param info_len data dimension
     * @param maximums the maximum value on each dimension of the data vector.
     *                 If it is null, then 255 is set for each dimension
     * @return inited means
     */
    int[][] random(int k,int info_len, int[] maximums)
    {
      int[][] means= new int[k][info_len];

      Random r= new Random();
      for (int i=0;i<k;i++) {
          for (int j=0;j<info_len;j++) {
            if (maximums != null) means[i][j] = r.nextInt(maximums[j] + 1);
            else means[i][j]= r.nextInt(256);
//            System.out.print(means[i][j]);
//            System.out.print(" ");
          }
//          System.out.println();
      }
      return means;
    }

    /**
     * Init the k means linear-ly
     * <P>
     * if k = 1, return (0, 0, ...)
     * </P>
     * <P>
     * [PREREQUIREMENT] <BR/>
     *   k > 1 <BR/>
     * </P>
     * <P>
     * [EXAMPLE] <BR/>
     * k=4; info vector length =5; <BR/>
     * the k-means are: <BR/>
     *   (  0,   0,   0,   0,   0) <BR/>
     *   (1/3, 1/3, 1/3, 1/3, 1/3) <BR/>
     *   (2/3, 2/3, 2/3, 2/3, 2/3) <BR/>
     *   (  1,   1,   1,   1,   1) <BR/>
     * </P>
     * @param k number of means
     * @param info_len data dimension
     * @return inited means
     */
    int[][] linear(int k,int info_len)
    {
      int[][] means= new int[k][info_len];
      int i,j;

      for (i=0;i<k;i++)
        for (j=0;j<info_len;j++) {
          if (k<2) means[i][j]=0;
          else
            means[i][j]= 255/(k-1)*i;
        }
      return means;
    }

    /**
     * Init the k means cube-ly
     * <P>
     * [PREREQUIREMENT] <BR/>
     *   k = 8 (k will be set to 8 anyway) <BR/>
     *   info_len = 3 (because it is "cube") <BR/>
     * </P>
     * <P>
     * [OUTPUT] <BR/>
     *   (0,0,0), (0,0,255), ..., (255,255,255) <BR/>
     * </P>
     * @param k number of means
     * @param info_len data dimension
     * @return inited means
     */
    int[][] cube(int k,int info_len)
    {
      int[][] means= new int[k][info_len];
      int i,j,m;

      if (k<8) k=8;

      for (i=0;i<2;i++)
        for (j=0;j<2;j++)
          for (m=0;m<2;m++) {
            means[(i*4+j*2+m)][0]= (255*i);
            means[(i*4+j*2+m)][1]= (255*j);
            means[(i*4+j*2+m)][2]= (255*m);
          }
      if (k>8)
        means[8][0]=means[8][1]=means[8][2]=127;
      return means;
    }

    /**
     * Init the k means statistically
     * <P>
     * [EXAMPLE] <BR/>
     *   mean = 100, standard deriation = 80, k = 5 <BR/>
     *   k means are: 20, 60, 100, 140, 180 <BR/>
     * </P>
     * @param info the data vectors
     * @param k number of means
     * @param info_len data dimension
     * @return inited means
     */
    int[][] statistical(int[][] info, int k,int info_len)
    {
        int[][] means= new int[k][info_len];

        int length=info.length;
        int i,j,temp;
        long[] sum= new long[info_len],sd= new long[info_len];
        int[] mean= new int[info_len];

        // init sum and standard-deriation array
        for (i=0;i<info_len;i++) {sum[i]=0;sd[i]=0;}
        // calculate sum
        for (i=0;i<length;i++)
                for (j=0;j<info_len;j++)
                        sum[j]+=info[i][j];
        // calculate mean
        for (i=0;i<info_len;i++) mean[i]=(int)(sum[i]/length);
        // calculate standard-deriation
        for (i=0;i<length;i++)
                for (j=0;j<info_len;j++) {
                        temp= info[i][j]-mean[j];
                        sd[j]+=temp*temp;
                }
        for (i=0;i<info_len;i++) sd[i]=(long)(Math.sqrt(sd[i]/(length-1)));

        for (i=0;i<k;i++) {
            for (j=0;j<info_len;j++) {
                if (k<2) means[i*info_len][j]=mean[j];
                else {
                    means[i][j]=(int)((mean[j]-sd[j]+(sd[j]*2)/(k-1)*i));
                }
            }
        }
        return means;
    }

    /**
     * This function initialize the means according the possibility.
     * Quantilize the space first, calculate the number of elements fell into
     * every bin.  Then consider those bins which have pixels more than a
     * certain threshold
     * [PREREQUEST]
     *   the values of info fall into the range of [0, 255]
     *   the 1st dimension of info is the number of info case
     *   the 2nd dimension of info is the elements index in a info vector
     * [EXAMPLE]
     *   A RGB color space can be divided into 8*8*8 bins.  The pixels will
     *   contribute to the corresponding bins.  If a bin has more than the
     *   threshold of pixels, its corresponding color will be one of the k means
     * @param info data vectors
     * @param vector_len number of dimension of the measure space.
     *     e.g. 3 for HCI space
     * @param bin_num number of bin along 1-dimension of the measure space
     * @param use_bin_ratio to decide the threshold. the candidate bin must
     *     have pixels more than certain time of the average
     * @return the inited means
     */
    int[][] possibility(int[][] info, int vector_len, int bin_num, int use_bin_ratio)
    {
      int bin_total_num= 1;
      for (int i=0;i<vector_len;i++) bin_total_num*=bin_num;
      int[] bin_stat= new int[bin_total_num];

      int quan=256/bin_num;       // will have problems when the max value
                                  // is larger than 255;
      for (int i=0;i<info.length;i++) {
          int bin_index=0;
          for (int j=0;j<vector_len;j++) {
              bin_index*=bin_num;
              bin_index+=info[i][j]/quan;
          }
          if (bin_index>=bin_total_num) {
              System.err.println("bin index overflow, check the max possible value of the info");
              bin_index=bin_total_num-1;
          }
          bin_stat[bin_index]++;
      }

      int candidate_num=0;
      int candidate_thrsh=info.length*use_bin_ratio/bin_total_num;
      System.out.println("init means' threshold = " + candidate_thrsh);
      for (int i=0;i<bin_total_num;i++) {
          if (bin_stat[i]>candidate_thrsh) {
            candidate_num++;
            System.out.println(String.valueOf(i) + "->" + bin_stat[i]);
          }
      }
      System.out.println("candidate num = " + candidate_num);

      int[][] means= new int[candidate_num][vector_len];
      candidate_num=0;
      for (int i=0;i<bin_total_num;i++) {
          if (bin_stat[i] > candidate_thrsh) {
            int[] mean_of_bin = getMeansOfBin(i, vector_len, bin_num, 256);
            System.arraycopy(mean_of_bin, 0, means[candidate_num], 0, vector_len);

            System.out.println("index = " + i + ", data in bin = " + bin_stat[i]);
            for (int j=0; j<vector_len; j++) {
              System.out.print(" " + means[candidate_num][j]);
            }
            System.out.println();
            candidate_num++;
          }
      }

      K = m_clusterNumber = candidate_num;
      return means;
    }

    int[] getMeansOfBin(int bin_index, int data_dim, int bin_num, int unit) {
      int[] means = new int[data_dim];
      for (int i=0; i<data_dim; i++) {
        int j = bin_index % bin_num;  // the bin index for the last dimension
        bin_index /= bin_num;
        means[data_dim - 1 - i] = j * unit / bin_num + unit / bin_num / 2;
      }
      return means;
    }

    public int getClusterNum() {
      return m_clusterNumber;
    }
}