defmodule SData.MerkleList do
  @moduledoc"""
  A simple Merkle list store.

  Future improvements:
    - When messages are inserted other than at the top, all intermediate hashes
      change. Keep track of the mapping from old hashes to new hashes so that get
      requests can work even for hashes that are not valid anymore.
    - group items in "pages" (bigger bundles)
  """

  defstruct [:root, :top, :cmp, :store]

  @doc"""
  Create a Merkle list store.

  `cmp` is a function that compares stored items and provides a total order.
  It must return:
    - `:after` if the first argument is more recent
    - `:duplicate` if the two items are the same
    - `:before` if the first argument is older
  """
  def new(cmp) do
    root_item = :root
    root_hash = SData.term_hash root_item
    state = %SData.MerkleList{
              root:  root_hash,
              top:   root_hash,
              cmp:   cmp,
              store: %{ root_hash => root_item }
            }
    state
  end

  defp push(state, item) do
    new_item = {item, state.top}
    new_item_hash = SData.term_hash new_item
    new_store = Map.put(state.store, new_item_hash, new_item)
    %{ state | :top => new_item_hash, :store => new_store }
  end

  defp pop(state) do
    if state.top == state.root do
      :error
    else
      {item, next} = Map.get(state.store, state.top)
      new_store = Map.delete(state.store, state.top)
      new_state = %{ state | :top => next, :store => new_store }
      {:ok, item, new_state}
    end
  end

  @doc"""
  Insert a list of items in the store.

  A callback function may be specified that is called on any item
  that is sucessfully added, i.e. that wasn't present in the store before.
  """
  def insert_many(state, items, callback \\ (fn _ -> nil end)) do
    items_sorted = Enum.sort(items, fn (x, y) -> state.cmp.(x, y) == :after end)
    insert_many_aux(state, items_sorted, callback)
  end

  defp insert_many_aux(state, [], _callback) do
    state
  end

  defp insert_many_aux(state, [item | rest], callback) do
    case pop(state) do
      :error ->
        new_state = push(insert_many_aux(state, rest, callback), item)
        callback.(item)
        new_state
      {:ok, front, state_rest} ->
        case state.cmp.(item, front) do
          :after ->
            new_state = push(insert_many_aux(state, rest, callback), item)
            callback.(item)
            new_state
          :duplicate -> insert_many_aux(state, rest, callback)
          :before -> push(insert_many_aux(state_rest, [item | rest], callback), item)
        end
    end
  end

  @doc"""
  Insert a single item in the store.

  A callback function may be specified that is called on the item
  if it is sucessfully added, i.e. it wasn't present in the store before.
  """
  def insert(state, item, callback \\ (fn _ -> nil end)) do
    insert_many(state, [item], callback)
  end

  @doc"""
  Read some items from the state.

  The two parameters are optional:
  - qbegin : hash of the first item to read
  - qlimit : number of items to read
  """
  def read(state, qbegin \\ nil, qlimit \\ nil) do
    begin = qbegin || state.top
    limit = qlimit || 20
    get_items_list(state, begin, limit)
  end

  @doc"""
  Get the hash of the last item
  """
  def top(state) do
    state.top
  end

  @doc"""
  Get the hash of the root item
  """
  def root(state) do
    state.root
  end

  @doc"""
  Check if the store holds a certain item
  """
  def has(state, hash) do
    Map.has_key?(state.store, hash)
  end

  defp get_items_list(state, begin, limit) do
    case limit do
      0 -> {:ok, [], begin}
      _ ->
        case Map.fetch(state.store, begin) do
          {:ok, :root} ->
            {:ok, [], nil }
          {:ok, {item, next}} ->
            case get_items_list(state, next, limit - 1) do
              {:ok, rest, past} ->
                {:ok, [ item | rest ], past }
              {:error, reason} -> {:error, reason}
            end
          :error -> {:error, begin}
        end
    end
  end

  @doc"""
    Compare function for timestamped strings
  """
  def cmp_ts_str({ts1, str1}, {ts2, str2}) do
    cond do
      ts1 > ts2 -> :after
      ts1 < ts2 -> :before
      str1 == str2 -> :duplicate
      str1 > str2 -> :after
      str1 < str2 -> :before
    end
  end
end