defmodule Vector do
  @moduledoc """
  Functions that work on vectors.

  This datastructure wraps Erlang's `array` type for fast random
  lookup and update to large collections.

  The point of this module is not meant to be a 1:1 wrapper, but to be
  a useful set of higher-level API operations.

  Note that this module is implemented as a struct with an `array` field,
  pointing to the underlying Erlang `array` implementation. This field
  is private, so you should use the functions in this module
  to perform operations.
  """

  # this is not great, but `array()` is not available in Elixir
  @type t :: %__MODULE__{array: :array.array()}
  @type index :: integer
  @type value :: term

  @behaviour Access

  defstruct array: :array.new()

  @doc """
  Constructs a array-backed vector

  ## Examples

      iex> Vector.new()
      #Vector<[]>

      iex> Vector.new(Vector.new())
      #Vector<[]>
  """
  def new(), do: %__MODULE__{}
  @doc """
  Constructs an array-backed vector from an enumerable

  ## Examples

      iex> Vector.new([1,2,3])
      #Vector<[1, 2, 3]>

      iex> Vector.new(%{a: 1, b: 2})
      #Vector<[a: 1, b: 2]>

      iex> Vector.new(0)
      #Vector<[]>

      # this is exposing a bit of implementation, but I am
      # unsure how else to test it
      iex> Vector.new(5).array
      {:array, 5, 10, :undefined, 10}
  """
  def new(%__MODULE__{} = vector), do: vector
  def new(size) when is_integer(size) do
    %__MODULE__{
      array: :array.new([
        {:size, size},
        {:fixed, false},
        {:default, :undefined}
      ])
    }
  end
  def new(enumerable) do
    array =
      enumerable
      |> Enum.to_list
      |> new_from_list

    %Vector{array: array}
  end

  defp new_from_list(list) when is_list(list) do
    :array.from_list(list)
  end

  @doc """
  Converts a `vector` to a list

  ## Examples

      iex> Vector.to_list(Vector.new([1,2,3]))
      [1,2,3]
  """
  def to_list(%Vector{array: array}) do
    :array.sparse_to_list(array)
  end

  @doc """
  Returns the size of a vector

  ## Examples

      iex> Vector.size(Vector.new())
      0

      iex> Vector.size(Vector.new([1,2,3,4,5]))
      5
  """
  def size(%Vector{array: array}) do
    :array.sparse_size(array)
  end

  @doc """
  Checks if `vector` contains `value`

  ## Examples

      iex> Vector.member?(Vector.new([1,2,3]), 99)
      false

      iex> Vector.member?(Vector.new([1,2,3]), 2)
      true
  """
  def member?(%Vector{array: array}, value) do
    array
    |> :array.sparse_to_list
    |> MapSet.new()
    |> MapSet.member?(value)
  end

  @doc """
  Finds the element at the given `index` (zero-based) in logarithmic time.
  Returns `{:ok, element}` if found, otherwise `:error`.

  A negative index can be passed, in which case the index is counted from the end (e.g. -1 finds the last element).

## Examples

      iex> Vector.fetch(Vector.new([1,2,3]), 9)
      :error

      iex> Vector.fetch(Vector.new([1,2,3]), 2)
      {:ok, 3}

      iex> Vector.fetch(Vector.new([1,2,3,4,5]), -2)
      {:ok, 4}
  """
  def fetch(%Vector{} = vector, index) when index < 0 do
    fetch(vector, Vector.size(vector) + index)
  end
  @spec fetch(t, index) :: {:ok, value} | :error
  def fetch(%Vector{array: array}, index) do
    case :array.get(index, array) do
      :undefined -> :error
      value -> {:ok, value}
    end
  end

  @doc """
  Finds the element at the given `index` (zero-based) in logarithmic time.

  Raises `OutOfBoundsError` if the given `index` is outside the range of
  the enumerable.

  A negative index can be passed, in which case the index is counted from the end (e.g. -1 finds the last element).

  ## Examples

      iex> Vector.fetch!(Vector.new([1,2,3]), 1)
      2

      iex> Vector.fetch!(Vector.new([1,2,3]), -1)
      3

      iex> Vector.fetch!(Vector.new([1,2,3]), 99)
      ** (Enum.OutOfBoundsError) out of bounds error
  """
  @spec fetch!(t, index) :: value | no_return
  def fetch!(%Vector{} = vector, index) do
    case fetch(vector, index) do
      {:ok, value} -> value
      :error -> raise Enum.OutOfBoundsError
    end
  end

  @doc """
  Puts the given value under index in vector in logarithmic time

  A negative index can be passed, in which case the index is counted from the end (e.g. -1 finds the last element).

  ## Examples

      iex> Vector.put(Vector.new([1,2,3]), 3, 99)
      #Vector<[1, 2, 3, 99]>

      iex> Vector.put(Vector.new([1,2,3]), 0, 3)
      #Vector<[3, 2, 3]>

      iex> Vector.put(Vector.new([1,2,3]), -1, 101)
      #Vector<[1, 2, 101]>
  """
  @spec put(t, index, value) :: t
  def put(%Vector{} = vector, index, value) when index < 0 do
    put(vector, Vector.size(vector) + index, value)
  end
  def put(%Vector{array: array}, index, value) do
    %Vector{array: :array.set(index, value, array)}
  end

  @doc """
  Updates the value in vector with the given function in logarithmic time.

  If index is present in vector with value, fun is invoked with
  argument value and its result is used as the new value of index. If index is
  not present in vector, initial is inserted as the value of index.

  A negative index can be passed, in which case the index is counted from the end (e.g. -1 finds the last element).

  ## Examples

      iex> Vector.update(Vector.new([1,2,3]), 0, 13, &(&1 * 2))
      #Vector<[2, 2, 3]>

      iex> Vector.update(Vector.new([1,2,3]), 5, 11, &(&1 * 2))
      #Vector<[1, 2, 3, 11]>

      iex> Vector.update(Vector.new([1,2,3]), -2, 11, &(&1 * 2))
      #Vector<[1, 4, 3]>
  """
  @spec update(t, index, value, (value -> value)) :: t
  def update(vector, index, initial, fun) when is_function(fun, 1) do
    case fetch(vector, index) do
      {:ok, value} ->
        put(vector, index, fun.(value))
      :error ->
        put(vector, index, initial)
    end
  end

  @doc """
  Updates index with the given function in logarithmic time.

  If index is present in map with value value, fun is invoked with argument value
  and its result is used as the new value of index. If index is not present in map,
  a Enum.OutOfBoundsError exception is raised.

  ## Examples

      iex> Vector.update!(Vector.new([1,2,3]), 0, &(&1 * 2))
      #Vector<[2, 2, 3]>

      iex> Vector.update!(Vector.new([1,2,3]), 5, &(&1 * 2))
      ** (Enum.OutOfBoundsError) out of bounds error

      iex> Vector.update!(Vector.new([1,2,3]), -2, &(&1 * 2))
      #Vector<[1, 4, 3]>
  """
  @spec update!(t, index, (value -> value)) :: t | no_return
  def update!(vector, index, fun) when is_function(fun, 1) do
    case fetch(vector, index) do
      {:ok, value} ->
        put(vector, index, fun.(value))
      :error ->
        raise Enum.OutOfBoundsError
    end
  end

  @doc """
  Gets the value at an index in logarithmic time, returning a default if it does not exist.

  ## Examples

      iex> Vector.get(Vector.new([1,2,3]), 0)
      1

      iex> Vector.get(Vector.new([1,2,3]), 9)
      nil

      iex> Vector.get(Vector.new([1,2,3]), 9, 1000)
      1000
  """
  @spec get(t, index, default :: value) :: value
  def get(vector, index, default \\ nil) do
    case fetch(vector, index) do
      {:ok, value} -> value
      :error -> default
    end
  end

  @doc """
  Returns either the vector without the value at index, or the original vector
  if no value is present at index.

  ## Examples

      iex> Vector.delete(Vector.new([1,2,3,4,5]), 2)
      #Vector<[1, 2, 4, 5]>

      iex> Vector.delete(Vector.new([1,2,3]), 9)
      #Vector<[1, 2, 3]>
  """
  @spec delete(t, index) :: t
  def delete(%Vector{array: array} = _vector, index) do
    %Vector{array: :array.reset(index, array)}
  end

  @doc """
  Gets and updates a value at the same time.

  ## Examples

      iex> {val, new_vector} = Vector.get_and_update(Vector.new([1,2,3]), 0, fn(value) -> {value, value + 100} end)
      iex> {val, Vector.to_list(new_vector)}
      {1, [101, 2, 3]}

      iex> {val, new_vector} = Vector.get_and_update(Vector.new([1,2,3]), 0, fn(_) -> :pop end)
      iex> {val, Vector.to_list(new_vector)}
      {1, [2, 3]}
  """
  @spec get_and_update(t, index, (value -> {value, value} | :pop)) :: {value, t}
  def get_and_update(vector, index, fun) do
    case fun.(get(vector, index)) do
      {value_to_return, new_value} -> {value_to_return, put(vector, index, new_value)}
      :pop -> pop(vector, index)
    end
  end

  @doc """
  Deletes a value at index, returning the new vector and the value that was deleted

  ## Examples

      iex> {value, new} = Vector.pop(Vector.new([1,2,3]), 2)
      iex> {value, Vector.to_list(new)} # arrays cannot be checked for value equality
      {3, [1, 2]}

      iex> {value, new} = Vector.pop(Vector.new([1,2,3]), 99)
      iex> {value, Vector.to_list(new)}
      {nil, [1, 2, 3]}
  """
  def pop(vector, index, default \\ nil) do
    value = get(vector, index, default)
    {value, delete(vector, index)}
  end

  @doc """
  Append an item to to a vector

  ## Examples

      iex> Vector.new([1, 2, 3]) |> Vector.append(9)
      Vector.new([1, 2, 3, 9])

      iex> Vector.new() |> Vector.append("hi")
      Vector.new(["hi"])

      iex> Vector.new([1, 2, 3]) |> Vector.append(9) |> Vector.size
      4
  """
  @spec append(t, value) :: t
  def append(%__MODULE__{} = vector, value) do
    size = Vector.size(vector)
    Vector.put(vector, size, value)
  end

  @doc """
  Reverse a vector.

  ## Examples

      iex> vector = Vector.new([1,2,3])
      iex> vector == vector |> Vector.reverse |> Vector.reverse
      true

      iex> Vector.reverse(Vector.new())
      #Vector<[]>

      iex> Vector.reverse(Vector.new([1, 2, 3]))
      #Vector<[3, 2, 1]>
  """
  def reverse(%__MODULE__{} = vector) do
    %{vector | array: :array.from_list(Enum.reverse(vector))}
  end

  @doc """
  Map a vector.

  ## Examples

      iex> Vector.new() |> Vector.map(fn(_i, val) -> val + 1 end)
      #Vector<[]>

      iex> Vector.new([1, 2, 3]) |> Vector.map(fn(_i, val) -> val + 1 end)
      #Vector<[2, 3, 4]>
  """
  def map(%__MODULE__{array: array} = vector, fun) when is_function(fun, 2) do
    %{vector | array: :array.sparse_map(fun, array)}
  end

  defimpl Enumerable do
    def count(vector), do: {:ok, Vector.size(vector)}
    def member?(vector, val), do: {:ok, Vector.member?(vector, val)}
    def reduce(vector, acc, fun), do: Enumerable.List.reduce(Vector.to_list(vector), acc, fun)
  end

  defimpl Collectable do
    def into(original) do
      {original, fn
        vector, {:cont, value} -> Vector.put(vector, Vector.size(vector) + 1, value)
        vector, :done -> vector
        _, :halt -> :ok
      end}
    end
  end

  defimpl Inspect do
    import Inspect.Algebra

    def inspect(set, opts) do
      concat(["#Vector<", Inspect.List.inspect(Vector.to_list(set), opts), ">"])
    end
  end
end