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
        def __iadd__(self, item):           # (+=) add element to set
            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 Sets 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
    s.forAll(add_to_t)
    print t
We could even write this as
    t = 0
    s.forAll(
        add_to_t
    )
    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

    def add_square_to_q(e):
        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()
    s.forAll(add_square_to_q)
    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. 

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


Last Change:  22 February 2010 / Michael Scott's email address