Collection: Histogram / Frequency table

You can use a histogram to count the number of occurences of a certain item in a collection.

Additionally you can query the histogram for the most frequently occuring items.


import java.util.*;

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

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

   public void clear()
   {
      this.map.clear();
   }

   public int put(T t)
   {
      return this.put(t, 1);
   }

   public int put(T t, int amount)
   {
      if (amount < 0)
         throw new IllegalArgumentException();

      int count = this.get(t);
      if (amount == 0)
         return count;

      count += amount;
      this.map.put(t, Integer.valueOf(count));
      return count;
   }

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

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

   public List<T> thresholdKeys(int atLeast)
   {
      int found = 0;
      for (Integer c : this.map.values())
         if (c.intValue() >= atLeast)
            found++;
      return topKeys(found);
   }

   public List<T> topKeys()
   {
      return this.topKeys(Integer.MAX_VALUE);
   }

   public List<T> topKeys(int amount)
   {
      List<T> kList = new ArrayList<T>();
      List<Integer> vList = new ArrayList<Integer>();

      for (Entry<T, Integer> e : this.map.entrySet())
      {
         if (vList.size() == amount + 1)
         {
            // when overflowed, remove lowest
            int index = indexOfMin(vList);
            kList.remove(index);
            vList.remove(index);
         }

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

      // bubble sort, assuming 'amount' is reasonably small
      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);
         }
      }

      if (kList.size() == amount + 1)
      {
         // drop smallest item, if overflowed
         kList.remove(kList.size() - 1);
         vList.remove(vList.size() - 1);
      }

      return kList;
   }

   public int remove(T t)
   {
      return this.remove(t, 1);
   }

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

      count = Integer.valueOf(count.intValue() - amount);
      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();
   }

   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;
   }

   //

   public Histogram<T> asSynchronized()
   {
      final Histogram<T> backing = this;

      return new Histogram<T>()
      {
         public synchronized int put(T t)
         {
            return backing.put(t);
         }

         public synchronized int put(T t, int amount)
         {
            return backing.put(t, amount);
         }

         public synchronized int get(T t)
         {
            return backing.get(t);
         }

         public synchronized int remove(T t)
         {
            return backing.remove(t);
         }

         public synchronized int reset(T t)
         {
            return backing.reset(t);
         }

         public synchronized int set(T t, int val)
         {
            return backing.set(t, val);
         }

         @Override
         public synchronized Set<T> keys()
         {
            return backing.keys();
         }

         @Override
         public synchronized List<T> topKeys()
         {
            return backing.topKeys();
         }

         @Override
         public synchronized List<T> topKeys(int amount)
         {
            return backing.topKeys(amount);
         }

         @Override
         public boolean equals(Object obj)
         {
            return backing.equals(obj);
         }

         @Override
         public int hashCode()
         {
            return backing.hashCode();
         }

         @Override
         public String toString()
         {
            return backing.toString();
         }

         @Override
         public Histogram<T> asSynchronized()
         {
            return this;
         }
      };
   }
}

Wouldn’t you want the “asSynchronized()” method return an instance of Histogram that contains all the objects in the parent Histogram?