lamport_clock.ex

defmodule :lamport_clock do
  @moduledoc ~S"""
  # Example

      iex> lc0 = :lamport_clock.new()
      %:lamport_clock{value: 1}

      iex> # Node: A
      iex> lc1a = :lamport_clock.increment(lc0)
      %:lamport_clock{value: 2}
      iex> lc2a = :lamport_clock.increment(lc1a)
      %:lamport_clock{value: 3}

      iex> # Node: B
      iex> lc1b = :lamport_clock.increment(lc0)
      %:lamport_clock{value: 2}

      iex> # Merged
      iex> lc1 = :lamport_clock.merge(lc2a, lc1b)
      %:lamport_clock{value: 4}

  """

  @type counter() :: non_neg_integer()
  @type t() :: %__MODULE__{value: counter()}

  @enforce_keys [:value]
  defstruct [:value]

  @spec new() :: t()
  def new() do
    %__MODULE__{value: 1}
  end

  @spec increment(t()) :: t()
  def increment(%__MODULE__{value: value}) do
    %__MODULE__{value: value + 1}
  end

  @spec merge(clock1 :: t(), clock2 :: t()) :: t()
  def merge(%__MODULE__{value: v1}, %__MODULE__{value: v2}) do
    %__MODULE__{value: max(v1, v2) + 1}
  end

  ## Utility Functions

  @spec compare(clock1 :: t(), clock2 :: t()) :: :eq | :gt | :lt
  def compare(clock1 = %__MODULE__{}, clock2 = %__MODULE__{}) do
    cond do
      clock1 === clock2 -> :eq
      descends(clock2, clock1) -> :lt
      descends(clock1, clock2) -> :gt
    end
  end

  @doc """
  Returns true if `clock1` is a descendant from `clock2`.
  """
  @spec descends(clock1 :: t(), clock2 :: t()) :: boolean()
  def descends(%__MODULE__{value: v1}, %__MODULE__{value: v2}) do
    v2 <= v1
  end

  @doc """
  Returns true if `clock1` is dominated by or less than `clock2`.
  """
  @spec dominates(clock1 :: t(), clock2 :: t()) :: boolean()
  def dominates(clock1 = %__MODULE__{}, clock2 = %__MODULE__{}) do
    descends(clock1, clock2) and not descends(clock2, clock1)
  end

  @spec get_counter(t()) :: counter()
  def get_counter(%__MODULE__{value: value}) do
    value
  end
end

simple_vector_clock.ex

defmodule :simple_vector_clock do
  @moduledoc ~S"""
  # Example

      iex> svc0 = :simple_vector_clock.new()
      %:simple_vector_clock{value: %{}}

      iex> # Node: A
      iex> svc0a = :simple_vector_clock.increment(svc0, :a)
      %:simple_vector_clock{value: %{a: 1}}
      iex> svc1a = :simple_vector_clock.increment(svc0a, :a)
      %:simple_vector_clock{value: %{a: 2}}

      iex> # Node: B
      iex> svc0b = :simple_vector_clock.increment(svc0, :b)
      %:simple_vector_clock{value: %{b: 1}}

      iex> # Node: A (Merged)
      iex> svc2a = :simple_vector_clock.merge(svc1a, svc0b)
      %:simple_vector_clock{value: %{a: 2, b: 1}}
      iex> svc3a = :simple_vector_clock.increment(svc2a, :a)
      %:simple_vector_clock{value: %{a: 3, b: 1}}

      iex> # Node: C
      iex> svc0c = :simple_vector_clock.increment(svc0, :c)
      %:simple_vector_clock{value: %{c: 1}}

      iex> # Node: B (Merged)
      iex> svc2a = :simple_vector_clock.merge(svc3a, svc0c)
      %:simple_vector_clock{value: %{a: 3, b: 1, c: 1}}

  """

  @type key() :: term()
  @type counter() :: non_neg_integer()
  @type t() :: %__MODULE__{value: %{key() => counter()}}

  @enforce_keys [:value]
  defstruct [:value]

  @spec new() :: t()
  def new() do
    %__MODULE__{value: Map.new()}
  end

  @spec increment(t(), key()) :: t()
  def increment(%__MODULE__{value: value}, key) do
    value = Map.update(value, key, 1, &(&1 + 1))
    %__MODULE__{value: value}
  end

  @spec merge(clock1 :: t(), clock2 :: t()) :: t()
  def merge(%__MODULE__{value: v1}, %__MODULE__{value: v2}) do
    keys = :ordsets.union(:ordsets.from_list(Map.keys(v1)), :ordsets.from_list(Map.keys(v2)))

    value =
      Enum.reduce(keys, Map.new(), fn key, acc ->
        Map.put(acc, key, max(Map.get(v1, key, 0), Map.get(v2, key, 0)))
      end)

    %__MODULE__{value: value}
  end

  ## Utility Functions

  @spec compare(clock1 :: t(), clock2 :: t()) :: :eq | :gt | :lt
  def compare(clock1 = %__MODULE__{}, clock2 = %__MODULE__{}) do
    cond do
      clock1 === clock2 -> :eq
      descends(clock2, clock1) -> :lt
      descends(clock1, clock2) -> :gt
    end
  end

  @doc """
  Returns true if `clock1` is a descendant from `clock2`.
  """
  @spec descends(clock1 :: t(), clock2 :: t()) :: boolean()
  def descends(%__MODULE__{value: v1}, %__MODULE__{value: v2}) do
    folder = fn
      key, c2, true ->
        c2 <= Map.get(v1, key, 0)
      _, _, false ->
        false
    end

    :maps.fold(folder, true, v2)
  end

  @doc """
  Returns true if `clock1` is dominated by or less than `clock2`.
  """
  @spec dominates(clock1 :: t(), clock2 :: t()) :: boolean()
  def dominates(clock1 = %__MODULE__{}, clock2 = %__MODULE__{}) do
    descends(clock1, clock2) and not descends(clock2, clock1)
  end

  @spec get_counter(t(), key()) :: counter()
  def get_counter(%__MODULE__{value: value}, key) do
    case Map.fetch(value, key) do
      {:ok, counter} when is_integer(counter) and counter > 0 ->
        counter

      :error ->
        0
    end
  end
end

timestamp_vector_clock.ex

defmodule :timestamp_vector_clock do
  @moduledoc ~S"""
  # Example

      iex> tsvc0 = :timestamp_vector_clock.new()
      %:timestamp_vector_clock{value: %{}}

      iex> # Node: A
      iex> tsvc0a = :timestamp_vector_clock.increment(tsvc0, :a)
      %:timestamp_vector_clock{
        value: %{
          a: {1, 1543253763430255}
        }
      }
      iex> tsvc1a = :timestamp_vector_clock.increment(tsvc0a, :a)
      %:timestamp_vector_clock{
        value: %{
          a: {2, 1543253772432071}
        }
      }

      iex> # Node: B
      iex> tsvc0b = :timestamp_vector_clock.increment(tsvc0, :b)
      %:timestamp_vector_clock{
        value: %{
          b: {1, 1543253777838787}
        }
      }

      iex> # Node: A (Merged)
      iex> tsvc2a = :timestamp_vector_clock.merge(tsvc1a, tsvc0b)
      %:timestamp_vector_clock{
        value: %{
          a: {2, 1543253772432071},
          b: {1, 1543253777838787}
        }
      }
      iex> tsvc3a = :timestamp_vector_clock.increment(tsvc2a, :a)
      %:timestamp_vector_clock{
        value: %{
          a: {3, 1543253788950345},
          b: {1, 1543253777838787}
        }
      }

      iex> # Node: C
      iex> tsvc0c = :timestamp_vector_clock.increment(tsvc0, :c)
      %:timestamp_vector_clock{
        value: %{
          c: {1, 1543253792702509}
        }
      }

      iex> # Node: B (Merged)
      iex> tsvc2a = :timestamp_vector_clock.merge(tsvc3a, tsvc0c)
      %:timestamp_vector_clock{
        value: %{
          a: {3, 1543253788950345},
          b: {1, 1543253777838787},
          c: {1, 1543253792702509}
        }
      }

  """

  @type key() :: term()
  @type counter() :: non_neg_integer()
  @type timestamp() :: pos_integer()
  @type t() :: %__MODULE__{value: %{key() => {counter(), timestamp()}}}

  @enforce_keys [:value]
  defstruct [:value]

  @spec new() :: t()
  def new() do
    %__MODULE__{value: Map.new()}
  end

  @spec increment(t(), key()) :: t()
  def increment(struct = %__MODULE__{}, key) do
    increment(struct, key, current_timestamp())
  end

  @spec increment(t(), key(), timestamp()) :: t()
  def increment(%__MODULE__{value: value}, key, now) do
    value = Map.update(value, key, {1, now}, fn {counter, _} -> {counter + 1, now} end)
    %__MODULE__{value: value}
  end

  @spec merge(clock1 :: t(), clock2 :: t()) :: t()
  def merge(%__MODULE__{value: v1}, %__MODULE__{value: v2}) do
    keys = :ordsets.union(:ordsets.from_list(Map.keys(v1)), :ordsets.from_list(Map.keys(v2)))

    value =
      Enum.reduce(keys, Map.new(), fn key, acc ->
        ct1 = {c1, t1} = Map.get(v1, key, {0, 0})
        ct2 = {c2, t2} = Map.get(v2, key, {0, 0})

        ct =
          cond do
            c1 > c2 -> ct1
            c1 < c2 -> ct2
            true -> {c1, max(t1, t2)}
          end

        Map.put(acc, key, ct)
      end)

    %__MODULE__{value: value}
  end

  ## Utility Functions

  @spec compare(clock1 :: t(), clock2 :: t()) :: :eq | :gt | :lt
  def compare(clock1 = %__MODULE__{}, clock2 = %__MODULE__{}) do
    cond do
      clock1 === clock2 -> :eq
      descends(clock2, clock1) -> :lt
      descends(clock1, clock2) -> :gt
    end
  end

  @doc """
  Returns true if `clock1` is a descendant from `clock2`.
  """
  @spec descends(clock1 :: t(), clock2 :: t()) :: boolean()
  def descends(%__MODULE__{value: v1}, %__MODULE__{value: v2}) do
    folder = fn
      key, {c2, _}, true ->
        {c1, _} = Map.get(v1, key, {0, 0})
        c2 <= c1

      _, _, false ->
        false
    end

    :maps.fold(folder, true, v2)
  end

  @doc """
  Returns true if `clock1` is dominated by or less than `clock2`.
  """
  @spec dominates(clock1 :: t(), clock2 :: t()) :: boolean()
  def dominates(clock1 = %__MODULE__{}, clock2 = %__MODULE__{}) do
    descends(clock1, clock2) and not descends(clock2, clock1)
  end

  @spec get_counter(t(), key()) :: counter()
  def get_counter(%__MODULE__{value: value}, key) do
    case Map.fetch(value, key) do
      {:ok, {counter, _}} when is_integer(counter) and counter > 0 ->
        counter

      :error ->
        0
    end
  end

  @spec get_timestamp(t(), key()) :: timestamp() | nil
  def get_timestamp(%__MODULE__{value: value}, key) do
    case Map.fetch(value, key) do
      {:ok, {_, timestamp}} when is_integer(timestamp) and timestamp > 0 ->
        timestamp

      :error ->
        nil
    end
  end

  @doc false
  defp current_timestamp() do
    :erlang.system_time(:microsecond)
  end
end