CPE 102

Winter 2008

Program 7

Due Date

You must turn in a functionally correct program to receive any credit.  The grade you receive will be based on when you turn it in minus any deductions for the quality of your implementation and/or multiple submissions.  There is no deduction for the first submission and a 5% deduction for each additional submission, if any.  Programs will be checked for correctness once a day and you will be notified by email if your submission is not functionally correct.  Programs will be graded after the last due date and the results will be emailed to you within a few days of that date.

100% (minus any deductions) by 9:00pm Friday 2/29/08

90% (minus any deductions) by 9:00pm Monday, 3/3/08

80% (minus any deductions) by 9:00pm Tuesday, 2/28/07

70% (minus any deductions) by 9:00pm Wednesday, 3/1/07

Errata:

   Updates and corrections, if any, will appear here.

Objectives

• To implement a linked-list data structure and associated Iterator.
• To understand the performance characteristics of a linked-list data structure.
• To gain more practice developing unit tests for code you develop.

Resources

1. Java Standard API
2. OrderedLinkedList javadocs
3. ListIterator javadocs
4. P7TestDriver.java (To be published Friday 2/29/08)
5. JUnit API
6. AllTests.java
   

Problem Description

1. You will be implementing an ordered linked-list data structure and associated Iterator from scratch matching provided javadoc behaviors. Except for being an ordered linked-list this implementation will be a simplification of the Java Standard library LinkedList and ListIterator classes. If you are not sure how a particular method should behave from this specification you should experiment with the closest equivalent in the Standard Library equivalent. In the absence of any explicit specification to the contrary your methods should behave like the Standard Library versions with the same or similar name. Ask for any necessary clarifications early!
   
2. You will be provided only the AllTests.java file.  You will need to create the test file OrderedLinkedListTest to test the functionality of your program.  Be sure to test each method in the OrderedLinkedList class.  To test the methods in your private inner-class ListIterator (see below for details), use OrderedLinkedList's listIterator() method to get you an instance of the ListIterator object, which can then be tested.  Ask your instructor if you have any questions on how to do this.
   
   Furthermore, the full list of asserts can be found in the JUnit API under the Assert class.

Suggestions

1. Implement a stubbed version of all the methods in the classes and make sure it compiles. Be sure to support generics as specified and work out any and all syntactic issues before proceeding.

2. Implement the constructor OrderedLinkedList(Comparator), add(E), get(int), and size() first and test them thoroughly with your own JUnit tests before working on the rest of the methods or using the provided test driver.

3. Do not use the ListIterator to iterate through the list in your OrderedLinkedList implementation – if you do you will not be able to test list and iterator until both are complete. I strongly suggest implementing the OrderedLinkedList first, making sure it works and then implement the ListIterator.
   
   
4. Follow the test-driven development style by first writing the test for how the method should work, see that it fails (since you have not written the code yet), then write the code to pass the test.
   
   
5. Keep track of your hours worked as you go, so you don’t have to guess when you hand in your assignment (see handin section below for information on time.txt).

Specification

1. Implement a class called OrderedLinkedList to this specification.

2. Implement an interface called ListIterator to this specification.

3. Remember that the ListIterator interface should be implemented by a private inner-class in OrderedLinkedList class.

Testing With the Provided Tests

1. Your code must be 100% correct to recieve credit.  Correctness will be determined by running the acceptance test P7TestDriver.java to be published Friday 2/29.  
2. In addition to the acceptance test, sections 7 and 9 will be graded on the quality of JUnit tests they create for this program, section 3 will not.
3. Use the JUnit tests while developing in a test-driven approach to ensure your code's correctness before the acceptance test is released.  Run them by opening the AllTests.java file and executing it.
4. Ask your instructor for assistance if you are not able to run these tests on your own.

Handing in Your Source Electronically…

1. Create a plain text file called time.txt to log the amount of time spent on the assignment. The file will contain only three lines with the following information on each line: name, project number, hours spent.
                Example time.txt file:
            Sally Student
            Program 7
            7.5 hours
   
2. Move the necessary file(s) to your vogon account using your favorite FTP client program.
   
   
3. Log on to vogon using your favorite Shell client program.
   
   
4. Change directory (cd-command) to the directory containing the file(s) to hand in.  Be sure you code compiles and runs correctly on vogon before turning it in!
   
   
5. Use the following handin command being sure to replace the x with the correct maximum score you can earn based on the due date, i.e., replace y with 100 if you are handing in by Friday's deadline, 90 for Monday, 80 for Tuesday, or 70 for Wednesday, for example Program7-100, Program7-90, et cetera.

12:01pm vogon ~$ handin graderkm Program7-x OrderedLinkedList.java ListIterator.java OrderedLinkedListTest.java time.txt