twitter/algebird — pull request #354 by miguno (2014-10-16 10:37:14+00:00)
Title: GH-345: Parameterize CMS to CMS[K] and decouple counting/querying from heavy hitters

_See the discussion in GH-345 for details on this pull request._

Note: This PR contains a "clean" fix plus regression tests for GH-353, i.e. the bug where heavy hitters are not correctly computed in CMS.

**High-level summary of this pull request**

* Parameterize `CMS` with a type `K` to decouple the item identifier type from hardcoded `Long`.
* Two traits `CMSCounting[K, C[_]]` and `CMSHeavyHitters[K]
* Three implementations of these traits:
* `CMS[K]`, which can only counting and estimate.
* `TopCMS[K]`, which can count, estimate, and track heavy hitters. The logic to compute heavy hitters is pluggable, see below.
* A trait `HeavyHittersLogic` (for the lack of a better name) that controls how a CMS that implements `CMSHeavyHitters` tracks heavy hitters.
* Two implementations of this trait: `TopPctLogic`, `TopNLogic`.
* A lot of new/improved CMS documentation.
* An updated spec/test suite, including regression tests for GH-353.
* Includes tests for `K in {Short, Int, Long, BigInt}`.
* Includes a "negative test case" that documents the `++` order bias of top-N CMS.
* A Caliper benchmark for CMS. Also adds a README to algebird-caliper.

Please take a look at the code and let me know which further changes you'd like me to do so that this PR and thus the improved CMS implementation can be merged.

And many thanks for all the help and support so far!
Michael

PS: For the sake of this PR I decided not to squash individual commits into a single, big commit so it's easier to back out of changes you may not like etc. I can of course squash the commits if needed once the PR code is approved.