Assignment 6
Goals: Practice working with function objects; understand binary search trees.
Instructions
The names of the projects and some of the project files must be exactly the same as specified in the assignment. Make sure you follow the specific submission instructions for each assignment.
Also make sure you follow the style guidelines as published in a separate document.
You will submit this assignment by the deadline using the Web-CAT submission system.
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:
You may divide your solution to both problems into any number of .java files, but make sure that the name of every file matches a name of one of the classes or interfaces defined within that file.
Name the Examples class for Problem 1 ExamplesImageFiles and define within an instance of the data for the list of files ILoIF imglistall that has been included in the Lab 6 files.
Make sure the method names for all methods, classes, interfaces, and fields you define match the names given in the assignment.
For Problem 2, make sure the message the exception generates matches exactly the one shown in the assignment.
Name the Examples class for Problem 2 ExamplesBooks and define within the data following data:
IBookComparator booksByTitle = new BooksByTitle();
IBookComparator booksByPrice = new BooksByPrice();
Book b1 = new Book("b1", "bb1", 50);
Book b2 = new Book("b2", "bb1", 20);
Book b3 = new Book("b3", "bb1", 10);
Book b4 = new Book("b4", "bb1", 40);
Book b5 = new Book("b5", "bb1", 30);
Submit one file HW6.zip
Due Date: Thursday, February 21st, 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.
Finish the following problems from Lab 6:
If you have some time left, design the method filterImageFile that produces a list of all ImageFiles that satisfy the ISelectImageFile predicate. Test it with as many of your predicates as you can.
Follow the same steps as above to design the method anySuchImageFile that that determines whether there is an item a list that satisfies the predicate defined by the select method of a given instance of the type ISelectImageFile.
Problem 1: Function objects, sorting
This problems is a 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.
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 representes 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.