Just a lowly counter that turned out to be surprisingly complicated

Question

While writing this review, I saw a need for a Counter object similar to Python's. It seemed like it would be easy to write such a class, but it turned out to be surprisingly complicated.

Counter.java

import java.util.*;

public class Counter<T> implements Map<T, Integer>,
                                   Iterable<Map.Entry<T, Integer>> {

    private final Map<T, Integer> c = new HashMap<T, Integer>();

    /**
     * Comparator to sort entries by decreasing count.  In case of a tie,
     * arbitrary but deterministic tie-breakers are used.
     */
    private final Comparator<Map.Entry<T, Integer>> DESC_FREQ_COMPARATOR =
            new Comparator<Map.Entry<T, Integer>>() {
        @Override
        public int compare(Map.Entry<T, Integer> a, Map.Entry<T, Integer> b) {
            int aValue = a.getValue().intValue();
            int bValue = b.getValue().intValue();
            int diff;
            if (0 != (diff = bValue - aValue)) {
                return diff;
            } else if (0 != (diff = b.hashCode() - a.hashCode())) {
                return diff;
            } else {
                T aKey = a.getKey();
                T bKey = b.getKey();
                if (aKey == null && bKey == null) {
                    return 0;
                } else if (aKey == null) {
                    return 1;
                } else if (bKey == null) {
                    return -1;
                } else if (bKey instanceof Comparable) {
                    @SuppressWarnings("unchecked")
                    Comparable<T> bKeyCmp = (Comparable<T>)bKey;
                    return bKeyCmp.compareTo(aKey);
                } else {
                    return bKey.toString().compareTo(aKey.toString());
                }
            }
        }
    };

    /**
     * Creates an empty counter.
     */
    public Counter() {}

    /**
     * Copy constructor.
     */
    public Counter(Map<T, Integer> counter) {
        this();
        this.putAll(counter);
    }

    /**
     * Returns the number of key-value mappings in this map, including entries
     * that have a zero count.
     */
    @Override
    public int size() {
        return this.c.size();
    }

    /**
     * Returns whether there are no entries.  Any entry, even an entry with a
     * zero count, makes the counter non-empty.
     */
    public boolean isEmpty() {
        return this.c.isEmpty();
    }

    /**
     * Returns whether the key exists.  A key with a zero count exists until it
     * is removed or the entire counter is cleared.
     */
    @Override
    public boolean containsKey(Object key) {
        return this.c.containsKey(key);
    }

    /**
     * Returns whether any key has the specified count.
     */
    @Override
    public boolean containsValue(Object integralNumber) {
        return integralNumber instanceof Number &&
               this.c.containsValue(((Number)integralNumber).intValue());
    }

    /**
     * Returns whether any key has the specified count.
     */
    public boolean containsValue(int value) {
        return this.c.containsValue(value);
    }

    /**
     * Returns the value to which the specified key is mapped, or null if this
     * map contains no mapping for the key.
     */
    @Override
    public Integer get(Object key) {
        Integer i = this.c.get(key);
        return i == null ? 0 : i.intValue();
    }

    /**
     * Sets the count for a key.
     */
    @Override
    public Integer put(T key, Integer value) {
        Integer prev = this.c.put(key, value);
        return (prev == null) ? 0 : prev;
    }

    /**
     * Removes a key.
     */
    @Override
    public Integer remove(Object key) {
        Integer prev = this.c.remove(key);
        return (prev == null) ? 0 : prev;
    }

    @Override
    public void putAll(Map<? extends T, ? extends Integer> m) {
        for (Map.Entry<? extends T, ? extends Integer> entry : m.entrySet()) {
            this.put(entry.getKey(), entry.getValue());
        }
    }

    @Override
    public void clear() {
        this.c.clear();
    }

    /**
     * Returns the keys in an arbitrary order.
     */
    @Override
    public Set<T> keySet() {
        return this.c.keySet();
    }

    /**
     * Returns the values in an arbitrary order.
     */
    @Override
    public Collection<Integer> values() {
        return this.c.values();
    }

    /**
     * Compares the specified object with this map for equality. Returns true
     * if the given object is also a map and the two maps have the same
     * counts.
     *
     * For this equality test, an entry with a zero count is treated the same
     * as no entry at all.
     */
    public boolean equals(Object o) {
        if (!(o instanceof Counter) || this.hashCode() != o.hashCode()) {
            return false;
        }
        Counter other = (Counter)o;
        Map.Entry<T, Integer>[] a = this.mostCommon();
        @SuppressWarnings("unchecked")
        Map.Entry<?, Integer>[] b = other.mostCommon();
        int i = 0;
        for (; i < Math.min(a.length, b.length); i++) {
            int aCount = (a[i] == null) ? 0 : a[i].getValue();
            int bCount = (b[i] == null) ? 0 : b[i].getValue();
            if (aCount == 0 && bCount == 0) {
                return true;
            } else if (aCount != bCount) {
                return false;
            }
            Object aKey = a[i].getKey();
            Object bKey = b[i].getKey();
            if (!aKey.equals(bKey)) {
                return false;
            }
        }
        // Nothing left over
        int aCount = (i >= a.length || a[i] == null) ? 0 : a[i].getValue();
        int bCount = (i >= b.length || b[i] == null) ? 0 : b[i].getValue();
        return aCount == 0 && bCount == 0;
    }

    /**
     * Returns the hash code value for this map. The hash code of a map is
     * defined to be the sum of the hash codes of each entry in the map's
     * entrySet() view. This ensures that m1.equals(m2) implies that
     * m1.hashCode()==m2.hashCode() for any two maps m1 and m2, as required by
     * the general contract of Object.hashCode().
     */
    @Override
    public int hashCode() {
        int sum = 0;
        for (Map.Entry<T, Integer> e : this) {
            if (e == null || e.getValue() == 0) {
                break;
            }
            sum += e.hashCode();
        }
        return sum;
    }

    public void increment(T key, int delta) {
        Integer prev = this.c.put(key, delta);
        if (prev != null) {
            this.c.put(key, prev + delta);
        }
    }

    /**
     * Increments the count of the specified key by 1.
     */
    public void increment(T key) {
        this.increment(key, 1);
    }

    /**
     * Increments the count of each element in the collection by 1.
     */
    public void increment(Collection<T> elements) {
        for (T e : elements) {
            this.increment(e, 1);
        }
    }

    /**
     * Increments the count of each element by some number.
     */
    public void increment(Iterable<Map.Entry<T, Integer>> elements) {
        for (Map.Entry<T, Integer> e : elements) {
            this.increment(e.getKey(), e.getValue());
        }
    }

    /**
     * Decrements the count of the specified key by 1.
     */
    public void decrement(T key) {
        this.increment(key, -1);
    }

    /**
     * Decrements the count of each element in the collection by 1.
     */
    public void decrement(Collection<T> elements) {
        for (T e : elements) {
            this.increment(e, -1);
        }
    }

    /**
     * Decrements the count of each element by some number.
     */
    public void decrement(Iterable<Map.Entry<T, Integer>> elements) {
        for (Map.Entry<T, Integer> e : elements) {
            this.increment(e.getKey(), -e.getValue());
        }
    }

    /**
     * Returns an iterator over <tt>entrySet()</tt>.
     */
    @Override
    public Iterator<Map.Entry<T, Integer>> iterator() {
        return this.entrySet().iterator();
    }

    /**
     * Returns a <tt>SortedSet</tt> of the entries in descending order of
     * frequency.  Entries with the same frequency are returned in an
     * arbitrary order.
     */
    @Override
    public Set<Map.Entry<T, Integer>> entrySet() {
        SortedSet<Map.Entry<T, Integer>> ss = new TreeSet<Map.Entry<T, Integer>>(DESC_FREQ_COMPARATOR);
        ss.addAll(this.c.entrySet());
        return ss;
    }

    /**
     * Returns the entries in descending order of frequency.  Entries with the
     * same frequency are returned in an arbitrary order.
     */
    public Map.Entry<T, Integer>[] mostCommon() {
        return this.mostCommon(this.size());
    }

    /**
     * Returns the <em>n</em> entries with the highest count in descending
     * order of frequency.  Entries with the same frequency are returned in an
     * arbitrary order.
     *
     * @return An array of length <em>n</em>.  If <em>n</em> exceeds the number
     *         of entries that exist, the result is padded with nulls.
     */
    @SuppressWarnings("unchecked")
    public Map.Entry<T, Integer>[] mostCommon(int n) {
        Map.Entry[] top = new Map.Entry[n];
        int i = 0;
        for (Map.Entry<T, Integer> e : this) {
            top[i++] = e;
            if (i == n) break;
        }
        return (Map.Entry<T, Integer>[])top;
    }
}

CounterTest.java

import static org.junit.Assert.*;
import static org.junit.Assume.*;

import org.junit.BeforeClass;
import org.junit.Test;
import org.junit.Ignore;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;

import java.io.*;
import java.net.MalformedURLException;
import java.net.URL;
import java.text.BreakIterator;
import java.util.Arrays;
import java.util.Map;
import java.util.Scanner;

// javac -cp .:junit.jar Counter.java CounterTest.java
// java -cp .:junit.jar:hamcrest-core.jar org.junit.runner.JUnitCore CounterTest

@RunWith(JUnit4.class)
public class CounterTest {
    private static String SHAKESPEARE_CORPUS;

    @BeforeClass
    public static void downloadShakespeare() throws MalformedURLException {
        URL shakespeare = new URL("http://norvig.com/ngrams/shakespeare.txt");
        try (Scanner s = new Scanner(shakespeare.openStream(), "UTF-8")) {
            SHAKESPEARE_CORPUS = s.useDelimiter("\\A").next();
        } catch (IOException e) {
            assertNull(SHAKESPEARE_CORPUS);
        }
    }

    @Test
    public void increment() {
        Counter<String> c = new Counter<String>();
        c.increment("duck");
        assertEquals("One duck", 1, (int)c.get("duck"));
        c.increment("duck");
        c.increment("goose");
        assertEquals("Two ducks", 2, (int)c.get("duck"));
        assertEquals("One goose", 1, (int)c.get("goose"));
        assertEquals("No pheasant", 0, (int)c.get("pheasant"));
    }

    @Test
    public void incrementCollectionRemoveCopy() {
        Counter<String> c = new Counter<String>();
        c.increment(Arrays.asList(new String[] { "duck", "duck", "goose" }));
        assertEquals("Two ducks", 2, (int)c.get("duck"));
        assertEquals("One goose", 1, (int)c.get("goose"));
        assertEquals("No pheasant", 0, (int)c.get("pheasant"));

        Counter<String> cc = new Counter<String>(c);
        c.remove("goose");
        assertEquals("No goose", 0, (int)c.get("goose"));

        assertEquals("Two ducks", 2, (int)cc.get("duck"));
        assertEquals("One goose", 1, (int)cc.get("goose"));
        assertEquals("No pheasant", 0, (int)cc.get("pheasant"));
    }

    @Test
    public void incrementPutSubtractRemove() {
        Counter<String> c = new Counter<String>();
        c.increment("duck");
        assertEquals("One duck", 1, (int)c.get("duck"));
        c.increment("duck", 98);
        assertEquals("99 ducks", 99, (int)c.get("duck"));
        c.put("duck", 200);
        assertEquals("200 ducks", 200, (int)c.get("duck"));
        c.increment("duck", -50);
        assertEquals("150 ducks", 150, (int)c.get("duck"));
        c.remove("duck");
        assertEquals("No duck", 0, (int)c.get("duck"));
    }

    @Test
    public void nullSemantics() {
        Counter<Integer> c = new Counter<Integer>();
        assertFalse("does not contain key null", c.containsKey(null));
        assertFalse("does not contain value 0", c.containsValue(0));

        c.put(null, 0);
        assertEquals("0 nulls", 0, (int)c.get(null));
        assertTrue("contains key null", c.containsKey(null));
        assertTrue("contains value 0", c.containsValue(0));

        c.increment((Integer)null);
        assertEquals("1 null", 1, (int)c.get(null));
        assertTrue("contains key null", c.containsKey(null));
        assertTrue("contains value 1", c.containsValue(1));

        c.decrement((Integer)null);
        assertEquals("no nulls", 0, (int)c.get(null));
        assertTrue("contains key null", c.containsKey(null));
        assertTrue("contains value 0", c.containsValue(0));
        assertFalse("contains no value 1", c.containsValue(1));
    }

    @Test
    public void mostCommon() {
        Counter<String> c = new Counter<String>();
        c.increment(Arrays.asList(new String[] { "duck", "duck", "goose" }));
        Map.Entry<String, Integer>[] common = c.mostCommon();
        assertEquals("2 entries", 2, common.length);
        assertEquals("2 ducks first", "duck", common[0].getKey());
        assertEquals("2 ducks first", 2, (int)common[0].getValue());
        assertEquals("1 goose last", "goose", common[1].getKey());
        assertEquals("1 goose last", 1, (int)common[1].getValue());
    }

    @Test
    public void mostCommonTooMany() {
        Counter<String> c = new Counter<String>();
        c.increment("duck");
        Map.Entry<String, Integer>[] common = c.mostCommon(3);
        assertEquals("3 entries", 3, common.length);
        assertEquals("1 duck first", "duck", common[0].getKey());
        assertNull("null", common[1]);
        assertNull("null", common[2]);
    }

    @Test
    public void emptinessAndSizeSemantics() {
        Counter<Integer> c = new Counter<Integer>();
        assertTrue("new counter is empty", c.isEmpty());
        assertEquals("new counter has 0 entries", 0, c.size());

        c.put(0, 1);
        assertFalse("entry makes it non-empty", c.isEmpty());
        assertEquals("(0, 1) has 1 entry", 1, c.size());

        c.decrement(0);
        assertFalse("entry with zero count makes it non-empty", c.isEmpty());
        assertEquals("(0, 0) has 1 entry", 1, c.size());

        c.remove(0);
        assertTrue("removed sole entry makes it empty", c.isEmpty());
        assertEquals("removed sole entry has 0 entries", 0, c.size());

        c.increment((Integer)null);
        assertFalse("null entry makes it non-empty", c.isEmpty());

        c.clear();
        assertTrue("clearing makes it empty", c.isEmpty());
    }

    @Test
    public void equality() {
        Counter<String> a = new Counter<String>();
        Counter<String> b = new Counter<String>();
        assertEquals("nothing == nothing", a, b);

        a.increment("duck");
        assertNotEquals("1 duck != nothing", a, b);

        a.decrement("duck");
        a.put(null, 0);
        assertEquals("0 duck + 0 null == nothing", a, b);
        assertEquals("nothing == 0 duck + 0 null", b, a);

        b.put("goose", 2);
        assertNotEquals("0 duck != 2 geese", a, b);

        a.increment("goose", 2);
        assertEquals("2 geese + 0 duck == 2 geese", a, b);
        assertEquals("2 geese == 2 geese + 0 duck", b, a);
    }

    @Test(timeout=500)
    public void performance() throws IOException {
        Counter<String> c = new Counter<String>();

        assumeTrue(null != SHAKESPEARE_CORPUS);
        StreamTokenizer tok = new StreamTokenizer(new StringReader(SHAKESPEARE_CORPUS));
        tok.ordinaryChar('\'');
        tok.ordinaryChar('"');
        int type;

        String word = "Ophelia";
        int KNOWN_COUNT = 19, myCount = 0;

        while (StreamTokenizer.TT_EOF != (type = tok.nextToken())) {
            if (StreamTokenizer.TT_WORD == type) {
                c.increment(tok.sval);
                if (word.equals(tok.sval)) {
                    myCount++;
                }
            }
        }
        assumeTrue(KNOWN_COUNT == myCount);
        assertEquals(word, myCount, (int)c.get(word));
    }
}

Please critique both the Counter and its unit tests in general.

Some concerns I have include:

1. Is there a common Java library that serves a similar purpose, or am I reinventing-the-wheel?
2. Are the semantics for null keys and zero counts reasonable?
3. Is it useful to implement the Map<T, Integer> and Iterable interfaces? Or does that unnecessarily complicate things?
4. I wrote many increment() and decrement() methods. Do they make the class convenient to use, or are they too redundant?
5. What do you think of the method signatures for mostCommon() and mostCommon(int)? Is there too much redundancy with entrySet() and iterator()?
6. I had to use @SuppressWarnings("unchecked") in three places. How can I avoid those warnings in the first place?
7. I increment a count using two calls to put() of a HashMap. Is there a more efficient way?
8. To support entrySet() and mostCommon(), I build a SortedSet from scratch. Is there a better data structure I could have used that could support entrySet() and mostCommon() efficiently?

Answer 1

Is there a common Java library that serves a similar purpose, or am I reinventing-the-wheel?

As far as I know the JRE doesn't offer this out of the box.

Are the semantics for null keys and zero counts reasonable?

Would it be typical to be counting nulls? I guess it's nice that it's possible, even though it opens the possibility for exceptions. Personally I'd disallow it.

What is reasonable is that getting a count for keys that are not present, simply returns 0.

Is it useful to implement the Map<T, Integer> and Iterable interfaces? Or does that unnecessarily complicate things?

Implementing the Map interface is unnecessary, it requires a lot of code that adds nothing to the intended responsibility of this class. In fact you do not fully abide to the Map interface contract. Honoring the Single Responsibility Principle mandates dropping this.

Implementing the Iterable interface is way more useful, as it exposes the results in a standard way.

I wrote many increment() and decrement() methods. Do they make the class convenient to use, or are they too redundant?

I would extract an interface from this class that captures its API, and you can make alternative implementations later on as needed.

public interface Counter<T> extends Iterable<Map.Entry<T, Integer>> {
    void increment(T key);

    void decrement(T key);

    int getCount(T key);

    Set<T> getKeys();
}

I would even replace Map.Entry<T, Integer> by a Counter specific interface.

Try to resist the urge to add convenience methods, You can always use the Decorator pattern to add candy as needed. In the mean time focus on making a great core implementation.

What do you think of the method signatures for mostCommon() and mostCommon(int)? Is there too much redundancy with entrySet() and iterator()?

These are superfluous, again decorators are the way to go in this case.

I had to use @SuppressWarnings("unchecked") in three places. How can I avoid those warnings in the first place?

First occurrence is :

CounterImpl other = (CounterImpl)o;
Map.Entry<T, Integer>[] a = this.mostCommon();
@SuppressWarnings("unchecked")
Map.Entry<?, Integer>[] b = other.mostCommon();

You declare the other variable without type parameter. Rule 1 to avoiding unchecked warnings is to specify the type parameter on classes that have one. After all, the only reason you can omit them, is that this was needed for backwards compatibility when generics were introduced.

CounterImpl<?> other = (CounterImpl)o;
Map.Entry<T, Integer>[] a = this.mostCommon();
Map.Entry<?, Integer>[] b = other.mostCommon();

A likewise case happens in mostCommon()

Next case :

} else if (bKey instanceof Comparable) {
    @SuppressWarnings("unchecked")
    Comparable<T> bKeyCmp = (Comparable<T>)bKey;

Reflection code and generics is bound to get you into trouble with unchecked warnings. In fact this cast actually isn't safe when T implements Comparable<S> where S is a supertype of T.

I increment a count using two calls to put() of a HashMap. Is there a more efficient way?

Yes there is. Instead of using Integer as the value in your Map, use a mutable count representation. You can easily write one yourself, or use AtomicInteger (although you may not need the thread safety). Then define :

private final Map<T, AtomicInteger> c = new HashMap<T, AtomicInteger>();

Now you'll only need to do a put if the key isn't in the Map yet :

public void increment(T key, int delta) {
    Integer prev = this.c.put(key, delta);
    if (!c.containsKey(key)) {
        c.put(key, new AtomicInteger());
    }
    c.get(key).addAndGet(delta);
}

In java 8 it becomes even simpler using java.util.Map#computeIfAbsent

c.computeIfAbsent(key, k -> new AtomicInteger()).addAndGet(delta);

To support entrySet() and mostCommon(), I build a SortedSet from scratch. Is there a better data structure I could have used that could support entrySet() and mostCommon() efficiently?

Why not use a SortedMap internally?

private final Map<T, Integer> c = new TreeMap<T, Integer>(DESC_FREQ_COMPARATOR);

this way c.entrySet() will return a set of which the iterator will return the keys in order. Although this Set isn't actually a SortedSet<T> it probably fulfills what you need anyway.

---

General remarks :

Counter

• avoid abbreviations as variable names.

CounterTest

• write seperate tests per assertion : e.g. equality() can be split into 7 different tests. You'll find that you won't need the String argument in your assertions any more.
• do performance tests in a different class than your unit tests. Unit tests should be as lightweight as possible.

---

Finally consider how I would approach this (JDK8)

EDIT : updated this code to use LongAdder instead of AtomicInteger, as LongAdder performs even better than AtomicInteger for this case.

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.LongAdder;
import java.util.stream.Collectors;

public interface Counter<T> extends Iterable<Counter.Count<T>> {
    void increment(T key);

    void decrement(T key);

    int getCount(T key);

    Set<T> getKeys();

    interface Count<T> {
        T getKey();

        int getCount();
    }
}

class SimpleCounter<T> implements Counter<T> {
    public static final LongAdder DEFAULT_VALUE = new LongAdder();

    private final Map<T, LongAdder> counts = new HashMap<>();

    @Override
    public void increment(T key) {
        counts.computeIfAbsent(key, k -> new LongAdder()).increment();
    }

    @Override
    public void decrement(T key) {
        counts.computeIfAbsent(key, k -> new LongAdder()).decrement();
    }

    @Override
    public int getCount(T key) {
        return counts.getOrDefault(key, DEFAULT_VALUE).intValue();
    }

    @Override
    public Set<T> getKeys() {
        return counts.keySet();
    }

    @Override
    public Iterator<Count<T>> iterator() {
        return counts.entrySet().stream().map(e -> new SimpleCount<T>(e)).collect(Collectors.<Count<T>>toSet()).iterator();
    }

    private static class SimpleCount<E> implements Count<E> {
        private final Map.Entry<E, LongAdder> entry;

        SimpleCount(Map.Entry<E, LongAdder> entry) {
            this.entry = entry;
        }

        @Override
        public E getKey() {
            return entry.getKey();
        }

        @Override
        public int getCount() {
            return entry.getValue().intValue();
        }
    }
}

Answer 2

I don't really have time to read through the whole code and the existing reviews now but as far I see no-one mentioned Guava's Multiset and its AtomicLongMap yet.

I've been able to change Counter to HashMultiset in the test methods with very few issues while the bar remained green:

• Multiset does not store keys (elements) with zero occurrences. (AtomicLongMap might be a better choice if it's a requirement.)
• mostCommon is not supported by Multiset out of box but Multisets supports it. (You might also need Iterables.limit here.)
• Minor method name changes.

Answer 3

containsValue() can return true when you pass in a Double that isn't a whole number. The implementation should be equivalent to the following for any value.

public boolean containsValue(Object integralNumber) {
  for (Integer i : values()) {
    if (i.equals(integralNumber) {
      return true;
    }
  }
  return false;
}

---

Your documentation matches that of the Map interface, not what the Counter is actually doing. Example: get() never returns null.

---

Is there a reason mostCommon() returns an array instead of a List? Everything else lines up with the collections library, so this seems out of place.

---

Your tests are doing edit-check-repeat. This can hide information about what the bug is. When the first assert in equality() fails, you only know that two empty counters aren't equivalent. However, if you break it up into 5 different tests, you might find that some of them pass, but not all. This will save you time when you start to debug the code.

---

Do you really need to access the internet to run your tests? If the internet connection drops out at just the right time, your tests fail even if there is nothing wrong with your code.

---

Your questions:

1. I don't know of one.
2. For the most part, the use of null seems to be minimized to interacting with other api's that force you to, not you using it yourself. This is fine, but see question 5.
3. I do think that implementing Map<T, Integer> makes some things unclean. There are cases where you have to take Object as an argument when it should be T or just an int and it adds methods to deal with what you would want the api to be.
4. Adding on to question 3, I would just have increment() and decrement().
5. Having nulls in the array seems wrong. I would have the method return a List of at most n elements.
6. This is just something you have to deal with when casting to a generic class. ¹
7. This is what profilers are for. You can try different implementations and see witch is faster or if it makes a difference.
8. It seems fine, but this is another case where a profiler can answer questions.

---

Last note: equals() and hashCode() seem overly complicated, but I didn't look deeply to see if there are any real issues.

¹ bowmore's answer is better in dealing with this question.

Answer 4

Your concerns

1. Re-inventing the wheel: I am not familiar with anything that does this functionality, but my knowledge of Apache Commons and Guava is a little limited .... @palacsint?

2. null-keys looks OK. You sort null first, which is neither here nor there, but you may want to document that. As for the int values... this code has me confused:

   /**
    * Returns the value to which the specified key is mapped, or null if this
    * map contains no mapping for the key.
    */
   @Override
   public Integer get(Object key) {
       Integer i = this.c.get(key);
       return i == null ? 0 : i.intValue();
   }
   

   The Javadoc says it returns null if the key is not mapped, but it actually returns 0. Further, if the value is mapped, you extract the int value, then autobox it back to Integer.

   Similarly, in the put() method you return 0 instead of null for a not-previously-mapped value

3. Implementing Map<...> - is it useful? I will dedicate a whole section to that.... ;-)

4. I have no particular concern about the number of increment/decrement methods. They are mostly convenient in conceptual cases. Some may argue YAGNI... but I am not in that camp... there is nothing worse than needing a convenient tool and discovering that it just isn't there.

5. Interesting question.... my initial reaction was that I do not like those methods (mostCommon* ). I figure it would be easy enough to iterate and break.

6. Unchecked warnings - actually, they are raw-type warnings too. This is related to the use of the Map<...> interface.

7. Yes. there are better ways.... not to use Map....

8. the big question.... I am sure there is, but not sure how to describe it until I do it ....

Using Map class

My big beef with the java.util.* collection interfaces is how complicated they are to implement (not to use).

Your code is full of bugs in this regard.

Consider this documentation for Map.entrySet():

Returns a Set view of the mappings contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own remove operation, or through the setValue operation on a map entry returned by the iterator) the results of the iteration are undefined. The set supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Set.remove, removeAll, retainAll and clear operations. It does not support the add or addAll operations.

Because you implement the entrySet as a distinct data TreeMap's entrySet(), you fail pretty much all of those requirements....

It is my experience that implementing Collection interfaces is hard (and I have some successful implementations that prove it). It gets especially hard when you want to do things 'right' with respect to things like ConcurrentModificationException.

My recommendation is for you not to expose it at all. That way you define your own simpler specification.

Bugs

There are a number of bugs I can see.

1. The constructor public Counter(Map<T, Integer> counter) {...} opens you up to a lot of problems:

   • people can supply null values for the Integer values in a HashMap, for example. This will cause your code to throw null-pointer exceptions in your Comparator.
   • people using the Counter.get(key) method will get a 0 value for a null-mapped Integer, but if they get the Map.Entry instance for the same key, the getValue() will be null.
   • all the increment/decrement methods will throw null-pointer-exception when un-autoboxing.

2. The Comparator has a bug on the sorting if the values are extreme:

          if (0 != (diff = bValue - aValue)) {
              return diff;
   

   If the aValue has been incremented to say +1000 and the bValue has been decremented to -2000 then we would want to sort the aValue first (return a negative number) because it has the larger count. The function -2000 - (+1000) will return -3000, which is right. But, if aValue was incremented to say +1,000,000,000 and the bValue was decremented to -2,000,000,000 then the result will underflow the int value, and will end up as a positive result.... leading to incorrect sorting.

   The right way to do this is with plain-jane comparisons:

   if (aValue != bValue) {
       return aValue < bValue ? 1 : -1;
   

Conclusion

The concept is good, but exposing the Map is a net-negative. Too many things to go wrong.

It also makes it almost impossible to have a Concurrent version later.

I would implement it with a custom interface that does not expose the internal classes at all... leave the interface as a simple (primitive based):

public int getCount(T key) { ... }

public int incrementAndGet(T key) { .... }  // similar to AtomicInteger
public int getAndIncrement(T key) { .... }  // similar to AtomicInteger

decrement options too

public Iterator<T> iterator() { ... } // simple iterator of keys in decreasing count order.

equals and hashCode.

That's it....