That’s very clear, thanks very much .
There’s another point: the given list is ordered.
for example, gievn list = ["/2/3", “/2/4”, “/2/4/6”, “/2/3/7”, “/2/3/5”, “/2/3/8”]
output is [’/’, ‘/2’, ‘/2/3’, ‘/2/3/7’, ‘/2/3/5’, ‘/2/3/8’, ‘/2/4’, ‘/2/4/6’]
“/2/3/7” is ahead of “/2/3/5”.
so, I have to do some sort when building the tree or traveling it.
Actually the task is something below:
Given a list of items, each item with a directory and a create_time, my task is to sort those items by two rules:
- first rule: a given index_dict, only contains part of the items.
- second rule: when the first rule is not exist, use create_time.
Here is a real task example:
# The given items
[
%{ "location" => "/folder1", "create_time" => "2019-03-01" },
%{ "location" => "/folder1/folder1-folder1", "create_time" => "2019-03-02" },
%{ "location" => "/folder1/folder1-folder1/file1", "create_time" => "2019-03-10" },
%{ "location" => "/folder1/folder1-folder1/file2", "create_time" => "2019-03-01" },
%{ "location" => "/folder1/folder1-folder1/file3", "create_time" => "2019-03-03" },
%{ "location" => "/folder1/folder1-folder1/file4", "create_time" => "2019-03-02" },
%{ "location" => "/folder2", "create_time" => "2019-01-01" },
%{ "location" => "/folder2/folder2-folder1", "create_time" => "2019-01-20" },
%{ "location" => "/folder2/folder2-folder1/file1", "create_time" => "2019-01-22" },
%{ "location" => "/folder2/folder2-folder1/file2", "create_time" => "2019-01-21" },
%{ "location" => "/folder2/folder2-folder2", "create_time" => "2019-01-10" },
%{ "location" => "/folder2/folder2-folder2/file1", "create_time" => "2019-01-11" },
%{ "location" => "/folder2/folder2-folder2/file2", "create_time" => "2019-01-12" },
%{ "location" => "/folder3", "create_time" => "2019-02-01" },
%{ "location" => "/folder3/folder3-folder1", "create_time" => "2019-02-10" },
%{ "location" => "/folder3/folder3-folder1/file1", "create_time" => "2019-02-02" },
%{ "location" => "/folder3/folder3-folder1/file2", "create_time" => "2019-02-01" },
%{ "location" => "/folder3/folder3-folder2", "create_time" => "2019-02-01" },
%{ "location" => "/folder3/folder3-folder2/file1", "create_time" => "2019-02-03" },
%{ "location" => "/folder3/folder3-folder2/file2", "create_time" => "2019-02-04" },
%{ "location" => "/folder3/folder3-folder3", "create_time" => "2019-02-03" },
%{ "location" => "/folder3/folder3-folder3/file1", "create_time" => "2019-02-05" },
%{ "location" => "/folder3/folder3-folder3/file2", "create_time" => "2019-02-04" },
%{ "location" => "/folder3/folder3-folder4", "create_time" => "2019-02-02" }
]
# The given index_dict,
# PAY attention, they have different levels, and the map keys have no orders .
%{
"/folder1/folder1-folder1" => [
"/folder1/folder1-folder1/file1",
"/folder1/folder1-folder1/file2"
],
"/folder2/folder2-folder1" => [
"/folder2/folder2-folder1/file1",
"/folder2/folder2-folder1/file2",
],
"/folder2/folder2-folder2" => [
"/folder2/folder2-folder2/file1",
"/folder2/folder2-folder2/file2"
],
"/folder3" => [
"/folder3/folder3-folder1",
"/folder3/folder3-folder2"
],
}
The final expected order is
['/',
'/folder2',
'/folder2/folder2-folder2',
'/folder2/folder2-folder2/file1',
'/folder2/folder2-folder2/file2',
'/folder2/folder2-folder1',
'/folder2/folder2-folder1/file1',
'/folder2/folder2-folder1/file2',
'/folder3',
'/folder3/folder3-folder1',
'/folder3/folder3-folder1/file2',
'/folder3/folder3-folder1/file1',
'/folder3/folder3-folder2',
'/folder3/folder3-folder2/file1',
'/folder3/folder3-folder2/file2',
'/folder3/folder3-folder4',
'/folder3/folder3-folder3',
'/folder3/folder3-folder3/file2',
'/folder3/folder3-folder3/file1',
'/folder1',
'/folder1/folder1-folder1',
'/folder1/folder1-folder1/file1',
'/folder1/folder1-folder1/file2',
'/folder1/folder1-folder1/file4',
'/folder1/folder1-folder1/file3']
Let me expain
“/folder1”, “/folder2” and “/folder3” are not in the index_dict, so they are sorted by create_time:
“/folder2” > “/folder3” > “/folder1”
then, Let’s loot at the subfolders of folder2
“/folder2/folder2-folder1” and “/folder2/folder2-folder2” are also not in the index_dict (values), so they are sorted by create_time
“/folder2/folder2-folder2” > “/folder2/folder2-folder1”
then, their subdirectories (here are files)
although “/folder2/folder2-folder1/file2” > “/folder2/folder2-folder1/file1” by create_time, in the index_dict, “file1” > “file2”, so the result is ‘/folder2/folder2-folder1/file1’ > ‘/folder2/folder2-folder1/file2’.
Another example, let’s look at folder3, they have sub folders in the index_dict, so sub folders need to be sorted like that
‘/folder3/folder3-folder1’ > ‘/folder3/folder3-folder2’, then ‘/folder3/folder3-folder4’ > ‘/folder3/folder3-folder3’, by their create_time.
My python code is
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]
@staticmethod
def dfs(root, index_dict):
stack, res = [], []
stack.append(root)
while len(stack):
curr = stack.pop()
if curr.path not in res:
res.append(curr.path)
children = list(curr.children.values())
if curr.path in index_dict:
index_list = index_dict[curr.path]
for item in curr.children.values():
if item.path not in index_list:
index_list.append(item.path)
children = sorted(children, key=lambda x:index_list.index(x.path))
stack.extend(reversed(children))
return res
# data is the given items
# index is the given index_dict
sorted_data = sorted(data, key=lambda x:x["create_time"])
sorted_loc = [w["location"] for w in sorted_data]
tree = MultiTree()
tree.build(sorted_loc)
ft = tree.dfs(tree.root, index)
# ft is the final expected order above.
I have written this task with python in three different ways
- the above one
- sort directly on nested structure with defaultdict
- sort hierarchically with or without tree
However, i can’t do it by Elixir, i am really frustrated though i am new to it…
Maybe i need some more exercise…
If anyone who met this issue before, i feel grateful if you give me some advice.
