Collaboration Policy. For this problem set, you may either work alone and turn in a problem set with just your name on it, or work with one other student in your section of your choice. If you work with a partner, you and your partner should turn in one assignment with both of your names on it.

Regardless of whether you work alone or with a partner, you are encouraged to discuss this assignment with other students in the class and ask and provide help in useful ways. You may consult any outside resources you wish including books, papers, web sites and people. If you use resources other than the class materials, indicate what you used along with your answer.

• Learn to use subtyping in a safe and useful way.
• Learn to design using inheritance.
• Gain some familiarity with graphical user interface programming.
• Add features to an image processing application (and use them to make some pretty pictures)

Subtyping

Liskov's Chapter 7 and Meyer's Static Typing and Other Mysteries of Life describe very different rules for subtypes.

Liskov's substitution principle requires that the subtype specification supports reasoning based on the supertype specification. When we reasoned about a call to a supertype method, we reasoned that if a callsite satisfies the preconditions in the requires clause, it can assume the state after the call satisfies the postconditions in the effects clause. This means the subtype replacement for the method cannot make the precondition stronger since then our reasoning about the callsite may no longer hold (that is, the callsite may not satisfy the stronger precondition). Hence, the type of the return value of the subtype method must be a subtype of the type of the return value for the supertype method; the types of the parameters of the subtype method must be supertypes of the types of the parameters of the supertype method. This is known as contravariant typing.

Bertrand Meyer prefers covariant typing: the subtype replacement method parameter types must be subtypes of the types of the parameters of the supertype method. We will generalize his rules to apply to preconditions and postconditions also: the subtype method preconditions must be stronger than the supertype method precondition (pre_sub => pre_super) and the subtype postconditions must be stronger than the supertype postconditions (post_sub => post_super). Note that unlike the corresponding Liskov substitution rule, (pre_super && post_sub) => post_super, there is no need for pre_super in the covariant rule since post_sub => post_super.

The signature rule in Java is stricter: subtype methods must have the exact same return and parameter types of the method they override, although they may throw fewer exception types. Java does not place constraints on the behavior of methods, however, since the compiler is not able to check this.

Consider the minimal Tree class and its BinaryTree subtype, both specified on the next page. The Java compiler will not allow the getChild method of BinaryTree. Here is the error message:

BinaryTree.java:29: getChild(int) in BinaryTree cannot override getChild(int) in Tree; 
   attempting to use incompatible return type
      found   : BinaryTree
      required: Tree

public class Tree
   // OVERVIEW: A Tree is a mutable tree where the nodes are int values.
   //   A typical Tree is < value, [ children ] > 
   //      where value is the int value of the root of the tree
   //       and children is a sequence of zero or more Tree objects
   //         that are the children of this tree node.
   //   A Tree may not contain cycles, and may not contain the same
   //   Tree object as a sub-tree in more than one place.

   public Tree (int val) 
	// EFFECTS: Creates a tree with value val and no children: 
        //             < value, [] >

   public void addChild (Tree t) 
	// REQUIRES: t is not contained in this.
	// MODIFIES: this
	// EFFECTS: Adds t to the children of this, as the rightmost child:
	//   this_post = < this_pre.value, children > 
	//    where children = [ this_pre.children[0], this_pre.children[1], ..., 
	//                  this_pre.children[this_pre.children.length - 1], t]
	//   NOTE: the rep is exposed!

   public Tree getChild (int n)
	// REQUIRES: 0 <= n < children.length
        // EFFECTS: Returns the Tree that is the nth leftmost child 
	//   of this.
	//   NOTE: the rep is exposed!

public class BinaryTree extends Tree
   // OVERVIEW: A BinaryTree is a mutable tree where the nodes are int values
   //   and each node has zero, one or two children.
   //
   //   A typical BinaryTree is < value, [ children ] > 
   //      where value is the int value of the root of the tree
   //       and children is a sequence of zero, one or two BinaryTree objects
   //         that are the children of this tree node.
   //   A BinaryTree may not contain cycles, and may not contain the same
   //   BinaryTree object as a sub-tree in more than one place.

   public BinaryTree (int val)
	// EFFECTS: Creates a tree with value val and no children: 
        //             < value, null, null >

   public void addChild (BinaryTree t)
	// REQUIRES: t is not contained in this and this has zero or one children.
	// MODIFIES: this
	// EFFECTS (same as supertype):
	//   Adds t to the children of this, as the rightmost child:
	//   this_post = < this_pre.value, children > 
	//     where children = [this_pre.children[0], this_pre.children[1], ..., 
	//                  this_pre.children[this_pre.children.length - 1], t]

   public BinaryTree getChild (int n) 
	// REQUIRES: 0 <= n < 2 
	// EFFECTS: If this has at least n children, returns a copy of the BinaryTree 
	//   that is the nth leftmost child of this.  Otherwise, returns null.

static public void main (String args[]) {
  Tree t = new BinaryTree (3);
  BinaryTree bt = new BinaryTree (4);

  t.addChild (bt);                   // Calls the addChild(Tree) method
  bt.addChild (new BinaryTree (5));  // Calls the addChild (BinaryTree) method
  bt.addChild (new Tree (12));       // Calls the addChild (Tree) method
}