On this page:
Instructions
Problem 1: Function objects and binary search trees
Problem 2: Visitors
6.10

Assignment 6: Visitors

Goals: To practice using the visitor pattern.

Instructions

As always, be very careful with your naming conventions.

The submissions will be organized as follows:

Due Date: June 3rd at 10:00pm

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:
interface IComparator<T> {
// Returns a negative number if t1 comes before t2 in this ordering // Returns zero if t1 is the same as t2 in this ordering // Returns a positive number if t1 comes after t2 in this ordering int compare(T t1, T t2);
}

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>  |
      +-------------------------+
      | IComparator<T> order -------------+
      +-------------------------+         |
                 / \                      |
                 ---                      |
                  |                       |
          -----------------               |
          |               |               |
     +---------+    +------------+        |
     | Leaf<T> |    | Node<T>    |        |
     +---------+    +------------+        |
                    | T data     |        |
                    | ABST left  |        |
                    | ABST right |        |
                    +------------+        |
                                          V
+---------------+    +-------------------------+
| Book          |    | IComparator<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’ve included an IComparator<T> as a field of the abstract base class of BST nodes and leaves, rather than only using an interface.

Problem 2: Visitors

In a new file IArith.java, implement the following class diagram:
      +-------------------+
      | IArith            |
      +-------------------+
      +-------------------+
          /_\      /_\
           |        |
           |        |
+-------------+  +------------------------------------+
| Const       |  | Formula                            |
+-------------+  +------------------------------------+
| double num  |  | IFunc2<Double, Double, Double> fun |
+-------------+  | String name                        |
                 | IArith left                        |
                 | IArith right                       |
                 +------------------------------------+