paul@6 | 1 | #!/usr/bin/env python |
paul@6 | 2 | |
paul@6 | 3 | """ |
paul@6 | 4 | Set objects. |
paul@6 | 5 | |
paul@528 | 6 | Copyright (C) 2015, 2016, 2017 Paul Boddie <paul@boddie.org.uk> |
paul@6 | 7 | |
paul@6 | 8 | This program is free software; you can redistribute it and/or modify it under |
paul@6 | 9 | the terms of the GNU General Public License as published by the Free Software |
paul@6 | 10 | Foundation; either version 3 of the License, or (at your option) any later |
paul@6 | 11 | version. |
paul@6 | 12 | |
paul@6 | 13 | This program is distributed in the hope that it will be useful, but WITHOUT |
paul@6 | 14 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS |
paul@6 | 15 | FOR A PARTICULAR PURPOSE. See the GNU General Public License for more |
paul@6 | 16 | details. |
paul@6 | 17 | |
paul@6 | 18 | You should have received a copy of the GNU General Public License along with |
paul@6 | 19 | this program. If not, see <http://www.gnu.org/licenses/>. |
paul@6 | 20 | """ |
paul@6 | 21 | |
paul@542 | 22 | from __builtins__.mapping import hashtable |
paul@528 | 23 | |
paul@542 | 24 | class frozenset(hashtable): |
paul@542 | 25 | |
paul@542 | 26 | "An immutable set representation holding a collection of distinct values." |
paul@542 | 27 | |
paul@542 | 28 | def __init__(self, iterable=None): |
paul@542 | 29 | |
paul@542 | 30 | "Initialise the set with any given 'iterable'." |
paul@542 | 31 | |
paul@542 | 32 | self.clear() |
paul@542 | 33 | |
paul@542 | 34 | if iterable is not None: |
paul@542 | 35 | for value in iterable: |
paul@542 | 36 | self._setitem(self.buckets, value) |
paul@542 | 37 | |
paul@542 | 38 | # Implementation methods. |
paul@542 | 39 | |
paul@544 | 40 | def _find_entry(self, buckets, value, index): |
paul@542 | 41 | |
paul@544 | 42 | """ |
paul@544 | 43 | Search in 'buckets' for 'value', using an 'index' identifying the bucket |
paul@544 | 44 | involved. |
paul@544 | 45 | """ |
paul@542 | 46 | |
paul@542 | 47 | i = 0 |
paul@542 | 48 | |
paul@544 | 49 | for found in buckets[index]: |
paul@542 | 50 | if found == value: |
paul@542 | 51 | return i |
paul@542 | 52 | i += 1 |
paul@542 | 53 | |
paul@542 | 54 | return None |
paul@542 | 55 | |
paul@542 | 56 | def _resize(self, capacity): |
paul@542 | 57 | |
paul@542 | 58 | "Resize the hashtable to have the given 'capacity'." |
paul@542 | 59 | |
paul@542 | 60 | buckets = self._get_buckets(capacity) |
paul@542 | 61 | |
paul@542 | 62 | for value in self._items(): |
paul@542 | 63 | self._setitem(buckets, value) |
paul@542 | 64 | |
paul@542 | 65 | self.buckets = buckets |
paul@542 | 66 | |
paul@542 | 67 | def _setitem(self, buckets, value): |
paul@6 | 68 | |
paul@542 | 69 | "Set in the 'buckets' an item having the given 'value'." |
paul@542 | 70 | |
paul@544 | 71 | index, i = self._get_entry(buckets, value) |
paul@542 | 72 | |
paul@542 | 73 | # With no existing entry, append to the bucket. |
paul@542 | 74 | |
paul@542 | 75 | if i is None: |
paul@542 | 76 | buckets[index].append(value) |
paul@542 | 77 | self.size += 1 |
paul@542 | 78 | |
paul@542 | 79 | # With an existing entry, replace the item. |
paul@542 | 80 | |
paul@542 | 81 | else: |
paul@542 | 82 | buckets[index][i] = value |
paul@542 | 83 | |
paul@542 | 84 | # String representations. |
paul@542 | 85 | |
paul@542 | 86 | def _str(self, name): |
paul@542 | 87 | |
paul@542 | 88 | "Return a string representation." |
paul@542 | 89 | |
paul@542 | 90 | b = buffer() |
paul@542 | 91 | b.append(name) |
paul@542 | 92 | b.append("(") |
paul@542 | 93 | b.append(self._items().__repr__()) |
paul@542 | 94 | b.append(")") |
paul@542 | 95 | return str(b) |
paul@542 | 96 | |
paul@542 | 97 | def __str__(self): |
paul@542 | 98 | |
paul@542 | 99 | "Return a string representation." |
paul@542 | 100 | |
paul@542 | 101 | return self._str("frozenset") |
paul@542 | 102 | |
paul@542 | 103 | __repr__ = __str__ |
paul@542 | 104 | |
paul@542 | 105 | # Public special methods. |
paul@542 | 106 | |
paul@542 | 107 | def __contains__(self, value): |
paul@542 | 108 | |
paul@542 | 109 | "Return whether 'value' is in the set." |
paul@542 | 110 | |
paul@544 | 111 | index, i = self._get_entry(self.buckets, value) |
paul@542 | 112 | return i is not None |
paul@6 | 113 | |
paul@6 | 114 | def __iter__(self): |
paul@6 | 115 | |
paul@6 | 116 | "Return an iterator." |
paul@6 | 117 | |
paul@544 | 118 | return setiterator(self) |
paul@6 | 119 | |
paul@542 | 120 | # Public conventional methods. |
paul@542 | 121 | |
paul@544 | 122 | def copy(self): |
paul@544 | 123 | |
paul@544 | 124 | "Return a copy of this set." |
paul@544 | 125 | |
paul@544 | 126 | result = set() |
paul@544 | 127 | result.update(self) |
paul@544 | 128 | return result |
paul@544 | 129 | |
paul@544 | 130 | def difference(self, other): |
paul@544 | 131 | |
paul@544 | 132 | """ |
paul@544 | 133 | Return a set containing only those values in this set that are not in |
paul@544 | 134 | 'other'. |
paul@544 | 135 | """ |
paul@544 | 136 | |
paul@544 | 137 | result = set() |
paul@544 | 138 | |
paul@544 | 139 | for value in self: |
paul@544 | 140 | if value not in other: |
paul@544 | 141 | result.add(value) |
paul@544 | 142 | |
paul@544 | 143 | return result |
paul@544 | 144 | |
paul@544 | 145 | def intersection(self, other): |
paul@544 | 146 | |
paul@544 | 147 | "Return a set containing only those values in this set and in 'other'." |
paul@544 | 148 | |
paul@544 | 149 | result = set() |
paul@544 | 150 | |
paul@544 | 151 | for value in self: |
paul@544 | 152 | if value in other: |
paul@544 | 153 | result.add(value) |
paul@544 | 154 | |
paul@544 | 155 | return result |
paul@544 | 156 | |
paul@544 | 157 | def issubset(self, other): |
paul@544 | 158 | |
paul@544 | 159 | "Return whether this set is a subset of 'other'." |
paul@544 | 160 | |
paul@544 | 161 | for value in self: |
paul@544 | 162 | if value not in other: |
paul@544 | 163 | return False |
paul@544 | 164 | |
paul@544 | 165 | return True |
paul@544 | 166 | |
paul@544 | 167 | def issuperset(self, other): |
paul@544 | 168 | |
paul@544 | 169 | "Return whether this set is a superset of 'other'." |
paul@544 | 170 | |
paul@544 | 171 | for value in other: |
paul@544 | 172 | if value not in self: |
paul@544 | 173 | return False |
paul@544 | 174 | |
paul@544 | 175 | return True |
paul@544 | 176 | |
paul@544 | 177 | def symmetric_difference(self, other): |
paul@544 | 178 | |
paul@544 | 179 | """ |
paul@544 | 180 | Return a set containing only the values either in this set or in 'other' |
paul@544 | 181 | but not in both. |
paul@544 | 182 | """ |
paul@544 | 183 | |
paul@544 | 184 | result = set() |
paul@544 | 185 | |
paul@544 | 186 | for value in self: |
paul@544 | 187 | if value not in other: |
paul@544 | 188 | result.add(value) |
paul@544 | 189 | |
paul@544 | 190 | for value in other: |
paul@544 | 191 | if value not in self: |
paul@544 | 192 | result.add(value) |
paul@544 | 193 | |
paul@544 | 194 | return result |
paul@544 | 195 | |
paul@544 | 196 | def union(self, other): |
paul@544 | 197 | |
paul@544 | 198 | "Return a set combining this set and 'other'." |
paul@544 | 199 | |
paul@544 | 200 | result = set() |
paul@544 | 201 | |
paul@544 | 202 | for value in self: |
paul@544 | 203 | result.add(value) |
paul@544 | 204 | |
paul@544 | 205 | for value in other: |
paul@544 | 206 | result.add(value) |
paul@544 | 207 | |
paul@544 | 208 | return result |
paul@542 | 209 | |
paul@542 | 210 | class set(frozenset): |
paul@542 | 211 | |
paul@542 | 212 | "A mutable set representation holding a collection of distinct values." |
paul@542 | 213 | |
paul@542 | 214 | # String representation methods. |
paul@542 | 215 | |
paul@542 | 216 | def __str__(self): |
paul@542 | 217 | |
paul@542 | 218 | "Return a string representation." |
paul@542 | 219 | |
paul@542 | 220 | return self._str("set") |
paul@542 | 221 | |
paul@542 | 222 | __repr__ = __str__ |
paul@542 | 223 | |
paul@542 | 224 | # Public conventional methods. |
paul@542 | 225 | |
paul@542 | 226 | def add(self, value): |
paul@542 | 227 | |
paul@542 | 228 | "Add the given 'value' to the set." |
paul@542 | 229 | |
paul@542 | 230 | capacity = len(self.buckets) |
paul@542 | 231 | |
paul@542 | 232 | if self.size > capacity: |
paul@542 | 233 | self._resize(capacity * 2) |
paul@542 | 234 | |
paul@542 | 235 | self._setitem(self.buckets, value) |
paul@542 | 236 | |
paul@544 | 237 | def difference_update(self, other): |
paul@544 | 238 | |
paul@544 | 239 | "Remove from this set all values from 'other'." |
paul@544 | 240 | |
paul@544 | 241 | for value in other: |
paul@544 | 242 | self.remove(value) |
paul@542 | 243 | |
paul@542 | 244 | def discard(self, value): |
paul@542 | 245 | |
paul@542 | 246 | "Remove 'value' from the set, if present." |
paul@542 | 247 | |
paul@542 | 248 | try: |
paul@542 | 249 | self.remove(value) |
paul@542 | 250 | except KeyError: |
paul@542 | 251 | pass |
paul@542 | 252 | |
paul@544 | 253 | def intersection_update(self, other): |
paul@544 | 254 | |
paul@544 | 255 | "Preserve in this set only values in this set found in 'other'." |
paul@544 | 256 | |
paul@544 | 257 | for value in self: |
paul@544 | 258 | if value not in other: |
paul@544 | 259 | self.remove(value) |
paul@544 | 260 | |
paul@544 | 261 | def pop(self): |
paul@542 | 262 | |
paul@544 | 263 | "Remove and return an arbitrary value." |
paul@544 | 264 | |
paul@544 | 265 | # Get the last element from the first non-empty bucket. |
paul@544 | 266 | |
paul@544 | 267 | for bucket in self.buckets: |
paul@544 | 268 | if bucket: |
paul@544 | 269 | self.size -= 1 |
paul@544 | 270 | return bucket.pop() |
paul@544 | 271 | |
paul@544 | 272 | raise KeyError |
paul@542 | 273 | |
paul@542 | 274 | def remove(self, value): |
paul@542 | 275 | |
paul@542 | 276 | "Remove 'value' from the set." |
paul@542 | 277 | |
paul@542 | 278 | self._remove_entry(value) |
paul@542 | 279 | |
paul@544 | 280 | def symmetric_difference_update(self, other): |
paul@544 | 281 | |
paul@544 | 282 | """ |
paul@544 | 283 | Remove from this set all values found in 'other', adding values only |
paul@544 | 284 | found in 'other'. |
paul@544 | 285 | """ |
paul@544 | 286 | |
paul@544 | 287 | to_add = other.difference(self) |
paul@544 | 288 | self.difference_update(other) |
paul@544 | 289 | self.update(to_add) |
paul@544 | 290 | |
paul@544 | 291 | def update(self, other): |
paul@544 | 292 | |
paul@544 | 293 | "Update this set using the contents of 'other'." |
paul@544 | 294 | |
paul@544 | 295 | for value in other: |
paul@544 | 296 | self.add(value) |
paul@544 | 297 | |
paul@544 | 298 | class setiterator: |
paul@544 | 299 | |
paul@544 | 300 | "An iterator for set types." |
paul@544 | 301 | |
paul@544 | 302 | def __init__(self, mapping): |
paul@544 | 303 | |
paul@544 | 304 | "Initialise the iterator with the given 'mapping'." |
paul@542 | 305 | |
paul@544 | 306 | self.mapping = mapping |
paul@544 | 307 | self.index = 0 |
paul@544 | 308 | self.i = 0 |
paul@544 | 309 | |
paul@544 | 310 | def next(self): |
paul@544 | 311 | |
paul@544 | 312 | "Return the next value." |
paul@544 | 313 | |
paul@544 | 314 | while True: |
paul@544 | 315 | |
paul@544 | 316 | # Access the current bucket. If no such bucket exists, stop. |
paul@544 | 317 | |
paul@544 | 318 | try: |
paul@544 | 319 | bucket = self.mapping.buckets[self.index] |
paul@544 | 320 | except IndexError: |
paul@544 | 321 | raise StopIteration |
paul@544 | 322 | |
paul@544 | 323 | # Access the current item. If no such item exists, get another |
paul@544 | 324 | # bucket. |
paul@544 | 325 | |
paul@544 | 326 | try: |
paul@544 | 327 | value = bucket[self.i] |
paul@544 | 328 | self.i += 1 |
paul@544 | 329 | return value |
paul@544 | 330 | |
paul@544 | 331 | except IndexError: |
paul@544 | 332 | self.index += 1 |
paul@544 | 333 | self.i = 0 |
paul@6 | 334 | |
paul@6 | 335 | # vim: tabstop=4 expandtab shiftwidth=4 |