Abstracting with Function Objects

CS 2102 - Bterm 09

Homework 6 - Abstracting with Function Objects

Due: Tuesday, December 8 at 5pm

Š2009 Felleisen, Proulx, et. al. (modified by Glynis Hamel)

Assignment Goals

To design programs that use function objects
To define data structures using Java generics
To use Javadoc to document a program
To implement methods for binary search trees

Assignment

In this assignment you will get to use some of the various features of Java that we have been discussing in the lectures lately, namely, function objects, generics, and Javadoc. As you write up the solution for this assignment,

Use Javadoc-style comments (you should use the tags @param, @return, and @throws as appropriate)
Use visibility modifiers - classes should be public, fields private, getters and setters defined where necessary
Use Java generics (type parameters)
Test everything

The Outline View in the Eclipse IDE should remind you of something - the template! Open the Outline View (Window -> Show View -> Outline) as you work on your program, and make use of it. We will no longer be requiring that you provide templates for classes.

Problems

Define a class Book that records the title, author, and price of a book (an int). Define an interface and implementing classes (using generics) that represent a list. Also, define an interface called ISelect (as we did in Lecture 19), and two classes: one that implements the ISelect interface so that it selects a Book by a given author, and the other that implements ISelect so that it selects a Book cheaper than the given price (hint: the classes that implement ISelect can have fields). Make sure you test the classes that implement the ISelect interface.
Implement the method filter for your list classes, filtering according to the given ISelect. Write tests for lists of Books.
Define the following interface:
```
// to represent a method that determines whether or not t1 is before t2 in an ordering
interface Ordering<T>{
  public boolean isBefore(T t1, T t2);
}
```
Define at least two classes that implement this interface for Books (you may order the books by price, the length of the book title, the authors' names, etc.) Test.
Design the method sort for the list classes that uses an instance of a class that implements Ordering to determine the appropriate ordering of the items in the list. Test on lists of Books.
Design the method isSorted for the list classes, that uses an instance of a class that implements Ordering to determine if the list is sorted correctly. Test.
Design the method merge for the list classes. merge merges this sorted list with that sorted list, producing a list that that contains the elements of both lists, again in sorted order. An instance of the class that implements Ordering determines the ordering of both the original two lists and the resulting list. Keep testing.

Still using generics, define the classes to represent a binary search tree. Model your classes after the following class diagram:

                 +------------------------+
                 | abstract class ABST<T> |
                 +------------------------+<--+
      +----------| Ordering<T> order      |   |
      |          +------------------------+   |
      |                 / \                   |
      |                 ---                   |
      |                  |                    |
      |      -----------------                |    
      |      |               |                |
      |   +--------+   +--------------+       |
      |   | Leaf<T>|   | Node<T>      |       |
      |   +--------+   +--------------+       |
      |                | T data       |       |
      |                | ABST<T> left |-------+        
      |                | ABST<T> right|-------+        
      |                +--------------+        
      |                                        
      v                                
+------------------------------------+  
| Ordering<T>                        |  
+------------------------------------+  
| boolean isBefore(T t1, T t2)       | 
+------------------------------------+

Define the method insert that inserts a new item into this binary search tree, using the Ordering that is defined for this tree. Test on trees that contain Books.(Clarification: insert returns an ABST<T>)
Define the method getFirst that produces the smallest element in this binary search tree. In the Leaf class the method should throw a RuntimeException. Test.
Define the method getRest that produces a binary search tree that contains all the elements of this binary search tree except the smallest element. In the Leaf class the method should throw a RuntimeException. Test.

What to Turn In

Create an archive of your Eclipse project (see "Saving your work" in Lab 4 if you forgot how to do this). Using web-based turnin, turn in a single zip file containing all code for this assignment (you do not need to turn in the documentation files that Javadoc generates from your Javadoc comments). Follow the naming conventions when naming your file.