## counter

Simple package to count generic iterables

### 19 releases

 0.5.7 Oct 12, 2022 Jul 16, 2022 May 5, 2022 Feb 7, 2022 Jan 4, 2017

#46 in FFI

Used in 51 crates (14 directly)

67KB
814 lines

# counter

Counter counts recurrent elements of iterables. It is based on the Python implementation.

The struct `Counter` is the entry-point type for this module.

## Math Underpinnings

Mathematically, a `Counter` implements a hash-based version of a multiset, or bag. This is simply an extension of the notion of a set to the idea that we care not only about whether an entity exists within the set, but the number of occurrences within the set. Normal set operations such as intersection, union, etc. are of course still supported.

## Examples

### Just count an iterable

``````use counter::Counter;
let char_counts = "barefoot".chars().collect::<Counter<_>>();
let counts_counts = char_counts.values().collect::<Counter<_>>();
``````

### Update a count

``````let mut counts = "aaa".chars().collect::<Counter<_>>();
counts[&'a'] += 1;
counts[&'b'] += 1;
``````
``````let mut counts = "able babble table babble rabble table able fable scrabble"
.split_whitespace().collect::<Counter<_>>();
// add or subtract an iterable of the same type
counts += "cain and abel fable table cable".split_whitespace();
// or add or subtract from another Counter of the same type
let other_counts = "scrabble cabbie fable babble"
.split_whitespace().collect::<Counter<_>>();
let difference = counts - other_counts;
``````

Extend a `Counter` with another `Counter`:

``````let mut counter = "abbccc".chars().collect::<Counter<_>>();
let another = "bccddd".chars().collect::<Counter<_>>();
counter.extend(&another);
let expect = [('a', 1), ('b', 3), ('c', 5), ('d', 3)].iter()
.cloned().collect::<HashMap<_, _>>();
assert_eq!(counter.into_map(), expect);
``````

### Get items with keys

``````let counts = "aaa".chars().collect::<Counter<_>>();
assert_eq!(counts[&'a'], 3);
assert_eq!(counts[&'b'], 0);
``````

### Get the most common items

`most_common_ordered()` uses the natural ordering of keys which are `Ord`.

``````let by_common = "eaddbbccc".chars().collect::<Counter<_>>().most_common_ordered();
let expected = vec![('c', 3), ('b', 2), ('d', 2), ('a', 1), ('e', 1)];
assert!(by_common == expected);
``````

`k_most_common_ordered()` takes an argument `k` of type `usize` and returns the top `k` most common items. This is functionally equivalent to calling `most_common_ordered()` and then truncating the result to length `k`. However, if `k` is smaller than the length of the counter then `k_most_common_ordered()` can be more efficient, often much more so.

``````let by_common = "eaddbbccc".chars().collect::<Counter<_>>().k_most_common_ordered(2);
let expected = vec![('c', 3), ('b', 2)];
assert!(by_common == expected);
``````

### Get the most common items using your own ordering

For example, here we break ties reverse alphabetically.

``````let counter = "eaddbbccc".chars().collect::<Counter<_>>();
let by_common = counter.most_common_tiebreaker(|&a, &b| b.cmp(&a));
let expected = vec![('c', 3), ('d', 2), ('b', 2), ('e', 1), ('a', 1)];
assert!(by_common == expected);
``````

### Test counters against another

Counters are multi-sets and so can be sub- or supersets of each other.

A counter is a subset of another if for all its elements, the other counter has an equal or higher count. Test for this with `is_subset()`:

``````let counter = "aaabb".chars().collect::<Counter<_>>();
let superset = "aaabbbc".chars().collect::<Counter<_>>();
let not_a_superset = "aaae".chars().collect::<Counter<_>>();
assert!(counter.is_subset(&superset));
assert!(!counter.is_subset(&not_a_superset));
``````

Testing for a superset is the inverse, `is_superset()` is true if the counter can contain another counter in its entirety:

``````let counter = "aaabbbc".chars().collect::<Counter<_>>();
let subset = "aabbb".chars().collect::<Counter<_>>();
let not_a_subset = "aaae".chars().collect::<Counter<_>>();
assert!(counter.is_superset(&subset));
assert!(!counter.is_superset(&not_a_subset));
``````

These relationships continue to work when using a signed integer type for the counter: all values in the subset must be equal or lower to the values in the superset. Negative values are interpreted as 'missing' those values, and the subset would need to miss those same elements, or be short more, to still be a subset:

``````let mut subset = "aaabb".chars().collect::<Counter<_, i8>>();
subset.insert('e', -2);  // short 2 'e's
subset.insert('f', -1);  // and 1 'f'
let mut superset = "aaaabbb".chars().collect::<Counter<_, i8>>();
superset.insert('e', -1);  // short 1 'e'
assert!(subset.is_subset(&superset));
assert!(superset.is_superset(&subset));
``````

### Counter intersection and union

You can intersect two counters, giving you the minimal counts of their combined elements using the `&` bitwise and operator, and produce their union with the maximum counts using `|` bitwise or:

``````let a = "aaabb".chars().collect::<Counter<_>>();
let b = "aabbbbe".chars().collect::<Counter<_>>();

let intersection = a & b;
let expected_intersection = "aabb".chars().collect::<Counter<_>>();
assert_eq!(intersection, expected_intersection);

let c = "aaabb".chars().collect::<Counter<_>>();
let d = "aabbbbe".chars().collect::<Counter<_>>();

let union = c | d;
let expected_union = "aaabbbbe".chars().collect::<Counter<_>>();
assert_eq!(union, expected_union)
``````

The in-place `&=` and `|=` operations are also supported.

### Treat it like a `HashMap`

`Counter<T, N>` implements `Deref``<Target=HashMap<T, N>>` and `DerefMut``<Target=HashMap<T, N>>`, which means that you can perform any operations on it which are valid for a `HashMap`.

``````let mut counter = "aa-bb-cc".chars().collect::<Counter<_>>();
counter.remove(&'-');
assert!(counter == "aabbcc".chars().collect::<Counter<_>>());
``````

Note that `Counter<T, N>` itself implements `Index`. `Counter::index` returns a reference to a `Zero::zero` value for missing keys.

``````let counter = "aaa".chars().collect::<Counter<_>>();
assert_eq!(counter[&'b'], 0);
// panics
// assert_eq!((*counter)[&'b'], 0);
``````

### Count any iterable which is `Hash + Eq`

You can't use the `most_common*` functions unless `T` is also `Clone`, but simple counting works fine on a minimal data type.

``````#[derive(Debug, Hash, PartialEq, Eq)]
struct Inty {
i: usize,
}

impl Inty {
pub fn new(i: usize) -> Inty {
Inty { i: i }
}
}

// <https://en.wikipedia.org/wiki/867-5309/Jenny>
let intys = vec![
Inty::new(8),
Inty::new(0),
Inty::new(0),
Inty::new(8),
Inty::new(6),
Inty::new(7),
Inty::new(5),
Inty::new(3),
Inty::new(0),
Inty::new(9),
];

let inty_counts = intys.iter().collect::<Counter<_>>();
println!("{:?}", inty_counts);
// {Inty { i: 8 }: 2, Inty { i: 0 }: 3, Inty { i: 9 }: 1, Inty { i: 3 }: 1,
//  Inty { i: 7 }: 1, Inty { i: 6 }: 1, Inty { i: 5 }: 1}
assert!(inty_counts.get(&Inty { i: 8 }) == Some(&2));
assert!(inty_counts.get(&Inty { i: 0 }) == Some(&3));
assert!(inty_counts.get(&Inty { i: 6 }) == Some(&1));
``````

### Use your own type for the count

Sometimes `usize` just isn't enough. If you find yourself overflowing your machine's native size, you can use your own type. Here, we use an `i8`, but you can use most numeric types, including bignums, as necessary.

``````let counter: Counter<_, i8> = "abbccc".chars().collect();
let expected: HashMap<char, i8> = [('a', 1), ('b', 2), ('c', 3)].iter().cloned().collect();
assert!(counter.into_map() == expected);
``````