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:

• Submission Homework 6 Problem 1: The ABST.java file with all its classes, interfaces, methods and tests.

• Submission Homework 6 Problem 2: The IArith.java file with all its classes, interfaces, methods and tests.

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 { // 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.

      +-------------------------+
| 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.

• 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. 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.)

• 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 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. Leave a comment explaining why the comparator is left out of this check.

• 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              b5

the 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

• 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.

• We would like to know whether a binary search tree of type T contains the same data as a list of type T.

Design the method for the binary search trees sameAsList that consumes a list (of the same type) and determines whether the binary search tree contains the same data as 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. But we know this is not the best way to do this.

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 IList<T> interface. The method consumes a binary search tree of type T, and inserts into it all items in this list, returning at the end a binary search tree that contains all items in this list as well as the items already in the tree.

If this method is invoked with a binary search tree that is a Leaf, then the resulting tree should be the sameAsList when compared 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 of type T that consumes a list of type T and adds to it one at a time all items from this tree in the sorted order. Due to the accumulator-nature of this problem, items from the tree inserted into the list should end up in reversed order. Specifically, if we invoke this method with an empty list, we should 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(someLeaf).buildList(new MtList())
produces a reverse-sorted blist. Hint: think carefully about where the ordering for the tree comes from!

### 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                       |
+------------------------------------+

• Design an interface IArithVisitor<R> representing a visitor that visits an IArith and produces a result of type R. Since a visitor is a special kind of function, we will have IArithVisitor<R> also extend IFunc, to get the apply method from the function interface.

• Design an accept(IArithVisitor<R>) method for the IArith interface and implement it on Const and Formula.

• Design a EvalVisitor that visits an IArith and evaluates the tree to a Double answer.

• Design a PrintVisitor that visits an IArith and produces a String showing the fully-parenthesized expression in Racket-like prefix notation (i.e. "(div (plus 1.0 2.0) 1.5)"), using the name for Formulas and using Double.toString(num) on Consts.

• Design a DoublerVisitor that vists an IArith and produces another IArith, where every Const in the tree has been doubled.

• Design an AllSmallVisitor that visits an IArith and produces a Boolean that is true if every constant in the tree is less than 10.

• Tricky! Design a NoDivBy0 visitor that visits an IArith and produces a Boolean that is true if anywhere there is a Formula named "div", the right argument does not evaluate to roughly zero. Since all values here are double, define “roughly zero” as “absolute value less than 0.0001”.