Repository navigation
Expand file tree
/
Copy pathsimplification.py
More file actions
96 lines (83 loc) · 2.75 KB
/
Copy pathsimplification.py
File metadata and controls
96 lines (83 loc) · 2.75 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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import operator
import itertools
from ppp_datamodel.nodes import Resource
from ppp_datamodel.nodes.list_operators import *
__all__ = ['simplify']
def partition(pred, list_):
# Partition the items in lists / non-lists
list_ = [x for x in list_ if x]
lists = list(filter(pred, list_))
not_lists = itertools.filterfalse(pred, list_)
return (lists, not_lists)
def simplify_union(tree):
# Trivial cases
if len(tree.list) == 0:
return List([])
elif len(tree.list) == 1:
return tree.list[0]
(lists, non_lists) = partition(lambda x:isinstance(x, (List, Resource)),
tree.list)
# Make union of lists
lists = [x.list if isinstance(x, List) else [x] for x in lists]
lists = list(set(itertools.chain(*lists)))
non_lists = list(non_lists)
if lists:
all_ = non_lists
all_.append(List(lists))
return Union(all_)
elif len(non_lists) == 1:
return non_lists
else:
return Union(non_lists)
def simplify_intersection(tree):
# Trivial cases
if len(tree.list) == 0:
return tree
elif len(tree.list) == 1:
return tree.list[0]
(a, b) = partition(lambda x:isinstance(x, (List, Resource)), tree.list)
(lists, non_lists) = partition(lambda x:isinstance(x, (List, Resource)),
tree.list)
lists = list(lists)
# Make intersection of lists
try:
# Efficient algorithm if everything is hashable
lists = [set(x.list) if isinstance(x, List) else {x} for x in lists] or [set()]
lists = list(lists[0].intersection(*lists[1:]))
except TypeError:
# If there is a non-hashable value, fallback to a less efficient algorithm
lists = [x.list if isinstance(x, List) else [x] for x in lists] or [[]]
intersected_lists = list(lists[0])
for l in lists[1:]:
intersected_lists = [x for x in intersected_lists if x in l]
lists = intersected_lists
non_lists = list(non_lists)
if lists:
all_ = non_lists
all_.append(simplify_list(List(lists)))
return Intersection(all_)
elif len(non_lists) == 1:
return non_lists
else:
return Intersection(non_lists)
def simplify_list(tree):
if len(tree.list) == 1:
return tree.list[0]
else:
return tree
predicates = {
Union: simplify_union,
Intersection: simplify_intersection,
List: simplify_list,
}
def predicate(tree):
for (cls, f) in list(predicates.items()):
if isinstance(tree, cls):
return f(tree)
return tree
def simplify(tree):
old_tree = None
while old_tree != tree:
old_tree = tree
tree = tree.traverse(predicate)
return tree