#!/usr/bin/env python3
# Source: t3-probability-information.html
import numpy as np


class CountMin:
    """Count-min sketch. Nonnegative counters never undercount before overflow. Toy hashes do not prove the textbook error bound."""

    def __init__(self, eps: float = 0.001, delta: float = 0.01, seed: int = 0):
        if not 0 < eps < 1 or not 0 < delta < 1:
            raise ValueError("Use 0 < eps, delta < 1")
        self.w = int(np.ceil(np.e / eps))         # width
        self.d = int(np.ceil(np.log(1 / delta)))  # depth (number of hash rows)
        self.table = np.zeros((self.d, self.w), dtype=np.int64)
        rng = np.random.default_rng(seed)
        self.salts = rng.integers(1, 2**31, size=self.d)

    def _cols(self, key: int) -> np.ndarray:
        if not isinstance(key, (int, np.integer)) or not 0 <= key < 2_147_483_647:
            raise ValueError("Toy hash keys must be integers within [0, 2147483647)")
        return (key * self.salts + 12345) % 2_147_483_647 % self.w

    def add(self, key: int, count: int = 1) -> None:
        if not isinstance(count, (int, np.integer)) or not 0 <= count <= np.iinfo(np.int64).max:
            raise ValueError("Count must be a nonnegative int64 value")
        cells = (np.arange(self.d), self._cols(key))
        if (self.table[cells] > np.iinfo(np.int64).max - count).any():
            raise OverflowError("Sketch counter would overflow")
        self.table[cells] += count

    def query(self, key: int) -> int:
        return int(self.table[np.arange(self.d), self._cols(key)].min())


rng = np.random.default_rng(0)
stream = rng.zipf(1.3, size=200_000)
stream = stream[stream < 10**6]
cm = CountMin()
for k in stream:
    cm.add(int(k))
true = np.bincount(stream)
for k in [1, 2, 10, 500]:
    print(f"key {k:>4}: true {true[k]:>6}  sketch {cm.query(k):>6}")
print(f"memory {cm.d} x {cm.w} counters, textbook reference eps*N (not a proven bound here) = {0.001 * len(stream):.0f}")
# key    1: true  50971  sketch  50972
# key    2: true  20577  sketch  20581
# key   10: true   2556  sketch   2561
# key  500: true     21  sketch     24
# memory 5 x 2719 counters, textbook reference eps*N (not a proven bound here) = 197
