1# Copyright 2018 The Bazel Authors. All rights reserved. 2# 3# Licensed under the Apache License, Version 2.0 (the "License"); 4# you may not use this file except in compliance with the License. 5# You may obtain a copy of the License at 6# 7# http://www.apache.org/licenses/LICENSE-2.0 8# 9# Unless required by applicable law or agreed to in writing, software 10# distributed under the License is distributed on an "AS IS" BASIS, 11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12# See the License for the specific language governing permissions and 13# limitations under the License. 14 15"""Skylib module containing common hash-set algorithms. 16 17 An empty set can be created using: `sets.make()`, or it can be created with some starting values 18 if you pass it an sequence: `sets.make([1, 2, 3])`. This returns a struct containing all of the 19 values as keys in a dictionary - this means that all passed in values must be hashable. The 20 values in the set can be retrieved using `sets.to_list(my_set)`. 21 22 An arbitrary object can be tested whether it is a set generated by `sets.make()` or not with the 23 `types.is_set()` method in types.bzl. 24""" 25 26load(":dicts.bzl", "dicts") 27 28def _make(elements = None): 29 """Creates a new set. 30 31 All elements must be hashable. 32 33 Args: 34 elements: Optional sequence to construct the set out of. 35 36 Returns: 37 A set containing the passed in values. 38 """ 39 40 # If you change the structure of a set, you need to also update the _is_set method 41 # in types.bzl. 42 elements = elements if elements else [] 43 return struct(_values = {e: None for e in elements}) 44 45def _copy(s): 46 """Creates a new set from another set. 47 48 Args: 49 s: A set, as returned by `sets.make()`. 50 51 Returns: 52 A new set containing the same elements as `s`. 53 """ 54 return struct(_values = dict(s._values)) 55 56def _to_list(s): 57 """Creates a list from the values in the set. 58 59 Args: 60 s: A set, as returned by `sets.make()`. 61 62 Returns: 63 A list of values inserted into the set. 64 """ 65 return s._values.keys() 66 67def _insert(s, e): 68 """Inserts an element into the set. 69 70 Element must be hashable. This mutates the original set. 71 72 Args: 73 s: A set, as returned by `sets.make()`. 74 e: The element to be inserted. 75 76 Returns: 77 The set `s` with `e` included. 78 """ 79 s._values[e] = None 80 return s 81 82def _remove(s, e): 83 """Removes an element from the set. 84 85 Element must be hashable. This mutates the original set. 86 87 Args: 88 s: A set, as returned by `sets.make()`. 89 e: The element to be removed. 90 91 Returns: 92 The set `s` with `e` removed. 93 """ 94 s._values.pop(e) 95 return s 96 97def _contains(a, e): 98 """Checks for the existence of an element in a set. 99 100 Args: 101 a: A set, as returned by `sets.make()`. 102 e: The element to look for. 103 104 Returns: 105 True if the element exists in the set, False if the element does not. 106 """ 107 return e in a._values 108 109def _get_shorter_and_longer(a, b): 110 """Returns two sets in the order of shortest and longest. 111 112 Args: 113 a: A set, as returned by `sets.make()`. 114 b: A set, as returned by `sets.make()`. 115 116 Returns: 117 `a`, `b` if `a` is shorter than `b` - or `b`, `a` if `b` is shorter than `a`. 118 """ 119 if _length(a) < _length(b): 120 return a, b 121 return b, a 122 123def _is_equal(a, b): 124 """Returns whether two sets are equal. 125 126 Args: 127 a: A set, as returned by `sets.make()`. 128 b: A set, as returned by `sets.make()`. 129 130 Returns: 131 True if `a` is equal to `b`, False otherwise. 132 """ 133 return a._values == b._values 134 135def _is_subset(a, b): 136 """Returns whether `a` is a subset of `b`. 137 138 Args: 139 a: A set, as returned by `sets.make()`. 140 b: A set, as returned by `sets.make()`. 141 142 Returns: 143 True if `a` is a subset of `b`, False otherwise. 144 """ 145 for e in a._values.keys(): 146 if e not in b._values: 147 return False 148 return True 149 150def _disjoint(a, b): 151 """Returns whether two sets are disjoint. 152 153 Two sets are disjoint if they have no elements in common. 154 155 Args: 156 a: A set, as returned by `sets.make()`. 157 b: A set, as returned by `sets.make()`. 158 159 Returns: 160 True if `a` and `b` are disjoint, False otherwise. 161 """ 162 shorter, longer = _get_shorter_and_longer(a, b) 163 for e in shorter._values.keys(): 164 if e in longer._values: 165 return False 166 return True 167 168def _intersection(a, b): 169 """Returns the intersection of two sets. 170 171 Args: 172 a: A set, as returned by `sets.make()`. 173 b: A set, as returned by `sets.make()`. 174 175 Returns: 176 A set containing the elements that are in both `a` and `b`. 177 """ 178 shorter, longer = _get_shorter_and_longer(a, b) 179 return struct(_values = {e: None for e in shorter._values.keys() if e in longer._values}) 180 181def _union(*args): 182 """Returns the union of several sets. 183 184 Args: 185 *args: An arbitrary number of sets. 186 187 Returns: 188 The set union of all sets in `*args`. 189 """ 190 return struct(_values = dicts.add(*[s._values for s in args])) 191 192def _difference(a, b): 193 """Returns the elements in `a` that are not in `b`. 194 195 Args: 196 a: A set, as returned by `sets.make()`. 197 b: A set, as returned by `sets.make()`. 198 199 Returns: 200 A set containing the elements that are in `a` but not in `b`. 201 """ 202 return struct(_values = {e: None for e in a._values.keys() if e not in b._values}) 203 204def _length(s): 205 """Returns the number of elements in a set. 206 207 Args: 208 s: A set, as returned by `sets.make()`. 209 210 Returns: 211 An integer representing the number of elements in the set. 212 """ 213 return len(s._values) 214 215def _repr(s): 216 """Returns a string value representing the set. 217 218 Args: 219 s: A set, as returned by `sets.make()`. 220 221 Returns: 222 A string representing the set. 223 """ 224 return repr(s._values.keys()) 225 226sets = struct( 227 make = _make, 228 copy = _copy, 229 to_list = _to_list, 230 insert = _insert, 231 contains = _contains, 232 is_equal = _is_equal, 233 is_subset = _is_subset, 234 disjoint = _disjoint, 235 intersection = _intersection, 236 union = _union, 237 difference = _difference, 238 length = _length, 239 remove = _remove, 240 repr = _repr, 241 str = _repr, 242 # is_set is declared in types.bzl 243) 244