Weird … it’s like save the space no matter what (here I mean confusion of people new in topic). It’s my first time using it and such assumption looks really bad at this part. Anyway, in that case my first code would not work as there’s no algorithm which can dynamically count the proper index without so much context.
However my second example is really easy to modify. Here goes an updated version which handles both use cases depends on custom_count option:
defmodule TreeNode do
defstruct ~w[data left right]a
end
defmodule Example do
def sample(input, opts \\ [custom_count: false]) do
input |> split(opts) |> transform(nil, opts)
end
# we split a list by count
# on top is only root, so default count is always 1
# every other level have count * 2 nodes
defp split(list, acc \\ [], count \\ 1, opts) do
{left, right} = Enum.split(list, count)
# we call split until right side is empty
if right == [] do
[left | acc]
else
# after each split the left side is added to acc
# therefore we would have leafs list as fist item in acc
# and a single root data as last item of acc
count = if opts[:custom_count], do: Enum.count(left, &(&1 != -1)), else: count
split(right, [left | acc], count * 2, opts)
end
end
defp transform([leafs | groups], nil, opts) do
# transform leafs into initial acc
# which would be used in transform groups
transform(groups, {Enum.map(leafs, &transform_leaf/1), []}, opts)
end
# finishing by returning root node
defp transform([], {[root_node], []}, _opts), do: root_node
defp transform([[] | groups], {[], acc_right}, opts) do
# reached end of group
# all nodes we have collected in acc_right
# are moved to acc_left
# so they would be used in next group
transform(groups, {Enum.reverse(acc_right), []}, opts)
end
defp transform([[-1 | group] | groups], {acc_left, acc_right}, opts) do
# skipping -1 as it should not consume leafs
custom_count = opts[:custom_count]
acc_left =
case acc_left do
acc_left when custom_count == true -> acc_left
[] -> []
[nil, nil | acc_left] -> acc_left
end
transform([group | groups], {acc_left, [nil | acc_right]}, opts)
end
defp transform([[data | group] | groups], {[], acc_right}, opts) do
# node #{data} does not have children
transform([group | groups], {[], [transform_node(data) | acc_right]}, opts)
end
defp transform([[data | group] | groups], {[left], acc_right}, opts) do
# node #{data} have only left child
transform([group | groups], {[], [transform_node(data, left) | acc_right]}, opts)
end
defp transform([[data | group] | groups], {[left, right | acc_left], acc_right}, opts) do
# node #{data} have both children
transform([group | groups], {acc_left, [transform_node(data, left, right) | acc_right]}, opts)
end
defp transform_leaf(-1), do: nil
defp transform_leaf(data), do: %TreeNode{data: data}
defp transform_node(data, left \\ nil, right \\ nil) do
# transforming node
%TreeNode{data: data, left: left, right: right}
end
end
input = [5, 4, 8, 11, -1, 17, 4, 7, -1, -1, -1, 5, -1, -1, -1, -1]
iex> Example.sample(input)
%TreeNode{
data: 5,
left: %TreeNode{
data: 4,
left: %TreeNode{
data: 11,
left: %TreeNode{data: 7, left: nil, right: nil},
right: nil
},
right: nil
},
right: %TreeNode{
data: 8,
left: %TreeNode{
data: 17,
left: %TreeNode{data: 5, left: nil, right: nil},
right: nil
},
right: %TreeNode{data: 4, left: nil, right: nil}
}
}
iex> Example.sample(input, custom_count: true)
%TreeNode{
data: 5,
left: %TreeNode{
data: 4,
left: %TreeNode{
data: 11,
left: %TreeNode{data: 7, left: nil, right: nil},
right: nil
},
right: nil
},
right: %TreeNode{
data: 8,
left: %TreeNode{data: 17, left: nil, right: nil},
right: %TreeNode{
data: 4,
left: %TreeNode{data: 5, left: nil, right: nil},
right: nil
}
}
}
I changed only 2 things here:
- Optionally change the
count before passing to split/4 call
- Handling transformation of
-1 entries (case statement)
, its my 2nd day with elixir.
