defmodule Heap.LeftiestTree do
@moduledoc """
A leftiest tree/heap implemtation with customizable priority and any type of item.
This tree always enforces the smallest priority at the top node, and the left path of tree is higher than right.
See https://en.wikipedia.org/wiki/Leftist_tree for algorithm details.
"""
@enforce_keys [:priority, :item]
defstruct left: nil, right: nil, priority: nil, item: :empty_tree, s_value: 1
@doc """
Returns a single node leftiest tree, with item and priority.
## Examples
iex> Heap.LeftiestTree.single(1, 1)
...> |> Heap.LeftiestTree.size
1
"""
@spec single(any, any) :: %Heap.LeftiestTree{
item: any,
left: nil,
priority: any,
right: nil,
s_value: 1
}
def single(item, priority) do
%Heap.LeftiestTree{priority: priority, item: item}
end
@doc """
Returns a single node leftest tree, with item and use this item as priority.
## Examples
iex> Heap.LeftiestTree.single(1)
...> |> Heap.LeftiestTree.size
1
"""
@spec single(any) :: %Heap.LeftiestTree{
item: any,
left: nil,
priority: any,
right: nil,
s_value: 1
}
def single(item) do
single(item, item)
end
@doc """
Returns true if the leftest tree is empty.
NOTE: the nil is an empty leftest tree also.
## Examples
iex> Heap.LeftiestTree.single(1)
...> |> Heap.LeftiestTree.empty?
false
"""
@spec empty?(atom | %{:item => any, optional(any) => any}) :: boolean
def empty?(nil) do
true
end
def empty?(tree) do
tree.item == :empty_tree
end
@doc """
Returns the top node of tree. If the tree is empty, returns {:error, "empty tree"}, otherwise returns {:ok, %{priority: ..., item: ...}}
## Examples
iex> Heap.LeftiestTree.single(1)
...> |> Heap.LeftiestTree.top
{:ok, %{priority: 1, item: 1}}
iex> Heap.LeftiestTree.single(1)
...> |> Heap.LeftiestTree.pop
...> |> Heap.LeftiestTree.top
{:error, "empty tree"}
"""
def top(tree) do
cond do
empty?(tree) -> {:error, "empty tree"}
true -> {:ok, %{priority: tree.priority, item: tree.item}}
end
end
@doc """
Removes the topest node of tree, rebalances the tree, and returns. Do nothing if tree is empty.
## Examples
iex> Heap.LeftiestTree.single(1)
...> |> Heap.LeftiestTree.pop
...> |> Heap.LeftiestTree.empty?
true
iex> Heap.LeftiestTree.single(1)
...> |> Heap.LeftiestTree.pop
...> |> Heap.LeftiestTree.pop
nil
"""
def pop(tree) do
cond do
empty?(tree) -> nil
true -> merge(tree.left, tree.right)
end
end
@doc """
Merges two leftiest trees into a leftiest tree.
## Examples
iex> nil
...> |> Heap.LeftiestTree.merge(Heap.LeftiestTree.single(1))
...> |> Heap.LeftiestTree.merge(nil)
...> |> Heap.LeftiestTree.merge(Heap.LeftiestTree.single(-1))
...> |> Heap.LeftiestTree.to_list
[%{item: 1, priority: 1}, %{item: -1, priority: -1}]
"""
def merge(tree1, tree2) do
cond do
empty?(tree1) ->
tree2
empty?(tree2) ->
tree1
tree1.priority > tree2.priority ->
merge_impl(tree2, tree1)
true ->
merge_impl(tree1, tree2)
end
end
@doc """
Returns the number of elements in tree.
## Examples
iex> nil |> Heap.LeftiestTree.size
0
iex> Heap.LeftiestTree.single(1) |> Heap.LeftiestTree.size
1
"""
def size(tree) do
size_impl(tree, 0)
end
defp size_impl(tree, acc) do
cond do
empty?(tree) -> acc
# tail call optimization for left or right is empty
empty?(tree.left) -> size_impl(tree.right, acc + 1)
empty?(tree.right) -> size_impl(tree.left, acc + 1)
# general situation.
# it could cause stack overflow if the right tree is too deep.
true -> size_impl(tree.left, size_impl(tree.right, acc + 1))
end
end
defp merge_impl(tree1, tree2) do
merged_tree = merge(tree1.right, tree2)
cond do
tree1.left == nil ->
%Heap.LeftiestTree{
left: merged_tree,
right: nil,
priority: tree1.priority,
item: tree1.item,
s_value: 1
}
# always make the left tree's s_value is larger than right tree.
# the returned tree's s_value = the returned tree.right.s_value + 1
tree1.left.s_value < merged_tree.s_value ->
%Heap.LeftiestTree{
left: merged_tree,
right: tree1.left,
priority: tree1.priority,
item: tree1.item,
s_value: tree1.left.s_value + 1
}
true ->
%Heap.LeftiestTree{
left: tree1.left,
right: merged_tree,
priority: tree1.priority,
item: tree1.item,
s_value: merged_tree.s_value + 1
}
end
end
@doc """
Returns the list of %{priority: ..., item:, ...} ordered by priority descendingly.
## Examples
iex> Heap.LeftiestTree.single(-10)
...> |> Heap.LeftiestTree.merge(Heap.LeftiestTree.single(1))
...> |> Heap.LeftiestTree.merge(Heap.LeftiestTree.single(3))
...> |> Heap.LeftiestTree.merge(Heap.LeftiestTree.single(-1))
...> |> Heap.LeftiestTree.to_list
[%{item: 3, priority: 3}, %{item: 1, priority: 1}, %{item: -1, priority: -1}, %{item: -10, priority: -10}]
"""
def to_list(tree) do
to_list_impl(tree, [])
end
defp to_list_impl(tree, acc) do
case top(tree) do
{:error, _} ->
acc
{:ok, top_elem} ->
sub_tree = merge(tree.left, tree.right)
to_list_impl(sub_tree, [top_elem | acc])
end
end
end