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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
"""Immutable sets that support efficient merging, traversal, and membership
check.
"""
def _empty():
"""Create an empty set.
Returns:
set, new empty set.
"""
return struct(_set_items = dict())
def _singleton(e):
"""Create a set with single element `e` inside.
Args:
e: The element to put in the set.
Returns:
set, new set.
"""
r = dict()
r[e] = None
return struct(_set_items = r)
def _is_member(s, e):
"""Return true if `e` is in the set `s`.
Args:
s: The set to inspect.
e: The element to search for.
Result:
Bool, true if `e` is in `s`, false otherwise.
"""
return e in s._set_items
def _insert(s, e):
"""Insert an element into the set.
Args:
s: Set to insert new element into.
e: The element to insert.
Result:
A copy of set `s` with `s` element added.
"""
r = dict(s._set_items)
r[e] = None
return struct(_set_items = r)
def _mutable_insert(s, e):
"""The same as `set.insert`, but modifies the first argument in place.
Args:
s: Set to insert new element into.
e: The element to insert.
Result:
set `s` with `s` element added.
"""
s._set_items[e] = None
return s
def _union(s0, s1):
"""Return union of two sets.
Args:
s0: One set.
s1: Another set.
Result:
set, union of the two sets.
"""
r = dict(s0._set_items)
r.update(s1._set_items)
return struct(_set_items = r)
def _mutable_union(s0, s1):
"""Modify set `s0` adding elements from `s1` to it.
Args:
s0: One set.
s1: Another set.
Result:
set, union of the two sets.
"""
s0._set_items.update(s1._set_items)
return s0
def _map(s, f):
"""Map elements of given set using a function.
Args:
s: Original set.
f: Function to apply to elements of the set.
Result:
set with elements obtained by application of function `f` to the
elements of `s`.
"""
return struct(_set_items = {f(x): None for x in s._set_items.keys()})
def _from_list(l):
"""Create a set containing elements from given list.
Args:
l: List, source of the elements for the new set.
Result:
set containing elements from given list.
"""
return (struct(_set_items = {x: None for x in l}))
def _to_list(s):
"""Convert set into a list of its elements.
Args:
s: Set to convert.
Returns:
List of elements of the set.
"""
return s._set_items.keys()
def _to_depset(s):
"""Similar to `set.to_list`, but produces a depset.
Args:
s: Set to convert.
Returns:
Depset of elements from the set.
"""
return depset(_to_list(s))
set = struct(
empty = _empty,
singleton = _singleton,
is_member = _is_member,
insert = _insert,
mutable_insert = _mutable_insert,
union = _union,
mutable_union = _mutable_union,
map = _map,
from_list = _from_list,
to_list = _to_list,
to_depset = _to_depset,
)
|
