package yi.iu.ft.local;

import java.util.*;
import yi.stat.hist.*;
import yi.ds.hd.*;
import yi.iu.processor.ort.*;
import java.io.*;
import yi.util.config.*;
import yi.util.io.*;
import java.io.*;
import java.util.*;
import yi.util.data.*;
import yi.stat.hist.*;
import yi.iu.processor.texture.reg.*;
import yi.ds.sort.*;
import yi.util.config.*;


public class HistogramWithCorrelatedHighD implements Configurable{

  StatCache m_positiveProbCache;
  StatCache m_negativeProbCache;
  /**
   * Cache the positive case number and negative case number since they will
   * be used a lot
   */
  int m_negativeCaseNum, m_positiveCaseNum;

  public double CORRELATED_RATE_THRESHOLD = 3.0;

  /**
   * The feature instance per positive case must be greater than that per
   * negative case.  This is the ratio
   */
  public double MIN_INST_PRE_CASE_RATIO = 1.2;

  /**
   * If a bin can't get positive case num * MIN_INST_PER_CASE, then it will be
   * out of the picture
   */
  public double MIN_INST_PER_CASE = 0.25;

  /**
   * If a bin can't get positive case num * MIN_INST_PER_CASE, then it will be
   * out of the picture.  Used in 1D selection
   */
  public double MIN_INST_PER_CASE_4_1D = 0;

  /**
   * Do the selection on the original features based on one attribute.
   */
  public boolean SELECT_ON_ORIGINAL_BINS = true;

  /**
   * construct multiple attributes based bins.
   */
  public boolean CONSTRUCT_ATTRIBUTES_BASED_BINS = true;

  /**
   * Maximum added combined bin when the attribute num increased by 1
   */
  public int MAX_COMBINED_BIN_NUM = 50;


  public String[] getParameterNames() {
    return new String[] {
      "CORRELATED_RATE_THRESHOLD",
      "MIN_INST_PRE_CASE_RATIO",
      "MIN_INST_PER_CASE",
      "MIN_INST_PER_CASE_4_1D",
      "MAX_COMBINED_BIN_NUM",
      "SELECT_ON_ORIGINAL_BINS",
      "CONSTRUCT_ATTRIBUTES_BASED_BINS",
    };
  }


  public HistogramWithCorrelatedHighD() {
    Configuration.configParameters(this);
  }

  LinkedList getHistograms(QuantizedFeature[] quans, IntArray[] attr_selectors, int attribute_num, int[] quantized_bin_nums, boolean[] categoris) {

    // resultant attributes (with selected bins)
    LinkedList rst = new LinkedList();

//    ObjectCounter c1 = getStatistics(makeList(2,2), quans, categoris, null, null, true);
//    ObjectCounter c2 = getStatistics(makeList(3,3), quans, categoris, null, null, true);
//    ObjectCounter c3 = getStatistics(makeList(2,3), quans, categoris, null, null, true);
//    System.out.println(c1);
//    System.out.println(c2);
//    System.out.println(c3);
//
//    if (true) return rst;

    // task queue
    TaskQueue queue = new TaskQueue();

    // for one attribute based bins
    AttributeWithSelectedBins[] attrs_1d = new AttributeWithSelectedBins[attribute_num];

    // init the probablistic cache
    m_positiveProbCache = new StatCache(quans, categoris, true);
    m_negativeProbCache = new StatCache(quans, categoris, false);

    // calculate the total positive case number and negative case number
    m_positiveCaseNum = 0; m_negativeCaseNum = 0;
    for (int i=0; i<categoris.length; i++) {
      if (categoris[i]) m_positiveCaseNum ++;
      else m_negativeCaseNum ++;
    }

    // calculate the total instance number of positive cases / negative cases
    int inst_num_in_positive = 0;
    int inst_num_in_negative = 0;
    for (int i=0; i<categoris.length; i++) {
      if (categoris[i]) {
        inst_num_in_positive += quans[i].getInstanceNum();
      }
      else {
        inst_num_in_negative += quans[i].getInstanceNum();
      }
    }


    // init the original bins (which corresponds to 1D feature)
    if (attr_selectors == null) {
      attr_selectors = new IntArray[attribute_num];
      for (int i=0; i<attribute_num; i++) {
        attr_selectors[i] = new IntArray(new int[] {i});
      }
    }
    for (int i=0; i<attr_selectors.length; i++) {

      IntArray attr_selector = attr_selectors[i];

      AttributeWithSelectedBins a = null;

      if (SELECT_ON_ORIGINAL_BINS) {
        a = selectBins(attr_selector, quans, categoris, null, null);
      } else {
        // select all the bins
        HashSet bin_selectors = makeSelectors(attr_selector, quantized_bin_nums);

        // the histogram
        a = new AttributeWithSelectedBins(attr_selector, bin_selectors);
      }

      attrs_1d[i] = a;

      // add it to results
      if (a != null) {
        rst.add(a);
        System.out.println(a);
      }

      // add it to queue
      if (CONSTRUCT_ATTRIBUTES_BASED_BINS && a != null && i < attribute_num-1) {
        queue.push(a);
      }

    }

    TopKeeper tops = new TopKeeper(MAX_COMBINED_BIN_NUM);

    // process from the queue
    while (queue.size() > 0 || tops.size() > 0) {

      if (queue.size() == 0) { // the attribute number will be increased

        // construct those selected attributes from top list
        System.out.println("select top " + tops.size());
        HashMap new_attrs = new HashMap();
        Vector topBins = tops.getTopObjects();
        for (int i=0; i<topBins.size(); i++) {
          BinDescriptor a_bin = (BinDescriptor)topBins.elementAt(i);
          IntArray attr_selector = a_bin.m_attributeSelector;
          IntArray bin_selector = a_bin.m_binSelector;
          System.out.println("top " + i + ":[" + attr_selector + "]=(" + bin_selector + "), score = " + (tops.getTops())[i]);
          if (!new_attrs.containsKey(attr_selector)) {
            HashSet bin_selectors = new HashSet();
            bin_selectors.add(bin_selector);
            new_attrs.put(attr_selector, bin_selectors);
          } else {
            HashSet bin_selectors = (HashSet)new_attrs.get(attr_selector);
            bin_selectors.add(bin_selector);
          }
        }

        // new those attribute with selected bins
        // add those tops into the queue and results
        Iterator i = new_attrs.keySet().iterator();
        while (i.hasNext()) {
          IntArray attr_selector = (IntArray)i.next();
          HashSet bin_selectors = (HashSet)new_attrs.get(attr_selector);
          AttributeWithSelectedBins new_attr = new AttributeWithSelectedBins(attr_selector, bin_selectors);
          rst.add(new_attr);
          // add new task to queue
          queue.push(new_attr);
        }

        // empty tops and recalculate from 0
        tops.clear();

        // deal with the queue
        continue;
      }

      // remove the first one from the queue
      AttributeWithSelectedBins attr1 = queue.pop();

      ObjectCounter prob1 = m_positiveProbCache.retrieve(attr1.getAttributeSelector(), attr1.getBinSelector(), null);

      // consider whether it is ok to combine it with other to be considered
      int max_attribute_index = attr1.getAttributeSelector().getMax();
      if (max_attribute_index + 1 >= attribute_num) continue; // no way to combine it with others
      for (int i=max_attribute_index + 1; i<attribute_num; i++) {
        AttributeWithSelectedBins attr2 = attrs_1d[i];
        if (attr2 == null) continue;  // that attribute may be picked out
        // statistics for attr2
        ObjectCounter prob2 = m_positiveProbCache.retrieve(
          attr2.getAttributeSelector(), attr2.getBinSelector(), null);

        // statistics for combination
        IntArray new_coord = IntArray.concat(attr1.getAttributeSelector(), attr2.getAttributeSelector());
        ObjectCounter prob3 = m_positiveProbCache.retrieve(new_coord, attr1.getBinSelector(), attr2.getBinSelector());
        ObjectCounter prob4 = m_negativeProbCache.retrieve(new_coord, attr1.getBinSelector(), attr2.getBinSelector());

        // select the good bins
//        HashSet good_bins = new HashSet();
        Iterator j = prob3.keySet().iterator();
        while (j.hasNext()) {
          IntArray bin_index = (IntArray)j.next();
          // seperate the bin index to the two part, from attr1 and attr2
          IntArray bin_index_1 = bin_index.subArray(0, bin_index.length() - 1);
          IntArray bin_index_2 = bin_index.subArray(bin_index.length() - 1, 1);

          // get the probs
          int p1 = prob1.getCount(bin_index_1);
          int p2 = prob2.getCount(bin_index_2);
          int p = prob3.getCount(bin_index);
          int p4 = prob4.getCount(bin_index);
          double ratio = ((double)p/m_positiveCaseNum)/((double)p4/m_negativeCaseNum);

          double predicted = (double)p1 * p2 / inst_num_in_positive;
          if (ratio >= MIN_INST_PRE_CASE_RATIO && p >= m_positiveCaseNum * MIN_INST_PER_CASE && p > predicted * CORRELATED_RATE_THRESHOLD) {
            System.out.println("["+ new_coord + "]=(" + bin_index + "):" + ratio +
              " (" + p + "/" + m_positiveCaseNum + "," + p4 + "/" + m_negativeCaseNum + ")");
            System.out.println(new_coord.toString() + '=' + bin_index.toString() + ": " + (p/predicted)+
              "(" + p + "/(" + p1 + " * " + p2 + "/" + inst_num_in_positive + ")");
            tops.insert(new BinDescriptor(new_coord, bin_index), p/predicted);
//            good_bins.add(bin_index);
          } else {
            j.remove();
          }
        }

//        // if there are good bins, add it to results and queue
//        if (good_bins.size() > 0) {
//          // the histogram
//          AttributeWithSelectedBins a = new AttributeWithSelectedBins(new_coord, good_bins);
//          // add it to results
//          rst.add(a);
//          // add it to queue
//          if (i < to_consider.length() - 1) {
//            queue.push(new AttrTask(a, to_consider.subArray(i+1, to_consider.length() - i - 1)));
//            // make a new instance of prob3, because the old one is a big hash table, and then lots
//            // of elements are removed.  there are not necessary to keep those empty spots
//            ObjectCounter new_prob3 = new ObjectCounter();
//            Iterator it = prob3.keySet().iterator();
//            while (it.hasNext()) {
//              Object key = it.next();
//              new_prob3.put(key, prob3.get(key));
//            }
//            // save the prob table for later use
//            m_positiveProbCache.save(new_coord, new_prob3);
//          }
//        }
      }
    }
    return rst;
  }



  /**
   * For each possible bin, calculate the possibility of instance/positive-case
   * and that of instance/negative-case, compare them and pick up the promising
   * bins
   * @param quans
   * @param attribute_num
   * @param quantized_bin_nums
   * @param categoris
   * @param attr_selector
   * @return
   */
  AttributeWithSelectedBins selectBins(IntArray attr_selector,
    QuantizedFeature[] quans, boolean[] categoris, HashSet pre_bin_selectors1, HashSet pre_bin_selectors2) {

      // get the statistics on the positive cases
      ObjectCounter p1 = m_positiveProbCache.retrieve(
        attr_selector, pre_bin_selectors1, pre_bin_selectors2);
      ObjectCounter p2 = m_negativeProbCache.retrieve(
        attr_selector, pre_bin_selectors1, pre_bin_selectors2);

      // select bins based on:
      // p(instances/positive_cases) / p (instances/negative_cases)
      HashSet selected_bins = new HashSet();
      Iterator i = p1.keySet().iterator();
      while (i.hasNext()) {
        Object selector = i.next();
        int num1 = p1.getCount(selector);
        int num2 = p2.getCount(selector);
        double ratio = ((double)num1/m_positiveCaseNum)/((double)num2/m_negativeCaseNum);
        if (ratio >= MIN_INST_PRE_CASE_RATIO && num1 >= m_positiveCaseNum * MIN_INST_PER_CASE_4_1D) {
          selected_bins.add(selector);
        }
        System.out.println("["+ attr_selector + "]=(" + selector + "):" + ratio +
          " (" + num1 + "/" + m_positiveCaseNum + "," + num2 + "/" + m_negativeCaseNum + ")");
      }
      if (!selected_bins.isEmpty()) return new AttributeWithSelectedBins(attr_selector, selected_bins);
      return null;
  }


  /**
   * Calculate the total of feature instances in positive case for each
   * attribute.
   * @param attr_selector the attribute selector
   * @param quans quantized features for each case
   * @param categories category for each case
   * @param bin_selectors1 bin selectors for the first n attributes.  if null,
   *                       don't care the first n attribute values
   * @param bin_selectors2 bin selector for the last m attributes.  if null,
   *                       don't care the last m attribute values.
   * @param on_positive calculate the statistics on positive cases
   * @return
   */
  ObjectCounter getStatistics(IntArray attr_selector,
    QuantizedFeature[] quans, boolean[] categories,
    HashSet bin_selectors1, HashSet bin_selectors2, boolean on_positive) {
      // see whether bin_selectors1 and bin_selectors2 are set and their length
      int bin_width = attr_selector.length();
      int bin_selectors1_width = 0, bin_selectors2_width = 0;
      if (bin_selectors1 != null) {
        if (bin_selectors1.size() > 0) {  // get the bin selector width from the first bin selector
          IntArray bin_selector_dummy = (IntArray)bin_selectors1.iterator().next();
          bin_selectors1_width = bin_selector_dummy.length();
        } else { // make the bin selector width to the width of the bin
          bin_selectors1_width = bin_width;
        }
      }
      if (bin_selectors2 != null) {
        if (bin_selectors2.size() > 0) {  // get the bin selector width from the first bin selector
          IntArray bin_selector_dummy = (IntArray)bin_selectors2.iterator().next();
          bin_selectors2_width = bin_selector_dummy.length();
        } else {
          bin_selectors2_width = bin_width;
        }
      }
      // new counter
      ObjectCounter counter = new ObjectCounter();
      // loop through all the cases
      for (int c=0; c<quans.length; c++) {

        if (on_positive && !categories[c]) continue; // ingore negative cases
        if (!on_positive && categories[c]) continue; // ingore positive cases

        // loop through each instances
        int[][] quan = quans[c].getQuantized();
        for (int j=0; j<quan.length; j++) {
          // get the values
          int[] values = selectValues(quan[j], attr_selector);
          // check whether the first n element is satisfying the bin_selectors1
          if (bin_selectors1_width != 0) {
            int[] first_part = IntArray.subArray(values, 0, bin_selectors1_width);
            if (!bin_selectors1.contains(new IntArray(first_part))) continue;  // not satisifying the bin selector
          }
          // check whether the last m element is satisfying the bin_selectors2
          if (bin_selectors2_width != 0) {
            int[] second_part = IntArray.subArray(values, values.length - bin_selectors2_width, bin_selectors2_width);
            if (!bin_selectors2.contains(new IntArray(second_part))) continue; // not satisfying the bin selector
          }
          // put it into the counter
          counter.put(new IntArray(values));
        }
      }
      return counter;
  }

  int[] selectValues(int[] data, IntArray selector) {
    int[] selected_index = selector.getCoordinates();
    int[] selected = new int[selected_index.length];
    for (int i=0; i<selected.length; i++) {
      selected[i] = data[selected_index[i]];
    }
    return selected;
  }

  class BinDescriptor {
    IntArray m_attributeSelector;
    IntArray m_binSelector;
    public BinDescriptor(IntArray attribute_selector, IntArray bin_selector) {
      m_attributeSelector = attribute_selector;
      m_binSelector = bin_selector;
    }
  }

  class TaskQueue extends ArrayList{
    void push(AttributeWithSelectedBins a) {
      add(a);
    }

    AttributeWithSelectedBins pop() {
      return (AttributeWithSelectedBins)remove(0);
    }
  }

  HashSet makeSelectors(int from, int to) {
    HashSet list = new HashSet();
    for (int i = from; i <= to ; i ++ ) {
      list.add(new IntArray(new int[]{i}));
    }
    return list;
  }

  HashSet makeSelectors(IntArray attr_selector, int[] quantized_bin_nums) {
    if (attr_selector == null || attr_selector.length() <= 0) {
      return new HashSet();
    }
    // if the length = 1, list all the bins and return
    if (attr_selector.length() == 1) {
      int bin_num = quantized_bin_nums[attr_selector.elementAt(0)];
      HashSet list = new HashSet();
      for (int i = 0; i < bin_num ; i ++ ) {
        list.add(new IntArray(new int[]{i}));
      }
      return list;
    }
    // recursive call
    IntArray new_attr_selector = attr_selector.subArray(0, attr_selector.length() - 1);
    HashSet the_set = makeSelectors(new_attr_selector, quantized_bin_nums);
    int bin_num = quantized_bin_nums[attr_selector.elementAt(attr_selector.length()-1)];
    HashSet list = new HashSet();
    Iterator it = the_set.iterator();
    while (it.hasNext()) {
      IntArray the_last = (IntArray)it.next();
      for (int i = 0; i < bin_num ; i ++ ) {
        list.add(IntArray.concat(the_last, i));
      }
    }
    return list;
  }

  IntArray makeList(int from, int to) {
    int[] list = new int[to - from + 1];
    for (int i = from; i <= to ; i ++ ) list[i - from] = i;
    return new IntArray(list);
  }

  class StatCache extends HashMap{
    QuantizedFeature[] m_quans;
    boolean[] m_categories;
    boolean m_onPositive;

    public StatCache(QuantizedFeature[] quans, boolean[] categories, boolean on_positive) {
      m_quans = quans;
      m_categories = categories;
      m_onPositive = on_positive;
    }

    void save(IntArray attr_selector, ObjectCounter stat) {
      m_positiveProbCache.put(attr_selector, stat);
    }

    ObjectCounter retrieve(IntArray attr_selector, HashSet bin_selectors1, HashSet bin_selector2) {
      if (!containsKey(attr_selector)) {
        put(attr_selector, getStatistics(
            attr_selector, m_quans, m_categories, bin_selectors1, bin_selector2, m_onPositive));
      }
      return (ObjectCounter)get(attr_selector);
    }
  }

  public static class TestGetHistograms {

    /**
     *
     */
    public static void main(String[] args) {
      QuantizedFeature[] quans = {
        new QuantizedFeature(new int[][]{
          {3,3,3},
          {2,1,0},
          {0,0,0},
        }),
        new QuantizedFeature(new int[][]{
          {2,0,3},
          {3,3,3},
          {0,3,0},
        }),
        new QuantizedFeature(new int[][]{
          {3,3,3},
          {1,1,1},
          {2,2,2},
        }),
        new QuantizedFeature(new int[][]{
          {3,3,3},
          {1,1,0},
          {0,2,2},
        }),
        new QuantizedFeature(new int[][]{
          {3,2,1},
          {2,3,0},
          {3,3,3},
        }),
        new QuantizedFeature(new int[][]{
          {0,2,2},
          {0,1,2},
          {3,3,3},
        }),
      };
      (new HistogramWithCorrelatedHighD()).getHistograms(quans, null, 3, new int[] {4,4,4}, new boolean[] {true, true, true, true, true, true});
    }
  }

  public static class ForDS_ORTLines{

    static String USAGE = "Usage: -i image_list_file_name -f feature_list_file_name -t target_object_for_learning -o output_root";
    static String IS_TARGET_OBJECT = new String("true");
    static String IS_NOT_TARGET_OBJECT = new String("false");

    static String[] getAttributeNames(String ft_names){
      if (ft_names.indexOf("DS_ORTLines") > 0) {
        String[] names = (new DS_ORTLines()).getQuantizedBinName();
        return names;
      }
      if (ft_names.indexOf("DS_GaborTextureRegions") > 0) {
        String[] names = (new DS_GaborTextureRegions()).getQuantizedBinName();
        return names;
      }
      return null;
    }

    static String getBinName(QuantizeTemplate quantizer, IntArray attr_selector, IntArray bin_selector) {
      StringBuffer s = new StringBuffer();
      for (int i=0; i<attr_selector.length(); i++) {
        int index = attr_selector.elementAt(i);
        String[] bin_names = quantizer.getQuantizedBinName(index);
        if (i != 0) s.append('.');
        try {
        s.append(bin_names[bin_selector.elementAt(i)]);
        } catch (Exception e) {
          System.out.println("bin name[0] = " + bin_names[0]);
          System.out.println("index = " + bin_selector.elementAt(i));
        }
      }
      return s.toString();
    }

    static QuantizedFeature[] readQuantizedFeatures(String[] img_names, String feature_name) {
      // space for result
      QuantizedFeature[] rst = new QuantizedFeature[img_names.length];
      // for each image
      for (int i=0; i<img_names.length; i++) {
        // image feature file
        String img_ft_file_name = img_names[i] + '.' + feature_name;
        System.out.println("read quan #" + i + "/" + img_names.length + ": " + img_ft_file_name);
        try {
          ObjectInputStream in = new ObjectInputStream(
            new BufferedInputStream(new FileInputStream(img_ft_file_name)));
          rst[i] = (QuantizedFeature)in.readObject();
          in.close();
        } catch (IOException e) {
          System.err.println("Can't read from file: " + img_ft_file_name);
          e.printStackTrace();
          continue;
        } catch (ClassNotFoundException e) {
          e.printStackTrace();
          continue;
        }
        int[][] quan = rst[i].getQuantized();
      }
      return rst;
    }

    static void outputArff(PrintStream out, String[] attribute_names, String[] img_names,
      String[] ft_names, boolean[] categories, String relation){

      QuantizedFeature[] quans = readQuantizedFeatures(img_names, ft_names[0]);

      HistogramWithCorrelatedHighD corelate = new HistogramWithCorrelatedHighD();
      QuantizeTemplate dummy = null;
      if (ft_names[0].indexOf("DS_ORTLines") >=0) {
        dummy = (new DS_ORTLines()).getQuantizeTemplate("quan");
      } else if (ft_names[0].indexOf("DS_GaborTextureRegions") >=0) {
        dummy = (new DS_GaborTextureRegions()).getQuantizeTemplate("quan");
      } else if (ft_names[0].indexOf("DS_ChromaticGaborTextureRegion") >=0) {
        dummy = (new DS_ChromaticGaborTextureRegions()).getQuantizeTemplate("quan");
      }

      LinkedList selectedAttributes = corelate.getHistograms(quans, null,
        dummy.getAttributeNum(), dummy.getQuantizedBinNums(), categories);

      // title
      // @relation
      out.println("@relation " + relation);
      out.println();

      // attributes
      // @attribute p0 real
      Iterator i = selectedAttributes.iterator();
      while (i.hasNext()) {
        AttributeWithSelectedBins a = (AttributeWithSelectedBins)i.next();
        HashSet bins = a.getBinSelector();
        Iterator b = bins.iterator();
        while (b.hasNext()) {
          IntArray bin = (IntArray)b.next();
          String attribute_name = getBinName(dummy, a.getAttributeSelector(), bin);
          out.println("@attribute " + attribute_name + " real");
        }
      }
      out.println("@attribute object {" + IS_TARGET_OBJECT + "," + IS_NOT_TARGET_OBJECT + "}");
      out.println();

      //data
      out.println("@data");
      for (int c=0; c<quans.length; c++) {
        i = selectedAttributes.iterator();
        while (i.hasNext()) {
          AttributeWithSelectedBins a = (AttributeWithSelectedBins)i.next();
          int[] data = a.getHistogram(quans[c]);
          for (int j=0; j<data.length; j++) {
            out.print(data[j]);
            out.print(',');
          }
        }
        out.println(categories[c]);
      }
    }

    static void outputArff(PrintStream out, IntArray[] attr_selectors, String[] attribute_names, String[] img_names,
      String[] ft_names, String[] dataset_names, String[] quantizer_ids, boolean[] categories, String relation) throws Exception{

      QuantizedFeature[] quans = readQuantizedFeatures(img_names, ft_names[0]);

      HistogramWithCorrelatedHighD correlate = new HistogramWithCorrelatedHighD();
      FeatureQuantizer dummy = (FeatureQuantizer)Class.forName(dataset_names[0]).newInstance();
      QuantizeTemplate quantize_template = dummy.getQuantizeTemplate(quantizer_ids[0]);

      LinkedList selectedAttributes = correlate.getHistograms(quans, attr_selectors,
        quantize_template.getAttributeNum(), quantize_template.getQuantizedBinNums(), categories);

      // title
      // @relation
      out.println("@relation " + relation);
      out.println();

      // attributes
      // @attribute p0 real
      Iterator i = selectedAttributes.iterator();
      while (i.hasNext()) {
        AttributeWithSelectedBins a = (AttributeWithSelectedBins)i.next();
        HashSet bins = a.getBinSelector();
        Iterator b = bins.iterator();
        while (b.hasNext()) {
          IntArray bin = (IntArray)b.next();
          String attribute_name = getBinName(quantize_template, a.getAttributeSelector(), bin);
          out.println("@attribute " + attribute_name + " real");
        }
      }
      out.println("@attribute object {" + IS_TARGET_OBJECT + "," + IS_NOT_TARGET_OBJECT + "}");
      out.println();

      //data
      out.println("@data");
      for (int c=0; c<quans.length; c++) {
        i = selectedAttributes.iterator();
        while (i.hasNext()) {
          AttributeWithSelectedBins a = (AttributeWithSelectedBins)i.next();
          int[] data = a.getHistogram(quans[c]);
          for (int j=0; j<data.length; j++) {
            out.print(data[j]);
            out.print(',');
          }
        }
        out.println(categories[c]);
      }
    }

    /**
     * Return the categories of all the given images.  If an image is positive
     * (has at least one of the target objects), the corresponding returning
     * string is as defined in IS_TARGET_OBJECT; otherwise, IS_NOT_TARGET_OBJECT
     * @param img_names
     * @param targets
     * @return
     * @throws IOException
     */
    static boolean[] readCategories(String[] img_names, String targets){
      boolean[] categories = new boolean[img_names.length];

      String[] target_objs = StringUtil.getDeliminatedStrings(targets, ",", true);

      // for each image
      for (int i=0; i<img_names.length; i++) {
        String short_name = yi.util.io.File.getShortName(img_names[i]);
        // the description file
        String description_file = yi.util.io.File.getPath(img_names[i]) + '/' + "descriptions.txt";
        // read decription file
        String[] descriptions = null;

        categories[i] = false;
        try {
          descriptions = ReadArgu.readStrings(description_file);
        } catch (IOException e) { // descriptions.txt not exist
          System.out.println("can't find " + description_file);
          continue;
        }

        boolean found_line = false;
        for (int j=0; j<descriptions.length; j++) {
          // find the line corresponding to the image
          if (descriptions[j].toUpperCase().indexOf(short_name.toUpperCase()) >= 0) {
            found_line = true;
            int index_of_colon = descriptions[j].indexOf(":");
            if (index_of_colon < 0) {
              continue;
            }
            String objects_line = descriptions[j].substring(index_of_colon + 1);
            System.out.println(objects_line);
            String[] objects = StringUtil.getDeliminatedStrings(objects_line, ",", true);
            // search all the target strings
            boolean found = false;
            for (int k=0; k<target_objs.length; k++) {
              for (int l=0; l<objects.length; l++) {
                if (objects[l].compareToIgnoreCase(target_objs[k]) == 0) {
                  categories[i] = true;
                  System.out.print(objects[l] + " ");
                  found = true;
                  break;
                }
              }
              if (found) break;
            }
            System.out.println(categories[i]);
            break;
          }
        }
        if (!found_line) {
          System.out.println("Can't find the descriptions for " + img_names[i]);
        }
      }
      return categories;
    }

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

      // get the image list file name
      String img_name = ReadArgu.getOption('i', args);
      if (img_name == null) {
        System.err.println(USAGE);
        System.exit(1);
      }

      // get the feature list file name
      String ft_name = ReadArgu.getOption('f', args);
      if (ft_name == null) {
        System.err.println(USAGE);
        System.exit(1);
      }

      // get the target_object_for_learning
      String target_object = ReadArgu.getOption('t', args);
      if (target_object == null) {
        System.err.println(USAGE);
        System.exit(1);
      }

      // get the target_object_for_learning
      String output_root = ReadArgu.getOption('o', args);
      if (output_root == null) {
        output_root = target_object.replace(',', '.').replace(' ', '_').toLowerCase() + '.' + ft_name.toLowerCase();
      }

      // read categories
      String category_file = ReadArgu.getOption('c', args);

      try {
        // reading from files
        String[] img_names = ReadArgu.readStrings(img_name);
        String[] ft_lines = ReadArgu.readStrings(ft_name);
        String[] ft_names = new String[ft_lines.length];
        String[] dataset_names = new String[ft_lines.length];
        String[] quantizer_ids = new String[ft_lines.length];
        IntArray[] attr_selectors = null;

        for (int i=0; i<ft_lines.length; i++) {
          StringTokenizer tokenizer = new StringTokenizer(ft_lines[0], ":");
          if (tokenizer.countTokens() < 3) {
            System.err.println("wrong feature description format: " + ft_name);
            System.err.println("  format: file_name, dataset_name, quantizer_id");
            System.exit(0);
          }
          if (tokenizer.hasMoreTokens()) ft_names[i] = tokenizer.nextToken();
          if (tokenizer.hasMoreTokens()) dataset_names[i] = tokenizer.nextToken();
          if (tokenizer.hasMoreTokens()) quantizer_ids[i] = tokenizer.nextToken();
          if (tokenizer.hasMoreTokens()) {
            String attribute_selectors = tokenizer.nextToken();
            StringTokenizer token = new StringTokenizer(attribute_selectors, ";");
            attr_selectors = new IntArray[token.countTokens()];
            int count = 0;
            while (token.hasMoreTokens()) {
              attr_selectors[count] = new IntArray(token.nextToken());
              System.out.println(attr_selectors[count]);
              count++;
            }
          }
        }

        // reading categories
        boolean[] categories = null;
        if (category_file != null) {
          String[] positive_img_names = ReadArgu.readStrings(category_file);
          HashSet name_set = new HashSet();
          for (int i=0; i<positive_img_names.length; i++) name_set.add(positive_img_names[i]);
          categories = new boolean[img_names.length];
          for (int i=0; i<img_names.length; i++) {
            categories[i] = (name_set.contains(img_names[i])) ? true : false;
          }
        }
        else categories = readCategories(img_names, target_object);

        // output t.data
        PrintStream arff_file = new PrintStream (new FileOutputStream(output_root + ".arff"));
        String[] attribute_names = getAttributeNames(ft_names[0]);
        outputArff(arff_file, attr_selectors, attribute_names, img_names, ft_names, dataset_names, quantizer_ids, categories, output_root);
        arff_file.close();
      } catch (Exception e) {
        e.printStackTrace();
      }

      System.exit(0);
    }
  }
}