Assignment 6: Generic data and 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.

Due Date: Friday, May 30th at 9:00pm

Problem 2 is optional and can be done for extra credit. You will not be penalized if you choose not to do it.

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). This method should use the BST properties to search efficiently.

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

  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: Function objects and lists

First: practice with functions of a single argument. From class we discussed an IFunc<Arg, Ret> interface, representing functions that take an argument of type Arg and return a value of type Ret.

• Design a function-object class SquareNum that takes a Double and squares it. The class declaration should be class SquareNum implements IFunc<what type names go here?> but you need to fill in the various type parameters.

• Design a function-object class SineNum that takes a Double and computes its sine.

• Design a function-object class that is an identity function that returns its input. The class declaration should look something like class Identity<what type name(s) should go here?> implements IFunc<what types go here?>, but you need to fill in the various type parameters.

• Design a function-object class PlusN that has a field n, which it adds to its argument (which is a Double) when applied. The value for n is supplied in the constructor for PlusN.

• Design a combinator function-object class FunctionComposition<Arg, Mid, Ret> implements IFunc<Arg, Ret> whose constructor takes two arguments of type IFunc<Arg, Mid> and IFunc<Mid, Ret> and whose apply method effectively composes them. Write a test case that uses the function objects above to produce a function-object representing the function f(x) = (sin(x) + 1)2. (Obviously, more test cases besides this one single test are needed...)