|
1
|
1 |
|
import operator |
|
2
|
1 |
|
import itertools |
|
3
|
|
|
|
|
4
|
1 |
|
from ppp_datamodel.nodes import Resource |
|
5
|
1 |
|
from ppp_datamodel.nodes.list_operators import * |
|
6
|
|
|
|
|
7
|
1 |
|
__all__ = ['simplify'] |
|
8
|
|
|
|
|
9
|
1 |
|
def partition(pred, list_): |
|
10
|
|
|
# Partition the items in lists / non-lists |
|
11
|
1 |
|
list_ = [x for x in list_ if x] |
|
12
|
1 |
|
lists = filter(pred, list_) |
|
13
|
1 |
|
not_lists = itertools.filterfalse(pred, list_) |
|
14
|
1 |
|
return (lists, not_lists) |
|
15
|
|
|
|
|
16
|
1 |
|
def simplify_union(tree): |
|
17
|
|
|
# Trivial cases |
|
18
|
1 |
|
if len(tree.list) == 0: |
|
19
|
1 |
|
return List([]) |
|
20
|
1 |
|
elif len(tree.list) == 1: |
|
21
|
1 |
|
return tree.list[0] |
|
22
|
|
|
|
|
23
|
1 |
|
(lists, non_lists) = partition(lambda x:isinstance(x, (List, Resource)), |
|
24
|
|
|
tree.list) |
|
25
|
|
|
# Make union of lists |
|
26
|
1 |
|
lists = [x.list if isinstance(x, List) else [x] for x in lists] |
|
27
|
1 |
|
lists = list(set(itertools.chain(*lists))) |
|
28
|
|
|
|
|
29
|
1 |
|
non_lists = list(non_lists) |
|
30
|
1 |
|
if lists: |
|
31
|
1 |
|
all_ = non_lists |
|
32
|
1 |
|
all_.append(List(lists)) |
|
33
|
1 |
|
return Union(all_) |
|
34
|
|
|
elif len(non_lists) == 1: |
|
35
|
|
|
return non_lists |
|
36
|
|
|
else: |
|
37
|
|
|
return Union(non_lists) |
|
38
|
|
|
|
|
39
|
1 |
|
def simplify_intersection(tree): |
|
40
|
|
|
# Trivial cases |
|
41
|
1 |
|
if len(tree.list) == 0: |
|
42
|
1 |
|
return tree |
|
43
|
1 |
|
elif len(tree.list) == 1: |
|
44
|
1 |
|
return tree.list[0] |
|
45
|
|
|
|
|
46
|
1 |
|
(a, b) = partition(lambda x:isinstance(x, (List, Resource)), tree.list) |
|
47
|
1 |
|
(lists, non_lists) = partition(lambda x:isinstance(x, (List, Resource)), |
|
48
|
|
|
tree.list) |
|
49
|
1 |
|
lists = list(lists) |
|
50
|
|
|
# Make intersection of lists |
|
51
|
1 |
|
try: |
|
52
|
|
|
# Efficient algorithm if everything is hashable |
|
53
|
1 |
|
lists = [set(x.list) if isinstance(x, List) else {x} for x in lists] or [set()] |
|
54
|
1 |
|
lists = list(lists[0].intersection(*lists[1:])) |
|
55
|
1 |
|
except TypeError: |
|
56
|
|
|
# If there is a non-hashable value, fallback to a less efficient algorithm |
|
57
|
1 |
|
lists = [x.list if isinstance(x, List) else [x] for x in lists] or [[]] |
|
58
|
1 |
|
intersected_lists = list(lists[0]) |
|
59
|
1 |
|
for l in lists[1:]: |
|
60
|
1 |
|
intersected_lists = [x for x in intersected_lists if x in l] |
|
61
|
1 |
|
lists = intersected_lists |
|
62
|
|
|
|
|
63
|
1 |
|
non_lists = list(non_lists) |
|
64
|
1 |
|
if lists: |
|
65
|
1 |
|
all_ = non_lists |
|
66
|
1 |
|
all_.append(simplify_list(List(lists))) |
|
67
|
1 |
|
return Intersection(all_) |
|
68
|
|
|
elif len(non_lists) == 1: |
|
69
|
|
|
return non_lists |
|
70
|
|
|
else: |
|
71
|
|
|
return Intersection(non_lists) |
|
72
|
|
|
|
|
73
|
1 |
|
def simplify_list(tree): |
|
74
|
1 |
|
if len(tree.list) == 1: |
|
75
|
1 |
|
return tree.list[0] |
|
76
|
|
|
else: |
|
77
|
1 |
|
return tree |
|
78
|
|
|
|
|
79
|
1 |
|
predicates = { |
|
80
|
|
|
Union: simplify_union, |
|
81
|
|
|
Intersection: simplify_intersection, |
|
82
|
|
|
List: simplify_list, |
|
83
|
|
|
} |
|
84
|
|
|
|
|
85
|
1 |
|
def predicate(tree): |
|
86
|
1 |
|
for (cls, f) in predicates.items(): |
|
87
|
1 |
|
if isinstance(tree, cls): |
|
88
|
1 |
|
return f(tree) |
|
89
|
1 |
|
return tree |
|
90
|
|
|
|
|
91
|
1 |
|
def simplify(tree): |
|
92
|
1 |
|
old_tree = None |
|
93
|
1 |
|
while old_tree != tree: |
|
94
|
1 |
|
old_tree = tree |
|
95
|
1 |
|
tree = tree.traverse(predicate) |
|
96
|
|
|
return tree |
|
97
|
|
|
|
ProjetPP /
PPP-libmodule-Python
