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
- Java
Standard API
- P6TestDriver.java (to be published Wednesday 2/20)
- P6UnitTests.zip
Problem
Description
You will be
modifying and enhancing your Project 5 source
code in the following ways:
- Implementing
a new interface, Comparable from the Java Standard Library, on your
Product class.
- Modifying the
Inventory.contains()
method’s return type and implementing it with a binary search algorithm
for significantly better searching performance.
- Modifying the
Inventory.equals()
method to do an order-independent equality check. This method
will use the modified contains() method for greater efficiency.
- 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.
- Implementing
multilevel sort specifications using the Comparator interface.
- 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
- Make sure
your Program 5 code successfully passes all of the Program 4 tests
before moving on to the Program 6 modifications.
- Then, and
only then, copy
all Program 5 source files to a new project and begin making the
Program 6 modifications.
- Remember to use the tests and given documentation to understand the conditions in which your implementation should work.
- 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.
- 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
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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
- 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
- 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
- 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.
- 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.
- 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.
- Ask
your instructor for assistance if you are not able to run these tests on
your own.
Handing
in Your Source Electronically…
- 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
- Move the
necessary file(s) to your vogon account using your favorite FTP client
program.
- Log on to vogon using your favorite Shell client program.
- 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!
- 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