[an error occurred while processing this directive] Problem Set 4 - Comments
Subtyping and Inheritance

1. (10) Does the getChild method in BinaryTree satisfy the Liskov substitution principle? Explain why or why not.

This was a tricky question. We accepted both "Yes" and "No" answers to this question for full credit if they had good explanations.

To answer it well, you had to map the BinaryTree.getChild specification to the Tree.getChild specification, and then show that the precondition of Tree.getChild implies the precondition of BinaryTree.getChild and the postcondition of BinaryTree.getChild implies the postcondition of Tree.getChild.

The simple part to check is the signature rule. The parameter types are the same, so the contravariant parameter types rule is satisfied. The return types are different: Tree.getChild returns a Tree, BinaryTree.getChild returns a BinaryTree. The subtype method must return a type that is a subtype of the type returned by the supertype; this is satisfied since BinaryTree ≤ Tree.

Next, we want to show the supertype method's precondition is stronger than the subtype method's precondition: preTree.getChild implies preBinaryTree.getChild. The precondition for Tree.getChild is 0 <= n < children.length. The precondition for BinaryTree.getChild is 0 <= n < 2. Without knowing anything else, this appears to violate the substitution principle: knowning n < children.length is not enough to know n < 2. But, we know from the overview that a BinaryTree has zero, one or two children. Hence, for a BinaryTree we know children.length ≤ 2. Hence, knowing 0 <= n < children.length from the preTree.getChild is enough to imply the precondition of BinaryTree.getChild and satisfy the substitution principle.

Next, we want to show postBinaryTree.getChild implies postTree.getChild, that is the postcondition of the subtype method should be stronger (or equally strong) than the postcondition of the supertype method. The postcondition of BinaryTree.getChild is: 

   // EFFECTS: If this has n children, returns a copy of the BinaryTree  
   // that is the nth leftmost child of this. Otherwise, returns null.
This appears to be weaker, than the postcondition of Tree.getChild: 
   // EFFECTS: Returns the Tree that is the nth leftmost child  
   // of this.
The BinaryTree.getChild method can return null, but the Tree.getChild method always returns a non-null tree. But, BinaryTree.getChild only returns null when this has less than n children (the specification should have been clearer: If this has at least n children...), in which case the precondition for the Tree.getChild method is not satisfied. Hence, it doesn't matter what the subtype method postcondition is in cases where the supertype method precondition is not satisfied: the supertype method can do anything when its precondition is not satisfied, so a subtype method can have a postcondition that does anything it wants in cases where the supertype method precondition is not satisfied. So, the substitution principle is satisfied.

The problem is that BinaryTree's postcondition is returns a copy of the BinaryTree and Tree's postcondition is returns the Tree. This makes the specifications incompatible: clients can tell the difference between getting a copy of the child, and exposing the representation to get the actual child. So, the substition principle is not satisfied since BinaryTree.getChild returns a copy. Client code that attempts to modify a tree by mutating the tree returned by Tree.getChild will not work as expected if the tree is a BinaryTree.

2. (10) Does the addChild method in BinaryTree satisfy the Liskov substitution principle? Explain why or why not.
No. The signature rule is violated since the type of the parameter parameter to the subtype method (BinaryTree) is not a supertype of the type of the parameter to the supertype method (Tree). Hence, we cannot substitute the BinaryTree.addChild method in places where Tree.addChild is called with a parameter that is not a BinaryTree subtype.
3. (10) Does the getChild method in BinaryTree satisfy the Eiffel subtyping rules? Explain why or why not.
No. The precondition rule for Eiffel is not satisfied: preBinaryTree.getChild is not strong enough to imply preTree.getChild since for a tree with one node, children.length is less than 2. The precondition for BinaryTree.getChild is satisfied when n = 1, but the precondition for Tree.getChild is not satisfied.
4. (10) Does the addChild method in BinaryTree satisfy the Eiffel subtyping rules? Explain why or why not.
Yes. The Eiffel signature rule has covariant typing of the parameters, so it is satisfied. We also need preBinaryTree.addChild implies preBinaryTree.addChild and postBinaryTree.addChild implies postTree.addChild. The precondition for BinaryTree.addChild is stronger, it add a requirement to the original precondition: t is not contained in this and this has zero or one children. That would violate the substitution principle, but it is okay according the the Eiffel rules. The postconditions are identical so the implication is satisfied.
5. (10) (10) Develop a new filter that replaces each pixel in the image with its negative (that is, the red value of the new image is 255 - the red value of the old image, and similarly for blue and green). To work with the provided GUI code, you should add the name of your filter to the effects array (initialized at the top of the GUI class. The GUI will load the class named ps4.effectFilter for the name selected from the menu, so if you name your class NegativeFilter in the ps4 package, you should add "Negative" to the effects array.
Our NegativeFilter should be a subclass of PointFilter, since we can implement it by adjusting each pixel color without any additional information. 
package ps4;
import java.awt.Color;

public class NegativeFilter extends PointFilter {

   @Override
   protected Color filterPoint(Color p_c) {
      return new Color (255 - p_c.getRed(), 
                        255 - p_c.getGreen(), 
                        255 - p_c.getBlue());
   }

   @Override
   public String getFilterName() {
      return "negative";
   }
}
Most of your implementations were correct, but involved lots of superflous code and variables. For example, a typical implementation did: 
   protected Color filterPoint(Color p_c) {
      int r = p_c.getRed();
      int g = p_c.getGreen();
      int b = p_c.getBlue();
      return new Color (r, g, b);
   }
Although this is okay, in my view it is harder to understand than the more direct code. When you don't need to use a value more than once, think carefully if it is necessary to make it a variable.
6. (10) Develop a new filter that tints an image so the pixels near the top of the image (low row numbers) become gradually more blue.
The question is unspecific about how the tinting should actually work. Our goal is to get a "blue-sky" effect, so we'll start the tinting halfway up the image and make the tint increases the blueness scale as we go up the image. 
public class BlueSkyFilter extends Filter {

   @Override
   protected void filter() {
      int topheight = pixels.getHeight() / 2;
      for (int row = 0; row < topheight; row++) {
         for (int col = 0; col < pixels.getWidth(); col++) {
            setColors(row, col, getRed(row, col), getGreen(row, col),
                      Math.min(255,
                               (int) (getBlue(row, col) 
                                      * (2.0 - ((double) (row) / (double) topheight)))));
         }
     }
   }

   @Override
   public String getFilterName() {
     return "bluesky";
   }
}
The most common "mistake" on this one was to copy the FlipFilter code model of using a temporary Pixels object. It works fine to do this here, but isn't necessary. For FlipFilter we needed the temp object since when we flip the left side pixels, they replace pixels on the right side of the image (which we need to flip onto the left side). (Of course, there are ways of implementing FlipFilter that would just store one temporary pixel, instead of needing a whole Pixels object.)

7. (10) Develop a new filter that produces an image that is the "average" of two or more images.

Here, we need to create a subclass of the MultiFilter. The AddFilter is the best model, but we need to do something a bit more complex to find the average color value. 
public class AverageFilter extends MultiFilter {

   @Override
   protected void filter() 
   {
      int r, g, b; 
      int width = getMinimumWidth();
      int height = getMinimumHeight();
      int numimages = 1 + getNumberSecondary();

      for(int col = 0; col < width; col++) {
         for(int row = 0; row < height; row++) {
            r = getRed(row, col);
            g = getGreen(row, col);
            b = getBlue(row, col);

            for(int i = 0; i < getNumberSecondary(); i++) {
                Pixels pimage = getImagePixels(i);
                r = r + pimage.getRed(row, col);
                g = g + pimage.getGreen(row, col);
                b = b + pimage.getBlue(row, col);
            }

            setColors(row, col, r / numimages, g / numimages, b / numimages);
        }
     }
  }

  // getFilterName not shown
}
8. (10) How well does the provided Filter type hierarchy follow the behavioral subtyping rules? Your answer should consider the PointFilter and MultiFilter abstract classes and their important methods, as well as the other filter subclasses, explaining whether or not they satisfy the substitution principle.
To follow the substitution principle, it should be the case that all subtypes of Filter can be used wherever Filter is expected. The signature rule is guaranteed by the Java compiler (it enforces the no-variant rule on the parameter and return types of the overriding methods, and because of inheritance we know the subtypes provide all of the supertype methods). So, we only need to consider the methods and properties rules. The relevant method is the filter method which Filter specifies as, 
protected abstract void filter();
   // REQUIRES: this must be initialized
   // EFFECTS: alters the image in a manner specified by the filter.
This is a good specification for behavioral substitution since the EFFECTS clause is very weak — it says the filter method can modify the image in any way it wants. Note that there is a big problem with this specification! It is missing a modifies clause, which means it cannot modify anything. (This was a mistake on my part, but I'm disappointed no one noticed it!) So, if we assume the correct filter specification, 
protected abstract void filter();
   // REQUIRES: this must be initialized
   // MODIFIES: this
   // EFFECTS: alters the image in a manner specified by the filter.
then a subtype of Filter can override filter with a method that modifies the image in any way it ways, and has a precondition that is no stronger than this must be initialized. All the provided Filter subtypes satisfy this, so the substitution principle is followed by the provided types.
9. (10) Describe at least two substantially different approaches to supporting parameterized filters. You may assume that the filter parameter value is a single integer. For each of your proposed approaches, draw the modified class hierarchy. Discuss the tradeoffs between the different designs — which design involves the most changes to the code? which design is easiest to implement?
This is a tough design problem, since the properties we want do not fit well onto the abstraction and inheritance mechanisms provided by Java. We want to support a new type of filter, ParameterizedFilter that is a filter with an integer parameter. Several of the provided filters, such as BlurFilter and TileFilter should be subtypes of ParameterizedFilter, but some of the filters do not take a parameter (e.g., AddFilter, FlipFilter).

One obvious design would be to make ParameterizedFilter an immediate subtype of Filter, so the new class hierarchy would look like this: 

java.lang.Object
 subtype ofps4.Filter
     subtype ofps4.ParameterizedFilter
         subtype ofps4.PointFilter
            subtype ofps4.BrightenFilter
            subtype ofps4.GreyscaleFilter
         subtype ofps4.BlurFilter
         subtype ofps4.MultiFilter
             subtype ofps4.AddFilter
             subtype ofps4.AverageFilter
             subtype ofps4.TileFilter
     subtype ofps4.FlipFilter
     subtype ofps4.NegativeFilter
The problem with this design is that is forces MultiFilter and PointFilter to be subtypes of ParameterizedFilter, even though not all of the subtypes of MultiFilter and PointFilter take a parameter. We would need some additional code to do this. Another approach would be to just add the parameter directly to the Filter class (so no new types are introduced in the type hierarchy). We could add methods for setting and getting the parameter, as well as a method for determining if a filter needs a parameter: 
    protected int value;
    public boolean getParameter() { return value; }
    public boolean setParameter(int val) { value = val; }
    public boolean hasParameter() { return false; }
that is used to tell if a filter takes a parameter. Filter subtypes that need a parameter would override this method to return true: 
    // in TileFilter
    public boolean hasParameter() { return true; }
Then, the GUI code would do something like this: 
   if (f.hasParameter ()) {
      int value = ... // code to get parameter from user
      f.setParameter (value);
   }
This design has the advantage of only needing a small amount of additional code, and making the GUI code changes simple. It has the disadvantage of needing to maintain a value field even for filters that don't have a parameter, and needing to override the hasParameter method to make a parameterized filter.

Another approach is to use an interface: 

public interface Parameterized {
   public boolean setParameter(int val);
   public int getParameter();
}
Then, we could make a filter that needs a parameter a subtype of both Parameterized and the filter type. For example, 
public class TileFilter extends MultiFilter implements Parameterized {
...
The GUI code could be written in the same way as it deals with MultiFilter: 
    if (f instanceof Parameterized) {
       Parameterized pf = (Parameterized) f;
       int value = ... // code to get parameter from user
       pf.setParameter (value);
    }
This seems like a somewhat more general design than adding the parameter to the Filter datatype. It has the disadvantage of requiring each parameterized filter to provide its own implementation of getParameter and setParameter. Since Java does not support multiple inheritance, there is no way to mix in these implementations and still inherit from Filter.
10. (10) Modify the application to suppoed the parameterized filters. In addition to modifying the filter classes, you will need to modify the GUI to allow a user to enter the parameter for a parameterized filter. This will involve modifying the GUIHandler.actionPerformed method defined in GUI.java. Hint: look at how the MultiFilter is handled.
See answer to 9 above.
11. (10) Develop a new filter of your choice, and use it (as well as the provided filter) to create an interesting image. Be creative!
The most interesting filter is the ImpressionismFilter from Patrick Harrison (I have made some modifications to simplify the code): 
public class ImpressionismFilter extends Filter {
   public boolean hasParameter() { return true; }
   public String getFilterName() { return "impressionism"; }

   @Override
   protected void filter() {
      java.util.Random rand = new java.util.Random();
         for (int i = 0; i < getParameter(); i++) {
            for (int row = 1; row < getImageHeight() - 1; row++) {
                for (int col = 1; col < getImageWidth() - 1; col++) {
                    int dice = rand.nextInt(4);
                    int coloffset = 0, rowoffset = 0;
                    if (dice == 0) {
                       coloffset = -1;
                    } else if (dice == 1) {
                       rowoffset = -1;
                    } else if (dice == 2) {
                       coloffset = 1;
                    } else if (dice == 3) {
                       rowoffset = 1;
                    } else {
                       assert false; // bad dice!
                    }

                    setColors(row, col,
                              getRed(row + rowoffset, col + coloffset), 
                              getGreen(row + rowoffset, col + coloffset), 
                              getBlue(row + rowoffset, col + coloffset));
            }
         }
      }
   }
}

See the course website for other pictures.

[an error occurred while processing this directive]