Elixir algorithms

graph.ex

defmodule Algorithms.Graph.Node do
  alias Algorithms.Graph.Node

  defstruct data: nil, edges: []

  def bfs(id, storage, visited, f) do
    if Map.has_key?(visited, id) do
      []
    else
      visited = Map.put(visited, id, true)
      node = Map.get(storage, id)
      result = f.({id, node.data})
      child_results = node.edges |> Enum.flat_map(&bfs(&1, storage, visited, f))
      [result | child_results]
    end
  end
end

defmodule Algorithms.Graph do
  alias Algorithms.Graph
  alias Algorithms.Graph.Node

  defstruct storage: %{}, curr_id: 0

  def add_node(graph, node) do
    graph = put_in(graph.storage[graph.curr_id], node)
    %{graph | curr_id: graph.curr_id + 1}
  end

  def add_edge(graph, a, b) do
    update_in(graph.storage[a].edges, &[b | &1])
  end 

  def bfs(graph, id, f) do
    Node.bfs(id, graph.storage, %{}, f)
  end
end

linked_list.ex

defmodule Algorithms.LinkedList.Node do
  @moduledoc """
  A node in a doubly linked list.

  A doubly linked list requires circular references so
  the next and prev "pointers" are simply ids to a map of
  id => node
  """
  alias Algorithms.LinkedList.Node

  defstruct data: nil, next: nil, prev: nil

  def print(%Node{data: nil}, _storage), do: IO.puts("Nil")
  def print(%Node{next: nil} = node, _storage) do
    IO.puts(inspect(node.data))
    IO.puts("Nil")
  end
  def print(node, storage) do
    IO.puts(inspect(node.data))
    print(Map.get(storage, node.next), storage)
  end

  def reverse(node_id, storage) do
    node = Map.get(storage, node_id)

    if node.next == nil do
      storage = update_in(storage[node_id].prev, fn _ -> nil end)
      {node_id, node_id, storage}
    else
      new_tail = node_id
      {head, tail, storage} = reverse(node.next, storage)

      storage = update_in(storage[tail].next, fn _ -> new_tail end)
      storage = update_in(storage[new_tail].prev, fn _ -> tail end)
      storage = update_in(storage[new_tail].next, fn  _ -> nil end)
      {head, new_tail, storage}
    end
  end
end

defmodule Algorithms.LinkedList do
  @moduledoc """
  A doubly linked list. It uses a map of ids to nodes to keep track
  of the pointers.

  ## Example

      iex> alias Algorithms.LinkedList
      Algorithms.LinkedList
      iex> list = %LinkedList{}
      %Algorithms.LinkedList{curr_id: 0, head: nil, storage: %{}, tail: nil}
      iex> node = %LinkedList.Node{data: 2}
      %Algorithms.LinkedList.Node{data: 2, next: nil, prev: nil}
      iex> list |> LinkedList.add_node(node) |> LinkedList.print
      2
      Nil
      :ok
      iex> list |> LinkedList.add_node(node) |> LinkedList.add_node(node) |> LinkedList.print
      2
      2
      Nil
      :ok

  """

  alias Algorithms.LinkedList
  alias Algorithms.LinkedList.Node

  defstruct storage: %{}, head: nil, tail: nil, curr_id: 0

  def add_node(%LinkedList{head: nil} = list, node) do
    %{list | storage: Map.put(list.storage, list.curr_id, node),
             head: list.curr_id,
             tail: list.curr_id,
             curr_id: list.curr_id + 1}
  end
  def add_node(list, node) do
    new_tail_node = %{node | prev: list.tail}
    new_tail = list.curr_id

    list = put_in(list.storage[new_tail], new_tail_node)
    list = update_in(list.storage[list.tail].next, fn _ -> new_tail end)

    %{list | tail: new_tail, curr_id: list.curr_id + 1}
  end

  def print(%LinkedList{head: nil}), do: IO.puts("Nil")
  def print(list) do
    Node.print(Map.get(list.storage, list.head), list.storage)
  end
  
  def reverse(list) do
    {head, tail, storage} = Node.reverse(list.head, list.storage)
    %{list | storage: storage, head: head, tail: tail}
  end
end