package yi.ds.sort;

import java.util.*;

/**
 * TopKeep keeps the top n values
 */
public class TopKeeper {
  Vector m_tops;
  int m_keepNum;

  Vector m_topObjects;

  public TopKeeper(int keep_num) {
    m_keepNum = keep_num;
    m_tops = new Vector(keep_num + 1);
    m_topObjects = new Vector(keep_num + 1);
  }

  public boolean insert(Object obj, double value) {
    if (m_tops.isEmpty()) {
      Double key = new Double(value);
      m_tops.add(key);
      m_topObjects.add(obj);
      return true;
    }

    // if the new added value is not greater than the smallest
    if (value <= ((Double)m_tops.lastElement()).doubleValue()) {
      if (m_tops.size() < m_keepNum) {
        Double key = new Double(value);
        m_tops.add(key);
        m_topObjects.add(obj);
        return true;
      } else {
        return false;
      }
    }

    // if the new added value is greater than the smallest
    boolean inserted = false;
    for (int i=m_tops.size()-1; i>=0; i--) {
      if (value <= ((Double)m_tops.elementAt(i)).doubleValue()) {
        Double key = new Double(value);
        m_tops.insertElementAt(key, i + 1);
        m_topObjects.insertElementAt(obj, i + 1);
        inserted = true;
        break;
      }
    }
    if (!inserted) {
        Double key = new Double(value);
        m_tops.insertElementAt(key, 0);
        m_topObjects.insertElementAt(obj, 0);
    }
    if (m_tops.size() > m_keepNum) {
      m_tops.remove(m_keepNum);
      m_topObjects.remove(m_keepNum);
    }
    return true;
  }

  public double[] getTops() {
    return yi.util.data.Conversion.toDoubleArray(m_tops);
  }

  public Vector getTopObjects() {
    return m_topObjects;
  }

  public void clear() {
    m_tops.clear();
    m_topObjects.clear();
  }

  public int size() {
    return m_tops.size();
  }

  public String toString() {
    StringBuffer str = new StringBuffer();
    for (int i=0; i<m_tops.size(); i++)  {
      if (i!=0) str.append(',');
      str.append(m_tops.elementAt(i));
      str.append("(" + m_topObjects.elementAt(i) + ")");
    }
    return str.toString();
  }

  /**
   *
   */
  public static void main(String[] args) {
    TopKeeper tops = new TopKeeper(3);
    tops.insert(new Double(2.1), 2.1);
    System.out.println(tops.toString());
    tops.insert(new Double(2.1), 2.1);
    System.out.println(tops.toString());
    tops.insert(new Double(2.0), 2.0);
    System.out.println(tops.toString());
    tops.insert(new Double(2.02), 2.0);
    System.out.println(tops.toString());
    tops.insert(new Double(2.5), 2.5);
    System.out.println(tops.toString());
    tops.insert(new Double(2.4), 2.4);
    System.out.println(tops.toString());
    tops.insert(new Double(2.31), 2.3);
    System.out.println(tops.toString());
    tops.insert(new Double(2.32), 2.3);
    System.out.println(tops.toString());
    tops.insert(new Double(2.45), 2.45);
    System.out.println(tops.toString());
    tops.insert(new Double(2.41), 2.41);
    System.out.println(tops.toString());
  }
}