1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

use std::{
    collections::{btree_map, hash_map, BTreeMap, HashMap},
    hash::Hash,
};

pub trait CountMap<K>: Default + Sized {
    fn add(&mut self, k: K, count: isize);
    fn empty() -> Self {
        Self::default()
    }
    fn singleton(k: K, count: isize) -> Self {
        let mut result: Self = Self::empty();
        result.add(k, count);
        result
    }
}

pub trait Observable {
    fn is_empty(&self) -> bool;
}

impl<K1: Eq + Hash, K2, M: CountMap<K2> + Observable> CountMap<(K1, K2)> for HashMap<K1, M> {
    fn add(&mut self, k: (K1, K2), count: isize) {
        if count == 0 {
            return;
        }
        let e = self.entry(k.0);
        match e {
            hash_map::Entry::Vacant(v) => {
                v.insert(CountMap::singleton(k.1, count));
            }
            hash_map::Entry::Occupied(mut o) => {
                let m = o.get_mut();
                m.add(k.1, count);
                if m.is_empty() {
                    o.remove();
                }
            }
        }
    }
}

impl<K, V> Observable for HashMap<K, V> {
    fn is_empty(&self) -> bool {
        HashMap::is_empty(self)
    }
}

impl<K1: Eq + Ord, K2, M: CountMap<K2> + Observable> CountMap<(K1, K2)> for BTreeMap<K1, M> {
    fn add(&mut self, k: (K1, K2), count: isize) {
        if count == 0 {
            return;
        }
        let e = self.entry(k.0);
        match e {
            btree_map::Entry::Vacant(v) => {
                v.insert(CountMap::singleton(k.1, count));
            }
            btree_map::Entry::Occupied(mut o) => {
                let m = o.get_mut();
                m.add(k.1, count);
                if m.is_empty() {
                    o.remove();
                }
            }
        }
    }
}

impl<K, V> Observable for BTreeMap<K, V> {
    fn is_empty(&self) -> bool {
        BTreeMap::is_empty(self)
    }
}

impl CountMap<()> for isize {
    fn add(&mut self, (): (), count: isize) {
        *self += count
    }
}

impl Observable for isize {
    fn is_empty(&self) -> bool {
        *self == 0
    }
}

impl<K: Eq + Hash> CountMap<K> for HashMap<K, isize> {
    fn add(&mut self, k: K, count: isize) {
        CountMap::<(K, ())>::add(self, (k, ()), count)
    }
}

impl<K: Ord> CountMap<K> for BTreeMap<K, isize> {
    fn add(&mut self, k: K, count: isize) {
        CountMap::<(K, ())>::add(self, (k, ()), count)
    }
}