Assignment 6: Generic data, function objects
Goals: Practice working with generic objects and function objects.
Instructions
As always, be careful of your naming of classes, interfaces, methods, and files.
The submissions will be organized as follows:
Submission Homework 6 Problem 1: The file ABST.java with all its classes, interfaces, methods and tests.
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 31.8 on page 474
Problem 1: Function objects and binary search trees
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 come after the current data item. The tree with no data is represented as a leaf. The trees below demonstrate some (small!) valid and invalid examples of binary search trees over integers (the leaves of the tree are not shown):
valid: valid: invalid:
3 2 3
/ \ / \ / \
2 4 1 4 1 4
/ / / \
1 3 2 5(In the last tree, even though the subtree beginning at 4 is a valid binary search tree on its own, the root node is not a valid binary search tree since 2 < 3 but 2 is in the right-subtree.)
Binary search trees are generic over the type of data they contain. To describe an ordering among the values, we need a comparator. We will use Java’s Comparator interface for this purpose.
Do Now!
Valid binary search trees seem to be organized pretty similarly to how well-formed ancestry trees were organized. Try writing out in English a description of the "well-formed ancestry tree property" and of the "valid binary search tree property". What’s the only difference between them?
You will work with a binary search tree that represents a collection of Book objects. 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 several different ordered ways - by title, by author, and by price.
The following class diagram should help you:
+-------------------------+
| abstract class ABST<T> |
+-------------------------+
| Comparator<T> order -------------+
+-------------------------+ |
/ \ |
--- |
| |
----------------- |
| | |
+---------+ +------------+ |
| Leaf<T> | | Node<T> | |
+---------+ +------------+ |
| T data | |
| ABST left | |
| ABST right | |
+------------+ |
V
+---------------+ +-------------------------+
| Book | | Comparator<T> |
+---------------+ +-------------------------+
| String title | | int compare(T t1, T t2) |
| String author | +-------------------------+
| int price |
+---------------+Because every node in a BST must know about how the ordering works, we will use Java’s Comparator<T> interface, and use it as a field of the abstract base class of BST nodes and leaves.
Design the classes BooksByTitle, BooksByAuthor, and BooksByPrice that allow us to compare the books by their title, their author, or price respectively (i.e. these classes will implement the Comparator<T> interface). String-based comparisons should be alphabetical; numeric comparisons should be by increasing value.
Design the classes that represent a binary search tree, following the class diagram shown above. The Node and Leaf constructors should take arguments in the order of its fields as above, starting with the inherited ones. Make examples of data, including binary search trees of Books. (In this example we use an abstract class, rather than an interface, because we need the order field.). Please write comments above each example so that we know more about what examples you are creating.
Design the method insert that takes an item and produces a new binary search tree with the given item inserted in the correct place. If the value is a duplicate according to the tree order, insert it into the right-side subtree. This should work for any of the comparators above. (Where should the newly created nodes obtain their ordering from?) Make sure you’ve tested this method thoroughly before proceeding as the other methods depend on a properly constructed tree. Remember, you want to design incrementally, make sure one method fully works before proceeding to another.
Design the method present that takes an item and returns whether that item is present in the binary search tree. This method should use the Comparator object used to build the tree (i.e. if BooksByTitle is used, then this method returns true if there is a book with the same title as the item, etc.)
Design the method getLeftmost that returns the leftmost item contained in this tree. In the Leaf class, you should throw an exception: throw new RuntimeException("No leftmost item of an empty tree")
Design the method getRight that returns the tree containing all but the leftmost item of this tree. In the Leaf class, you should throw an exception: throw new RuntimeException("No right of an empty tree")
Design the method sameTree that determines whether this binary search tree is the same as the given one: that is, they have matching structure and matching data in all nodes.
Design the method sameData that determines whether this binary search tree contains the same data as the given tree.
Note: Given the following four trees:
bstA: bstB: bstC: bstD: b3 b3 b2 b3 / \ / \ / \ / \ b2 b4 b2 b4 b1 b4 b1 b4 / / / \ b1 b1 b3 b5the following should hold:bstA is the sameTree as bstB
bstA is not the sameTree as bstC
bstA is not the sameTree as bstD
bstA has the sameData as bstB
bstA has the sameData as bstC
bstA does not have the sameData as bstD
Hint: Articulate clearly (in plain language) when one BST has the same data as the another BST. Do the same for sameTree. This will give you any helper operations you may need.
Copy into your project the IList<T> interface and its related classes. Make examples of IList<Book>, including examples that contain the same books (in the same order) as some of your binary search trees.
Design the method buildList for the classes that represent the binary search tree of type T that produces a list of items in the tree in the sorted order.
Hint: Draw a simple BST with 2 or 3 items, and the expected output of buildList. Now think about how to produce this list, given the tree. Now try with bigger examples.