defmodule Hobbes.VersionMap do
  @moduledoc """
  VersionMap is an ordered in-memory mapping of keys to versions
  used by Resolvers to keep track of when a key or range was
  last written to.

  VersionMap is backed by an `:ets` table.
  """

  import Hobbes.Utils

  @opaque t :: :ets.table

  @doc """
  Creates a new VersionMap.
  """
  @spec new :: :ets.table
  def new do
    :ets.new(:version_map, [:ordered_set, :private])
  end

  @doc """
  Adds `keys` to the version map at `version`.

  ## Examples

      iex> add_writes(vm, 100, ["foo", "hello"])
      :ok

  """
  @spec add_writes(VersionMap.t, non_neg_integer, [binary]) :: :ok
  def add_writes(table, version, keys) when is_integer(version) and is_list(keys) do
    Enum.each(keys, fn
      {sk, ek} -> add_range(table, version, sk, ek)
      k -> add_range(table, version, k, next_key(k))
    end)
    :ok
  end

  defp add_range(table, version, start_key, end_key) do
    prev_key =
      case :ets.prev_lookup(table, start_key) do
        {_, [{sk, {ek, ver}}]} ->
          cond do
            ek <= start_key ->
              # The previous range does not intersect with this range
              :noop
            ek <= end_key ->
              # The previous range intersects with this range and must be trimmed to {sk, start_key}
              :ets.insert(table, {sk, {start_key, ver}})
            ek > end_key ->
              # The previous range completely envelops this range and must be split into {sk, start_key} and {end_key, ek}
              :ets.insert(table, {sk, {start_key, ver}})
              :ets.insert(table, {end_key, {ek, ver}})
          end

          sk

        :"$end_of_table" ->
          # There is no previous range
          nil
      end

    case clear_between(table, end_key, prev_key) do
      {sk, {ek, ver}} ->
        case sk < end_key do
          true ->
            # The last range of the clear intersects with the end of this range and must be trimmed to {end_key, ek}
            :ets.delete(table, sk)
            :ets.insert(table, {end_key, {ek, ver}})

          false -> :noop
        end

      nil -> :noop
    end

    :ets.insert(table, {start_key, {end_key, version}})
  end

  defp clear_between(table, end_key, prev_key) do
    case :ets.next_lookup(table, prev_key) do
      {_, [{sk, {ek, ver}}]} ->
        case ek <= end_key do
          true ->
            :ets.delete(table, sk)
            clear_between(table, end_key, sk)
          false ->
            {sk, {ek, ver}}
        end

      :"$end_of_table" ->
        nil
    end
  end

  @doc """
  Checks if a key or key range has been written to after `version`.

  ## Examples

      iex> written_after?(vm, 100, "foo")
      false

      iex> written_after?(vm, 100, {"foo", "zoo"})
      true

  """
  @spec written_after?(VersionMap.t, non_neg_integer, binary | {binary, binary}) :: boolean
  def written_after?(table, version, key_or_range)

  def written_after?(table, version, key) when is_integer(version) and is_binary(key) do
    case :ets.prev_lookup(table, next_key(key)) do
      {_, [{_sk, {ek, ver}}]} -> ver > version and key < ek
      :"$end_of_table" -> false
    end
  end

  @spec written_after?(VersionMap.t, non_neg_integer, {binary, binary}) :: boolean
  def written_after?(table, version, {start_key, end_key})
      when is_integer(version) and is_binary(start_key) and is_binary(end_key) do
    # Check first key, then scan
    case written_after?(table, version, start_key) do
      true -> true
      false -> do_written_after_scan(table, version, start_key, end_key)
    end
  end

  defp do_written_after_scan(table, version, prev_key, end_key) do
    case :ets.next_lookup(table, prev_key) do
      {_, [{sk, {_ek, ver}}]} ->
        case sk < end_key do
          true ->
            # Range intersects, check for a conflict
            case ver > version do
              # Conflict found
              true -> true
              # Range does not conflict, keep scanning
              false -> do_written_after_scan(table, version, sk, end_key)
            end

          # Range does not intersect, scan complete
          false -> false
        end

      # Reached the end of the table without finding a conflict
      :"$end_of_table" -> false
    end
  end

  @doc """
  Clears out keys with a version less than or equal to `version`.

  ## Examples

      iex> clear_old(vm, 100)
      :ok

  """
  @spec clear_old(VersionMap.t, non_neg_integer) :: :ok
  def clear_old(table, up_to_version) when is_integer(up_to_version) and up_to_version >= 0 do
    :ets.select_delete(table, [{
      {:"$1", {:"$2", :"$3"}},
      [{:"=<", :"$3", up_to_version}],
      [true],
    }])
    :ok
  end

  # For debugging and tests
  @doc false
  def dump(table) do
    :ets.tab2list(table)
  end
end