2010 September 15 / jj|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u

Assignment: Classes

Carleton College CS 201, Fall 2010, Prof. Joshua R. Davis

Introduction

The goal of this assignment is for you to practice with Python and classes (and refresh your memory after a long summer). There is really just one key idea that you need to understand:

Every function and method has a specification (which in Python shows up as the docstring). The specification is a contract between the creator of the function/method and the user. The user can count on the function/method to fulfill the contract, but she cannot count on anything else; she cannot make any assumptions about how the function/method works. The creator of the function/method can change how it works at any time, as long as it still fulfills the contract.
This assignment is in two parts. In the first part, you pretend that you are the creator of the Set class; you change how Set works, without changing the specification. In the second part, you pretend that you are not the creator, but rather just a user of the Set class; you write a subclass, using only the methods of the superclass — not any knowledge of how its methods work, and certainly not any of its instance variables.

You may work on this assignment alone or with a single partner. If you work with a partner, then you and your partner submit one copy of the assignment, with both of your names on all of the files. The work is due by the start of class on Friday.

Improve Set

In this part of the assignment, you should imagine that you are the original author of the Set class. Your class is a great success; it's included in a popular programming library that is used in thousands of other programs, written by people from all over the world. But there are two aspects of Set that have always bothered you. You're going to edit Set to fix these two problems. You must do it in a way that doesn't change the interface of the Set class — that is, the specifications of its methods — because if you changed the interface then the thousands of programs that use Set might break.

Your first problem is that the getSize method is slower than it needs to be. Instead of counting the objects in the set every time getSize is called, the Set object could just keep a counter that tracks how many items there are. When a new object is added, the count increases by 1; when an object is removed, the count decreases by 1; when getSize is called, the set simply reports the current count. Edit Set to add this counting mechanism.

Your second problem is that in the years since you've written Set you've implemented many other classes using the linked list idea. Every one of these class files contains its own copy of the same LinkedListNode code, which is wasteful. You decide to split this code into its own file, linkedlistnode.py, and have all of your other files access the class there. Here are the steps involved:

At the end of all of this, the Set class should work exactly as it did before you started, except that getSize is faster. The demo code in set.py should certainly produce the same results as it did before. You haven't changed the interface of the Set class; you've just changed its implementation.

Don't forget to add a demo section to linkedlistnode.py; that's part of Good Python Style. When I did this assignment, my demo section wasn't very long; it made a list a few items long, and then printed out the list using a while loop.

Implement BetterSet

In this part of the assignment, you should imagine that you are not the author of the Set class, but rather one of those other programmers around the world who uses it. You have never seen the Set code, so you don't know how it works; all you know is that Set's methods fulfill their specifications. Unfortunately, your latest program uses sets so heavily that the basic Set class doesn't suffice. You decide to create a subclass of Set, called BetterSet, with some new methods.

In a new file betterset.py, import Set from set.py and declare the BetterSet class as a subclass of Set. Then declare these three methods: 

def getMaximumSize(self):
    """Returns the largest size that the set has ever achieved."""

def union(self, other):
    """The input other must be a Set object. Adds every element of other to this set. The other set is left unchanged."""

def contains(self, other):
    """The input other must be a Set object. Returns True or False, based on whether this set contains the other set as a subset --- that is, whether every object in other is also in this set. The other set is left unchanged."""
Then implement the three methods. You may give BetterSet some instance variables, if you like, and you may access those instance variables from anywhere in BetterSet's code. But you must not access Set's instance variables; you must use only its publicly declared methods: __init__, add, remove, has, getSize, getElement, and __str__. Why? Well, the specifications for these methods are all you know about Set. You don't know which instance variables it has. You don't know that it's implemented using a linked list. Even if you did know these things, the creator of Set could change them at any time, so you couldn't rely on them.

Talk to the instructor or prefect if you need help. Here are some hints. In order to get getMaximumSize working, you're probably going to have to override the __init__ method and the add method. In writing union and contains you'll need to use getElement and remove heavily; note well, from reading the docstrings, that these methods must leave the other Set unchanged.

Don't forget to add a docstring for BetterSet and a demo section; always remember Good Python Style.

Submit Your Work

There are three files in this assignment: linkedlistnode.py, set.py, and betterset.py. Make sure that each file exhibits Good Python Style. On the third file, you and your partner are the only authors; on the first two files, I am also an author. You and your partner should both keep copies of these files for future use in this course, but only one of you should submit them for grading. Follow the directions for submitting work on the COURSES file server, from Assignment: Introduction. These are the grading criteria: