|
CSE 143 Winter 2004 -- Homework #6 |
|
 UW Home |
CSE Home |
Announcements
|
Message
Board |
Contact Info |
|
|
Homework 6. Two kinds of ListsYour assignment is to implement the functionality found in Java's List interface. (PDF of Java's List interface here)You should implement two different versions. One based on the recursive structure presented in class (a list is either empty, or an item followed by a list), and the other based on the linked structure (a list is set of links, where each link contains an item and a reference to the next link). Your recursive implementation should be in a class called RecursiveList, and your linked implementation should be in a class called LinkedList. You might, as you're implementing, discover that some of the methods in the List interface are neutral to the actual implementation, generally because they can be expressed in terms of lower level operations (eg, add(object) can be defined in terms of add(index, object)). In order to avoid duplicating work, you might want to put these common operations in a base class, called CommonList, which can serve as a common parent to Recursive and Linked classes. TestingIn addition to your implementation, you should also make sure that your code works. I have provided a class ListTester, that provides a framework for building and running tests. You will need to study this framework, specifically class Tester, and add your own tests following the model of the few that are already in there. In the end, your implementation (LinkedList and RecursiveList) should demonstrate that they work with the following List methods: [laptop:Lectures/L7/hw] bershad% java ListTester -linked LinkedList-Test:add LinkedList-Test:addAll LinkedList-Test:clear LinkedList-Test:contains LinkedList-Test:containsAll LinkedList-Test:equals LinkedList-Test:get LinkedList-Test:indexOf LinkedList-Test:isEmpty LinkedList-Test:iterator LinkedList-Test:lastIndexOf LinkedList-Test:remove LinkedList-Test:removeAll LinkedList-Test:retainAll LinkedList-Test:set LinkedList-Test:size LinkedList-Test:subList LinkedList-Test:toArray PASSED Similarly, [laptop:Lectures/L7/hw] bershad% java ListTester RecursiveList-Test:add RecursiveList-Test:addAll RecursiveList-Test:clear RecursiveList-Test:contains RecursiveList-Test:containsAll RecursiveList-Test:equals RecursiveList-Test:get RecursiveList-Test:indexOf RecursiveList-Test:isEmpty RecursiveList-Test:iterator RecursiveList-Test:lastIndexOf RecursiveList-Test:remove RecursiveList-Test:removeAll RecursiveList-Test:retainAll RecursiveList-Test:set RecursiveList-Test:size RecursiveList-Test:subList RecursiveList-Test:toArray PASSEDYou should make sure that your test routines stress your implementation. A good test routine is one that reveals lots of bugs. A bad one hides bugs. We will be testing your solution with our own set of test routines and expect that it will pass. Lastly, you should modify the solution to the midterm so that, instead of using a two dimensional array to represent the tiles, you use a list of lists. The main list contains a list per row, where each list per row contains a list of tiles. You might find it useful to define either a subtype or a wrapper method which provides the appropriate indexing operations. In either case, you should be able to invoke the PuzzleController as: java PuzzleControlleror java PuzzleController -linkedThe first should use the recursive implementation of lists, and the second should use the linked implementation. Some List Routines That You Don't Need to ImplementThere are four methods in the List interface that you don't need to implement. So that your class implementations compile, I have provided you with roughed out versions of these four methods, which you can use directly. You will find these in a file called CommonList.java. You may either copy these methods directly into your class implementations, or, as described above, use subtyping. What to Turn InYou should turn in a directory containing:
When and How to Turn InUsing the turnin program, please submit your solution by 11.59 PM Monday March 8.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
