summaryrefslogtreecommitdiffstats
path: root/Lib/sets.py
Commit message (Collapse)AuthorAgeFilesLines
* Teach the sets module to correctly compute s-=s and s^=s as the empty set.Raymond Hettinger2005-08-131-0/+4
|
* Remove deprecation of sets.Set.update().Raymond Hettinger2003-11-191-4/+0
|
* Improve backwards compatibility code to handle True/False.Raymond Hettinger2003-11-121-0/+4
|
* Set the warnings stacklevel to two.Raymond Hettinger2003-09-081-2/+2
|
* Improvements to set.py:Raymond Hettinger2003-08-171-38/+57
| | | | | | | | | | | | | | | | | | | * Relaxed the argument restrictions for non-operator methods. They now allow any iterable instead of requiring a set. This makes the module a little easier to use and paves the way for an efficient C implementation which can take better advantage of iterable arguments while screening out immutables. * Deprecated Set.update() because it now duplicates Set.union_update() * Adapted the tests and docs to include the above changes. * Added more test coverage including testing identities and checking to make sure non-restartable generators work as arguments. Will backport to Py2.3.1 so that the interface remains consistent across versions. The deprecation of update() will be changed to a FutureWarning.
* Make sets.py compatible with Py2.2Raymond Hettinger2003-08-151-1/+19
|
* Portion of SF patch #761104. Fixes a minor docstring error.Raymond Hettinger2003-06-261-4/+3
| | | | _TemporarilyImmutableSet is in fact a subclass of BaseSet
* SF bug 693121: Set == non-Set is a TypeError.Tim Peters2003-03-021-6/+26
| | | | | | | | | Allow mixed-type __eq__ and __ne__ for Set objects. This is messier than I'd like because Set *also* implements __cmp__. I know of one glitch now: cmp(s, t) returns 0 now when s and t are both Sets and s == t, despite that Set.__cmp__ unconditionally raises TypeError (and by intent). The rub is that __eq__ gets tried first, and the x.__eq__(y) True result convinces Python that cmp(x, y) is 0 without even calling Set.__cmp__.
* SF bug #663701: sets module reviewRaymond Hettinger2003-02-141-7/+7
| | | | Renamed hook methods to use the double underscore convention.
* C Code:Raymond Hettinger2003-02-091-6/+6
| | | | | | | | | | | | | | | * Removed the ifilter flag wart by splitting it into two simpler functions. * Fixed comment tabbing in C code. * Factored module start-up code into a loop. Documentation: * Re-wrote introduction. * Addede examples for quantifiers. * Simplified python equivalent for islice(). * Documented split of ifilter(). Sets.py: * Replace old ifilter() usage with new.
* Whitespace normalization.Tim Peters2003-02-041-1/+1
|
* One more use of ifilter()Raymond Hettinger2003-02-021-3/+2
|
* SF patch #678899: Save time and memory by using itertools in sets module.Raymond Hettinger2003-02-021-19/+11
|
* Explicitly raise an exception in __cmp__ -- this clarifies that cmp()Guido van Rossum2003-01-141-0/+5
| | | | | | is not supported on sets. (Unfortunately, sorting a list of sets may still return random results because it uses < exclusively, but for sets that inly implements a partial ordering. Oh well.)
* SF 643115: Set._update() had a special case for dictionaries which allowedRaymond Hettinger2002-11-251-3/+0
| | | | | non-true values to leak in. This threw-off equality testing which depends on the underlying dictionaries having both the same keys and values.
* Add getstate and setstate implementation to concrete set classes.Jeremy Hylton2002-11-131-0/+12
|
* Another attempt at making the set constructor both safe and fast. [SFGuido van Rossum2002-11-081-18/+24
| | | | bug 628246]
* _update(): Commented the new obscurity. Materialized into a tupleTim Peters2002-11-081-2/+8
| | | | | | instead of into a list for a bit of speed/space savings. Reopened the bug report too (628246), as I'm unclear on why we don't sort out the cause of the TypeError instead.
* Closes SF bug #628246.Raymond Hettinger2002-11-081-0/+2
| | | | | | | | The _update method detected mutable elements by trapping TypeErrors. Unfortunately, this masked useful TypeErrors raised by the iterable itself. For cases where it is possible for an iterable to raise a TypeError, the iterable is pre-converted to a list outside the try/except so that any TypeErrors propagate through.
* .iterkeys() is not needed.Raymond Hettinger2002-10-041-1/+1
|
* Sped _update().Raymond Hettinger2002-08-291-0/+9
| | | | Uses the fast update() method when a dictionary is available.
* Gave intersection_update a speed boost.Tim Peters2002-08-261-3/+1
|
* Gave issubet() and issuperset() major speed boosts. That's it for now!Tim Peters2002-08-251-2/+4
| | | | Someone else may want to tackle the mutating operations similarly.
* Gave __sub__/difference a factor of 2-5 speed boost.Tim Peters2002-08-251-1/+2
|
* Gave __xor__/symmetric_difference a factor of 2-5 speed boost.Tim Peters2002-08-251-4/+6
|
* Sped union by a factor of 3-4.Tim Peters2002-08-251-1/+2
|
* Sped intersection by large factors (3-5x faster than before on sets ofTim Peters2002-08-251-7/+2
| | | | cardinality 500; and the smaller the intersection, the bigger the speedup).
* Added a clue about why xyz_update isn't the same as __xyz__.Tim Peters2002-08-251-1/+4
|
* Implemented <, <=, >, >= for sets, giving subset and proper-subsetTim Peters2002-08-251-0/+12
| | | | | | meanings. I did not add new, e.g., ispropersubset() methods; we're going nuts on those, and, e.g., there was no "friendly name" for == either.
* Record a clue about why __or__ is not union, etc.Tim Peters2002-08-251-0/+5
|
* Removed < <= > >= from the API. Implemented as comparisons of theRaymond Hettinger2002-08-241-18/+1
| | | | | | | | underlying dictionaries, there were no reasonable use cases (lexicographic sorting of a list of sets is somewhat esoteric). Frees the operators for other uses (such as strict subset and superset comparisons). Updated documentation and test suite accordingly.
* At Tim Peter's suggestion, propagated GvR's binary operator changes toRaymond Hettinger2002-08-241-8/+16
| | | | | | | | | | | | the inplace operators. The strategy is to have the operator overloading code do the work and then to define equivalent method calls which rely on the operators. The changes facilitate proper application of TypeError and NonImplementedErrors. Added corresponding tests to the test suite to make sure both the operator and method call versions get exercised. Add missing tests for difference_update().
* Since instances of _TemporarilyImmutableSet are always thrown awayRaymond Hettinger2002-08-241-5/+1
| | | | | | immediately after the comparison, there in no use in caching the hashcode. The test, 'if self._hashcode is None', never fails. Removing the caching saves a few lines and a little time.
* 1. Removed module self test in favor of unittests -- Timbot's suggestion.Raymond Hettinger2002-08-241-109/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 2. Replaced calls to Set([]) with Set() -- Timbot's suggestion 3. Fixed subtle bug in sets of sets: The following code did not work (will add to test suite): d = Set('d') s = Set([d]) # Stores inner set as an ImmutableSet s.remove(d) # For comparison, wraps d in _TemporarilyImmutableSet The comparison proceeds by computing the hash of the _TemporarilyImmutableSet and finding it in the dictionary. It then verifies equality by calling ImmutableSet.__eq__() and crashes from the binary sanity check. The problem is that the code assumed equality would be checked with _TemporarilyImmutableSet.__eq__(). The solution is to let _TemporarilyImmutableSet derive from BaseSet so it will pass the sanity check and then to provide it with the ._data element from the wrapped set so that ImmutableSet.__eq__() will find ._data where it expects. Since ._data is now provided and because BaseSet is the base class, _TemporarilyImmutableSet no longer needs .__eq__() or .__ne__(). Note that inheriting all of BaseSet's methods is harmless because none of those methods (except ones starting with an underscore) can mutate the .data element. Also _TemporarilyImmutableSet is only used internally as is not otherwise visible.
* pop() docstring: this isn't a randomly-chosen element, it's merelyTim Peters2002-08-231-1/+1
| | | | arbitrary. I already changed the docs for this.
* Comment repair.Tim Peters2002-08-231-4/+4
|
* RH pointed out that discard(element) doesn't do the transformation onGuido van Rossum2002-08-231-1/+1
| | | | the element if necessary. Fixed by calling self.remove(element).
* Change the binary operators |, &, ^, - to return NotImplemented ratherGuido van Rossum2002-08-221-14/+40
| | | | | | | | | | | | | | | | | | | | than raising TypeError when the other argument is not a BaseSet. This made it necessary to separate the implementation of e.g. __or__ from the union method; the latter should not return NotImplemented but raise TypeError. This is accomplished by making union(self, other) return self|other, etc.; Python's binary operator machinery will raise TypeError. The idea behind this change is to allow other set implementations with an incompatible internal structure; these can provide union (etc.) with standard sets by implementing __ror__ etc. I wish I could do this for comparisons too, but the default comparison implementation allows comparing anything to anything else (returning false); we don't want that (at least the test suite makes sure e.g. Set()==42 raises TypeError). That's probably fine; otherwise other set implementations would be constrained to implementing a hash that's compatible with ours.
* Now that __init__ transforms set elements, we know that all of theRaymond Hettinger2002-08-211-1/+3
| | | | | elements are hashable, so we can use dict.update() or dict.copy() for a C speed Set.copy().
* Sped ._update() method by factoring try/except out of the inner loop.Raymond Hettinger2002-08-211-4/+5
|
* Ouch. The test suite *really* needs work!!!!! There were severalGuido van Rossum2002-08-211-46/+38
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | superficial errors and one deep one that aren't currently caught. I'm headed for bed after this checkin. - Fixed several typos introduced by Raymond Hettinger (through cut-n-paste from my template): it's _as_temporarily_immutable, not _as_temporary_immutable, and moreover when the element is added, we should use _as_immutable. - Made the seq argument to ImmutableSet.__init__ optional, so we can write ImmutableSet() to create an immutable empty set. - Rename the seq argument to Set and ImmutableSet to iterable. - Add a Set.__hash__ method that raises a TypeError. We inherit a default __hash__ implementation from object, and we don't want that. We can then catch this in update(), so that e.g. s.update([Set([1])]) will transform the Set([1]) to ImmutableSet([1]). - Added the dance to catch TypeError and try _as_immutable in the constructors too (by calling _update()). This is needed so that Set([Set([1])]) is correctly interpreted as Set([ImmutableSet([1])]). (I was puzzled by a side effect of this and the inherited __hash__ when comparing two sets of sets while testing different powerset implementations: the Set element passed to a Set constructor wasn't transformed to an ImmutableSet, and then the dictionary didn't believe the Set found in one dict it was the same as ImmutableSet in the other, because the hashes were different.) - Refactored Set.update() and both __init__() methods; moved the body of update() into BaseSet as _update(), and call this from __init__() and update(). - Changed the NotImplementedError in BaseSet.__init__ to TypeError, both for consistency with basestring() and because we have to use TypeError when denying Set.__hash__. Together those provide sufficient evidence that an unimplemented method needs to raise TypeError.
* Add Raymond H to the list of authors; add some XXX comments aboutGuido van Rossum2002-08-211-0/+9
| | | | possible API improvements.
* Fast size check for sub/super set testsRaymond Hettinger2002-08-211-0/+4
|
* Optimize try/except ordering in sets.py.Raymond Hettinger2002-08-211-25/+25
| | | | | | | | Gains a 5:1 speed-up for membership testing by handling the most common case first (the case where the element is hashable). Closes SF Patch 597444.
* Minor typoRaymond Hettinger2002-08-201-1/+1
|
* Rename popitem() to pop(). (An idea from SF patch 597444.)Guido van Rossum2002-08-201-1/+1
|
* Move __init__ from BaseSet into Set and ImmutableSet. This causes aGuido van Rossum2002-08-201-16/+28
| | | | | tiny amount of code duplication, but makes it possible to give BaseSet an __init__ that raises an exception.
* Add a note reminding the reader that sets are not sequences. IGuido van Rossum2002-08-201-0/+10
| | | | | received feedback that was based in the misunderstanding that sets were sequences.
* Fix typo in __slots__ of ImmutableSet.Guido van Rossum2002-08-191-1/+1
|
* Set classes and their unit tests, from sandbox.Guido van Rossum2002-08-191-0/+529