CSC 148 H1, Winter 2013

Project, Part I (updated on Thu 7 Feb 2013)

Purpose

The goal of this project is to give you lots of practice with linked data structures and with most of the programming techniques taught in this course: inheritance, recursion, exceptions, unit testing, etc.

Warning

The term tests and final exam will contain questions based on the concepts in this project — they are major concepts in the course after all! If you let your partner(s) do too much of the work, you are very likely to do badly on the tests. We want to make sure that everyone understands how to solve this project, individually. If you are feeling lost, don't wait: talk to us now!


Multisets

The ADT

A multiset is a collection of arbitrary elements, like a regular set but with one important difference: elements can occur multiple times in a multi-set. For example, the multiset {a,a,b} is different from the multiset {a,b}, even though both of them are identical sets. You can read more about Multisets on Wikipedia — just the overview contains everything you need to know.

For this project, we want to support the following operations on multisets. (There will be a few more operations added later, but we'll start with these.)

For more information on Python's "special methods", check out Section 3.3 of the Python Language Reference.


Your First Task

In a file named "multiset.py", write a class MultiSet with method stubs for each of the operations above, and detailed docstrings for the class and each method. (Remember that a stub is just a function with an "empty" body — in other words the keyword pass.)

In a file named "test_multiset.py", write a detailed suite of test cases for your class MultiSet, using the unittest framework. Include docstrings for each of your test cases to explain what you are testing and why. Yes, we are asking you to write your test cases before you write any code that you can test — this is what test-driven development means! The idea is that you need to understand exactly how your methods are supposed to perform before you try to write the code for them. And if you do, then you can write test cases that demonstrate the desired behaviour, to allow you to verify that your implementation is correct as soon as you have written it.

You may be tempted to skip this step! But keep in mind: you'll never find out how well this technique works unless you give it a good, honest try. And you have a perfect opportunity to do this right now; don't throw it away! In fact, I strongly recommend that you do this before you read the rest of this handout, to make sure that your test cases represent exactly the functionality you want and are not based on implementation details.


Skip Lists

For Part I, you do not have to implement a skip list anymore. (We'll keep this task for Part II.) Instead, we provide you with a working "skip list" implementation in file skiplist.py. Download this file and read through it to see the methods that it provides.


Your Second Task

Implement class MultiSet, by making use of the functionality provided by class SkipList. In other words, your MultiSet should use a SkipList to store its data (in a similar way that we used a builtin Python list to store the data in our class Stack). Since you have already written a good testing suite for your class MultiSet, you should be able to easily test your code as you implement each method!

You are allowed to add new methods to class SkipList in order to implement additional functionality that is required by MultiSet. Keep in mind that classes _SkipNode and _SkipIter are private to the skiplist module. This means that you should not write any code outside of file skiplist.py that makes direct use of _SkipNodes. Of course, it's fine to use SkipLists outside of the file, and that makes use of _SkipNodes, indirectly, but this is fine. What you should not do is to write code that accesses _SkipNodes and their attributes directly, anywhere except within file skiplist.py.


Requirements and coding standards

You may not use built-in lists or dictionaries (or any other container type from a Python module) to store any of the data in your implementation of class MultiSet: doing so will result in an automatic failure for this project!

Your code must be written following the style conventions from PEP8, as described on the Homework page. In addition to the style conventions that are checked by the pep8.py script, pay attention to the guidelines that concern variable, function, and class names, docstrings and comments, design principles (making good use of helpers to remove duplication), etc.

In particular, each file you submit must start with an appropriate docstring. Please include the CDF username of each group member at the end of this docstring, preceded by the word "Authors:". Do this even if you worked alone. For example, your docstring might look like this:

    """An implementation of the Multiset ADT using a Skip List.
    ...details go here...

    Authors: fpitt
    """

The "Authors:" line in your docstring takes the place of your signature, to confirm that you have read and understood the policy on Academic Offences given on the Course Information Sheet, and that your submission contains only the work of the students listed. Your submission cannot be graded if any of your files is missing this line!