kmv

defmodule KMV do
  @moduledoc """
  K-minimum value sketch to estimate cardinality of sets.

  KMV can also be used to perform set operations:
    - union
    - intersection
    - difference

  Implementation is based on the paper: "On synopses for distinct-value
  estimation under multiset operations" by Beyer et al, 2007.
  """

  # KMV struct
  defstruct heap: nil, set: nil, max_size: nil, size: nil
  @type t :: %KMV{heap: Heap.t, set: Set.t, max_size: integer, size: integer}

  #Hash a value and returns value between [0, 1].
  @spec hash(any) :: float
  defp hash(v) do
    Murmur.hash_x64_128(v, 42) / :math.pow(2,128)
  end

  @doc """
  Create a new KMV of max size `k`.

  Increasing the size of `k` increases the accuracy.

  Returns: `KMV`

  ## Parameters

    - k: Max size of the KMV. Must be greater than 0.

  """
  @spec new() :: KMV.t
  @spec new(integer) :: KMV.t
  def new(k \\ 1024) when k > 0 do
    %KMV{heap: Heap.max, set: MapSet.new, max_size: k, size: 0}
  end

  @doc """
  Insert a value into a `KMV`.

  Returns: `KMV`

  ## Parameters

    - kmv: `KMV` sketch.

  ## Example

  Create a `KMV` of size 3, insert 6 elements, and estimate cardinality.

      iex> a = KMV.new(3)
      iex> a = KMV.insert(a, "test")
      iex> a = KMV.insert(a, 1)
      iex> a = KMV.insert(a, 2)
      iex> a = KMV.insert(a, 3)
      iex> a = KMV.insert(a, :thisAlsoWorks)
      iex> a = KMV.insert(a, [:a, :list, :becomes, :a, :single, :value])
      iex> KMV.cardinality(a) |> round
      7
  """
  @spec insert(KMV.t, any) :: KMV.t
  def insert(kmv, value)
  def insert(s = %KMV{heap: heap, set: set, max_size: max_size, size: size}, value) when size < max_size do
    # Generate the hash for the input
    value_hash = hash(value)

    if !MapSet.member?(set, value_hash) do
      %KMV{heap: Heap.push(heap, value_hash),
       set: MapSet.put(set, value_hash),
       max_size: max_size,
       size: size + 1}
    else
      s
    end
  end
  def insert(s = %KMV{heap: heap, set: set, max_size: max_size, size: size}, value) do
    # Generate the hash for the input
    value_hash = hash(value)

    if !MapSet.member?(set, value_hash) && value_hash < Heap.root(heap) do
      set = MapSet.delete(set, Heap.root(heap))
      heap = Heap.pop(heap)

      %KMV{heap: Heap.push(heap, value_hash),
       set: MapSet.put(set, value_hash),
       max_size: max_size,
       size: size}
    else
      s
    end
  end

  @doc """
  Estimate the cardinality of the set in the KMV.

  Returns: `float`

  ## Parameters

    - kmv: `KMV`

  ## Example

  Insert 10,000 unique values into a new KMV of size 500, and estimate its
  cardinality which should be around 10,000.

      iex> 1..10_000 |> Enum.into(KMV.new(500)) |> KMV.cardinality |> round
      9_693
  """
  @spec cardinality(KMV.t) :: float
  def cardinality(kmv)
  def cardinality(%KMV{heap: _heap, set: _set, max_size: max_size, size: size}) when size < max_size do
    # Have inserted fewer unique items than max_size, can return exact count
    size
  end
  def cardinality(%KMV{heap: heap, set: _set, max_size: _max_size, size: size}) do
    #
    (size - 1) / Heap.root(heap)
  end

  @doc """
  Union a list of `KMV` sketches.

  Returns: `KMV`

  ## Parameters

    - kmv_list: A list of `KMV`

  ## Example

  The union the three `KMV` sketches around 12,000.

      iex> a = 10_000..15_000 |> Enum.into(KMV.new(500))
      iex> b = 13_000..18_000 |> Enum.into(KMV.new(500))
      iex> c = 15_000..22_000 |> Enum.into(KMV.new(500))
      iex> KMV.union([a, b, c]) |> KMV.cardinality |> round
      12_840
  """
  @spec union(nonempty_list(KMV.t)) :: KMV.t
  def union(kmv_list) when length(kmv_list) > 1 do
    # Find the min size of the KMV list
    min_size = Enum.min(for %KMV{size: size} <- kmv_list, do: size)

    data = (for %KMV{set: set} <- kmv_list, do: set)
            |> Enum.reduce(&(MapSet.union(&1, &2)))
            |> MapSet.to_list
            |> Enum.sort
            |> Enum.take(min_size)

    heap = data |> Enum.into(Heap.max)

    %KMV{heap: heap,
     set: MapSet.new(data),
     max_size: min_size,
     size: min_size}
  end

  @doc """
  Intersection of two `KMV` sketches.

  Returns: `float`

  ## Parameters

    - kmv_list: A list of `KMV`

  ## Example

  The intersection of the three `KMV` sketches should be around 25,000.

      iex> a =      0..100_000 |> Enum.into(KMV.new(500))
      iex> b = 50_000..150_000 |> Enum.into(KMV.new(500))
      iex> c = 25_000..75_000 |> Enum.into(KMV.new(500))
      iex> KMV.intersection([a, b, c]) |> round
      25_074
  """
  @spec intersection(nonempty_list(KMV.t)) :: float
  def intersection(kmv_list) when length(kmv_list) > 1 do
    # Find the min size of the KMV list
    size_list = for %KMV{size: size} <- kmv_list, do: size
    min_size = Enum.min(size_list)
    total_union = union(kmv_list)
    cardinality_of_union = cardinality total_union

    # Must use the union in the intersection
    kmv_list = [total_union | kmv_list]

    number_of_intersections = (for %KMV{set: set} <- kmv_list, do: set)
                              |> Enum.reduce(&(MapSet.intersection(&1, &2)))
                              |> MapSet.size

    (number_of_intersections / min_size) * cardinality_of_union
  end
end