Assignment 6

Goals: Understanding function objects, exceptions.

Instructions

The names of the projects and some of the project files must be exactly the same as specified in the assignment. Failure to do so makes it impossible for the graders to run your submission and results in immediate loss of at least 50% of the homework credit.

Make sure you follow the style guidelines for code indentation.

You will submit this assignment by the deadline using the Web-CAT submission system. We will be practicing its use during the lab next week.

With each homework you will also submit your log file named pairxxx.txt where you replace xxx with your pair number.

On top of every file you submit you will have the names of both partners, and the pair number.

The .txt file will be the log of your work on this assignment. Each log entry will have data and time, who was present (one or both of the partners) and a short comment decribing what you were working on.

There will be a separate submission for each problem - it makes it easier to grade each problem, and to provide you with the feedback for each problem wou work on.

The two submissions will be organized as follows:

• Submission HW6P1: The log file and the Strings.java file (with all classes, methods, and tests) in one .zip file

• Submission HW6P2: The file ABST.java with all classes, interfaces, methods, and tests. If you wish to keep the examples and tests in a separate Java file, you may do so.

Due Date: Tuesday, February 18th, 10:59 pm.

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

• Design the interface INumPredicate with the method selectNum that consumes one Integer argument and produces a boolean value.

  Design three classes that represent predicates on Integers as follows:

  • OddNumPredicate that selects all odd numbers

  • MultipleOf that selects all numbers that are multiples of the Integer provided in the constructor.

  Design the method filterInteger for the classes that represent a list of Integer that consumes an instance of the INumPredicate and produces a list of all numbers that satisfy the given predicate.

  Make tests that produce multiples of 3, multiples of 5, and odd numbers.

Pair programming assignment

Problem 1: Function objects, sorting

Start with your solution to the String problem from the previous homework.

• Design the interface StringsCompare that contains a method

  public boolean comesBefore(String s1, Strings2);

• Design a class (function object) StringLexComp that implements this interface by comparing the Strings lexicographically.

• Design a class (function object) StringLengthComp that implements this interface by comparing the Strings by their length from the shortest to the longest.

• Modify your solution for the method isSorted so that it would verify that the list is sorted by one of the desired orders.

• Modify your solution for the method merge so that it would merge the list that are sorted by one of the desired orders.

• Design the method sort that produces a sorted list, in the order given by the StringsCompare function object.

Problem 2: Function objects, binary search trees

You will work with a binary search tree that represents a collection of Book objects. Remember, 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 coma after the current data item.

The tree with no data is represented as a leaf.

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 seeral different ordered ways - by title, by author, and by price.

The following class diagram should help you.

• Start a new project and define in it the class that represents a Book as shown in the class diagram. We want to keep track of the books in several different ordered ways - by title, by author, and by price.

• Design the interface IBookComparator and design the classes BooksByTitle, BooksByAuthor, and BooksByPrice that allow us to compare the books by their title, to author, or price respectively.

• Design the classes that represent a binary search tree of books, following the class diagram shown above. Make examples of data.

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

  the following should hold:

  • 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

• Now add to your project the data definitions for a list of books, i.e. the interface ILoBook and the classes MtLoBook and ConsLoBook.

  Make examples, including those that contain the same data as some of your binary search trees, arranged in order.

• We would like to know whether a binary search tree of books contains the same data as a list of books.

  Design the method for the binary search trees sameAsList that consumes a list of books and determines whether the binary search tree contains the same books and the given list (in the same order).

  Hint: There are two ways how this can be done.

  The first one is to add the methods isEmpty, getFirst(), and getRest() to the classes that represent the list of books.

  The second is to first design the method buildList below, then compare the resulting list with the one given before.

• Design a buildTree method for the classes that represent a list of books. The method consumes a binary search tree of books, and inserts into it all items in this list, returning at the end a binary search tree that contains all items in this list.

  If this method is invoked with a binary search tree that is a Leaf, then the resulting tree should be the sameAsList when ocmpared to the sorted version of this list.

  So, for example, the list (b3, b1, b4, b5) would produce the tree bstD shown above.

• Design the method buildList for the classes that represent the binary search tree that consumes a list of books and adds to it one at a time all items from this tree in the sorted order. (If we invoke this method with an empty list, we end up with a list of all items in this tree in the reverse order.)

• Test that your design works by checking that

  (blist.buildTree(new Leaf())).buildList(new MtLoBook())

  produces a reverse-sorted blist.