defmodule Iteraptor.Array do
@moduledoc """
Array emulation implementing `Access` behaviour. Index in array is zero-based.
`Array` is the "go to" array data structure in Elixir. An array can be
constructed using `Array.new/{0,1}`:
iex> Iteraptor.Array.new()
#Array<[]>
iex> Iteraptor.Array.new(2)
#Array<[nil, nil]>
iex> Iteraptor.Array.new([:foo, :bar])
#Array<[:foo, :bar]>
An array can contain any kind of elements, and elements in an array don't have
to be of the same type. By definition, arrays have _keys_ in `0..size-1` range.
Arrays are implicitly expandable, which means adding an element at index `100`
to the array currently containing 1 element would increase the size of the
array to `100`.
iex> array = Iteraptor.Array.new([:foo])
iex> Iteraptor.Array.set(array, 3, :bar)
#Array<[:foo, nil, nil, :bar]>
An `Array` is represented internally using the `%Array{}` struct. Note that,
however, the struct fields are private and must not be accessed directly;
use the functions in this module to perform operations on arrays.
`Array`s can also be constructed starting from other collection-type data
structures: for example, see `Array.new/1` or `Enum.into/2`.
iex> Enum.into([1, 2, 3], Iteraptor.Array.new())
#Array<[1, 2, 3]>
`Array`s do implement `Access` behaviour.
iex> array = Iteraptor.Array.new([%{foo: 42}, %{bar: :baz}])
iex> get_in(array, [0, :foo])
42
"""
# Arrays have an underlying Map. Array elements are values of said map,
# indices are keys.
@type value :: term
@type t :: %__MODULE__{map: %{required(non_neg_integer) => any()}}
defstruct map: %{}, version: 1
@behaviour Access
alias Iteraptor.Array
@doc """
Returns a new array.
iex> Iteraptor.Array.new()
#Array<[]>
Creates an array of the given length or from enumerable. Might we used to wrap
the existing instance of `Iteraptor.Array`.
iex> Iteraptor.Array.new(3)
#Array<[nil, nil, nil]>
iex> Iteraptor.Array.new([:foo, :bar, 42])
#Array<[:foo, :bar, 42]>
Also the transformation function might be passed via second argument.
iex> Iteraptor.Array.new([1, 2, 3], fn x -> 2 * x end)
#Array<[2, 4, 6]>
"""
# @spec new(enumerable :: nil | t() | integer() | Enum.t(), transform :: (term() -> any())) :: t()
def new(enumerable \\ nil, transform \\ nil)
def new(nil, nil), do: %Array{}
def new(%__MODULE__{} = array, nil), do: array
def new(n, nil) when is_integer(n) and n >= 0,
do: Iteraptor.Array.new(List.duplicate(nil, n))
def new(enumerable, nil) do
list = Enum.to_list(enumerable)
map =
0..(length(list) - 1)
|> Enum.zip(list)
|> Enum.into(%{})
%Array{map: map}
end
def new(enumerable, transform) when is_function(transform, 1) do
list =
enumerable
|> Enum.map(&transform.(&1))
|> Enum.to_list()
map =
0..(length(list) - 1)
|> Enum.zip(list)
|> Enum.into(%{})
%Array{map: map}
end
@doc """
Appends another enumerable to the array.
iex> array = Iteraptor.Array.new([1, 2, 3])
iex> Iteraptor.Array.append(array, [4, 5])
#Array<[1, 2, 3, 4, 5]>
"""
@spec append(t(), any()) :: t()
def append(%Array{map: map} = array, other) do
index = map |> Map.keys() |> List.last() || -1
map =
if Enumerable.impl_for(other) do
appender =
other
|> Enum.reduce({index + 1, []}, fn e, {i, acc} -> {i + 1, [{i, e} | acc]} end)
|> elem(1)
|> Enum.reverse()
|> Enum.into(%{})
Map.merge(map, appender)
else
Map.put(map, index + 1, other)
end
%Array{array | map: map}
end
@doc """
Returns the `value` at `index` in `array`, or `default` if index is out of array bounds.
iex> array = Iteraptor.Array.new([42])
iex> Iteraptor.Array.get(array, 0)
42
iex> Iteraptor.Array.get(array, 2, 42)
42
"""
@spec get(t(), non_neg_integer(), any()) :: any()
def get(array, index, default \\ nil)
def get(%Array{map: map}, index, default) when index < 0 or index >= map_size(map), do: default
def get(%Array{map: map}, index, _default), do: map[index]
@doc """
Pops (deletes) `value` at `index` from `array`, setting the value at the
respective index to `nil`.
Returns a tuple containing the value removed and the new array.
iex> array = Iteraptor.Array.new([1, 2, 3])
iex> {elem, array} = Iteraptor.Array.pop(array, 1)
iex> elem
2
iex> array
#Array<[1, nil, 3]>
"""
@impl Access
@spec pop(t(), non_neg_integer()) :: {any(), t()}
def pop(%Array{map: map} = array, index) do
value = map[index]
{value, %{array | map: Map.put(map, index, nil)}}
end
@doc """
Sets the `value` at `index` in `array`, expanding the array if necessary.
Returns a new array.
iex> array = Iteraptor.Array.new([42])
iex> Iteraptor.Array.set(array, 0, :foo)
#Array<[:foo]>
iex> Iteraptor.Array.set(array, 2, :bar)
#Array<[42, nil, :bar]>
"""
@spec set(t(), non_neg_integer(), any()) :: t()
def set(%Array{map: map} = array, index, value) do
size = Array.size(array)
map =
if size > index do
Map.put(map, index, value)
else
fill = Enum.reverse([value | List.duplicate(nil, index - size)])
Map.merge(map, Enum.into(Enum.zip(size..index, fill), %{}))
end
%Array{array | map: map}
end
@doc """
Trims `nil` values from the tail of the `Array`. Returns a trimmed array.
iex> array = Iteraptor.Array.new([42, nil, nil])
#Array<[42, nil, nil]>
iex> Iteraptor.Array.trim(array)
#Array<[42]>
"""
@spec trim(array :: t()) :: t()
def trim(%Array{map: map} = array) do
map =
map
|> Enum.reverse()
|> Enum.drop_while(fn
{_, nil} -> true
_ -> false
end)
|> Enum.reverse()
|> Enum.into(%{})
%Array{array | map: map}
end
@doc """
Returns the number of elements in `array`.
iex> Iteraptor.Array.size(Iteraptor.Array.new([1, 2, 3]))
3
"""
@spec size(t()) :: non_neg_integer()
def size(%Array{map: map}), do: map_size(map)
@doc """
Converts `array` to a list.
iex> Iteraptor.Array.to_list(Iteraptor.Array.new([1, 2, 3]))
[1, 2, 3]
"""
@spec to_list(t()) :: [any()]
def to_list(%Array{map: map}),
do: map |> Enum.sort() |> Enum.map(&elem(&1, 1))
@doc """
Converts a tuple given as parameter to `array`.
iex> Iteraptor.Array.from_tuple({1, 2, 3})
#Array<[1, 2, 3]>
"""
@spec from_tuple(tuple :: tuple()) :: t()
def from_tuple(tuple) when is_tuple(tuple),
do: tuple |> Tuple.to_list() |> Array.new()
### Access behaviour
@doc false
@impl true
def fetch(%Array{map: map}, index), do: Map.fetch(map, index)
@doc false
@impl true
def get_and_update(%Array{map: map} = array, index, function) do
case function.(map[index]) do
:pop -> Array.pop(array, index)
{get_value, update_value} -> {get_value, Array.set(array, index, update_value)}
end
end
defimpl Enumerable do
def count(array) do
{:ok, Array.size(array)}
end
def member?(%Array{map: map}, val) do
{:ok,
!!Enum.find(map, fn
{_, ^val} -> true
{_, _} -> false
end)}
end
def reduce(array, acc, fun),
do: Enumerable.List.reduce(Array.to_list(array), acc, fun)
if Version.compare(System.version(), "1.10.0-dev") == :lt do
def slice(array) do
{:ok, Array.size(array), &Enumerable.List.slice(Array.to_list(array), &1, &2)}
end
else
defp slice(_list, _start, 0, _size), do: []
defp slice(list, start, count, size) when start + count == size, do: list |> drop(start)
defp slice(list, start, count, _size), do: list |> drop(start) |> take(count)
defp drop(list, 0), do: list
defp drop([_ | tail], count), do: drop(tail, count - 1)
defp take(_list, 0), do: []
defp take([head | tail], count), do: [head | take(tail, count - 1)]
def slice(array) do
size = Array.size(array)
{:ok, size, &slice(Array.to_list(array), &1, &2, size)}
end
end
end
defimpl Collectable do
def into(array) do
fun = fn
list, {:cont, x} -> [x | list]
list, :done -> Array.append(array, Enum.reverse(list))
_, :halt -> :ok
end
{[], fun}
end
end
defimpl Inspect do
import Inspect.Algebra
def inspect(array, opts) do
opts = %Inspect.Opts{opts | charlists: :as_lists}
concat(["#Array<", Inspect.List.inspect(Array.to_list(array), opts), ">"])
end
end
end
