// Count-Min Sketch frequency estimator.
//
// Reference: Cormode & Muthukrishnan, "An improved data stream summary:
// The Count-Min Sketch and its applications", J. Algorithms, 2005.

///|
/// A Count-Min Sketch frequency estimator.
pub struct CountMinSketch {
  priv table : Array[Array[Int]]
  priv width : Int
  priv depth : Int
} derive(Show)

///|
/// Creates a new `CountMinSketch`.
///
/// * `width` — number of counters per row (default 1000).
/// * `depth` — number of hash functions / rows (default 5).
///
/// Returns `Err(InvalidDimension)` when `width` or `depth` is not positive.
pub fn CountMinSketch::new(
  width? : Int = 1000,
  depth? : Int = 5,
) -> CountMinSketch raise SketchError {
  if width <= 0 || depth <= 0 {
    raise InvalidDimension
  }
  let table : Array[Array[Int]] = Array::new()
  for i = 0; i < depth; i = i + 1 {
    table.push(Array::make(width, 0))
  }
  { table, width, depth }
}

///|
/// Maps a hash to a column index in [0, width).
/// `lsr32(hash, 1)` performs an unsigned right shift by 1, clearing the sign
/// bit so the result is always non-negative. `% width` is therefore safe.
fn cms_col(hash : Int, width : Int) -> Int {
  lsr32(hash, 1) % width
}

///|
/// Increments the frequency of `value` by `count` (default 1).
pub fn CountMinSketch::add(
  self : CountMinSketch,
  value : String,
  count? : Int = 1,
) -> Unit {
  for i in 0.. Int {
  let mut result = self.table[0][cms_col(murmurhash3(value, seed=0), self.width)]
  for i in 1.. CountMinSketch raise SketchError {
  if self.width != other.width || self.depth != other.depth {
    raise PrecisionMismatch
  }
  // width and depth are already validated, so this cannot fail.
  let result = try! CountMinSketch::new(width=self.width, depth=self.depth)
  for i in 0..