On this page:
Instructions
Practice Problems
Problem 1: Visitors
Problem 2: Function objects and binary search trees
8.5

Assignment 6: Generic data, function objects, visitors

Goals: Practice working with generic objects and function objects and visitors.

Reminder about 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, February 29th 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 1: Visitors

In a new file Visitors.java, implement the following class diagram:
      +-------------------+
      | IArith            |
      +-------------------+
      +-------------------+
          /_\      /_\
           |        |----------------------------------------------------------------
           |        |                                                               |
+-------------+  +------------------------------+           +------------------------------------------+
| Const       |  | UnaryFormula                 |           |              BinaryFormula               |
+-------------+  +------------------------------+           +------------------------------------------+
| double num  |  | Function<Double,Double> func |           | BiFunction <Double, Double, Double> func |
+-------------+  | String name                  |           | String name                              |
                 | IArith child                 |           | IArith left                              |
                 +------------------------------+           | IArith right                             |
                                                            +------------------------------------------+

Specifically, the above represents an arithmetic expression. The Function and BiFunction in UnaryFormula and BinaryFormula respectively denote the arithmetic operation to be applied to their respective operands (child and left,right).

You must support 4 binary formulas (named "plus", "minus", "mul" and "div" representing addition, subtraction, multiplication and division respectively), and 2 unary formulas (named "neg" and "sqr" representing negation and squaring respectively).

Problem 2: 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.