PATCH: sets.py for Jython 2.1

[Dave Benjamin]

Hola,

I made a backport of sets.py that will run on Jython 2.1. Here is a diff
against the Python 2.3 version of sets.py. The changes were simple, but I
may have made a mistake here or there, and since the unit tests depend on
generators, it was too much trouble to try to test the module this way. I'd
appreciate any help on testing it more thoroughly. So far, everything seems
to be working fine.

The majority of the changes were due to the new iterator protocol,
lack of generators and itertools, and dictionaries not supporting "x in d".

To use this diff, copy sets.py from the standard Python 2.3 library location
to a directory where you have saved the following code as "sets.py.diff"
and type the following:

$ patch < sets.py.diff

Your copy of sets.py should be ready to go.

Enjoy,
Dave

--- /usr/lib/python2.3/sets.py 2003-10-09 09:05:40.001000000 -0700
+++ sets.py 2003-12-10 15:34:14.655250000 -0700
@@ -54,29 +54,15 @@
# - Raymond Hettinger added a number of speedups and other
# improvements.

-from __future__ import generators
-try:
- from itertools import ifilter, ifilterfalse
-except ImportError:
- # Code to make the module run under Py2.2
- def ifilter(predicate, iterable):
- if predicate is None:
- def predicate(x):
- return x
- for x in iterable:
- if predicate(x):
- yield x
- def ifilterfalse(predicate, iterable):
- if predicate is None:
- def predicate(x):
- return x
- for x in iterable:
- if not predicate(x):
- yield x
+from __future__ import nested_scopes
+def filterfalse(func, seq):
+ return filter(lambda elt: not func(elt), seq)
+False = 0
+True = not False

__all__ = ['BaseSet', 'Set', 'ImmutableSet']

-class BaseSet(object):
+class BaseSet:
"""Common base class for mutable and immutable sets."""

__slots__ = ['_data']
@@ -90,7 +76,7 @@
raise TypeError, ("BaseSet is an abstract class. "
"Use Set or ImmutableSet.")

- # Standard protocols: __len__, __repr__, __str__, __iter__
+ # Standard protocols: __len__, __repr__, __str__, __getitem__

def __len__(self):
"""Return the number of elements of a set."""
@@ -112,12 +98,8 @@
elements.sort()
return '%s(%r)' % (self.__class__.__name__, elements)

- def __iter__(self):
- """Return an iterator over the elements or a set.
-
- This is the keys iterator for the underlying dict.
- """
- return self._data.iterkeys()
+ def __getitem__(self, index):
+ return self._data.keys()[index]

# Three-way comparison is not supported. However, because __eq__ is
# tried before __cmp__, if Set x == Set y, x.__eq__(y) returns True and
@@ -176,7 +158,7 @@
memo[id(self)] = result
data = result._data
value = True
- for elt in self:
+ for elt in self._data.keys():
data[deepcopy(elt, memo)] = value
return result

@@ -227,7 +209,7 @@
little, big = self, other
else:
little, big = other, self
- common = ifilter(big._data.has_key, little)
+ common = filter(big._data.has_key, little._data.keys())
return self.__class__(common)

def __xor__(self, other):
@@ -252,9 +234,9 @@
otherdata = other._data
except AttributeError:
otherdata = Set(other)._data
- for elt in ifilterfalse(otherdata.has_key, selfdata):
+ for elt in filterfalse(otherdata.has_key, selfdata.keys()):
data[elt] = value
- for elt in ifilterfalse(selfdata.has_key, otherdata):
+ for elt in filterfalse(selfdata.has_key, otherdata.keys()):
data[elt] = value
return result

@@ -279,7 +261,7 @@
except AttributeError:
otherdata = Set(other)._data
value = True
- for elt in ifilterfalse(otherdata.has_key, self):
+ for elt in filterfalse(otherdata.has_key, self._data.keys()):
data[elt] = value
return result

@@ -291,12 +273,12 @@
(Called in response to the expression `element in self'.)
"""
try:
- return element in self._data
+ return element in self._data.keys()
except TypeError:
transform = getattr(element, "__as_temporarily_immutable__", None)
if transform is None:
raise # re-raise the TypeError exception we caught
- return transform() in self._data
+ return transform() in self._data.keys()

# Subset and superset test

@@ -305,7 +287,7 @@
self._binary_sanity_check(other)
if len(self) > len(other): # Fast check for obvious cases
return False
- for elt in ifilterfalse(other._data.has_key, self):
+ for elt in filterfalse(other._data.has_key, self._data.keys()):
return False
return True

@@ -314,7 +296,7 @@
self._binary_sanity_check(other)
if len(self) < len(other): # Fast check for obvious cases
return False
- for elt in ifilterfalse(self._data.has_key, other):
+ for elt in filterfalse(self._data.has_key, other._data.keys()):
return False
return True

@@ -360,31 +342,14 @@

value = True

- if type(iterable) in (list, tuple, xrange):
- # Optimized: we know that __iter__() and next() can't
- # raise TypeError, so we can move 'try:' out of the loop.
- it = iter(iterable)
- while True:
- try:
- for element in it:
- data[element] = value
- return
- except TypeError:
- transform = getattr(element, "__as_immutable__", None)
- if transform is None:
- raise # re-raise the TypeError exception we caught
- data[transform()] = value
- else:
- # Safe: only catch TypeError where intended
- for element in iterable:
- try:
- data[element] = value
- except TypeError:
- transform = getattr(element, "__as_immutable__", None)
- if transform is None:
- raise # re-raise the TypeError exception we caught
- data[transform()] = value
-
+ for element in iterable:
+ try:
+ data[element] = value
+ except TypeError:
+ transform = getattr(element, "__as_immutable__", None)
+ if transform is None:
+ raise # re-raise the TypeError exception we caught
+ data[transform()] = value

class ImmutableSet(BaseSet):
"""Immutable set class."""
@@ -476,8 +441,8 @@
value = True
if not isinstance(other, BaseSet):
other = Set(other)
- for elt in other:
- if elt in data:
+ for elt in other._data.keys():
+ if elt in data.keys():
del data[elt]
else:
data[elt] = value
@@ -493,7 +458,7 @@
data = self._data
if not isinstance(other, BaseSet):
other = Set(other)
- for elt in ifilter(data.has_key, other):
+ for elt in filter(data.has_key, other._data.keys()):
del data[elt]

# Python dict-like mass mutations: update, clear