Assignment 8
Goals: Practice working with ArrayList and Comparator. Learn to define and use visitors to provide extensibility for a union of classes.
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.
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.
Due Date: Monday, November 5th, 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 all of the problems from the Lab 8 that deal with ArrayList, other than the binary search.
Finoish the problem from the Lab 8 that deals with the list visitors.
Problem 1
Finish and hand in the Binary Search problem from the Lab 8.
Design a class Book (with the author and the title given as a String), and define five examples of books. Create two ArrayListss of books, one sorted by the author’s names, one sorted by their titles.
Design two classes that implement the Comparator<Book> interface, one that compares the books by their title, another that compares the books by the authors’ names. Use these two classes to design six additional tests for your binary search method (three with each Comparator).
Problem 2
You will work with a binary search tree that represents a collection of Book objects. (Use the same Book class you have defined for the first problem.)
A binary search tree (BST) is defined by the following class diagram:
+------------------------+ |
| abstract class ABST | |
+------------------------+ |
+----------| Comparator<Book> order | |
| +------------------------+ |
| / \ |
| --- |
| | |
| ----------------- |
| | | |
| +------+ +------------+ |
| | Leaf | | Node | |
| +------+ +------------+ |
| | Book data |--------+ |
| | ABST left | | |
| | ABST right | | |
| +------------+ | |
| v |
v +---------------+ |
+-------------------------------+ | Book | |
| Comparator<Book> | +---------------+ |
+-------------------------------+ | String title | |
| int compare(Book b1, Book b2) | | String author | |
+-------------------------------+ | int price | |
+---------------+ |
and must satisfy with the following constraints:
Every data item in the left subtree comes before the data item in the node
Every data item in the right subtree comes after the data in the node
The left subtree is a ABST
The right subtree is a ABST
Your task is to design classes that represent binary search trees, design some
methods for these classes, make these classes accept a visitor —
Here are the details:
Design the method insert that produces a new binary search tree with the given Book inserted in the correct place.
Design the method getFirst that produces the first Book in the binary search tree (as given by the appropriate Comparator<Book>.
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 in 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).
Define the visitor interface for the ABST as follows:
// to represent a visitor for ABST
interface IABST_Visitor<R>{
// define the method for the leaf
R forLeaf();
// define the method for the node
R forNode(Book data, ABST left, ABST right);
}
and add the needed accept method to the ABST class hierarchy.
Design the class ABST_TitleVisitor that implements the IABST_Visitor<String> that produces a String that combines the titles of all books in the ABST in such a way that each title is on one line (i.e. follow each title with the String "\n", and all titles in the left subtree are shown first, followed by the title of the node, then followed by the titles in the right subtree.
Of course, run tests to make sure your methods work correctly.
Design the class ABST_AuthorVisitor that implements the IABST_Visitor<String> that produces a String that combines the authors of all books in the ABST in such a way that each author is on one line (i.e. follow each author with the String "\n", and all authors in the left subtree are shown first, followed by the author of the node, then followed by the authors in the right subtree.
Of course, run tests to make sure your methods work correctly.
Design the class ABST_TraversalVisitor that implements the IABST_Visitor<ArrayList<Book>> that produces an ArrayList<Book> that combines all books in the ABST in such a way that all books in the left subtree are added first, followed by the book in the node, then followed by the books in the right subtree.
Of course, run tests to make sure your methods work correctly.