CSC 162 Sets Project

Spring 2010

In class we have discussed several ways to implement a set abstraction, including characteristic arrays, arrays-based or singly-linked lists (ordered or unordered), search trees or skip lists, and hash tables.  So far, however, we have not paid much attention to how convenient (or inconvenient) these are to use in Python.

In mathematics, we don’t say C = A.union(B), we say C = A ∪ B.  Python lists support a `+` operator, but since this represents concatenation, with no regard to duplicates, it isn’t directly useful for set addition.  Given that an element e is in A ∪ B if it is in A or in B, one might propose using the Python “or” operator, `|`, for union.  In a similar vein, `&` might be used for intersection, and `-` for difference.  And instead of `A.add(e)` and `A.remove(e)`, we might say `A += e` and `A -= e`.  We can achieve all of this by defining the appropriate “double-underscore” methods, which Python calls when it encounters built-in operators:

```    class Set:
def __init__(self, el = None):
self.contents = list()
if el != None:
for e in el:
self += e
if item not in self.contents:
self.contents.append(item)
return self
def __isub__(self, item):           # (-=) remove element from set
if item in self.contents:
self.contents.remove(item)
return self
def __or__(self, other):            # (|) set union
rtn = Set(self.contents)
for e in other:
rtn += e
return rtn
def __and__(self, other):           # (&) set intersection
rtn = Set()
for e in self:
if e in other:
rtn += e
return rtn
def __sub__(self, other):           # (-) set difference
rtn = Set()
for e in self:
if e not in other:
rtn += e
return rtn
def __str__(self):                  # string to represent set
rtn = str(self.contents)
return "{" + rtn[1:len(rtn)-1] + "}"```

Note that we’ve defined the constructor (initializer) to take an optional Python list, which we use as initial contents of the set.  In the last method we’ve defined a convert-to-string routine that will be called implicitly by the `print` statement.

Using the `Set` class above, we can interact with the interpreter as follows:

```    >>> s1 = Set([1, 2, 3])
>>> print s1
{1, 2, 3}
>>> s2 = Set([3, 4, 5])
>>> print s2
{3, 4, 5}
>>> s1 += 4         # add element to set
>>> print s1
{1, 2, 3, 4}
>>> s2 -= 4         # remove element from set
>>> print s2
{3, 5}
>>> u = s1 | s2     # union
>>> print u
{1, 2, 3, 4, 5}
>>> i = s1 & s2     # intersection
>>> print i
{3}
>>> d = s1 - s2     # difference
>>> print d
{1, 2, 4}
>>>```

But there’s more.  The built-in sequence types of Python (list, tuple, dictionary) support iteration and membership tests using `for` loops and the `in` operator.  We can provide these for `Set`s by defining the `__iter__` method:

```        def __iter__(self):
i = 0
limit = len(self.contents)
while i < limit:
yield self.contents[i]
i += 1```

This code illustrates a feature of Python that we have not seen before:  the `yield` statement.  We can think of an iterator (a method containing `yield`) as returning (yielding) a sequence of objects over which a `for` loop iterates.  Instead of returning the sequence all at once however (before the loop starts running), Python’s `yield` arranges to return them a bit at a time, as required.  If we type

```        s = Set([1, 2, 3])
t = 0
for e in s:
t += e
print t```
the Python interpreter calls `s.__iter__()` when it first encounters the `for` loop.  The iterator yields one element of `s` (say, 1), and the interpreter executes the first iteration of the loop.  It then resumes execution of the iterator where it last left off (right after the `yield` statement).  The iterator yields a value for the second iteration of the loop (say, 2), and so on.  When the iterator finally returns (or falls off the end of its code), the `for` loop terminates.  In our example, the `print` will then print 6.

The `in` comparison test uses `__iter__` as well.  The statement

```        if e in s:
...```
is essentially equivalent to
```        t = False
for x in s:
if e == x:
t = True
break       # exit loop
if t:
...```
for some hidden temporary variable `t`

In a nutshell, Python `for` loops exist for the purpose of executing certain code (the body of the loop) for every element of a sequence.  Interestingly, there’s another way to implement this functionality:

```        def forAll(self, f):
for e in self:
f(e)```
Given this definition, we can type
```    def add_to_t(e):
global t
t += e
...
t = 0
print t```
We could even write this as
```    t = 0
s.forAll(
)
print t```
to emphasize its similarity to the `for` loop.

Finally, if we want to make sets convenient, it turns out to be very handy to have a method, usually called `map`, that creates a new set by applying a specified function to every element of some existing set:

```        def map(self, f):
rtn = Set()
for e in self:
rtn += f(e)
return rtn```
Now given
```    def square(n):
return n*n

global q
q += square(e)

s = Set([1, 2, 3])```
the following are all equivalent:
```    q = Set()
for e in s:
q += square(e)
print q

q = Set()
print q

q = s.map(square)
print q```
They all print `{1, 4, 9}`

So What’s the Assignment?

The examples above flesh out convenience routines for sets based on Python lists.  You can find the code all together in one file HERE.  Your task in this brief (1-week) project is to flesh out similar routines for sets based on sorted, singly-linked lists.  You’ll probably want to build on your code from Lab 6

Reminder

Please read the grading standards web page carefully and follow its instructions.  In particular, note that you will need to create a `README.txt` or `README.pdf` file, and you will need to turn your code in using Blackboard.

Extra Credit Suggestions

For extra credit (counted at the end of the semester; may raise your final grade), you might consider the following possibilities.

• The `__iadd__` (`+=`) method defined above allows you to add a single element to a set.  Modify this method so that its parameter may also be a Python list or another `Set` object.  You’ll need to use the `type` function to tell which kind of parameter you’ve been given.  Note that `A += B` is very different from `C = A | B`.  The former adds the elements of `B` to `A`.  The latter creates a new set containing the elements of both `A` and `B`; it does not modify either `A` or `B`

• Repeat the assignment for hash-table-based sets.

Due Date:  Tues., Mar. 2 at 12:00 noon; no extensions.

Last Change:  22 February 2010 /