//Source file: D:\\Projects\\src\\yi\\iu\\imgdb\\learn\\kmeans\\KMeansLikeAdapter.java

package yi.iu.imgdb.learn.kmeans;

import java.util.*;
import yi.ds.*;
import yi.util.data.*;
import yi.math.*;
import yi.util.config.*;
import yi.util.io.*;
import yi.iu.imgdb.learn.*;
import yi.ds.hash.*;

/**
 * KMeansLearner implements the object feature learning idea suggested by Jeff
 * Bilms.  The detailed idea is documented in
 * Projects\learning2\doc\learning.doc
 *
 * The algorithm contains two steps: boot step and iteration step.
 *
 * This code is a modified version of KMeansModel
 */
public class KMeansLikeAdapter extends StatModelAdapter
{

  /**
   * This adapter only learns on one feature
   */
  String m_feature = null;

  /**
   * Store the init accumulators for the objects.  The key is the name of the
   * object and the value is the corresponding accumulator (DoubleArrayCumulator)
   */
  AccumulatorHashMap m_initAccumulators = new AccumulatorHashMap();

  /**
   * Store the final accumulators for the objects after iteration step.  The key
   * is the name of the object and the value is the corresponding accumulator
   * (DoubleArrayCumulator)
   */
  AccumulatorHashMap m_rstAccumulators = new AccumulatorHashMap();

  /**
   * Store the mapping from image to its object list.  The key is the name of
   * the image and the value is a String collection
   */
  HashMap m_imgObjList = new HashMap();

  /**
   * Store the mapping from image to its feature vector list.  The key is the
   * name of the image and the value is a double[] collection
   */
  HashMap m_imgFvList = new HashMap();

  public double BREAK_THRESHOLD = 1e-4;

  public final static int BREAK_ON_MEAN_DIFF = 0;
  public final static int BREAK_ON_STEP_COUNT = 1;
  public int BREAK_COND = BREAK_ON_MEAN_DIFF;
  /**
   * If break condition (BREAK_COND) is set to BREAK_ON_STEP_COUNT, this number
   * decides it breaks after how many steps.  See iterationSteps() for more
   * information
   */
  public int break_on_step_count = 5;

  public boolean SHOW_PROGRESS = true;


  public KMeansLikeAdapter(ImgDataCenter data_center, LinkedList img_list, LinkedList ft_list, LinkedList obj_list)
  {
    super(data_center, img_list, ft_list, obj_list);

    // this method only learns on one feature
    m_feature = (String)m_featureList.getFirst();

    int feature_len = data_center.getFeatureLength(m_feature);

    // init the k clusters
    // for each image
    if (img_list == null) img_list = data_center.getImageList();
    if (obj_list == null) obj_list = data_center.getObjectList();
    HashSet obj_set = new HashSet(obj_list);
    for (Iterator i= img_list.iterator(); i.hasNext(); ) {
      String img_name = (String)i.next();
      // get the image feature vectors
      double[][] feature_vects = data_center.getImgFeatureList(img_name, m_feature).as2DDoubleArray();
      LinkedList ft_vt_list = Conversion.toLinedList(feature_vects);
      m_imgFvList.put(img_name, ft_vt_list);

      // get the image description keywords
      LinkedList desc_list = (LinkedList)data_center.getImgDescriptions(img_name).clone();
      for (Iterator j= desc_list.iterator(); j.hasNext(); ) {
        String desc = (String)j.next();
        // check whether the description is in the object list to learn
        // if not, just remove it
        if (!obj_set.contains(desc)) j.remove();
      }
      m_imgObjList.put(img_name, desc_list);

      // for each feature vector
      for (int f=0; f<feature_vects.length; f++) {
        double[] ft = feature_vects[f];
        for (Iterator o= desc_list.iterator(); o.hasNext(); ) {
          m_initAccumulators.accumulate((String)o.next(), ft);
        }
      }

    }
    learnTheModel();
  }

  public HashMap getMeans() {
    if (m_rstAccumulators == null) {
      learnTheModel();
    }
    return m_rstAccumulators.getMeans();
  }

  /**
   * This method triggers the iteration steps.  It returns the resultant model
   * for each object calculated in the iteration step.
   * @return The key is the name of the object and the value is the
   * corresponding model
   */
  public void learnTheModel() {
    // go iteration steps
    iterationSteps();

  }

  /**
   * The iteration steps described in Projects\learning2\doc\learning.doc
   */
  void iterationSteps() {

    HashMap last_means = m_initAccumulators.getMeans();

    // init a empty accumulator set
    AccumulatorHashMap new_accumulators = new AccumulatorHashMap();
    int iteration_step = 0;
    do {
      // assign each feature vector to its cloest mean
      Iterator i_iter = m_imgFvList.keySet().iterator();
      while (i_iter.hasNext()) {
        String img_name = (String)i_iter.next();
        Collection ft_vects = (Collection)m_imgFvList.get(img_name);
        Iterator ft_iter = ft_vects.iterator();
        while (ft_iter.hasNext()) {
          double[] fv = (double[]) ft_iter.next();
          // find the cloest one
          String obj = getClosest(last_means, fv);
          new_accumulators.accumulate(obj, fv);
        }
      }

      // test the break condition
      if (BREAK_COND == BREAK_ON_MEAN_DIFF) {
        // if the means didn't change, then exit the iterations
        HashMap new_means = new_accumulators.getMeans();
        double change_sum = getSumOfDistance(last_means, new_means); // the sum of differences between last_means and new_means
        last_means = new_means;
//        System.out.println("step: " + iteration_step + ", changes = " +
//                           change_sum);
        if (change_sum <= BREAK_THRESHOLD * last_means.size())
          break;
      } else if (BREAK_COND == BREAK_ON_STEP_COUNT) {
//        System.out.println("step: " + iteration_step);
        if (iteration_step >= break_on_step_count) {
          break;
        }
      }
      if (SHOW_PROGRESS && (iteration_step%10 == 0)) System.out.print(".");
      iteration_step++;
    } while (true);

    if (SHOW_PROGRESS) System.out.println();

    // keep the stable means
    m_rstAccumulators = new_accumulators;
  }

  /**
   * Return the summary of the distance between the corresponding vectors in the
   * two HashMap.  If there is no corresponding vector for a key, then vector 0
   * is assumed.
   * @param vectors1
   * @param vectors2
   * @return
   */
  private double getSumOfDistance(HashMap vectors1, HashMap vectors2) {
    double diff_sum = 0; // the sum of differences between last_means and new_means

    // loop through the keys in vectors 1
    Iterator iter = vectors1.keySet().iterator();
    while (iter.hasNext()) {
      Object key = iter.next();
      double[] v1 = (double[])vectors1.get(key);
      if (!vectors2.containsKey(key)) {
        diff_sum += VectorUtil.lenth(v1);
      } else {
        double[] v2 = (double[]) vectors2.get(key);
        diff_sum += VectorUtil.EuclideanDistance(v1, v2);
      }
    }

    // loop through the keys in vectors 2
    iter = vectors2.keySet().iterator();
    while (iter.hasNext()) {
      Object key = iter.next();
      if (!vectors1.containsKey(key)) {
        double[] v2 = (double[])vectors2.get(key);
        diff_sum += VectorUtil.lenth(v2);
      }
    }
    return diff_sum;
  }

  /**
   * Return the name of closest mean.  Users is responsible for making sure that
   * the means is not empty
   * @param means
   * @param value
   * @return
   */
  private String getClosest(HashMap means, double[] value) {
    double closest_d = -1;
    String closest_obj = null;

    Iterator iter = means.keySet().iterator();
    while (iter.hasNext()) {
      String key = (String)iter.next();
      double[] mean = (double[])means.get(key);
      double dist = yi.math.VectorUtil.EuclideanDistance(mean, value);
      if (closest_obj == null || dist < closest_d) {
        closest_d = dist;
        closest_obj = key;
      }
    }
    return closest_obj;
  }

  public String toString() {
    StringBuffer str = new StringBuffer();
    if (m_rstAccumulators != null) {
      HashMap means = m_rstAccumulators.getMeans();
      Iterator iter = means.keySet().iterator();
      while (iter.hasNext()) {
        String key = (String) iter.next();
        double[] mean = (double[]) means.get(key);
        str.append("<<" + key + ">>\nmean: ");
        for (int j = 0; j < mean.length; j++) {
          str.append(mean[j]);
          str.append(" ");
        }
        str.append('\n');
      }
    }
    return str.toString();
  }

  public StatTestRst test(LinkedList imgs) {
    HashMap means = getMeans();
    StatTestRst rst = new StatTestRst(false);
    for (Iterator j = imgs.iterator(); j.hasNext(); ) {
      String img = (String)j.next();
      FeatureRepresentationList fr_list = m_imgDataCenter.getImgFeatureList(img, m_feature);
      LinkedList feature_list = Conversion.toLinedList(fr_list.as2DDoubleArray());
      DoubleScoreHashMap dist = distances(means, feature_list);
      for (Iterator o = dist.keySet().iterator(); o.hasNext(); ) {
        Object object = o.next();
        double d = dist.getScore(object);
        rst.putScore(object, img, d);
      }
    }
    return rst;
  }

  /**
   * Calculate the Euclidean distance from the specified feature to means
   * of clusters
   * @param means
   * @param feature
   * @return
   */
  public DoubleScoreHashMap distances(HashMap means, double[] feature) {
    DoubleScoreHashMap objects = new DoubleScoreHashMap();
    for (Iterator i= means.keySet().iterator(); i.hasNext(); ) {
      Object key = i.next();
      double[] mean = (double[]) means.get(key);
      double distance = yi.math.VectorUtil.EuclideanDistance(mean, feature);
      if (distance < 0 || distance > 100) {
        OutputResult.print(System.out, mean);
        OutputResult.print(System.out, feature);
      }
      objects.putScore(key, distance);
    }
    return objects;
  }

  /**
   * Calculate the shortest distance from any feature vector of the specified
   * feature vector list to means of clusters
   * @param means
   * @param features
   * @return
   */
  public DoubleScoreHashMap distances(HashMap means, Collection features) {
    DoubleScoreHashMap rsts = new DoubleScoreHashMap();
    for (Iterator i= features.iterator(); i.hasNext(); ) {
      double[] feature = (double[]) i.next();
      DoubleScoreHashMap rst = distances(means, feature);
      for (Iterator j= rst.keySet().iterator(); j.hasNext(); ) {
        Object obj = j.next();
        rsts.putScoreOnCondition(obj, rst.getScore(obj), false);
      }
    }
    return rsts;
  }

  public final static String USAGE = "Usage: -d img_data_center_file [-i img_list_file] [-f feature_class_name[,feature_class_name]*] [-o object_name[,object_name]*] [-r rst_file]";


  public static void main(String[] args) {
    try {
      // init configuration
      Configuration.init(args);

      // get the datacenter
      String data_center_name = ReadArgu.getOption(
         'd', args,
         "groundtruth.ser"
      );

      ImgDataCenter data_center = ImgDataCenter.createFromFile(
         data_center_name);

      // get the image list file name
      String img_list_file = ReadArgu.getOption('i', args);
      // read image list from a file if it is specified
      LinkedList img_list = null;
      if (img_list_file != null) {
        String[] images = yi.util.io.ReadArgu.readStrings(img_list_file);
        img_list = yi.util.data.Conversion.asLinkedList(images);
      }

      // get the feature data class names
      String ft_class_names = ReadArgu.getOption(
         'f', args
      );
      // feature list
      LinkedList ft_list = null;
      if (ft_class_names != null) {
        String[] features = ft_class_names.split(",");
        yi.util.data.Conversion.asLinkedList(features);
      }

      // get the object names
      String obj_names = ReadArgu.getOption('o', args);
      LinkedList obj_list = null;
      if (obj_names != null) {
        String obj_names_wspace = obj_names.replace('_', ' ');
        String[] objects = obj_names_wspace.split(",");
        obj_list = yi.util.data.Conversion.asLinkedList(objects);
      }

      KMeansLikeAdapter experiment = new KMeansLikeAdapter(
          data_center,
          img_list,
          ft_list,
          obj_list);
      System.out.println(experiment);

//      StatTestRst rst = experiment.test();
//      System.out.println(rst);
//
//      String rst_output_file = ReadArgu.getOption('r', args);
//      if (rst_output_file != null) {
//        rst.writeToFile(rst_output_file);
//      }


//      HashMap rpcs = rst.rpcAnalysis(data_center); // right positive curves
//      rst.drawROCs(rpcs);

    } catch (Exception e) {
      e.printStackTrace();
    }
  }

}
