package yi.iu.processor.cluster;

import yi.iu.processor.*;
import yi.iu.processor.channel.CYMaker;
import yi.util.io.OutputResult;
import yi.iu.ui.DisplayFrame;

import java.awt.*;
import java.util.Random;

/**
 * This class is moved to yi.ai.cluster.KMCluster.  Use that class instead
 * because this one will not be maintained any more.
 * <P>
 * Class KMCluster implements K-means cluster algorithm
 * </P>
 * <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/>
 *   int[] labels = c.getLabels();<BR/>
 *   int[] means  = c.getMeans();<BR/>
 * </P>
 * <P>
 * [REFERENCE]<BR/>
 *   A. R. Weeks, Color segmentation in the HSI color space using the K-means
 *   algorithm
 * </P>
 */
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)

    int initMethod = RANDOM;    // initial method for the means
    int K = 16;                 // as in K means
    int[][] init_means = null;  // initial means
    transient int[][] data = null;        // data to clusterize
    int info_len;               // the vector length of every data
    int[] label = null;         // cluster result for every data
    int[][] means = null;       // resultant cluster meas

    /**
     * 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
     */
    public KMCluster(int k, int init_type, int[][] data) {
        this.K = k;
        initMethod=init_type;
        this.data = data;
        info_len = data[0].length;
        init_means =  getInitMeans(initMethod, K, info_len, data);
        means = new int[K][info_len];
        for (int i=0; i<K; i++) {
            for (int j=0; j<info_len; j++) {
                means[i][j] = init_means[i][j];
            }
        }
        clustering(this.data, this.means);
    }

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

    /**
     * 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;
    }

    /**
     * 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.
     * @return the data -> cluster index map
     */
    int[] clustering(int[][] info, int[][] means)
    {
        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][3];
        int[] num= new int[k];

        while (changed) {
            //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;
                }
            }
        }

        return label;
    }

    /**
     * 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
     * @return the inited means
     */
    int[][] getInitMeans(int initmethod, int k, int info_len, int[][] info)
    {
        int[][] means = null;
        switch (initmethod) {
            case RANDOM: means= random(k,info_len);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
     * @return inited means
     */
    int[][] random(int k,int info_len)
    {
      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++)
              means[i][j]= r.nextInt()%256;
      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;
        for (int i=0;i<bin_total_num;i++)
            if (bin_stat[i]>candidate_thrsh) candidate_num++;

        int[][] means= new int[candidate_num][vector_len];
      return means;
    }

}