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