2009-08-30

Histogram :: map-based

public class Histogram<T>
{
   private final Map<T, Integer> map;

   public Histogram()
   {
      this.map = new HashMap<T, Integer>();
   }

   public int put(T t)
   {
      Integer count = this.map.get(t);
      if (count == null)
         count = Integer.valueOf(0);
      count = Integer.valueOf(count.intValue() + 1);
      this.map.put(t, count);
      return count.intValue();
   }

   public int get(T t)
   {
      Integer count = this.map.get(t);
      if (count == null)
         return 0;
      return count.intValue();
   }

   public List<T> topKeys(int amount)
   {
      //int threshold = Integer.MIN_VALUE;

      List<T> kList = new ArrayList<T>();
      List vList = new ArrayList();

      for (Entry e : this.map.entrySet())
      {
         //int val = e.getValue().intValue();
         //if (val <= threshold)
         {
            //continue;
         }

         // when full, remove lowest
         if (vList.size() == amount)
         {
            int index = indexOfMin(vList);
            kList.remove(index);
            vList.remove(index);
         }

         kList.add(e.getKey());
         vList.add(e.getValue());
      }

      // bubble sort
      for (int i = 0; i < vList.size(); i++)
      {
         for (int k = i + 1; k < vList.size(); k++)
         {
            if (vList.get(i).intValue() >= vList.get(k).intValue())
            {
               continue;
            }

            Integer a = vList.get(i);
            Integer b = vList.get(k);
            vList.set(k, a);
            vList.set(i, b);

            T x = kList.get(i);
            T y = kList.get(k);
            kList.set(k, x);
            kList.set(i, y);
         }
      }

      return kList;
   }

   public int remove(T t)
   {
      Integer count = this.map.get(t);
      if (count == null)
         throw new NoSuchElementException(String.valueOf(t));
      if (count.intValue() == 0)
         throw new IllegalStateException("cannot remove");

      count = Integer.valueOf(count.intValue() - 1);
      if (count.intValue() == 0)
         this.map.remove(t);
      else
         this.map.put(t, count);

      return count.intValue();
   }

   public int reset(T t)
   {
      Integer count = this.map.remove(t);
      if (count == null)
         return 0;
      return count.intValue();
   }

   public int set(T t, int val)
   {
      if (val < 0)
         throw new IllegalArgumentException();
      Integer count = this.map.get(t);

      if (count == null)
      {
         if (val != 0)
            this.map.put(t, Integer.valueOf(val));
         return 0;
      }

      if (val == 0)
         return this.map.remove(t).intValue();
      return this.map.put(t, Integer.valueOf(val)).intValue();
   }

   public Set<T> keys()
   {
      return this.map.keySet();
   }

   private static int indexOfMin(List<Integer> ids)
   {
      int minAt = 0;
      for (int i = 1; i < ids.size(); i++)
         if (ids.get(i).intValue() < ids.get(minAt).intValue())
            minAt = i;
      return minAt;
   }
}

No comments:

Post a Comment