copyright 2012 Felleisen, Proulx, et. al.

CS 2510 Spring 2012:Assignment 6 - Function Objects

Practice Problems

Work out as the following exercises from the textbook. Do not add them to your assignment submission, though you should keep them in your electronic portfolio in your own svn repository.

Problems:

Include the solution of the Lab 6 in your portfolio.
Add a few more examples of tests in the Examples class.
Define a class ImageSmallerThanAndGivenKind that implements the ISelectImageFile interface with a method that selects image files that are small and of the given kind. Allow the user to decide how small should the images be (measuring the size as the number of pixels in the image) and allowing the user to choose the kind of images that should be selected. (All selected images must be of the same kind.) Test your class definition on several examples before you use it in your allSuch, anySuch, and filter methods.
Add test cases that will test the methods allSuch, anySuch, and filter with several instances of the ImageSmallerThanAndGivenKind predicate.

Pair Programming Assignment

Problem 1

The goal of this problem set is to see in practice the design and use of function objects, as well as get more practice with the design recipe and with using accumulators when needed. We strongly encourage you to include templates in all classes. They are required in the classes that represent cons list of books and the node of the binary search tree.

Create a project with the name HW06Problem1. Download the file Assignment6.zip and import the .java files defined there.

Define the following interface in your project:

// interface to represent a method compare for books
public interface ICompareBooks{
  
  // does b1 come before b2 in this ordering?
  public boolean compare(Book b1, Book b2);
}

Define three classes that implement this interface, ordering the books by the length of the book title (class BookOrderByTitleLength), author's names (class BookOrderByAutor), and one more criterion of your choice. Remember to follow the design recipe.
Design the method sort for the classes that represent a list of Books that uses an instance of a class that implements the ICompareBooks interface to define the appropriate ordering of the books and produces the list in the correctly sorted order.
Design the method isSorted for the classes that represent a list of Books that uses an instance of a class that implements the ICompareBooks interface to determine whether a list of Books is sorted correctly.

Make sure your tests use all three ways of comparing books.

Note: Remember the one task one method rule.

Note: This is something you have already done several times - just slightly modified.

Problem 2

You will work with a binary search tree that represents a collection of Book objects. It is similar (with a slight change) to the binary search trees that had only integer data.

The following class diagram on the next page should help you.

                 +---------------------+
                 | abstract class ABST |
                 +---------------------+
      +----------| ICompareBooks order |
      |          +---------------------+
      |                 / \
      |                 ---
      |                  |
      |      -----------------     
      |      |               |
      |   +------+   +------------+
      |   | Leaf |   | Node       |
      |   +------+   +------------+
      |              | Book data  |--------+
      |              | ABST left  |        |
      |              | ABST right |        |
      |              +------------+        |
      |                                    v
      v                                 +---------------+
+------------------------------------+  | Book          |
| ICompareBooks                      |  +---------------+
+------------------------------------+  | String title  |
| boolean isBefore(Book b1, Book b2) |  | String author |
+------------------------------------+  | int price     |
                                        +---------------+

Design the method insert that produces a new binary search tree with the given item inserted in the correct place.
Design the method getFirst that produces the first Book in the binary search tree (as given by the appropriate ICompareBooks.

In the Leaf class this method should have the following body:
```
throw new RuntimeException("No first in an empty tree");
```
Design the method getRest that produces a new binary search tree with the first Book removed.

In the Leaf class this method should have the following body:
```
throw new RuntimeException("No rest of an an empty tree");
```
Design the method sameTree that determines whether this binary search tree is the same as the given one (i.e., has matching structure and matching data in all nodes).
Design the method sameData that determines whether this binary search tree contains the same books as the given tree.

Note: Given the following three trees:
```
bstA:       bstB:       bstC:       bstD:       
     b3          b3          b2          b3
    /  \        /  \        /  \        /  \
   b2  b4      b2  b4      b1   b4     b1   b4
  /           /                /             \ 
b1           b1               b3              b5
```
- bstA is the same tree as bstB
- bstA is not the same tree as bstC
- bstA is not the same tree as bstD
- bstA has the same data as bstB
- bstA has the same data as bstC
- bstA does not have the same data as bstD
We would like to know whether a binary search tree of books contains the same data as a list of books. Design the method sameAsList that allows us to make this comparison.

Write a short explanation of your design.

Note: You are allowed to introduce new classes or interfaces to solve this problem.
Design a new bstSort method for the classes that represent a list of books, that first builds a binary search tree from the data in this list, then converts the binary search tree into a sorted list.

Write a short explanation of your design.

Last modified: Tue Feb 14 18:44:04 EST 2012