CPE 102

Winter 2007

Program 6

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 Wednesday, 2/20/08

90% (minus any deductions) by 9:00pm Thursday, 2/21/07

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

70% (minus any deductions) by 9:00pm Monday, 2/25/07

Errata:

None

Objectives

• To write ordering logic that can be used by any sorting algorithm.
• To implement a sorting algorithm.
• To implement a binary search algorithm and make use of it to perform an order-independent equality check of a collection.

Resources

1. Java Standard API

2. P6TestDriver.java (to be published Wednesday 2/20)
   
   
3. P6UnitTests.zip
   

Problem Description

You will be modifying and enhancing your Project 5 source code in the following ways:

1. Implementing a new interface, Comparable from the Java Standard Library, on your Product class.

2. Modifying the Inventory.contains() method’s return type and implementing it with a binary search algorithm for significantly better searching performance.

3. Modifying the Inventory.equals() method to do an order-independent equality check.  This method will use the modified contains() method for greater efficiency.

4. Implementing a sort algorithm (your choice - Bubble, Selection, or Insertion sort). This sort algorithm will be used to sort the Inventory in two ways, one using the compareTo method of the Product objects in the inventory and the other using Comparator objects.

5. Implementing multilevel sort specifications using the Comparator interface.
   
   
6. JUnit tests will be provided in P6UnitTests.zip.  Replace the stubbed out versions of InventoryTest, BookOnTapeTest, and CDTest with the tests you wrote in Program 5.  Your Program 5 versions will now need to be extended to test additional methods that you write in Program 6 and some tests will need to be modified to reflect changes in Program 6.  
   
   Below you will find out that you need to modify the return type of contains() to return a Product instead of a boolean.  You can test for the return of a null by assertNull().  There is also an assertNotNull().  The full list of asserts can be found in the JUnit API under the Assert class.

Suggestions

1. Make sure your Program 5 code successfully passes all of the Program 4 tests before moving on to the Program 6 modifications.

2. Then, and only then, copy all Program 5 source files to a new project and begin making the Program 6 modifications.
   
3. Remember to use the tests and given documentation to understand the conditions in which your implementation should work.
   
4. Follow the test-driven development style by first reading the given JUnit test for the method you want to implement, then implement that method's functionality and watch the test pass.  If the test is not given, then write 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. All of the text files (*.txt) used in Program 5 will need to be present in the directory where your Program 6 .class files are found for the test driver to run successfully.

2. Implement the Comparable interface in the Product class.  You may read about the interface and its method in your text and/or in the Java documentation.  Your implementation of the compareTo() method should result in Products with numerically lower product IDs to be considered less than Products with numerically higher product IDs and equal when the product IDs are the same.

3. Modify the return type of the Inventory.contains(int productID) method from boolean to Product.  It should return null if the inventory does not contain a product with the specified product ID or a reference to the Product if it finds a match.

4. Modify the contains() method to do a binary search as opposed to the linear search used in Project 4.  I suggest you use the binary search algorithm presented in your text with a few minor modifications to allow it to work with the ArrayList of inventory.  Your inventory will be sorted using the compartTo() method described above prior to any calls to contains() so, as long as your compareTo() implementation is correct, your binary search can assume the inventory is in ascending order by product ID.

5. Modify the Inventory.equals() method to do an order-independent equality check.  Two Products are to be considered equal if they have the same product-ID and are equal as determined by the equals() method of Product and all its subclasses.  This method must use the Inventory.contains() method described above so that it takes advantage of the relatively efficient binary search you just implemented.  An order-independent equality test of inventory will make sure that the two inventories have the same number of objects and that all of the objects in one list appear in the second list.  Note that matching product IDs is not an adequate test.  You can use the contains() method to get a reference to a Product that has the same product ID but you MUST USE the product’s equals() method to determine if they are identical products (quantity is still ignored). This implies that each object’s equals method must be correctly implemented (which should be true since you did that way back in Program 4!).  Note that your solution will be graded on its efficiency.

6. Implement a new method in the Inventory class with the following signature:

public void sort()

This method must implement one of three sort algorithms, Bubble, Selection, or Insertion sort, and sort your inventory using the Comparable.compareTo() method implemented on your Product class to determine ordering. You should use the algorithm in your text with a few modifications so that it works with an ArrayList and the Comparable.compareTo() method above.

7. Implement a new method in the Inventory class with the following signature:

public void sort(Comparator<Product> comparator)

This method must also implement one of three sort algorithms, Bubble, Selection, or Insertion sort, and sort your inventory in whatever order is specified by the Comparator object passed in.  Obviously, you will need to understand how a Comparator object works to be able to write this method successfully.  Lecture, your text, the Java documentation, and my office hour are your resources.

8. Implement a new class called InventorySortA that implements the Comparator interface.  This interface requires you to implement a method called compare(Product, Product).  This method determines the relative order of two Product objects.  When used to sort Product objects this method should result in all products being sorted in ascending order by class name.  This means all Book objects would come before all BookOnTape objects which would come before all CD objects.  Within Book objects, the books should be sorted by ascending author last name, then first name, then middle name.  Within BookOnTape objects, the book-on-tapes should be sorted by reader last name, then first name, then middle name.  Finally, within CD objects the cds should be sorted by artist last name, then first name, then middle name.  For example, examine the following products:

Book, Allen, John, G

Book, Allen, Mark, Stone

Book, Poe, Edgar, Allen

BookOnTape, Jones, James, Earl

BookOnTape, Zed, Led,

CD, Bach, Johan, Sebastian

CD, Marley, Bob,

CD, Marley, Robert, A

CD, Marley, Robert, B

9. Implement a new class called InventorySortB that implements the Comparator interface (See more detailed description above.  When used to sort Product objects this method should result in all products being sorted in descending order by class name and within class name by ascending product ID.  For example:

CD, 66666

CD, 88888

CD, 99999

BookOnTape, 55555

BookOnTape, 77777

Book, 11111

10. Implement a new method in the Inventory class with the following signature:

public ArrayList<Product> getInventory()

This method should return a reference to the private ArrayList containing the inventory of Product objects in your Inventory class.  Note that this method violates the encapsulation of the inventory data and is not a method you would typically provide.  It is necessary in this project so that I can inspect your data from my test program and so that I can, if necessary, bypass errors in your sort and search logic and grade other parts of your implementation.

Testing With the Provided Tests

1. Your code must be 100% correct to recieve credit.  Correctness will be determined by running the acceptance test P6TestDriver.java to be published Monday 2/18.  
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 6
            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 Wednesday's deadline, 90 for Thursday, 80 for Friday, or 70 for Monday, for example Program6-100, Program6-90, et cetera.

12:01pm vogon ~$ handin graderkm Program6-x Inventory.java Product.java AbstractBook.java Book.java BookOnTape.java CD.java Name.java DuplicateProductIDException.java DuplicateProductException.java MissingProductException.java InsufficientProductException.java DelimitedTextIO.java InventorySortA.java InventorySortB.java BookOnTapeTest.java InventoryTest.java CDTest.java time.txt