hypex

defmodule Hypex do
  @moduledoc """
  This module provides an Elixir implementation of HyperLogLog as described within
  http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf. Various implementations
  are provided in order to account for performance and memory optimizations.

  A Hypex instance is simply a three-element Tuple, which provides a slight speed
  improvement over using a struct (roughly 10% at last benchmark). This tuple
  should only ever be constructed via `Hypex.new/2` otherwise you run the risk of
  pattern matching errors throughout modification.
  """
  import Record

  # alias some internals
  alias Hypex.Utilities

  # record structure
  defrecord :hypex,
    mod: nil,
    width: nil,
    register: nil

  @typedoc """
  A Hypex interface structure
  """
  @type t ::
          record(:hypex,
            mod: term(),
            width: number(),
            register: any()
          )

  @doc """
  Create a new Hypex using a width when `16 >= width >= 4`.

  The type of register is determined by the module backing the Hypex instance.
  We normalize to ensure we have a valid module and then initialize the module
  with the widths.

  Once the register are initialized, we return them inside a Tuple alongside
  the width and module name.

  ## Examples

      iex> Hypex.new(4)
      {:hypex, Hypex.Array, 4, {:array, 16, 0, 0, 100}}

      iex> Hypex.new(4, Bitstring)
      {:hypex, Hypex.Bitstring, 4, <<0, 0, 0, 0, 0, 0, 0, 0>>}

  """
  @spec new(width :: number(), mod :: term()) :: hypex :: Hypex.t()
  def new(width \\ 8, mod \\ Hypex.Register.Array)
      when is_integer(width) and width <= 16 and width >= 4,
      do: hypex(mod: mod, width: width, register: mod.init(width))

  @doc """
  Calculates a cardinality based upon a passed in Hypex.

  We use the reduce function of the module representing the register, and track
  the number of zeroes alongside the initial value needed to create a raw estimate.

  Once we have these values we just apply the correction by using the `m` value,
  the zero count, and the raw estimate.

  ## Examples

      iex> hypex = Hypex.new(4)
      iex> hypex = Hypex.update(hypex, "one")
      iex> hypex = Hypex.update(hypex, "two")
      iex> hypex = Hypex.update(hypex, "three")
      iex> Hypex.cardinality(hypex) |> round
      3

  """
  @spec cardinality(hypex :: Hypex.t()) :: cardinality :: number()
  def cardinality(hypex(mod: mod, width: width, register: register)) do
    m = :erlang.bsl(1, width)

    {value, zeroes} =
      mod.reduce(register, width, {0, 0}, fn int, {current, zeroes} ->
        {1 / :erlang.bsl(1, int) + current, (int == 0 && zeroes + 1) || zeroes}
      end)

    raw_estimate = Utilities.a(m) * m * m * 1 / value

    Utilities.apply_correction(m, raw_estimate, zeroes)
  end

  @doc """
  Merges together many Hypex instances with the same seed.

  This is done by converting the underlying register structure to a list of bits
  and taking the max of each index into a new list, before converting back into
  the register structure.

  We accept an arbitrary number of Hypex instances to merge and due to the use
  of List zipping this comes naturally. We catch empty and single entry Lists to
  avoid wasting computation.

  If you have a scenario in which you have to merge a lot of Hypex structures,
  you should typically buffer up your merges and then pass them all as a list to
  this function. This is far more efficient than merging two structures repeatedly.

  ## Examples

      iex> h1 = Hypex.new(4)
      iex> h1 = Hypex.update(h1, "one")
      iex> h1 = Hypex.update(h1, "two")
      iex> h2 = Hypex.new(4)
      iex> h2 = Hypex.update(h2, "three")
      iex> h3 = Hypex.merge([h1, h2])
      iex> Hypex.cardinality(h3) |> round
      3

  """
  @spec merge([hypex :: Hypex.t()]) :: hypex :: Hypex.t()
  def merge(hypices) when is_list(hypices),
    do: Enum.reduce(hypices, &merge/2)

  @doc """
  Merges together two Hypex instances with the same seed.
  """
  @spec merge(hypex :: Hypex.t(), hypex :: Hypex.t()) :: hypex :: Hypex.t()
  def merge(
        hypex(mod: mod, width: width, register: left),
        hypex(mod: mod, width: width, register: right) = hypex
      ),
      do: hypex(hypex, register: mod.merge(left, right))

  @doc """
  Updates a Hypex instance with a value.

  Internally `:erlang.phash2/2` is used as a 32-bit hash function due to it being
  both readily available and relatively fast. Everything here is done via pattern
  matching to achieve fast speeds.

  The main performance hit of this function comes when there's a need to modify
  a bit inside the register, so we protect against doing this unnecessarily by
  pre-determining whether the modification will be a no-op.

  ## Examples

      iex> 4 |> Hypex.new(Bitstring) |> Hypex.update("one")
      { Hypex.Bitstring, 4, << 0, 0, 0, 0, 0, 0, 0, 2 >> }

  """
  @spec update(hypex :: Hypex.t(), value :: any) :: hypex :: Hypex.t()
  def update(hypex(mod: mod, width: width, register: register) = hypex, value) do
    max_uniques = Utilities.max_uniques()
    hash_length = Utilities.hash_length()

    <<idx::size(width), rest::bitstring>> =
      <<:erlang.phash2(value, max_uniques)::size(hash_length)>>

    current_value = mod.get(register, idx, width)

    case max(current_value, Utilities.count_leading_zeros(rest)) do
      ^current_value ->
        hypex

      new_value ->
        hypex(hypex, register: mod.put(register, idx, width, new_value))
    end
  end
end