Introduction

This tutorial serves as a review to exam #1.  It contains a few sample questions similar to the exam given in Comp 212 a year ago.  You need to also review all the design patterns decribed in the handouts.  You also should review all the labs and all the homework assigments.  The solutions to homework 3 will be posted on Tuesday Oct. 5, 99.

Problem I. For this problem, you are given the following collection of classes defining functional lists of integers (represented by the type IntList):
abstract class IntList {
  abstract int first();
  abstract IntList rest();
}
class Empty extends IntList {
  int first(){
    throw new java.util.NoSuchElementException (''first faults on Empty'');
  }
  IntList rest(){
    throw new NoSuchElementException (''rest faults on Empty'');
  }
}
class Cons extends IntList {
  int first;
  IntList rest;
  Cons(int f, IntList r) {first = f; rest = r;}
  int first() {return first;}
  IntList rest() { return rest;}
}
The usual overriding of toString has been omitted from the preceding code to save space.

1. In the space provided in the program text above, add a method int prod() to the class IntList that computes the product of the elements of the list. On the Empty list,
   int prod() should return 1.  Add the usual main method to IntList to compute the product for the list (4 10 7).
2. Redesign the IntList, Empty, and Cons classes using the visitor pattern to decouple the list intrinsic structural behavior from the external algorithms that operate on the list .  Write the appropriate Product visitor to compute the product of a host IntList.   Does it make sense to apply the Singleton pattern to the Product visitor?  Briefly explain your answer.
   Add the usual main method to IntList to compute the product for the list (4 10 7).

Problem II. For this problem, you are given the following collection of Java classes defining functional lists of Objects (represented by the type ObjList):
abstract class ObjList {
  abstract Object first();
  abstract ObjList rest();
}
class Empty extends ObjList {
  Object first() {
    throw new java.util.NoSuchElementException (''first faults on Empty'');
  }
  ObjList rest() {
    throw new java.util.NoSuchElementException (''rest faults on Empty'');
  }
}
class Cons extends ObjList {
  Object first;
  ObjList rest;
  Cons(Object f, ObjList r) { first = f; rest = r; }
  Object first() {return first; }
  ObjList rest() { return rest;}
}

1. Define a Java interface called Property with a method called boolean eval (Object obj). This interface is to represent what is commonly known in non object-oriented thinking as "property functions"  that maps a data element to a boolean.  Add a method called Object suchThat(Property p) to ObjList that finds the first element of this that has property p and return it. If no such element exists, suchThat(Property p) returns null.
2. Define a subclass IsString that implements Property such eval (s) == true if and only if s is a String object.
   Assume l is an object of type ObjList. Write a Java expression that returns the first String in l.
   

Problem III.  Recall the functional binary tree structure in homework 1 (FunBiTree, Empty, and NEBiTree).

1. Redesign it using the visitor pattern to decouple the structure from the extrinsic algorithms that operate on the structure.
2. Write a ComputeSum visitor to compute the sum of all the integers in a FunBiTree.
3. Write a ComputeSupremum visitor to compute the supremum of a tree.  sup is said to be the supremum of a set of numbers S, if for all x in S, x less or equal to sup.  Does it make sense to define the supremum of the empty tree as Integer.MIN_VALUE?  Briefly explain your answer.   (Review the documentation of the solutions to homework 1).
4. Write a CheckIsLeaf visitor to return Boolean (true) if the host tree is a leaf, Boolean (false) otherwise.  You should not use type checking in your code.  Feel free to add any number of "helper" visitors.
5. A FunBiTree is said to have the binary search tree (BST) property if it is empty or when it is not empty, all elements in the left subtree are less or equal to the root element, and all elements in the right subtree are greater than the root element.  Write a visitor called InsertInOrder that assumes the host tree has the BST property, computes and returns a FunBiTree with the following properties: a/ it contains all the elements of the host tree and the input Integer object  b/ it has the BST property, i.e. all elements of its left subtree are less or equal to its root element, and all elements of its right subtree are greater than its root element.