2 # A Set class that works all the way back to Python 1.5. From:
4 # Python Cookbook: Yet another Set class for Python
5 # http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/106469
8 # This is a pure Pythonic implementation of a set class. The syntax
9 # and methods implemented are, for the most part, borrowed from
10 # PEP 218 by Greg Wilson.
12 # Note that this class violates the formal definition of a set() by adding
13 # a __getitem__() method so we can iterate over a set's elements under
14 # Python 1.5 and 2.1, which don't support __iter__() and iterator types.
20 """The set class. It can contain mutable objects."""
22 def __init__(self, seq = None):
23 """The constructor. It can take any object giving an iterator as an optional
24 argument to populate the new set."""
28 if elem not in self.elems:
30 self.elems.append(elem)
33 return "set([%s])" % string.join(map(str, self.elems), ", ")
37 """Shallow copy of a set object."""
38 return Set(self.elems)
40 def __contains__(self, elem):
41 return elem in self.elems
44 return len(self.elems)
46 def __getitem__(self, index):
47 # Added so that Python 1.5 can iterate over the elements.
48 # The cookbook recipe's author didn't like this because there
49 # really isn't any order in a set object, but this is necessary
50 # to make the class work well enough for our purposes.
51 return self.elems[index]
54 """Returns a list of the elements in the set."""
58 """Add one element to the set."""
59 if elem not in self.elems:
61 self.elems.append(elem)
63 def remove(self, elem):
64 """Remove an element from the set. Return an error if elem is not in the set."""
66 self.elems.remove(elem)
68 raise LookupError, "Object %s is not a member of the set." % str(elem)
70 def discard(self, elem):
71 """Remove an element from the set. Do nothing if elem is not in the set."""
73 self.elems.remove(elem)
77 def sort(self, func=cmp):
80 #Define an iterator for a set.
82 return iter(self.elems)
84 #The basic binary operations with sets.
85 def __or__(self, other):
86 """Union of two sets."""
88 for elem in other.elems:
90 ret.elems.append(elem)
93 def __sub__(self, other):
94 """Difference of two sets."""
96 for elem in other.elems:
100 def __and__(self, other):
101 """Intersection of two sets."""
103 for elem in self.elems:
104 if elem in other.elems:
105 ret.elems.append(elem)
108 def __add__(self, other):
109 """Symmetric difference of two sets."""
112 for elem in self.elems:
113 if elem in temp.elems:
114 temp.elems.remove(elem)
116 ret.elems.append(elem)
117 #Add remaining elements.
118 for elem in temp.elems:
119 ret.elems.append(elem)
122 def __mul__(self, other):
123 """Cartesian product of two sets."""
125 for elemself in self.elems:
126 x = map(lambda other, s=elemself: (s, other), other.elems)
130 #Some of the binary comparisons.
131 def __lt__(self, other):
132 """Returns 1 if the lhs set is contained but not equal to the rhs set."""
133 if len(self.elems) < len(other.elems):
135 for elem in self.elems:
136 if elem in temp.elems:
140 return len(temp.elems) == 0
144 def __le__(self, other):
145 """Returns 1 if the lhs set is contained in the rhs set."""
146 if len(self.elems) <= len(other.elems):
148 for elem in self.elems:
149 if elem not in other.elems:
156 def __eq__(self, other):
157 """Returns 1 if the sets are equal."""
158 if len(self.elems) != len(other.elems):
161 return len(self - other) == 0
163 def __cmp__(self, other):
164 """Returns 1 if the sets are equal."""
165 if self.__lt__(other):
167 elif other.__lt__(self):