Writing Code For Others to Read
You are developing into a real programmer. You are able to solve problems with code. You can write programs that pass tests. You can implement an ADT.
In this lab, we will be taking the next step towards programming excellence by practicing two vital aspects of programming, testing and style standards. Both of these concepts are essential for larger projects, especially when there is more than one person writing the code. The style standards make it easier to read someone else’s code and the tests give the clearest indication of how the code is meant to work. Tests also give some confidence that the code that is already written behaves as expected.
The Task
You will implement a simple ADT for (sparse) bit vectors. A bit vector is a sequence of 0’s and 1’s. Addition of bit vectors is componentwise addition mod 2, so if we were using lists, [0,1,1] plus [0,0,1] would equal [0,1,1] . That is, the elements at corresponding indices are added mod 2 to produce a new bit vector.
Construction The constructor ( __init__ ) should take a list/set/tuple of indices that should be 1 in the newly constructed bit vector. For example, one could construct the bit vector [0,0,1,1,0,1] with the code:
SparseBitVector([2,3,5])
There is no set length to the bit vector. It can be assumed that the bit vector has an infinite tail of 0’s at the end.
The constructor should raise a ValueError if any of the indices are not non-negative integers.
Accessing by index It should be possible to access the value in index i of a vector v by writing v[i] . To do this in python, you implement the __getitem__ method. It takes two parameters, self and the index. It returns the value (0 or 1).
Addition For bit vectors u and v , return u + v . To do this in python, you implement
the __add__ method.
lastone Returns the largest index in the vector that is a 1. If there are no 1’s, then this
should return -1.
One could use a list for these, but if there are only very few 1’s, then it makes sense to just store a collection of the indices of the 1’s. A set is a good choice here. Addition mod 2 is like symmetric difference of sets A + B = (A | B) – (A & B). Look up the python set operations.
Testing
You have already gotten some experience in running tests. Some kind of tests were given to you directly for most of the homework assignments and labs we’ve done so far. Starting with this lab, you will be expected to write your own tests. This is the best way for you (or a collaborator) to know whether or not your code works.
Unit tests are small tests that exercise individual behaviors. Each unit test is designed to test a particular behavior in a particular situation. If you find a bug that your tests missed, then that is a new situation that was not tested, so you should write a new test rather than modifying the old tests.
The standard package for writing unit tests in python is called unittest . In the unittest package, there is a class called TestCase . A TestCase will have methods
that are individual tests. To write your own tests, you import unittest and then you create a class that extends unittest.TestCase . Each test will be a method whose name starts with the letters “test”. Here is an example of some tests that test the behavior of a Stack .
import unittest
from stack import Stack
class TestStack(unittest.TestCase):
def testinit(self):
“””
Just test that there are no errors when I create a new Stack object.
“””
s = Stack()
def testpushexists(self):
s = Stack()
s.push(5)
s.push(7)
def testpop(self):
s = Stack()
s.push(100)
s.push(2)
self.assertEqual(s.pop(), 2)
self.assertEqual(s.pop(), 100)
In addition to these tests, we might also want to test for error conditions. For example, we might expect there to be an error if one pops an empty stack. This can be done using the following syntax.
def testpopemptystackraiseserror(self):
s = Stack()
with self.assertRaises(IndexError):
s.pop()
Remember that self in these methods refers to the TestCase object. There are several inherited methods that help clarify the results of the tests. These include assertTrue and assertEqual . If the assertion fails, then the test fails.
Running the tests can be done by calling the unittest.main() method. You can put this at the bottom of your test file so that executing the file runs the tests. One would write:
if __name__ == ‘__main__’:
unittest.main()
Tests express expected behavior. You write some short code that uses a method and you assert that the result is what you expected.
Tests don’t have to be DRY.
It is almost always a good idea to keep your code DRY (D on’t R epeat Y ourself). However, for tests, this is not always desirable. It is better to have short, completely self contained tests. This way, there is no need to look all over the test code to see what a test is trying to do.
However, if you copy a test and forget to change the name, only one will execute.
I have included a simple class and some tests so that you will have something to compare to when you write your own tests.
Style Standards
Programs are written to be read by humans. It’s easy to forget this. Neat code and consistent code is easier to read. The specific standards for writing “good” python are written down in a document known as PEP8. It can be found online at https://www.python.org/dev/peps/pep-0008/
You can test your code automatically using a python program called pep8. You can install it using pip or conda depending on how you manage python packages. So, pip install pep8 or conda install pep8 will work on many systems from the terminal. You can find more info about this package at https://pypi.python.org/pypi/pep8 .
For example, when I run pep8 teststack.py on the sample test code included in the skeleton, I get the following output:
$ pep8 teststack.py
teststack.py:4:1: E302 expected 2 blank lines, found 1
teststack.py:29:27: E231 missing whitespace after ‘,’
So, in line 4, I should have had an extra blank line to separate imports and on line 29, I forgot to put a space after a comma.
Summary of Deliverables
1. A Data Structure implementing the Sprase Bit Vector ADT. Call your class SparseBitVector and put it in a file called sparsebitvector.py .
2. Write a set of tests that test all the expected behavior of the class as described in the ADT.
3. Look through the naming conventions and code lay-out sections of the PEP8 document and see if you can get your code to pass the pep8 test and the style test in
Mimir. This is not required for this lab but you might as well practice because it will be part of every homework assignment going forward.