Repository navigation
Expand file tree
/
Copy pathtree.py
More file actions
73 lines (57 loc) · 2.13 KB
/
Copy pathtree.py
File metadata and controls
73 lines (57 loc) · 2.13 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class TreeNode:
def __init__(self, **kwargs):
self.children = dict()
def get(self, key):
return self.children.get(key, None)
def get_children(self, sort=False):
if sort:
return sorted(self.children.values())
return self.children.values()
def add(self, key, node=None, **kwargs):
if key not in self.children:
if node is None:
node = self.__class__(**kwargs)
self.children[key] = node
return self.children[key]
def set(self, key, val, **kwargs):
self.children[key] = val
return self.children[key]
class OrderedTreeNode:
def __init__(self, **kwargs):
self.children = list()
def get(self, index):
return self.children[index]
def get_children(self, sort=False):
if sort:
return sorted(self.children)
return self.children
def add(self, node=None, **kwargs):
if node is None:
node = self.__class__(**kwargs)
self.children.append(node)
return self.children[-1]
def set(self, index, val, **kwargs):
self.children[index] = val
return self.children[index]
class Tree:
def __init__(self, root=None, node_class=TreeNode, **kwargs):
if root is None:
root = node_class(**kwargs)
self.root = root
self.node_class = node_class
def get_children(self, node, sort=False):
return node.get_children(sort=sort)
def dfs(self, action=None, pre_action=None, post_action=None, sort=False):
assert(action is None or (pre_action is None and post_action is None))
if action is not None and pre_action is None and post_action is None:
pre_action = post_action = action
def visit(node, depth=0, parent=None):
if pre_action:
if pre_action(node, depth, parent):
return
for n in self.get_children(node, sort=sort):
visit(n, depth+1, node)
if post_action:
if post_action(node, depth, parent):
return
visit(self.root)