package edu.stanford.nlp.util;import java.util.*;import java.io.Serializable;/**  * Specialized Map for storing numeric counts for objects. Works like a normal * Map but with extra methods for easily getting/setting/incrementing counts * for objects and computing various functions with the counts. Any attempt to * put a non-Double value into this Counter will result in an  * IllegalArgumentException being thrown. Note however that the Map constructor * and <tt>putAll</tt> method can be used to copy another Counter's contents  * over (see also <tt>addAll(Counter)</tt>). This class also provides access * to Comparators that can be used to sort the keys or entries of this Counter * by the counts, in either ascending or descending order. * @author Dan Klein * @author Joseph Smarr (jsmarr@stanford.edu) */public class Counter extends HashMap implements Serializable {    /** Default comparator for breaking ties in argmin and argmax. */    private static final Comparator naturalComparator=new NaturalComparator();    private static final long serialVersionUID = 3;        private double total; // current total count of all entries        /** Constructs a new (empty) Counter. */    public Counter() { super(); }        /**     * Constructs a new Counter with the contents of the given Map.     * The values in <tt>m</tt> must all be Doubles or an      * IllegalArgumentException will be thrown when they are added.     */    public Counter(Map m) { this(); putAll(m); }        // --- Standard access/modification methods --- //        /**      * Returns the current total count for all objects in this Counter. The     * total is maintained as counts are adjusted so it can be returned quickly     * without having to sum all the counts on demand.     */    public double totalCount() { return(total); }          /**      * Returns the total count for all objects in this Counter that pass the      * given Filter. Passing in a filter that always returns true is equivalent      * to calling {@link #total()}, though the latter is faster since the total     * is maintained internally as counts are adjusted.     */    public double totalCount(Filter filter)    {        double total=0.0;        for(Iterator iter=seenSet().iterator();iter.hasNext();)        {            Object key=iter.next();            if(filter.accept(key)) total+=getCount(key);        }        return(total);    }        /** Returns the mean of all the counts (totalCount/size). */    public double averageCount() { return(totalCount()/size()); }           /**     * Returns the current count for the given key, which is 0 if it hasn't been     * seen before. This is a convinient version of <tt>get</tt> that casts     * and extracts the primitive value.     */    public double getCount(Object key)    {        Number count=(Number)get(key);        if(count==null) return(0); // haven't seen this object before -> 0 count        return(count.doubleValue());    }        /**     * Returns the current count for the given key as a fraction of the total     * count in the counter. This is equivalent to assuming that all the counts     * sum to one, but it doesn't actually change the raw counts.     */    public double getNormalizedCount(Object key)    {        return(getCount(key)/total());    }        /**     * Sets the current count for the given key. This will wipe out any existing     * count for that key.      * <p>     * To add to a count instead of replacing it, use      * {@link #incrementCount(Object,double)}.     */    public void setCount(Object key,double count)    {        put(key,new Double(count));    }        /**     * Sets the current count for each of the given keys. This will wipe out     * any existing counts for these keys.     * <p>     * To add to the counts of a collection of objects instead of replacing them,     * use {@link #incrementCounts(Collection,double)}.     */    public void setCounts(Collection keys,double count)    {        for(Iterator iter=keys.iterator();iter.hasNext();)            setCount(iter.next(),count);    }        /**     * Adds the given count to the current count for the given key. If the key     * hasn't been seen before, it is assumed to have count 0, and thus this      * method will set its count to the given amount. Negative increments are     * equivalent to calling <tt>decrementCount</tt>.     * <p>     * To more conviently increment the count by 1.0, use      * {@link #incrementCount(Object)}.     * <p>     * To set a count to a specifc value instead of incrementing it, use      * {@link #setCount(Object,double)}.     */    public void incrementCount(Object key,double count)    {        put(key,new Double(count+getCount(key)));    }        /**     * Adds 1.0 to the count for the given key. If the key hasn't been seen      * before, it is assumed to have count 0, and thus this method will set     * its count to 1.0.      * <p>     * To increment the count by a value other than 1.0, use      * {@link #incrementCount(Object,double)}.     * <p>     * To set a count to a specifc value instead of incrementing it, use      * {@link #setCount(Object,double)}.     */    public void incrementCount(Object key) { incrementCount(key,1.0); }           /**     * Adds the given count to the current counts for each of the given keys.     * If any of the keys haven't been seen before, they are assumed to have     * count 0, and thus this method will set their counts to the given     * amount. Negative increments are equivalent to calling <tt>decrementCounts</tt>.     * <p>     * To more conviniently increment the counts of a collection of objects by     * 1.0, use {@link #incrementCounts(Collection)}.     * <p>     * To set the counts of a collection of objects to a specific value instead     * of incrementing them, use {@link #setCounts(Collection,double)}.     */    public void incrementCounts(Collection keys,double count)    {        for(Iterator iter=keys.iterator();iter.hasNext();)            incrementCount(iter.next(),count);    }        /**     * Adds 1.0 to the counts for each of the given keys. If any of the keys      * haven't been seen before, they are assumed to have count 0, and thus      * this method will set their counts to 1.0.     * <p>     * To increment the counts of a collection of object by a value other      * than 1.0, use {@link #incrementCounts(Collection,double)}.     * <p>     * To set the counts of a collection of objects  to a specifc value instead     * of incrementing them, use  {@link #setCounts(Collection,double)}.     */    public void incrementCounts(Collection keys) { incrementCounts(keys,1.0); }        /**     * Subtracts the given count from the current count for the given key.      * If the key hasn't been seen before, it is assumed to have count 0, and      * thus this  method will set its count to the negative of the given amount.      * Negative increments are equivalent to calling <tt>incrementCount</tt>.     * <p>     * To more conviently decrement the count by 1.0, use      * {@link #decrementCount(Object)}.     * <p>     * To set a count to a specifc value instead of decrementing it, use      * {@link #setCount(Object,double)}.     */    public void decrementCount(Object key,double count)    {        incrementCount(key,-count);    }        /**     * Subtracts 1.0 from the count for the given key. If the key hasn't been      * seen  before, it is assumed to have count 0, and thus this method will      * set its count to -1.0.      * <p>     * To decrement the count by a value other than 1.0, use      * {@link #decrementCount(Object,double)}.     * <p>     * To set a count to a specifc value instead of decrementing it, use      * {@link #setCount(Object,double)}.     */    public void decrementCount(Object key) { decrementCount(key,1.0); }                   /**     * Subtracts the given count from the current counts for each of the given keys.     * If any of the keys haven't been seen before, they are assumed to have     * count 0, and thus this method will set their counts to the negative of the given     * amount. Negative increments are equivalent to calling <tt>incrementCounts</tt>.     * <p>     * To more conviniently decrement the counts of a collection of objects by     * 1.0, use {@link #decrementCounts(Collection)}.     * <p>     * To set the counts of a collection of objects to a specific value instead     * of decrementing them, use {@link #setCounts(Collection,double)}.     */    public void decrementCounts(Collection keys,double count)    {        incrementCounts(keys,-count);    }        /**     * Subtracts 1.0 from the counts of each of the given keys. If any of the keys      * haven't been seen before, they are assumed to have count 0, and thus      * this method will set their counts to -1.0.     * <p>     * To decrement the counts of a collection of object by a value other      * than 1.0, use {@link #decrementCounts(Collection,double)}.     * <p>     * To set the counts of a collection of objects  to a specifc value instead     * of decrementing them, use  {@link #setCounts(Collection,double)}.     */    public void decrementCounts(Collection keys) { decrementCounts(keys,1.0); }    /**     * Adds the counts in the given Counter to the counts in this Counter.     * <p>     * To copy the values from another Counter rather than adding them, use     * {@link #putAll(Map)} or {@link #Counter(Map)}.     */    public void addAll(Counter counter)    {        for(Iterator iter=counter.keySet().iterator();iter.hasNext();)        {            Object key=iter.next();            incrementCount(key,counter.getCount(key));        }    }        /**     * Subtracts the counts in the given Counter from the counts in this Counter.     * <p>     * To copy the values from another Counter rather than subtracting them, use     * {@link #putAll(Map)} or {@link #Counter(Map)}.     */    public void subtractAll(Counter counter)    {        for(Iterator iter=counter.keySet().iterator();iter.hasNext();)        {            Object key=iter.next();            decrementCount(key,counter.getCount(key));        }    }        // --- Collection methods (to constrain values and keep total) --- //        /**     * Adds a count for the given key if value is a Number. Throws an     * IllegalArgumentException otherwise. All of HashMap's various put     * functions route through this method, so it's the single choke point     * to ensure that only Object-->Double entries are contained in this map.     * If the value is a non-Double Number, its doubleValue is extracted and     * inserted in a new Double, so the values should always be of type Double,     * but this way adding an Integer doesn't break it.     * For normal use, use <tt>incrementCount</tt> instead.     */    public Object put(Object key,Object value) throws IllegalArgumentException    {           if(value!=null && value instanceof Number)        {                 double count=((Number)value).doubleValue();            total+=count; // add new count                        Double oldCount=(Double)super.put(key,new Double(count));             if(oldCount!=null) total-=oldCount.doubleValue(); // subtract old count (it's being replaced)                        return(oldCount); // this is what put() normally returns        }        else throw(new IllegalArgumentException("value must be a Number"));    }    /**      * Removes the given key from this Counter. Its count will now be 0 and it     * will no longer be considered previously seen.     */    public Object remove(Object key)    {        total-=getCount(key); // subtract removed count from total (may be 0)        return(super.remove(key));    }        /** Removes all the given keys from this Counter. */    public void removeAll(Collection c)    {        for(Iterator iter=c.iterator();iter.hasNext();)            remove(iter.next());    }        /**  Removes all counts from this Counter. */    public void clear()    {        super.clear();        total=0;    }           // --- Extra calculation methods --- //            /**      * Divides all the counts by the total so they collectively sum to 1.0.      * This effectively turns this Counter into a probability distribution.     * The behavior will be weird if there are any negative counts.     * Note that calling {@link #getNormalizedCount} returns the same thing     * as {@link #getCount} after calling <tt>normalize</tt> but it doesn't     * change the raw counts.     */    public void normalize()    {        double total=total(); // cache value since it will change as we normalize        for(Iterator iter=keySet().iterator();iter.hasNext();)        {            Object key=iter.next();            setCount(key,getCount(key)/total);        }    }        /**