I have a python code like this:
class Node:
def __init__(self, path: str):
self.path = path
self.children = {}
class MultiTree:
def __init__(self, root="/"):
self.root = Node(root)
def build(self, lst: list):
for p in lst:
f = p.split("/")
pointer = self.root
for i in range(1, len(f)):
path = "/".join(f[:i+1])
if path not in pointer.children:
node = Node(path)
pointer.children[path] = node
pointer = node
else:
pointer = pointer.children[path]
def dfs(self, root):
stack, res = [], []
stack.append(root)
while len(stack):
curr = stack.pop()
if curr.path not in res:
res.append(curr.path)
stack.extend(reversed(list(curr.children.values())))
return res
That’s a solution to construct a directory tree.
For example, given a dataset like:
list = ["/2/3", “/2/4”, “/2/4/6”, “/2/3/7”, “/2/3/5”, “/2/3/8”]
the output of dfs will be:
[’/’, ‘/2’, ‘/2/3’, ‘/2/3/7’, ‘/2/3/5’, ‘/2/3/8’, ‘/2/4’, ‘/2/4/6’]
Now in Elixir, i don’t know how to return the root.
would anyone met the similar situation?
My solution is:
defmodule MultiTree do
defmodule Node do
defstruct path: nil, children: %{}
end
@root "/"
def tree_root(list) do
root = list
|> Enum.reduce(%Node{}, fn p, root ->
f = Enum.drop(String.split(p, "/"), 1)
build(f, f, root)
end)
%Node{ path: @root, children: root }
end
defp build([], full_list, root) do
root
end
defp build([_ | children], full_list, root) do
eol = Enum.count(full_list) - Enum.count(children)
path = "/" <> Enum.join(Enum.slice(full_list, 0..eol-1), "/")
%Node{path: path, children: build(children, full_list, root)}
end
def dfs() do
end
end
However, there’s a problem… The keys are duplicated, for example:
list = ["/2/3", "/2/4", "/2/3/5"]
tree = MultiTree.tree_root(list)
IO.inspect(tree)
The output is:
%MultiTree.Node{
children: %MultiTree.Node{
children: %MultiTree.Node{
children: %MultiTree.Node{
children: %MultiTree.Node{
children: %MultiTree.Node{
children: %MultiTree.Node{
children: %MultiTree.Node{
children: %MultiTree.Node{children: %{}, path: nil},
path: "/2/3"
},
path: "/2"
},
path: "/2/4"
},
path: "/2"
},
path: "/2/3/5"
},
path: "/2/3"
},
path: "/2"
},
path: "/"
}
The expected output should be:
path: "/":
children: {"/2":
{path: "/2",
children: {"/2/3": {path: "/2/3",
children: {"/2/3/4": {path: "/2/3/4", children: {}},
{"/2/3/5}: {path: "/2/3/5", children: {}}
},
},
"/2/4": {path: "/2/4", children: {} }}}}
I also wrote a non-recursion one:
def build_tree(list) do
root = list
|> Enum.reduce(%Node{}, fn p, root ->
f = Enum.drop(String.split(p, "/"), 1)
pointer = root
Enum.reduce(1..Enum.count(f), fn i, _ ->
path = Enum.join(Enum.slice(f, 0..i+1), "/")
ele = Map.get(pointer.children, path)
pointer =
if ele == nil do
node = %Node{ path: path }
Map.put(pointer.children, path, node)
node
else
ele
end
end)
end)
%Node{ path: @root, children: root }
end
however it’s not right…
