CS 242 Fall 2009 : Assignment 2.1
CS 242 Fall 2009 : Assignment 2.1
This page last changed on Sep 22, 2009 by cemeyer2.
Note, always remember to check this assignment description for Update markers over the course of the next week or so for changes to the assignment specification.
Objective: Write a spec for a library to solve mazes and then write unit tests for how that library will function
Language: Java with jUnit or C# with csUnit
This week we will begin looking into unit testing and test-driven development. Eventually, we’ll explore the Model-View-Controller (MVC) design methodology to help us create a GUI. We’ll be designing and creating a maze-solving library, using the above techniques. We’ll also learn a little bit of AI along the way.
Since the intention is to eventually design a GUI, you should consider using either Java or C# to complete this assignment. Bear in mind that you should be able to run your code during class, so please bring in whatever you need to demonstrate your code (especially important if you decide to use an IDE such as Eclipse or Visual Studio).
The assignment will span three weeks, and in this first week, we will cover unit testing and test-driven development. You will be expected to write a maze-solving library. For this first week, we will only be concerned with stubbing out our functions for our library and writing unit tests. The library will eventually need to implement a wall-following (or right-hand rule) algorithm, and any supporting methods. Your library should be able to read in a maze, solve it (if there is a solution) and return the winning path. Also, your library should be able to be pluggable to support new algorithms for solving mazes. See the questions to consider portion of the assignment near the bottom to see all the things you should keep in mind when working on this assignment.
The assignment is due on Wednesday September 23 at 8am in SVN. Please place all files files needed for compilation and demo’ing of your assignment (but no executables) into a folder in your repository called Assignment2.1, that is, you should be able to bring up https://csil-projects.cs.uiuc.edu/svn/fa09/cs242/NETID/Assignment2.1/ in a web browser (replacing NETID with your actual netid) and see all of your code.
For this and the next couple assignments, you will write a library for solving mazes. You will be expected to write a library that can solve a maze and return the winning path through the maze. You will then write unit tests to build a “living documentation” of the desired functionality of that code. As usual, your code will be required to compile without errors.
The mazes will be defined in a BMP image. White (255) will denote walls and black (0) will denote eligible paths. The start and end points of a maze will correspond to points along the edges of the maze where the color is black. You may assume that there will only ever be two such areas. Note that these areas may be several pixels wide, and you will be expected to enter via one path and exit via a different path. Below are some examples:
Not all mazes are solvable. Of the ones that are solvable, you may not enter and exit via the same path. For example, in the first maze above, you must either enter via the topmost path and exit via the bottomost path, or vice versa.
For this first week, you will be expected to have a design that can implement a wall-following algorithm. You can imagine that this algorithm works as if you were to traverse the maze yourself, and keep your right hand on a wall at all times. The result is that you will be able to find your way out of simply connected mazes. We will only expect you to be able to solve mazes that are solvable via this algorithm.
A slightly more detailed description is provided on Wikipedia: http://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower
But when you lay out your design, you should think carefully about modularity. What if we asked you to change the algorithm used to solve the maze? How would your design be able to adapt to change? See the questions to consider section for this and other things you should keep in mind when coming up with and writing your design.
Unit testing is a great way to ensure that, given an implementation, the code works correctly. This is enforced by creating small (unit) tests for each function. Each test should be able to call the function it is testing, and determine if the function worked according to specification.
This can be a funny concept at first, but it is really quite simple: If you know the input to a function, and you know how the function works, you should know exactly what the output of the function is. Since you know what the output should be before even calling the function, you can compare the output you get from making the function call to the expected output. If they match up, then the test has succeeded. Otherwise, it fails.
In general, one test is not sufficient to be confident in the correctness of a function. While it is better than nothing, a complete test suite would try all corner-cases, as well as the common case. For instance, if a function operates on positive integers, and it is called with a negative parameter, does it do the right thing? The success and failure of tests are completely defined by the person designing the application. Therefore, it is necessary to clearly understand what a function should do in order to test it.
Each test should have a comment header block the explains exactly what the test does, including objects it works on, specific methods it tests, and any preconditions and postconditions that must be met and are set if the test passes. An example of a valid jUnit test would look like (for an imaginary Phone object):
Every function should have at least one test, but to get full points you should ensure that you cover all corner cases and other possibilities that your library might eventually encounter. For the purposes of this assignment, you do not need to write tests for VERY trivial, small functions (5 lines or less). As an example, below are some functions you should implement:
Of course, these method-tasks are a very rough guide. You should further split up these tasks into sub-tasks depending on your specific implementation. These sub-tasks will be performed by helper functions which will be easier to test. Modularity is key to unit-testing. The less that each individual function does, the easier it will be to test each one fully, and the more correct your code will be as a result. It may even be a good idea to split your library into multiple classes depending on the data structure you use as an internal representation for a maze.
There are some resources which aid in the unit testing process: JUnit for Eclipse, CSUnit for C#, as well as others. You are free to use these if you would like. Eclipse and JUnit are available on the CSIL Linux computers, and an introduction to using JUnit with Eclipse is provided in this assignment description.
An example of jUnit 4 tests was shown above. Generally, developers put all unit tests for one type in one file, with multiple files of tests composing a test suite for the library or application. It will be much easier for you to keep things organized if you follow a similar pattern. Although Eclipse will let you run a single file containing jUnit tests directly, it takes a bit more effort to have Eclipse run all tests in all files at once (your test suite). For example, say I had tests for a Phone object in a file called PhoneTests and tests for an Address object in a file called AddressTests, I could have the Eclipse jUnit runner run them both by creating a file called something like ContactInfoTests and have it contain:
If I was to then instruct Eclipse to run ContactInfoTests as a jUnit test, it would run all the tests in both the PhoneTests class and the AddressTests class. You might not need to, but you can chain it up even further if you divide your tests into subcategories and have a master suite file like:
You are encouraged to use the Eclipse which is installed on the CSIL Linux Terminal Servers. If you would like, you may download and install Eclipse on your own machine. Once you have downloaded eclipse, there is a great plug-in called Subversive that integrates subversion into the IDE for you, so you do not have to worry about using the command line client or tortoisesvn. In addition, it is smart in that it only will commit the files that we require and nothing more, so you do not have to worry about accidentally committing binaries to the repository. Instructions on how to install Subversive can be found here.
There is a good tutorial at http://www.vogella.de/articles/JUnit/article.html. You may ignore section 5 on Easy Mock, as it is not a requirement for this assignment. Also note that the JUnit4.x.jar file is included with Eclipse 3.5, so you should not have to download the file from the JUnit website to add it to your classpath.
After writing some JUnit tests, you can run them by right-clicking the project in the Package Explorer, and select Run As > JUnit Test. This will bring up the JUnit view which shows information on which tests were run, and how many passed. For this assignment, all tests should fail.
Visual Studio is free to all engineers to download from the Cites Software Webstore under the departments tab. We are not very familiar with the specifics of setting up and running csUnit like we are with jUnit, but if you plan on using C#, csUnit is a good choice to use. See http://www.csunit.org/tutorials/ for more information about getting up and running with csUnit.
First, ask questions on the newsgroup. If you have a question, there is a pretty good chance someone else has the some one and an even better chance that someone else in the class or one of the TAs will be able to answer it for you. If you are still having a problem, email your moderator or one of the TAs to get advice. Remember, its best to ask questions early on so they have time to be answered. Don’t wait until the last second to get started then realize that you are confused.
Below are the exact requirements for completing this assignment. You will be graded primarily on the thoroughness of your unit tests, and on your design, documentation, and usability of your library. You must be able to run all your unit tests and inform the user if they have passed or failed. Note, we expect all unit tests to fail the first week since your library will have no implementation, only function definitions. You should be prepared to defend your design decisions and let your section know exactly how your implementation will work once it is defined.
|Document generated by Confluence on Feb 22, 2012 18:18|