# 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

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.)

• `e in s`: Return `True` iff element `e` belongs to multiset `s`. (Implemented through special method `__contains__`.)

• `s.count(e)`: Return the number of occurrences of element `e` in multiset `s`.

• `s.insert(e)`: Add element `e` to multiset `s`.

• `s.remove(e)`: Remove one occurrence of element `e` from multiset `s` — do nothing if `s` does not contain element `e`.

• `s.clear()`: Remove all elements from multiset `s`.

• `len(s)`: Return the number of elements in multiset `s`, counting each occurrence of an element separately. (Implemented through special method `__len__`.)

• `repr(s)`: Return a string representation of multiset `s` of the form

```    MultiSet([e1, e2, ..., en])
```

where each `ei` is the representation of one occurrence of one element in `s`; the order of the elements does not matter. (Implemented through special method `__repr__`.)

• `s1 == s2`: Return `True` iff multiset `s1` contains exactly the same elements (and the same number of each one) as multiset `s2`. (Implemented through special method `__eq__`.)

• `s1 <= s2`: Return `True` iff every element in multiset `s1` also belongs to multiset `s2` (counting separate occurrences separately); in other words, iff `s1` is a subset of (or maybe equal to) `s2`. (Implemented through special method `__le__`.)

• `s1 − s2`: Return a new multiset that contains every element that belongs to multiset `s1` but not to multiset `s2`; in other words, `s1 − s2` is the difference of `s1` and `s2`. (Implemented through special method `__sub__`.)

• `s1 −= s2`: Update multiset `s1` so that it becomes equal to `s1 − s2`; this changes `s1` directly without creating a new object. (Implemented through special method `__isub__`.)

• `s1 + s2`: Return a new multiset that contains every element that belongs to either multiset `s1` or multiset `s2`, with a number of occurrences equal to the maximum number of occurrences in either set; in other words, `s1 + s2` is the union of `s1` and `s2`. (Implemented through special method `__add__`.)

• `s1 += s2`: Update multiset `s1` so that it becomes equal to `s1 + s2`; this changes `s1` directly without creating a new object. (Implemented through special method `__iadd__`.)

• `s1 & s2`: Return a new multiset that contains every element that belongs to both multiset `s1` and multiset `s2`; in other words, `s1 & s2` is the intersection of `s1` and `s2`. (Implemented through special method `__and__`.)

• `s1 &= s2`: Update multiset `s1` so that it becomes equal to `s1 & s2`; this changes `s1` directly without creating a new object. (Implemented through special method `__iand__`.)

• `s1.isdisjoint(s2)`: Return `True` iff multiset `s1` has no element in common with multiset `s2`; in other words, iff `s1 & s2` is empty.

• `__init__`: must take no parameter (other than the required `self`, of course) and make the new multiset empty.

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

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.

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 `_SkipNode`s. Of course, it's fine to use `SkipList`s outside of the file, and that makes use of `_SkipNode`s, indirectly, but this is fine. What you should not do is to write code that accesses `_SkipNode`s 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!