structure

defmodule Structure.BST do
  @moduledoc """
  A Binary Search Tree. This is a binary tree where each element
  is greater than every element in its left subtree and less than every
  element in its right subtree.
  """
  defstruct value: nil, left: nil, right: nil

  @doc """
  Creates a new Binary Search Tree.

  ## Example:

      iex> Structure.BST.new()
      %Structure.BST{value: nil, left: nil, right: nil}
  """
  def new do
    %__MODULE__{}
  end

  @doc """
  Insertes a new item into the Binary Search Tree.

  ## Example:

      iex> Structure.BST.insert(nil, 12)
      %Structure.BST{value: 12, left: nil, right: nil}

  """
  def insert(nil, value) do
    %__MODULE__{value: value}
  end
  def insert(%__MODULE__{value: nil} = tree, value) do
    %{tree | value: value}
  end
  def insert(%__MODULE__{value: v} = tree, value) when value <= v do
    %{tree | left: insert(tree.left, value)}
  end
  def insert(%__MODULE__{} = tree, value) do
    %{tree | right: insert(tree.right, value)}
  end

  @doc """
  Walks a tree inorder.
  """
  def inorder(%__MODULE__{value: nil}) do
    []
  end
  def inorder(%__MODULE__{} = tree) do
    Enum.reverse inorder(tree, [])
  end
  defp inorder(nil, acc) do
    acc
  end
  defp inorder(%{value: value, left: left, right: right}, acc) do
    left = inorder(left, acc)
    mid = [value | left]
    inorder(right, mid)
  end

end

defimpl Inspect, for: Structure.BST do
  import Inspect.Algebra
  alias Structure.BST

  def inspect(%BST{} = tree, opts) do
    concat ["#BST<", to_doc(BST.inorder(tree), opts), ">"]
  end
end