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