Lab 9 - Function Objects

Part 1: Setup

Download the lab zip file and unzip it. Start a new Project in eclipse with the name Lab9. Add all .java files from the unzipped lab folder to your project. Also, add the libraries jpt.jar and SimpleTestHarness.jar to the project.

The test harness used here is there same as that introduced in lab 7. Refer to lab 7 if you need to review how to use the test harness.

Part 2: Introduction

We will be working with a class of books. Each book has an author, year of publication, and a price. We would like to answer the following questions about various lists of books:

A1: Is there a            book  in this list that is written by the "MF"?
B1: Are all the           books in this list written by "MF"?
C1: Produce a list of all books in this list written by "MF".

A2: Is there a            book  in this list that was published before 1980?
B2: Are all the           books in this list published before 1980?
C2: Produce a list of all books in this list published before 1980.

A3: Is there a            book  in this list that costs more that $10?
B3: Are all the           books in this list that cost more that $10?
C3: Produce a list of all books in this list that cost more that $10.

We can clearly see several patterns in these questions. All the 'A' questions inquire whether there is at least one item with the given property. All the 'B' question question whether all items in the list satisfy the given property. Finally, the question 'C' is really a request to extract from the list only those items that satisfy the given property.

Part 3: Answering Questions of the Type 'Is there a...'

We start with designing the classes to represent books and lists of books. The class diagram is shown here - the code is included with the lab, together with examples.

           | ALoB |<-------------+
           +------+              |
           +------+              |
              / \                |
              ---                |
               |                 |
      ----------------           |
      |              |           |
  +-------+    +------------+    |
  | MTLoB |    | ConsLoB    |    |
  +-------+    +------------+    |
  +-------+  +-| Book first |    |
             | | ALoB rest  |----+
             | +------------+ 
    | Book          |
    | String author |
    | int year      |
    | int price     |

We will start with methods for the questions A1, A2, and A3. Below are the purpose statements and headers for the methods in the class ALoB.

  // is there a book written by "MF" in this list?
  abstract boolean anyBookWrittenByMF();

  // is there a book published before 1980 in this list?
  abstract boolean anyBookBefore1980();

  // is there a book that costs more than $10 in this list?
  abstract boolean anyBookMoreThan10();

Exercise: design the above methods for the classes representing lists of books. Be sure to include tests in the class Tests.

Note: to complete the bodies of these three methods in the ConsLoB class, we must first add to the class Book the methods that determine whether this book was written by "MF", or whether this book was published before 1980, or whether this book costs more than $10.

Part 4: The Function Object ISelect

We see, that if we changes the names of the three methods to a common name (e.g. anyBookSuch), the only place where they differ is in determining whether the Book this.first satisfies the predicate. We would like to abstract over this part and pass it to the method anyBookSuch as an argument.

There are two problems to overcome. The way the question is written in our body requires that the methods writtenBy, before1980, and moreThan10 are defined in the class Book. But if the methods are to have the same name, they cannot be defined in the same class. Furthermore, we can only pass an instnce of a class as an argument to a method. This leads us to consider to have three different classes, each with the method that determines whether a book satisfies the specific predicate. Here is the method purpose statement and the header:

  // determine whether the given book satisfies a condition
  boolean selectBook(Book b){...}

However, to define an argument for our method anyBookSuch, we need to specify its type. The instances of our three classes need to have some unifying type. One option os for all three classes to extend a common superclass. We will see later why that may not be the best option. The other option is for all three classes to implement a common interface. This option makes it clear that we aim to represent commmon behavior.

So, the interface is:

interface ISelectBook{
  // determine whether the given book satisfies a condition
  boolean selectBook(Book b);

Exercise: Design the following three classes, each of which implements the interface ISelectBook above. Each must implement the method selectBook as defined above (which returns true if the given Book satifies the corresponding predicate.

class WrittenByMF implements ISelectBook{...}
class Before1980 implements ISelectBook{...}
class MoreThan10 implements ISelectBook{...}

We can now define the method anyBookSuch with the following purpose statement and header.

  // is there a book that satisfies the condition?
 boolean anyBookSuch(ISelectBook choose);

Exercise: Design the method anyBookSuch as described above and rerun the original tests using the method anyBookSuch with the appropriate arguments.

Part 5: Extending Function Objects

The methods we defined for selecting books are rather limited. We canonly select one specific author, one specific publication date limit, or one base price. But this is easily remedied by adding a field to the classes that implement the 'selectBook' method as follows:

class WrittenBy implements ISelectBook{
  String author;

  WrittenBy(String author){ = author;

  boolean selectBook(Book b){

The test cases will become:

  // tests for the method anyBookWrittenBy
  sth.test("AnyBookWritten1", mtlist.anyBookSuch(new WrittenBy("MF")), false);
  sth.test("AnyBookWritten2", list1.anyBookSuch(new WrittenBy("MF")), true);
  sth.test("AnyBookWritten3", list2.anyBookSuch(new WrittenBy("MF")), false);

Exercise: Design the classes Before and MoreThan that allow us to select a book published before a specified date, or a book that costs more than a specified price. Make sure you run again the examples using the new function objects.

Part 6: Scheme Loops and more uses of Function Objects

Let us step back and think about the method we just designed. It determines whether there is an item in a list that satisfies the given predicate. This corresponds to the Scheme the loop ormap. Here is the description of ormap:

;; ormap: (X -> boolean)(Listof X) -> boolean
;; to determine whether p holds for at least one item on alox
;; that is, (ormap p (list x-1 ... x-n)) = (or (p x-1) (or ... (p x-n)))
(define (ormap p alox) ... )

Our (Listof X) is the list of books that invokes the method anyBookSuch, the function (X -> boolean) is encapsulated in the function objects that implement ISelectBook that we pass to our method, and our result is boolean, the same as for the 'ormap'.

Exercise: Figure out which Scheme loops correspond to questions B and C.

Exercise: Design the methods that solve the problems B1, B2, and B3, and abstract them into the corresponding Scheme loop.

Exercise: Do the same for the methods needed to solve the problems C1, C2, C3.

Part 7: Sorting with Comparators

This same kind of function abstracting that we used above can also be used for sorting. In this case, we want to determine if one object should come before or after another. The interface ICompBook defines this type of function object.

Challange Problem:

Define three classes that all implement ICompBook: CompBookByAuthor, CompBookByYear, and CompBookByPrice, that compare two Books by the corresponding field.

Design a single sort method in the list-of-books classes that sorts using the provided comparator. The sort and insert methods should have the following purpose statements and headers:

  // Sort this list of books using the given comparator
  ALoB sort(ICompBook comp);
  // Insert the given Book into this sorted list, according to the given comparator
  ALoB insert(Book b, ICompBook comp);

For more details and help, see these Lecture Notes on Sorting Using Function Objects.