Package SCons :: Package compat :: Module _scons_sets
[hide private]
[frames] | no frames]

Source Code for Module SCons.compat._scons_sets

  1  """Classes to represent arbitrary sets (including sets of sets). 
  2   
  3  This module implements sets using dictionaries whose values are 
  4  ignored.  The usual operations (union, intersection, deletion, etc.) 
  5  are provided as both methods and operators. 
  6   
  7  Important: sets are not sequences!  While they support 'x in s', 
  8  'len(s)', and 'for x in s', none of those operations are unique for 
  9  sequences; for example, mappings support all three as well.  The 
 10  characteristic operation for sequences is subscripting with small 
 11  integers: s[i], for i in range(len(s)).  Sets don't support 
 12  subscripting at all.  Also, sequences allow multiple occurrences and 
 13  their elements have a definite order; sets on the other hand don't 
 14  record multiple occurrences and don't remember the order of element 
 15  insertion (which is why they don't support s[i]). 
 16   
 17  The following classes are provided: 
 18   
 19  BaseSet -- All the operations common to both mutable and immutable 
 20      sets. This is an abstract class, not meant to be directly 
 21      instantiated. 
 22   
 23  Set -- Mutable sets, subclass of BaseSet; not hashable. 
 24   
 25  ImmutableSet -- Immutable sets, subclass of BaseSet; hashable. 
 26      An iterable argument is mandatory to create an ImmutableSet. 
 27   
 28  _TemporarilyImmutableSet -- A wrapper around a Set, hashable, 
 29      giving the same hash value as the immutable set equivalent 
 30      would have.  Do not use this class directly. 
 31   
 32  Only hashable objects can be added to a Set. In particular, you cannot 
 33  really add a Set as an element to another Set; if you try, what is 
 34  actually added is an ImmutableSet built from it (it compares equal to 
 35  the one you tried adding). 
 36   
 37  When you ask if `x in y' where x is a Set and y is a Set or 
 38  ImmutableSet, x is wrapped into a _TemporarilyImmutableSet z, and 
 39  what's tested is actually `z in y'. 
 40   
 41  """ 
 42   
 43  # Code history: 
 44  # 
 45  # - Greg V. Wilson wrote the first version, using a different approach 
 46  #   to the mutable/immutable problem, and inheriting from dict. 
 47  # 
 48  # - Alex Martelli modified Greg's version to implement the current 
 49  #   Set/ImmutableSet approach, and make the data an attribute. 
 50  # 
 51  # - Guido van Rossum rewrote much of the code, made some API changes, 
 52  #   and cleaned up the docstrings. 
 53  # 
 54  # - Raymond Hettinger added a number of speedups and other 
 55  #   improvements. 
 56   
 57  # protect this import from the fixers... 
 58  exec('from itertools import ifilterfalse as filterfalse') 
 59   
 60  __all__ = ['BaseSet', 'Set', 'ImmutableSet'] 
 61   
62 -class BaseSet(object):
63 """Common base class for mutable and immutable sets.""" 64 65 __slots__ = ['_data'] 66 67 # Constructor 68
69 - def __init__(self):
70 """This is an abstract class.""" 71 # Don't call this from a concrete subclass! 72 if self.__class__ is BaseSet: 73 raise TypeError("BaseSet is an abstract class. " 74 "Use Set or ImmutableSet.")
75 76 # Standard protocols: __len__, __repr__, __str__, __iter__ 77
78 - def __len__(self):
79 """Return the number of elements of a set.""" 80 return len(self._data)
81
82 - def __repr__(self):
83 """Return string representation of a set. 84 85 This looks like 'Set([<list of elements>])'. 86 """ 87 return self._repr()
88 89 # __str__ is the same as __repr__ 90 __str__ = __repr__ 91
92 - def _repr(self, sort_them=False):
93 elements = list(self._data.keys()) 94 if sort_them: 95 elements.sort() 96 return '%s(%r)' % (self.__class__.__name__, elements)
97
98 - def __iter__(self):
99 """Return an iterator over the elements or a set. 100 101 This is the keys iterator for the underlying dict. 102 """ 103 # Wrapping name in () prevents fixer from "fixing" this 104 return (self._data.iterkeys)()
105 106 # Three-way comparison is not supported. However, because __eq__ is 107 # tried before __cmp__, if Set x == Set y, x.__eq__(y) returns True and 108 # then cmp(x, y) returns 0 (Python doesn't actually call __cmp__ in this 109 # case). 110
111 - def __cmp__(self, other):
112 raise TypeError("can't compare sets using cmp()")
113 114 # Equality comparisons using the underlying dicts. Mixed-type comparisons 115 # are allowed here, where Set == z for non-Set z always returns False, 116 # and Set != z always True. This allows expressions like "x in y" to 117 # give the expected result when y is a sequence of mixed types, not 118 # raising a pointless TypeError just because y contains a Set, or x is 119 # a Set and y contain's a non-set ("in" invokes only __eq__). 120 # Subtle: it would be nicer if __eq__ and __ne__ could return 121 # NotImplemented instead of True or False. Then the other comparand 122 # would get a chance to determine the result, and if the other comparand 123 # also returned NotImplemented then it would fall back to object address 124 # comparison (which would always return False for __eq__ and always 125 # True for __ne__). However, that doesn't work, because this type 126 # *also* implements __cmp__: if, e.g., __eq__ returns NotImplemented, 127 # Python tries __cmp__ next, and the __cmp__ here then raises TypeError. 128
129 - def __eq__(self, other):
130 if isinstance(other, BaseSet): 131 return self._data == other._data 132 else: 133 return False
134
135 - def __ne__(self, other):
136 if isinstance(other, BaseSet): 137 return self._data != other._data 138 else: 139 return True
140 141 # Copying operations 142
143 - def copy(self):
144 """Return a shallow copy of a set.""" 145 result = self.__class__() 146 result._data.update(self._data) 147 return result
148 149 __copy__ = copy # For the copy module 150
151 - def __deepcopy__(self, memo):
152 """Return a deep copy of a set; used by copy module.""" 153 # This pre-creates the result and inserts it in the memo 154 # early, in case the deep copy recurses into another reference 155 # to this same set. A set can't be an element of itself, but 156 # it can certainly contain an object that has a reference to 157 # itself. 158 from copy import deepcopy 159 result = self.__class__() 160 memo[id(self)] = result 161 data = result._data 162 value = True 163 for elt in self: 164 data[deepcopy(elt, memo)] = value 165 return result
166 167 # Standard set operations: union, intersection, both differences. 168 # Each has an operator version (e.g. __or__, invoked with |) and a 169 # method version (e.g. union). 170 # Subtle: Each pair requires distinct code so that the outcome is 171 # correct when the type of other isn't suitable. For example, if 172 # we did "union = __or__" instead, then Set().union(3) would return 173 # NotImplemented instead of raising TypeError (albeit that *why* it 174 # raises TypeError as-is is also a bit subtle). 175
176 - def __or__(self, other):
177 """Return the union of two sets as a new set. 178 179 (I.e. all elements that are in either set.) 180 """ 181 if not isinstance(other, BaseSet): 182 return NotImplemented 183 return self.union(other)
184
185 - def union(self, other):
186 """Return the union of two sets as a new set. 187 188 (I.e. all elements that are in either set.) 189 """ 190 result = self.__class__(self) 191 result._update(other) 192 return result
193
194 - def __and__(self, other):
195 """Return the intersection of two sets as a new set. 196 197 (I.e. all elements that are in both sets.) 198 """ 199 if not isinstance(other, BaseSet): 200 return NotImplemented 201 return self.intersection(other)
202
203 - def intersection(self, other):
204 """Return the intersection of two sets as a new set. 205 206 (I.e. all elements that are in both sets.) 207 """ 208 if not isinstance(other, BaseSet): 209 other = Set(other) 210 if len(self) <= len(other): 211 little, big = self, other 212 else: 213 little, big = other, self 214 common = iter(filter(big._data.has_key, little)) 215 return self.__class__(common)
216
217 - def __xor__(self, other):
218 """Return the symmetric difference of two sets as a new set. 219 220 (I.e. all elements that are in exactly one of the sets.) 221 """ 222 if not isinstance(other, BaseSet): 223 return NotImplemented 224 return self.symmetric_difference(other)
225
226 - def symmetric_difference(self, other):
227 """Return the symmetric difference of two sets as a new set. 228 229 (I.e. all elements that are in exactly one of the sets.) 230 """ 231 result = self.__class__() 232 data = result._data 233 value = True 234 selfdata = self._data 235 try: 236 otherdata = other._data 237 except AttributeError: 238 otherdata = Set(other)._data 239 for elt in filterfalse(otherdata.has_key, selfdata): 240 data[elt] = value 241 for elt in filterfalse(selfdata.has_key, otherdata): 242 data[elt] = value 243 return result
244
245 - def __sub__(self, other):
246 """Return the difference of two sets as a new Set. 247 248 (I.e. all elements that are in this set and not in the other.) 249 """ 250 if not isinstance(other, BaseSet): 251 return NotImplemented 252 return self.difference(other)
253
254 - def difference(self, other):
255 """Return the difference of two sets as a new Set. 256 257 (I.e. all elements that are in this set and not in the other.) 258 """ 259 result = self.__class__() 260 data = result._data 261 try: 262 otherdata = other._data 263 except AttributeError: 264 otherdata = Set(other)._data 265 value = True 266 for elt in filterfalse(otherdata.has_key, self): 267 data[elt] = value 268 return result
269 270 # Membership test 271
272 - def __contains__(self, element):
273 """Report whether an element is a member of a set. 274 275 (Called in response to the expression `element in self'.) 276 """ 277 try: 278 return element in self._data 279 except TypeError: 280 transform = getattr(element, "__as_temporarily_immutable__", None) 281 if transform is None: 282 raise # re-raise the TypeError exception we caught 283 return transform() in self._data
284 285 # Subset and superset test 286
287 - def issubset(self, other):
288 """Report whether another set contains this set.""" 289 self._binary_sanity_check(other) 290 if len(self) > len(other): # Fast check for obvious cases 291 return False 292 for elt in filterfalse(other._data.has_key, self): 293 return False 294 return True
295
296 - def issuperset(self, other):
297 """Report whether this set contains another set.""" 298 self._binary_sanity_check(other) 299 if len(self) < len(other): # Fast check for obvious cases 300 return False 301 for elt in filterfalse(self._data.has_key, other): 302 return False 303 return True
304 305 # Inequality comparisons using the is-subset relation. 306 __le__ = issubset 307 __ge__ = issuperset 308
309 - def __lt__(self, other):
310 self._binary_sanity_check(other) 311 return len(self) < len(other) and self.issubset(other)
312
313 - def __gt__(self, other):
314 self._binary_sanity_check(other) 315 return len(self) > len(other) and self.issuperset(other)
316 317 # Assorted helpers 318
319 - def _binary_sanity_check(self, other):
320 # Check that the other argument to a binary operation is also 321 # a set, raising a TypeError otherwise. 322 if not isinstance(other, BaseSet): 323 raise TypeError("Binary operation only permitted between sets")
324
325 - def _compute_hash(self):
326 # Calculate hash code for a set by xor'ing the hash codes of 327 # the elements. This ensures that the hash code does not depend 328 # on the order in which elements are added to the set. This is 329 # not called __hash__ because a BaseSet should not be hashable; 330 # only an ImmutableSet is hashable. 331 result = 0 332 for elt in self: 333 result ^= hash(elt) 334 return result
335
336 - def _update(self, iterable):
337 # The main loop for update() and the subclass __init__() methods. 338 data = self._data 339 340 # Use the fast update() method when a dictionary is available. 341 if isinstance(iterable, BaseSet): 342 data.update(iterable._data) 343 return 344 345 value = True 346 347 if type(iterable) in (list, tuple, xrange): 348 # Optimized: we know that __iter__() and next() can't 349 # raise TypeError, so we can move 'try:' out of the loop. 350 it = iter(iterable) 351 while True: 352 try: 353 for element in it: 354 data[element] = value 355 return 356 except TypeError: 357 transform = getattr(element, "__as_immutable__", None) 358 if transform is None: 359 raise # re-raise the TypeError exception we caught 360 data[transform()] = value 361 else: 362 # Safe: only catch TypeError where intended 363 for element in iterable: 364 try: 365 data[element] = value 366 except TypeError: 367 transform = getattr(element, "__as_immutable__", None) 368 if transform is None: 369 raise # re-raise the TypeError exception we caught 370 data[transform()] = value
371 372
373 -class ImmutableSet(BaseSet):
374 """Immutable set class.""" 375 376 __slots__ = ['_hashcode'] 377 378 # BaseSet + hashing 379
380 - def __init__(self, iterable=None):
381 """Construct an immutable set from an optional iterable.""" 382 self._hashcode = None 383 self._data = {} 384 if iterable is not None: 385 self._update(iterable)
386
387 - def __hash__(self):
388 if self._hashcode is None: 389 self._hashcode = self._compute_hash() 390 return self._hashcode
391
392 - def __getstate__(self):
393 return self._data, self._hashcode
394
395 - def __setstate__(self, state):
396 self._data, self._hashcode = state
397
398 -class Set(BaseSet):
399 """ Mutable set class.""" 400 401 __slots__ = [] 402 403 # BaseSet + operations requiring mutability; no hashing 404
405 - def __init__(self, iterable=None):
406 """Construct a set from an optional iterable.""" 407 self._data = {} 408 if iterable is not None: 409 self._update(iterable)
410
411 - def __getstate__(self):
412 # getstate's results are ignored if it is not 413 return self._data,
414
415 - def __setstate__(self, data):
416 self._data, = data
417
418 - def __hash__(self):
419 """A Set cannot be hashed.""" 420 # We inherit object.__hash__, so we must deny this explicitly 421 raise TypeError("Can't hash a Set, only an ImmutableSet.")
422 423 # In-place union, intersection, differences. 424 # Subtle: The xyz_update() functions deliberately return None, 425 # as do all mutating operations on built-in container types. 426 # The __xyz__ spellings have to return self, though. 427
428 - def __ior__(self, other):
429 """Update a set with the union of itself and another.""" 430 self._binary_sanity_check(other) 431 self._data.update(other._data) 432 return self
433
434 - def union_update(self, other):
435 """Update a set with the union of itself and another.""" 436 self._update(other)
437
438 - def __iand__(self, other):
439 """Update a set with the intersection of itself and another.""" 440 self._binary_sanity_check(other) 441 self._data = (self & other)._data 442 return self
443
444 - def intersection_update(self, other):
445 """Update a set with the intersection of itself and another.""" 446 if isinstance(other, BaseSet): 447 self &= other 448 else: 449 self._data = (self.intersection(other))._data
450
451 - def __ixor__(self, other):
452 """Update a set with the symmetric difference of itself and another.""" 453 self._binary_sanity_check(other) 454 self.symmetric_difference_update(other) 455 return self
456
457 - def symmetric_difference_update(self, other):
458 """Update a set with the symmetric difference of itself and another.""" 459 data = self._data 460 value = True 461 if not isinstance(other, BaseSet): 462 other = Set(other) 463 if self is other: 464 self.clear() 465 for elt in other: 466 if elt in data: 467 del data[elt] 468 else: 469 data[elt] = value
470
471 - def __isub__(self, other):
472 """Remove all elements of another set from this set.""" 473 self._binary_sanity_check(other) 474 self.difference_update(other) 475 return self
476
477 - def difference_update(self, other):
478 """Remove all elements of another set from this set.""" 479 data = self._data 480 if not isinstance(other, BaseSet): 481 other = Set(other) 482 if self is other: 483 self.clear() 484 for elt in filter(data.has_key, other): 485 del data[elt]
486 487 # Python dict-like mass mutations: update, clear 488
489 - def update(self, iterable):
490 """Add all values from an iterable (such as a list or file).""" 491 self._update(iterable)
492
493 - def clear(self):
494 """Remove all elements from this set.""" 495 self._data.clear()
496 497 # Single-element mutations: add, remove, discard 498
499 - def add(self, element):
500 """Add an element to a set. 501 502 This has no effect if the element is already present. 503 """ 504 try: 505 self._data[element] = True 506 except TypeError: 507 transform = getattr(element, "__as_immutable__", None) 508 if transform is None: 509 raise # re-raise the TypeError exception we caught 510 self._data[transform()] = True
511
512 - def remove(self, element):
513 """Remove an element from a set; it must be a member. 514 515 If the element is not a member, raise a KeyError. 516 """ 517 try: 518 del self._data[element] 519 except TypeError: 520 transform = getattr(element, "__as_temporarily_immutable__", None) 521 if transform is None: 522 raise # re-raise the TypeError exception we caught 523 del self._data[transform()]
524
525 - def discard(self, element):
526 """Remove an element from a set if it is a member. 527 528 If the element is not a member, do nothing. 529 """ 530 try: 531 self.remove(element) 532 except KeyError: 533 pass
534
535 - def pop(self):
536 """Remove and return an arbitrary set element.""" 537 return self._data.popitem()[0]
538
539 - def __as_immutable__(self):
540 # Return a copy of self as an immutable set 541 return ImmutableSet(self)
542
544 # Return self wrapped in a temporarily immutable set 545 return _TemporarilyImmutableSet(self)
546 547
548 -class _TemporarilyImmutableSet(BaseSet):
549 # Wrap a mutable set as if it was temporarily immutable. 550 # This only supplies hashing and equality comparisons. 551
552 - def __init__(self, set):
553 self._set = set 554 self._data = set._data # Needed by ImmutableSet.__eq__()
555
556 - def __hash__(self):
557 return self._set._compute_hash()
558 559 # Local Variables: 560 # tab-width:4 561 # indent-tabs-mode:nil 562 # End: 563 # vim: set expandtab tabstop=4 shiftwidth=4: 564