defmodule SData.MerkleList do
  use GenServer

  def start_link([cmp, name: name]) do
    GenServer.start_link(__MODULE__, cmp, [name: name])
  end

  defp term_hash(term) do
    :crypto.hash(:sha256, (:erlang.term_to_binary term))
  end

  @doc """
    Initialize a Merkle List storage.
    `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 init(cmp) do
    root_item = :root
    root_hash = term_hash root_item
    state = %{
              root:  root_hash,
              top:   root_hash,
              cmp:   cmp,
              store: %{ root_hash => root_item }
            }
    {:ok, state}
  end

  defp state_push(item, state) do
    new_item = {item, state.top}
    new_item_hash = 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 state_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

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

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

  def handle_cast({:insert, item}, state) do
    handle_cast({:insert_many, [item]}, state)
  end

  def handle_cast({:insert_many, items}, state) do
    handle_cast({:insert_many, items, fn _ -> nil end}, state)
  end

  def handle_cast({:insert_many, items, callback}, state) do
    items_sorted = Enum.sort(items, fn (x, y) -> state.cmp.(x, y) == :after end)
    new_state = insert_many(state, items_sorted, callback)
    {:noreply, new_state}
  end

  def handle_call({:read, qbegin, qlimit}, _from, state) do
    begin = qbegin || state.top
    limit = qlimit || 20
    items = get_items_list(state, begin, limit)
    {:reply, items, state}
  end

  def handle_call(:top, _from, state) do
    {:reply, state.top, state}
  end

  def handle_call(:root, _from, state) do
    {:reply, state.root, state}
  end

  def handle_call({:has, hash}, _from, state) do
    {:reply, Map.has_key?(state.store, hash), state}
  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