This is a pure Pythonic implementation of a set class. The syntax and methods implemented are, for the most part, borrowed from PEP 218 by Greg Wilson.
Python version: 2.2
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | class Set:
"""The set class. It can contain mutable objects."""
def __init__(self, seq = None):
"""The constructor. It can take any object giving an iterator as an optional
argument to populate the new set."""
self.elems = []
if seq:
for elem in seq:
if elem not in self.elems:
self.elems.append(elem)
def __str__(self):
return "{%s}" % ", ".join(map(str, self.elems))
def copy(self):
"""Shallow copy of a set object."""
return Set(self.elems)
def __contains__(self, elem):
return elem in self.elems
def __len__(self):
return len(self.elems)
def items(self):
"""Returns a list of the elements in the set."""
return self.elems
def add(self, elem):
"""Add one element to the set."""
if elem not in self.elems:
self.elems.append(elem)
def remove(self, elem):
"""Remove an element from the set. Return an error if elem is not in the set."""
try:
self.elems.remove(elem)
except ValueError:
raise LookupError, "Object %s is not a member of the set." % str(elem)
def discard(self, elem):
"""Remove an element from the set. Do nothing if elem is not in the set."""
try:
self.elems.remove(elem)
except ValueError:
pass
#Define an iterator for a set.
def __iter__(self):
return iter(self.elems)
#The basic binary operations with sets.
def __or__(self, other):
"""Union of two sets."""
ret = self.copy()
for elem in other.elems:
if elem not in ret:
ret.elems.append(elem)
return ret
def __sub__(self, other):
"""Difference of two sets."""
ret = self.copy()
for elem in other.elems:
ret.discard(elem)
return ret
def __and__(self, other):
"""Intersection of two sets."""
ret = Set()
for elem in self.elems:
if elem in other.elems:
ret.elems.append(elem)
return ret
def __add__(self, other):
"""Symmetric difference of two sets."""
ret = Set()
temp = other.copy()
for elem in self.elems:
if elem in temp.elems:
temp.elems.remove(elem)
else:
ret.elems.append(elem)
#Add remaining elements.
for elem in temp.elems:
ret.elems.append(elem)
return ret
def __mul__(self, other):
"""Cartesian product of two sets."""
ret = Set()
for elemself in self.elems:
ret.elems.extend([(elemself, elemother) for elemother in other.elems])
return ret
#Some of the binary comparisons.
def __lt__(self, other):
"""Returns 1 if the lhs set is contained but not equal to the rhs set."""
if len(self.elems) < len(other.elems):
temp = other.copy()
for elem in self.elems:
if elem in temp.elems:
temp.remove(elem)
else:
return 0
return len(temp.elems) == 0
else:
return 0
def __le__(self, other):
"""Returns 1 if the lhs set is contained in the rhs set."""
if len(self.elems) <= len(other.elems):
ret = 1
for elem in self.elems:
if elem not in other.elems:
ret = 0
break
return ret
else:
return 0
def __eq__(self, other):
"""Returns 1 if the sets are equal."""
if len(self.elems) != len(other.elems):
return 0
else:
return len(self - other) == 0
|
Implementation Issues: To satisfy the requirement that a set can hold mutables we had to forego the dictionary implementation in favor of a list. This implies a loss of performance since every lookup operation is O(n) and not O(1).
Since there are several loops floating around, especially when binary operations are involved, speed could be gained by implementing this in a compiled language and then have it available in Python.
All the algorithms rely in making simple checks for equality. It is the responsability of the user to ensure that the objects he puts in a set provide the right notion of equality, that is, deep equality and not shallow.
Syntax Issues: The symmetric difference is denoted by + instead of ^. This is reasonable, not only because this notation is used throughout the mathematical community but also because symmetric difference has all the properties one could hope for a reasonable addition (e.g. commutativity, associativity, etc.).
Minor glitch. I think there is a pair of minor bugs. In order to try this class without getting a syntax error I had to change
del self.elems.remove(elem)
to
self.elems.remove(elem)
in both the remove and discard methods
Changed... You are absolutely right.
thwaps himself on the head for being so distracted
Added. took the opportunity of correcting the minor glitch and overloaded multiplication with cartesian product.
sort is missing. Nearly trivial, but the sort method is missing. Suggestion:
For those of use who have to use Python 2.1 for some reason... ... could I suggest the following addition?
This gives the class all that's needed to run under 2.1 (afaict). The __iter__ won't matter because 2.1 will just ignore it. I don't think that 2.2 will be bothered by the __getitem__ either: it just means that some can do a -- potentially meaningless -- lookup of a set item by index.
Not really. sets have no order and implementations are free to swap the order of the elements around as much as they want. It is only the fact that the underlying implementation uses a list that gives an idea of order. Just imagine a set for hashables-only implemented via dicts to see where I'm getting at. If you want a sorted list of the elements just ask for it: