$29
Assignment 4 Solution
Goals: Practice working with abstract classes, constructors, exceptions.
Instructions
The names of the projects and some of the project files must be exactly the same as specified in the assignment. Failure to do so makes it impossible for the graders to run your submission and results in immediate loss of at least 50% of the homework credit.
Make sure you follow the style guidelines for code indentation.
You will submit this assignment by the deadline using the Web-CAT submission system. We will be practicing its use during the lab next week.
With each homework you will also submit your log file named pairxxx.txt where you replace xxx with your pair number.
On top of every file you submit you will have the names of both partners, and the pair number.
The .txt file will be the log of your work on this assignment. Each log entry will have data and time, who was present (one or both of the partners) and a short comment decribing what you were working on.
Submission instructions:
• For all problems make sure the name of the class that contains the sample data and the tests starts with Examples... — otherwise WebCAT does not know where the tests are defined.
• Submit the file Strings.java with all classes, interfaces, methods, and tests.
• Submit the file ABST.java with all classes, interfaces, methods, and tests. If you wish to keep the examples and tests in a separate Java file, you may do so.
• Submit the file BoundedPt.java with all classes, interfaces, methods, and tests.
• Do not forget your log file.
• Submit one file HW4.zip
Due Date: Thursday, October 17th, 11:59 pm.
Practice Problems
Work out these problems on your own. Save them in an electronic portfolio, so you can show them to your instructor, review them before the exam, use them as a reference when working on the homework assignments.
Problem 1
• Design the class Date that represents a calendar date with the day, month, and year.
Make sure that the constructor verifies that the day is in the range from 1 to 31, the month is between 1 and 12, and the year is greater than 1900.
• Add a constructor that allows the user to give only the day and month, assuming the year will be 2013.
• Add a constructor that allow the user to give them month as "Jan", or "Feb" or "Mar", instead of the numeric value. (You may do this just for the first three months - to save yourself a lot of typing and many tests.
• Add to your class a method with the header
public String toString()
that produces the date in the form 10/8/2103
Problem 2
Follow-up on the work you have done in the last lab. You already have the files that represent a list of ImageFiles. Start a new project that includes these files,you may reuse the sample data you have defined for your lab project.
Now do the following:
• You now want to sort the image files by size, later by their names. How could you do it writing only one sort method?
Hint: Design the interface ImageFileComparator that defines a method compareImageFiles that consumes two ImageFiles and produces an integer less that zero, if the first item is comes before the second in our ordering, produces a zero, if the two items are equal in our ordering, and prodces a positive integer if the second item comes before the first one in our ordering.
• Of course, you now need to define a class that represent the ordering by the image size (name it ImageFileSizeComparator, and another class that compares the image files by their names (name this class ImageFileNameComparator.
• You are now ready to design the sortImageFiles method that produces a sorted list of ImageFiles based on the desired ordering.
Finish this method design — make sure you test all the methods.
Make sure you follow the design recipe.
Pair programming assignment
Problem 1: Function objects, sorting
Start with your solution to the String problem from the previous homework.
• Design the interface StringsCompare that contains a method
public boolean comesBefore(String s1, Strings2);
• Design a class (function object) StringLexComp that implements this interface by comparing the Strings lexicographically.
• Design a class (function object) StringLengthComp that implements this interface by comparing the Strings by their length from the shortest to the longest.
• Modify your solution for the method isSorted so that it would verify that the list is sorted by one of the desired orders.
• Modify your solution for the method merge so that it would merge the list that are sorted by one of the desired orders.
• Design the method sort that produces a sorted list, in the order given by the StringsCompare function object.
Problem 2: Function objects, binary search trees
You will work with a binary search tree that represents a collection of Book objects. Remember, a binary search tree represents an ordered collection of data where each node holds one data item and has links to two subtrees, such that all data items in the left subtree come before the current data item and all data items in the right subtree coma after the current data item.
The tree with no data is represented as a leaf.
Start a new project and define in it the class that represents a Book as shown in the class diagram below. We want to keep track of the books in seeral different ordered ways - by title, by author, and by price.
The following class diagram should help you.
+-----------------------+
| abstract class ABST |
+-----------------------+
+----------| IBookComparator order |
| +-----------------------+
| / \
| ---
| |
| -----------------
| | |
| +------+ +------------+
| | Leaf | | Node |
| +------+ +------------+
| | Book data |--------+
| | ABST left | |
| | ABST right | |
| +------------+ |
| v
v +---------------+
+-------------------------------+ | Book |
| IBookComparator | +---------------+
+-------------------------------+ | String title |
| int compare(Book b1, Book b2) | | String author |
+-------------------------------+ | int price |
+---------------+
• Start a new project and define in it the class that represents a Book as shown in the class diagram. We want to keep track of the books in several different ordered ways - by title, by author, and by price.
• Design the interface IBookComparator and design the classes BooksByTitle, BooksByAuthor, and BooksByPrice that allow us to compare the books by their title, to author, or price respectively.
• Design the classes that represent a binary search tree of books, following the class diagram shown above. Make examples of data.
• Design the method insert that produces a new binary search tree with the given item inserted in the correct place.
• Design the method getFirst that produces the first Book in the binary search tree (as given by the appropriate ICompareBooks.
In the Leaf class this method should have the following body:
throw new RuntimeException("No first in an empty tree");
• Design the method getRest that produces a new binary search tree with the first Book removed.
In the Leaf class this method should have the following body:
throw new RuntimeException("No rest of an empty tree");
• Design the method sameTree that determines whether this binary search tree is the same as the given one (i.e., has matching structure and matching data in all nodes).
• Design the method sameData that determines whether this binary search tree contains the same books as the given tree.
Note: Given the following three trees:
bstA: bstB: bstC: bstD:
b3 b3 b2 b3
/ \ / \ / \ / \
b2 b4 b2 b4 b1 b4 b1 b4
/ / / \
b1 b1 b3 b5
the following should hold:
◦ bstA is the same tree as bstB
◦ bstA is not the same tree as bstC
◦ bstA is not the same tree as bstD
◦ bstA has the same data as bstB
◦ bstA has the same data as bstC
◦ bstA does not have the same data as bstD
• Now add to your project the data definitions for a list of books, i.e. the interface ILoBook and the classes MtLoBook and ConsLoBook.
Make examples, including those that contain the same data as some of your binary search trees, arranged in order.
• We would like to know whether a binary search tree of books contains the same data as a list of books.
Design the method for the binary search trees sameAsList that consumes a list of books and determines whether the binary search tree contains the same books and the given list (in the same order).
Hint: There are two ways how this can be done.
The first one is to add the methods isEmpty, getFirst(), and getRest() to the classes that represent the list of books.
The second is to first design the method buildList below, then compare the resulting list with the one given before.
• Design a buildTree method for the classes that represent a list of books. The method consumes a binary search tree of books, and inserts into it all items in this list, returning at the end a binary search tree that contains all items in this list.
If this method is invoked with a binary search tree that is a Leaf, then the resulting tree should be the sameAsList when ocmpared to the sorted version of this list.
So, for example, the list (b3, b1, b4, b5) would produce the tree bstD shown above.
• Design the method buildList for the classes that represent the binary search tree that consumes a list of books and adds to it one at a time all items from this tree in the sorted order. (If we invoke this method with an empty list, we end up with a list of all items in this tree in the reverse order.)
• Test that your design works by checking that
(blist.buildTree(new Leaf())).buildList(new MtLoBook())
produces a reverse-sorted blist.
Problem 3: Constructors
Here is a class that represents a location within our drawing canvas:
class BoundedPt extends Posn{
int width = 600; // the width of the canvas
int height = 400; // the height of the canvas
BoundedPt(int x, int y){
super(x, y);
}
}
We would like to make sure that the user cannot define a point outside of the width and height of the canvas.
Design a new constructor that throws an exception if the given coordinates are outside of the bounds, and lets the user know how far out of bounds the values were on each side. So the message should match exactly the following (replacing, of course the word right with the appropriate one from left, right, top, or bottom.
"The given x coordinate was 40 points beyond the right edge"
Note: The call to the super constructor must be the first action of the constructor for this class, even when the constructor throws an exception.
