"""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,
)
