Assignment 7: Generic data, function objects, circular data
Goals: Practice working with generic objects and function objects and circular data.
Partners: This is a partner assignment. Pair programming means that you and your partner work on the problem sets jointly. Every partner must be able to solve every homework problem in the end. It is an academic integrity violation to submit work under your name that you have not worked on. Doing so may result in earning a 0 on the work and a report to OSCCR. You may also lose the privelege of working with a partner. Therefore both partners must make the effort to meet regularly and work together on every part of the assignments/labs.
Instructions
As always, be careful of your naming of classes, interfaces, methods, and files.
Due Date: Thursday, November 2nd at 9:00pm
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. 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?)
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 in the same order 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.
Problem 2: The Registrar’s Office
The registrar’s office maintains a great deal of information about classes, instructors, and students. Your task in this problem is to model that data, and implement a few methods on it. We deliberately do not give you the class diagram for this problem: from the description below, you should properly design whatever classes you think are relevant. Please use generic lists (i.e. IList<T>) for this problem.
7.1 Data constraints
A Course consists of a name (a String), an Instructor named prof, and a list of Students named students. No Course can be constructed without an Instructor available to teach it. Hint: Do you think that you should provide a list when constructing a Course? Why or why not?
An Instructor has a name and a list of Courses named courses he or she teaches. Instructors are initially constructed without any Courses to teach.
A Student has a name, an id number (an int), and a list of Courses they are taking. Students are initially constructed without taking any Courses.
It should always be the case that any Student who is enrolled in a Course should appear in the list of Students for that Course, and the Course should likewise appear in the Student’s list of Courses.
It should always be the case that the Instructor for any Course should have that Course appear in the Instructor’s list of Courses.
7.2 Methods and examples to design
Design a method void enroll(Course c) that enrolls a Student in the given Course. Design any helper methods as appropriate.
Design a method boolean classmates(Student c) that determines whether the given Student is in any of the same classes as this Student.
Design a method boolean dejavu(Student c) that determines whether the given Student is in more than one of this Instructor’s Courses.
Construct example data consisting of at least five Students, at least four Courses and at least two Instructors. Test all your methods thoroughly.