package yi.ai.cluster;

import java.util.*;
import yi.stat.hist.*;

public class OneDSplitCluster {

  public double SCORE_THRESHOLD = 0.3333;

  /**
   * 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, double size_threshold) {
    int[] labels = new int[data.length];
    int cluster_num = clustering(data, data_dim, labels, max_cluster_num, size_threshold);
    return new Clusters(cluster_num, data_dim, (double[][])null, 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 size_threshold) {
    if (labels == null) labels = new int[data.length];

    int[][] data_sheets = new int[data_dim][data.length];
    for (int i=0; i<data.length; i++) {
      for (int j=0; j<data_dim; j++) {
        data_sheets[j][i] = data[i][j];
      }
    }

    return clustering(data_sheets, data.length, data_sheets.length, labels, max_cluster_num, size_threshold);


// filter out small regions
//    ConnectComponent cc = new ConnectComponent();
//    int[] cc_label = cc.compactLabeling(labels, new Dimension(width, height), false);
//    for (int i=0; i<cc_label.length; i++) cc_label[i]++; // for background 0
//    Morph.filterSmallRegions(cc_label, cc.getMaxLabel() + 1, width * height / 100, 0);
//    yi.util.label.Label.sequential(cc_label, null, true);
//
//    int[] cc_label_img = yi.util.ImageUtil.makeNewImageFromLabel(cc_label);
//    OutputResult.outputGIFImage(img_name + "." + "filtered.final" + ".gif", cc_label_img, width, height);

  }

  private int out_counter = 0;

  /**
   * class SplitJob is to record the clusters to be considered to split.  The
   * first split job will be on cluster labeled "0".  If it is split to 2
   * clusters, "1" and "2", then itself (job on label "0") will be removed from
   * the job queue and job "1" and job "2" are added.  The scores of the best
   * possible splits on job "1" and job "2" are calculated and the better one
   * is choosed to split.  Say, job "2" is selected to split and it is split to
   * "3" and "4".  Now the job queue has "1", "3", "4".  Again, the best split
   * is choosed and the split will going on until the maximum cluster number is
   * reached or the score is too low
   */
  class SplitJob {
    /**
     * cluster label
     */
    int m_label;
    /**
     * whether the best score for this job is calculated
     */
    boolean m_scoreCalculated = false;
    double m_score;
    int m_splitSheet;
    int m_threshold;
    /**
     * The best thresholding on this job
     */
    OtsuThresholding m_bestThresholding = null;

    public SplitJob(int label) {
      m_label = label;
    }

    /**
     * Return the best score among those data sheets.  One data sheet is 1D
     * feature data for every data point.  If the feature data is n-long, then
     * there will be n data sheets.
     *
     * For example, the Laws texture energy measures for each pixel is 9D.  The
     * data sheets are 9 sheets.
     *
     * Each data sheet will be mapped to histogram first, a score is caculated
     * based on whether it is likely from a uniform model.  (higher score means
     * a more uniform like model).  The highest score is returned.  So the lower
     * the score, the better to split it
     *
     * @param dataSheets the data sheet
     * @return the highest score
     */
    double getScore(int[][] dataSheets, int[] labels, double size_threshold) {
      System.setProperty("label", String.valueOf(m_label));
      if (m_scoreCalculated) return m_score;
      completeSearch(dataSheets, labels, size_threshold);
      // calculat the scores for each data sheet
      for (int i=0; i<dataSheets.length; i++) {
        int[] sheet = dataSheets[i];
        int size_t = (int)Math.round(sheet.length * size_threshold);
        // construct the histogram
        int min = yi.stat.Util.minimum(sheet);
        int max = yi.stat.Util.maximum(sheet);
        SimpleHistogram hist = new SimpleHistogram(min, max);
        for (int j=0; j<sheet.length; j++) {
          if (labels[j] == m_label) hist.putToBin(sheet[j]);
        }
        OtsuThresholding otsu = new OtsuThresholding();
        otsu.thresholding(hist.getHistogram(), hist.getMinValue());

// Output demos
//        String id_str = String.valueOf(m_label) + '.' + i;
//        System.out.println(id_str);
//        System.out.println(otsu);
//        hist.output(id_str + ".hist");
//
//        int[] sheet_filtered = new int[sheet.length];
//        int minimum = yi.stat.Util.minimum(sheet);
//        for (int j=0; j<sheet.length; j++) {
//          if (labels[j] == m_label) sheet_filtered[j] = sheet[j];
//          else sheet_filtered[j] = minimum;
//        }
//        int[] graph = yi.stat.graph.Graph.grayGraph(sheet_filtered);
//        for (int j=0; j<sheet.length; j++) {
//          if (labels[j] != m_label) graph[j] = 0xffff7f7f;
//        }
//        int img_width = Integer.parseInt(System.getProperty("img_width"));
//        int img_height = Integer.parseInt(System.getProperty("img_height"));
//        yi.util.io.OutputResult.outputGIFImage(id_str + ".hist." + out_counter + ".gif", graph, img_width, img_height);
//
//        int[] demo_img = new int[img_width * img_height];
//        int threshold = otsu.getThreshold();
//        System.out.println("use threshold " + otsu.getThreshold());
//        for (int h=0; h<img_height; h++) {
//          for (int w=0; w<img_width; w++) {
//            int index = h * img_width + w;
//            if (labels[index] == m_label) {
//              demo_img[index] = (sheet[h * img_width + w] >= threshold) ? 0xffffffff: 0xff000000;
//            } else {
//              demo_img[index] = 0xff7f7f7f;
//            }
//          }
//        }
//        yi.util.io.OutputResult.outputGIFImage(id_str + ".pass." + out_counter + ".gif", demo_img, img_width, img_height);
//        out_counter ++;

        if (otsu.getNumber1() < size_threshold || otsu.getNumber2() < size_threshold) {
          continue;
        }
        double score = otsu.getScore();
        if (m_bestThresholding == null || score < m_score) {
          m_bestThresholding = otsu;
          m_score = score;
          m_splitSheet = i;
          m_threshold = otsu.getThreshold();
        }
      }
      m_scoreCalculated = true;
      return m_score;
    }

    /**
     * Calculate the score for every possible combination of feature data
     * @param dataSheets
     * @param labels
     * @param size_threshold
     * @return
     */
    void completeSearch(int[][] dataSheets, int[] labels, double size_threshold) {
      int[] subset = new int[labels.length];
      int feature_len = dataSheets.length;
      int count = 0;
      for (int i=0; i<labels.length; i++) {
        if (labels[i] == m_label) subset[i] = count++;
        else subset[i] = -1;
      }
      dataSheets = yi.util.data.Conversion.swapXandY(dataSheets, labels.length, dataSheets.length);
      int[][] useful_data_sheets = new int[count][];
      for (int i=0; i<labels.length; i++) {
        if (labels[i] == m_label) useful_data_sheets[subset[i]] = dataSheets[i];
      }

      double best_score = 1;
      int best_score_index = -1;

      for (int i=1; i<1<<feature_len; i++) {
        int[][] now_data_sheets = filterFeatureData(useful_data_sheets, i);
        DistanceCluster cluster = new DistanceCluster();
        Clusters clusters = cluster.clustering(now_data_sheets, now_data_sheets[0].length, 2);
        double score = clusters.getScore(now_data_sheets);
        if (score < best_score) {
          best_score = score;
          best_score_index = i;
        }
        String id_str = System.getProperty("pass") + '.' + System.getProperty("label")
                    + '.' + i;
        System.out.println(id_str + " : " + score);

//        int img_width = Integer.parseInt(System.getProperty("img_width"));
//        int img_height = Integer.parseInt(System.getProperty("img_height"));
//        int[] map = clusters.getClusterMap();
//
//        int[] demo_img = new int[img_width * img_height];
//        for (int h=0; h<img_height; h++) {
//          for (int w=0; w<img_width; w++) {
//            int k = h * img_width + w;
//            if (subset[k] == -1) {
//              demo_img[k] = 0;
//            } else {
//              demo_img[k] = map[k] + 1;
//            }
//          }
//        }
//        demo_img = yi.util.ImageUtil.makeNewImageFromLabel(demo_img);
//        yi.util.io.OutputResult.outputGIFImage(id_str + ".pass." + ".gif", demo_img, img_width, img_height);
      }
      System.out.println("best score is: " + best_score + " on " + best_score_index);
    }
  }

  int[][] filterFeatureData(int[][] data, int bitFilter) {
    int f_copy = bitFilter;
    int numOfOne = 0;
    while (f_copy>0) {
      numOfOne += f_copy & 1;
      f_copy >>= 1;
    }
    int[][] new_data = new int[data.length][numOfOne];
    numOfOne = 0;
    for (int b=0; b<data[0].length; b++) {
      int isOne = bitFilter >> b & 1;
      numOfOne += isOne;
      if (isOne == 1) {
        for (int j=0; j<data.length; j++) {
          new_data[j][numOfOne-1] = data[j][b];
        }
      }
    }
    return new_data;
  }

  SplitJob findFirstRankJob(HashSet jobs, int[][] dataSheets, int[] labels, double size_threshold) {
    System.setProperty("pass", String.valueOf(jobs.size()));
    SplitJob best = null;
    double best_score = 1; // 1 is the worst case since the score is normalized (0 is the best)
    Iterator i = jobs.iterator();
    while (i.hasNext()) {
      SplitJob job = (SplitJob)i.next();
      double score = job.getScore(dataSheets, labels, size_threshold);
      if (best == null && score < best_score) {
        best = job;
        best_score = score;
      }
    }
    return best;
  }

  void split(SplitJob job, int[][] data_sheets, int[] label, int next_label) {
    OtsuThresholding thresholding = job.m_bestThresholding;
    int threshold = job.m_threshold;
    int[] data_sheet = data_sheets[job.m_splitSheet];
    int current_label = job.m_label;
    for (int i=0; i<label.length; i++) {
      if (label[i] == current_label) {
        if (data_sheet[i] >= threshold) label[i] = next_label;
      }
    }
  }

  /**
   * clustering a region of the image.  It goes though each measure, calculate
   * the score (normalized sum of variance) for splitting the histogram on it.
   * Pick up one with the smallest, split it, and then call recursively
   * @param gray the image
   * @param width image width
   * @param height image height
   * @param labels the region labels for each pixel (pixel->region_label mapping)
   * @param the_label the label of region to be clustered
   * @param rst the Laws texture energy measures
   * @return the labels after clustering
   */
  int clustering(int[][] dataSheets, int data_num, int sheet_num,
                   int[] labels, int max_cluster_num, double size_threshold) {
    // init the job queue
    HashSet job_queue = new HashSet(max_cluster_num);
    // add the first job
    Arrays.fill(labels, 0);
    job_queue.add(new SplitJob(0));

    while (!job_queue.isEmpty() && job_queue.size() < max_cluster_num) {
      SplitJob job = findFirstRankJob(job_queue, dataSheets, labels, size_threshold);
      if (job.m_score > SCORE_THRESHOLD) break;
      int next_label = job_queue.size();
      job_queue.remove(job);
      split(job, dataSheets, labels, next_label);
      System.out.println("The best score is = " + job.m_score);
//      int[] label_img = yi.util.ImageUtil.makeNewImageFromLabel_back(labels);
//      int img_width = Integer.parseInt(System.getProperty("img_width"));
//      int img_height = Integer.parseInt(System.getProperty("img_height"));
//      yi.util.io.OutputResult.outputGIFImage("step" + job_queue.size() + ".gif", label_img, img_width, img_height);
      job_queue.add(new SplitJob(job.m_label));
      job_queue.add(new SplitJob(next_label));

    }
    return job_queue.size();

  }

  /**
   * Test the algorithm
   */
  public static class Test {
    public static void main(String[] args) {
      int[][] data = {
        {1, 2},
        {2, 1},
        {2, 2},
        {2, 3},
        {3, 2},
        {4, 5},
        {5, 4},
        {5, 5},
        {5, 6},
        {6, 5},
//        {2, 5}
      };
//      int[][] data = {
//        {0, 3, 2},
//        {2, 4, 3},
//        {3, 3, 5},
//        {4, 4, 5},
//        {5, 3, 5},
//        {6, 7, 8},
//        {7, 7, 8},
//        {8, 7, 8},
//        {9, 7, 5}
//      };
      OneDSplitCluster clustering = new OneDSplitCluster();
      Clusters clusters = clustering.clustering(data, 2, 3, 0.01);
      int[] labels = clusters.getClusterMap();
      yi.util.io.OutputResult.print(System.out, labels);
    }
  }



}