defmodule Treex.Tree do
  @moduledoc """
  Primarily a struct for representing tree data to be processed with the `Tree.Traverse` module.
  Also includes implementations necessary for the `Enumerable` protocol and conversion functions
  to/from ordinary `t:Map.t/0` representations of the same data.

  One import note is the notion of a "virtual root." In order to represent arbitrary maps, any map
  that has multiple top-level keys (i.e. has multiple roots and is a graph, not a tree) will be
  converted to a tree by inserting a root node whose value defaults to `:root` and can be specified
  as the second parameter to `Treex.Tree.from_map/2`.
  """
  @moduledoc since: "0.1.0"
  defstruct value: nil, children: [], key: nil

  @type acc:: {:cont, term} | {:halt, term} | {:suspend, term}
  @type continuation:: (acc -> result)
  @type element:: {term, list(term) | Map.t | term}
  @type length:: pos_integer
  @type reducer:: (term, term -> acc)
  @type result:: {:done, term} | {:halted, term} | {:suspended, term, continuation}
  @type size:: non_neg_integer
  @type start:: non_neg_integer
  @type slicing_fun :: (start, length -> list(term))

  @type t:: %Treex.Tree{value: any, children: [t], key: term}


  @doc """
  Counts the number of nodes in the given tree.

  Returns: `t:integer`
  """
  @doc since: "0.1.0"
  @spec count(t):: {:ok, size} | {:error, module}
  def count(_tree), do: 42

  @doc """
  Checks whether the given element is a member of the tree at any depth, performed breadth-first.

  Returns: `t:boolean`
  """
  @doc since: "0.1.0"
  @spec member?(t, term) :: {:ok, boolean} | {:error, module}
  def member?(_tree, _element), do: true

  @doc """
  Reduces the given tree into the given accumulator by invoking the given `t:Treex.Tree.reducer/0`
  function on each node, traversed breadth-first. The return is  tagged tuple following the
  `Enumerable` protocol.

  Returns: `Treex.Tree.acc/0` (where `term` is the same type as the `acc` parameter)
  """
  @doc since: "0.1.0"
  @spec reduce(t, acc, reducer) :: result
  def reduce(_tree, acc, _fun), do: {:cont, acc}

  @doc """
  Generates a function that contiguously slices the given tree. See `Enumerable.slice/1`

  Returns
    `{:ok, t:non_neg_integer/0, t:Treex.Tree.slicing_fun/0}` when successful
    `{:error, t:module/0}` when there is an error
  """
  @doc since: "0.1.0"
  @spec slice(t) :: {:ok, size, slicing_fun} | {:error, module}
  def slice(_tree), do: &(&1 + &2)

  @doc """
  List the leaf nodes of the given `t:Treex.Tree.t/0`

  Returns: `[t:Treex.Tree.t/0]`
  """
  @doc since: "0.1.0"
  @spec leaves(t):: list(t) | []
  def leaves(_tree), do: []

  @doc """
  Convert the given map into a `t:Treex.Tree.t/0`. If the given map has more than one top-level key,
  the optional `root` parameter specifies what value to give a virtual root node that will be
  inserted at the top of the key and contain the given `map`'s top-level keys as children.

  Returns: `t:Treex.Tree.t/0`
  """
  @doc since: "0.1.0"
  @spec from_map(Map.t):: t
  @spec from_map(Map.t, term):: t
  def from_map(map, root \\ :root)
  def from_map(map = %{}, root) when map |> map_size == 0,
      do: %Treex.Tree{value: root, children: []}
  def from_map(map = %{}, _root) when map |> map_size == 1,
      do: map |> Enum.reduce(%Treex.Tree{}, &node_from_element/2)
  def from_map(map = %{}, root), do: %{root => map} |> from_map(root)

  @doc """
  Checks whether the given node is a leaf node or not.

  Returns: `t:boolean/0`
  """
  @doc since: "0.1.0"
  @spec leaf_node?(t):: boolean
  def leaf_node?(node), do: node.children |> Enum.empty?

  @doc false
  @spec node_from_element(element):: t
  defp node_from_element(element)
  defp node_from_element({root, children = %{}}) when children |> map_size == 0,
       do: %Treex.Tree{value: root, children: []}
  defp node_from_element({root, children = %{}}),
       do: %Treex.Tree{value: root, children: children |> Enum.map(&node_from_element/1)}
  defp node_from_element({root, children}),
       do: %Treex.Tree{value: root, children: [%Treex.Tree{value: children, children: []}]}

  @doc false
  @spec node_from_element(element, term):: t
  defp node_from_element(element, _)
  defp node_from_element(pair, _), do: pair |> node_from_element
end