SparseCells

iex_session.ex

iex(1)> cells = SparseCells.build([cell_1: ["a", "b"], cell_2: [1, 2], cell_3: ["w", "x", "y", "z"]])
%SparseCells{
  key_sizes: [cell_1: 2, cell_2: 2, cell_3: 4],
  map: %{
    {:cell_1, 0} => "a",
    {:cell_1, 1} => "b",
    {:cell_2, 0} => 1,
    {:cell_2, 1} => 2,
    {:cell_3, 0} => "w",
    {:cell_3, 1} => "x",
    {:cell_3, 2} => "y",
    {:cell_3, 3} => "z"
  }
}
iex(2)> SparseCells.slice(cells, 0..10)                                                              
[
  [cell_1: "a", cell_2: 1, cell_3: "w"],
  [cell_1: "b", cell_2: 1, cell_3: "w"],
  [cell_1: "a", cell_2: 2, cell_3: "w"],
  [cell_1: "b", cell_2: 2, cell_3: "w"],
  [cell_1: "a", cell_2: 1, cell_3: "x"], 
  [cell_1: "b", cell_2: 1, cell_3: "x"],
  [cell_1: "a", cell_2: 2, cell_3: "x"],
  [cell_1: "b", cell_2: 2, cell_3: "x"],
  [cell_1: "a", cell_2: 1, cell_3: "y"],
  [cell_1: "b", cell_2: 1, cell_3: "y"],
  [cell_1: "a", cell_2: 2, cell_3: "y"]
]
iex(3)> SparseCells.slice(cells, 10..20)                                                             
[
  [cell_1: "a", cell_2: 2, cell_3: "y"],
  [cell_1: "b", cell_2: 2, cell_3: "y"],
  [cell_1: "a", cell_2: 1, cell_3: "z"],
  [cell_1: "b", cell_2: 1, cell_3: "z"],
  [cell_1: "a", cell_2: 2, cell_3: "z"], 
  [cell_1: "b", cell_2: 2, cell_3: "z"],
  [cell_1: "a", cell_2: 1, cell_3: "w"] 
]
iex(4)> SparseCells.slice(cells, 20..21)
[]
iex(5)> 

sparse_cells.ex

defmodule SparseCells do
  # data [cell_1: ["a", "b", "c"], cell_2: [1, 2, 3], cell_3: ["v", "w", "x", "y", "z"]]

  defstruct map: %{},
            key_sizes: []

  def build(cells) when is_list(cells) do
    %SparseCells{
      map: cells_to_index_map(cells),
      key_sizes: Enum.map(cells, fn {k, values} -> {k, length(values)} end)
    }
  end

  defp key_sizes(%SparseCells{key_sizes: k}), do: k
  defp keys(%SparseCells{key_sizes: k}), do: Keyword.keys(k)
  defp map(%SparseCells{map: map}), do: map

  def size(%SparseCells{key_sizes: key_sizes}) do
    key_sizes
    |> Keyword.values()
    |> Enum.reduce(1, fn n, acc -> n * acc end)
  end

  defp check_and_adjust_range(low..high, lower_limit..upper_limit) do
      if low > high do
      raise "For #{inspect(low..high)} as low..high low cannot be greater than high."
    end
    if low < lower_limit do
      raise "Lower part of range #{inspect(low..high)} cannot be less than #{lower_limit}."
    end

    if high > upper_limit do
      low..upper_limit
    else
      low..high
    end
  end
  def slice(cells, low..high) when low <= high do
    low..high = check_and_adjust_range(low..high, 0..size(cells))
    do_slice(cells, low..high, [])
  end
  defp do_slice(cells, low..high, acc) when low <= high do
    case fetch_index(cells, low) do
      [] ->
        # empty list means we had a key miss and we are out of range
        Enum.reverse(acc)
      row when is_list(row) ->
        # row that is not empty means we found the index and we continue to slice
        do_slice(cells, (low + 1)..high, [row | acc])

    end
  end


  defp do_slice(_cells, high..low, acc) when high > low do
    Enum.reverse(acc)
  end

  defp fetch_index(cells, index) do
    map = map(cells)
    cells
    |> generate_keys(index)
    |> Enum.reduce_while([], fn {key_name, key_index}, acc ->
      case Map.fetch(map, {key_name, key_index}) do
        {:ok, value} ->

          {:cont, [{key_name, value} | acc]}
        :error ->

          {:halt, :error}
      end
    end)
    |> case do
      :error ->
        []
      rows when is_list(rows) ->
        Enum.reverse(rows)
    end
  end

  defp generate_keys(cells, index) do
    Enum.zip([keys(cells), indexes_for_keys(cells, index)])
  end

  defp indexes_for_keys(cells, orig_index) do
    cells
    |> key_sizes()
    |> Enum.reduce({orig_index, []}, fn {_k, k_count}, {index, acc} ->
      {div(index, k_count), [rem(index, k_count) | acc]}
    end)
    # just want the generated indexes not the remaining
    |> elem(1)
    |> Enum.reverse()
  end

  defp cells_to_index_map(cells) do
    cells
    |> Enum.flat_map(fn {k, values} ->
      values
      |> Enum.with_index()
      |> Enum.map(fn {v, i} -> {{k, i}, v} end)
    end)
    |> Map.new()
  end
end