Skip to main content

Section D.10 Exercise Sheet 10

Inheritance

1. Static and Dynamic Types.

In this exercise, you will learn how function calls are resolved in Java. The code parts are to be interpreted as connected, the divisions are supposed to highlight the program parts relevant for each subtask.

  1. Determine the static and dynamic type of each variable.

    A a = new A();
    A b = new B();
    A c = new C();
    
    B bB = new B();
    C cC = new C();
    

  2. Is the static or dynamic type used when a method is overloaded? What about overwritten methods?

  3. For all classes, determine those methods which are overloaded and those which are overwritten.

    class A {
      void f (boolean b) { System.out.println("A.f(boolean)"); }
    
      void f (double d) { System.out.println("A.f(double)"); }
    }
    
    class B extends A {
      void f (boolean b) { System.out.println("B.f(boolean)"); }
    
      void f (int i) { System.out.println("B.f(int)"); }
    }
    
    class C extends B {
      void f (boolean b) { System.out.println("C.f(boolean)"); }
    
      void f (float f) { System.out.println("C.f(float)"); }
    
      void f (int i) { System.out.println("C.f(int)"); }
    
      void f (short s) { System.out.println("C.f(short)"); }
    }
    

  4. Now determine the output of the following calls by searching for the most specific signature for each call (with respect to the static and dynamic type).

    cC.f(1);
    cC.f(1.0f);
    
    a.f(true);
    b.f(true);
    c.f(true);
    
    bB.f(1);
    b.f(1);
    cC.f(1.0);
    c.f((short) 1);
    

202207281550

202206171400
Solution.
  1. \(\displaystyle \)

    Variable Static Type Dynamic Type
    a A A
    b A B
    c A C
    bB B B
    cC C C
  2. Overloading: Static, Overwriting: Dynamic

  3. \(\)

    Class Methods
    A A.f(double) A.f(boolean)
    B B.f(boolean) B.f(int)
    C C.f(boolean) C.f(int) C.f(short) C.f(float)
    If methods are vertically adjacent in the table, the lower method overwrites the upper method (e.g. C.f(int) overwrites B.f(int)). Methods with differing argument types are overloaded (e.g. B.f(int) overloads A.f(double)).

  4. \(\)

    cC.f(1) \(\implies\) C.f(int)
    cC.f(1.0f) \(\implies\) C.f(float)
    a.f(true) \(\implies\) A.f(boolean)
    b.f(true) \(\implies\) B.f(boolean)
    c.f(true) \(\implies\) C.f(boolean)
    bB.f(1) \(\implies\) B.f(int)
    b.f(1) \(\implies\) A.f(double)
    cC.f(1.0) \(\implies\) A.f(double)
    c.f((short) 1) \(\implies\) A.f(double)

    The most specific signature appears in the calls b.f(1) and c.f((short) 1), since here the signature f(double) is chosen according to the static type A. Since this method is neither defined in B nor C, the method of A is taken which is transitively inherited by B and C.

2. Overloading and Overwriting.

Take a look at the following code and explain which methods are called. Argue in terms of overloading and overwriting.

class A {
  void f (float v) { 
    System.out.println("A.f(float)"); 
  }
}
class B extends A {
  void f (int v) { 
    System.out.println("B.f(int)"); 
  }
}
class C extends B {
  void f (int v) { 
    System.out.println("C.f(int)"); 
  }
}
A a = new B();
B b = new B();
B c = new C();

a.f(15);
b.f(15);
c.f(15);

202207281550

202206171400
Solution.

Output:

A.f(float)
B.f(int)
C.f(int)

  • a.f(15): a is an object of type B which is casted to type A. Since the signatures of A.f and B.f are not the same, A.f is not overwritten but overloaded. Hence, the method void f(int v) from class B is no longer visible in class A. 15 is therefore casted to float, A.f is called and "A.f(float)" is printed.

  • b.f(15): 15 is of type int by default. Hence, the overloaded method void f (int v) is called and "B.f(int)" is printed.

  • c.f(15): In class C, the method B.f is overwritten. Since methods are dynamically bound in Java, the method C.f is called even if c has static type B. The output is therefore "C.f(int)".

3. Inheritance Hierarchy.

Which method is called in each case? State the output of the program.

public class A {
    public void foo(A a) {
        System.out.println("A.foo(A)");
    }
    public void foo(B b) {
        System.out.println("A.foo(B)");
    }
}
public class B extends A {
    public void foo(A a) {
        System.out.println("B.foo(A)");
    }
    public void foo(C c) {
        System.out.println("B.foo(C)");
    }
}
public class C extends B {
    public void foo(B b) {
        System.out.println("C.foo(B)");
    }
}
public class D extends C {
    public void foo(A a) {
        System.out.println("D.foo(A)");
    }
    public void foo(C c) {
        System.out.println("D.foo(C)");
    }
}
public class E extends B {
}
public class Main {
    public static void main(String[] args) {
        A aa = new A();
        A ad = new D();
        A ab = new B();
        B bd = new D();
        B be = new E();
        C cd = new D();
        D dd = new D();
        E ee = new E();

        aa.foo(dd);
        ad.foo(be);
        ad.foo(ad);
        ab.foo(bd);

        bd.foo(ee);
        be.foo(dd);

        cd.foo(be);
        cd.foo(ab);

        dd.foo(cd);
        dd.foo(dd);

        ee.foo(be);
        ee.foo(cd);
        ee.foo(ad);

        ad.foo(cd);
    }
}

202207281550

202206171400
Solution.

aa.foo(dd); \(\implies\)A.foo(B)
ad.foo(be); \(\implies\)C.foo(B)
ad.foo(ad); \(\implies\)D.foo(A)
ab.foo(bd); \(\implies\)A.foo(B)
bd.foo(ee); \(\implies\)C.foo(B)
be.foo(dd); \(\implies\)B.foo(C)
cd.foo(be); \(\implies\)C.foo(B)
cd.foo(ab); \(\implies\)D.foo(A)
dd.foo(cd); \(\implies\)D.foo(C)
dd.foo(dd); \(\implies\)D.foo(C)
ee.foo(be); \(\implies\)A.foo(B)
ee.foo(cd); \(\implies\)B.foo(C)
ee.foo(ad); \(\implies\)B.foo(A)
ad.foo(cd); \(\implies\)C.foo(B)

4. Vectors and Method Chaining.

In this exercise, you must implement a class which represents a two-dimensional point.

  1. Define a class Vec2 with the private members x, y of type double. Create a constructor receiving two arguments of type double.

  2. Insert a toString method which returns a String representation of the point in human-readable format. To this end, extend the following implementation to also include the member y.

    public String toString() {
      return "(" + x + ")";
    }
    

  3. Add accessor methods for the fields x and y.

  4. Test your implementation by inserting the following main function into your class and executing it:

    static public void main(String[] args) {
      // create a Vec2 here named v
      Vec2 v = new Vec2 (1.0 , 2.0);
      // Prints v according to its toString method.
      System.out.println(v);
    }
    
    The program should output (1.0, 2.0).

  5. Implement the methods addAssign and mulAssign with the following signatures:

    addAssign(double scalar)
    addAssign(final Vec2 point)
    mulAssign(double scalar)
    mulAssign(final Vec2 point)
    
    mulAssign shall multiply both vectors componentwise and not calculate the scalar- or cross product. Test your implementation by creating two vectors, adding the second onto the first, then multipliying the first one with 5, and finally printing both vectors.

  6. The methods in the previous subtask had type void. In this subtask we change the methods such that we can implement the calculation \(v*5 + w\) with v.mulAssign(5).addAssign(w). This programming idiom is called method chaining. Adapt mulAssign and addAssign so that they return the Vec2 object on which the method is called. Make sure that your modified program still produces the same output as before.

  7. Implement a copy constructor which receives a Vec2 instance v and creates a new Vec2 instance with the same coordinates as v. Test it with your main method.

202207281550

202206171400
Solution.
public class Vec2 {

  // Task a.
  private double x,y;

  public Vec2(double x, double y) {
    this.x = x;
    this.y = y;
  }

  // Task b.
  @Override
  public String toString() {
    return "(" + x + ", " + y + ")";
  }

  // Task c.
  public double getX() {
    return this.x;
  }

  public void setX(double x) {
    this.x = x;
  }

  public double getY() {
    return this.y;
  }

  public void setY(double y) {
    this.y = y;
  }

  @Override
  public boolean equals(Object o) {
    if (!(o instanceof Vec2))
      return false;
    Vec2 v = (Vec2) o;
    return v.getX() == getX() && v.getY() == getY();
  }

  public static void main(String[] args) {
    // Task d.
    Vec2 v = new Vec2(1.0, 2.0);
    System.out.println(v);

    // Start test for task e.
    test();

    // Test for task g.
    Vec2 v2 = new Vec2(v);
    if (v.equals(v2)) {
      System.out.println("Correct. The copy is equal.");
    } else {
      System.out.println("Error. Object is no equal.");
    }
  }

  // Task e.
  public void addAssign(double scalar) {
    this.x += scalar;
    this.y += scalar;
  }

  public void addAssign(final Vec2 point) {
    this.x += point.x;
    this.y += point.y;
  }

  public void mulAssign(double scalar) {
    this.x *= scalar;
    this.y *= scalar;
  }

  public void mulAssign(final Vec2 point) {
    this.x *= point.x;
    this.y *= point.y;
  }

  // Test for implementation of task e.
  public static void test() {
    Vec2 v1 = new Vec2(5.2, 3.2);
    Vec2 v2 = new Vec2(3.2, 5.2);
    v1.addAssign(v2);
    v1.mulAssign(5);
    System.out.println(v1);
  }

  // Task g.
  public Vec2(Vec2 v) {
    this(v.x, v.y);
  }
}

In subtask f), the methods are changed as follows:

public Vec2 addAssign(double scalar) {
  this.x += scalar;
  this.y += scalar;
  return this;
}

public Vec2 addAssign(final Vec2 point) {
  this.x += point.x;
  this.y += point.y;
  return this;
}

public Vec2 mulAssign(double scalar) {
  this.x *= scalar;
  this.y *= scalar;
  return this;
}

public Vec2 mulAssign(final Vec2 point) {
  this.x *= point.x;
  this.y *= point.y;
  return this;
}

// Test for task f. Returns the same as for task e.
public static void test2() {
  Vec2 v = new Vec2(5.2, 3.2);
  Vec2 w = new Vec2(3.2, 5.2);
  System.out.println(v.addAssign(w).mulAssign(5));
}
5. References.

Implement a class Rectangle which represents a rectangle using two Vec2 objects. Implement an appropriate constructor. Write access methods for the upper left point and the lower right point.

Test your program according to the following schema to assert that the class Rectangle correctly encapsulates its internal data:

Vec2 v = new Vec2(1.0, 2.0);
Vec2 w = new Vec2(3.0, 4.0);
Rectangle r = new Rectangle(v,w);
System.out.println(r);
v.setX(10.0);
System.out.println(r);
r.getTopLeft().setX(10.0);
System.out.println(r);
The following output should be printed:
Rectangle: (1.0, 2.0) to (3.0, 4.0)
Rectangle: (1.0, 2.0) to (3.0, 4.0)
Rectangle: (1.0, 2.0) to (3.0, 4.0)

202207281550

202206171400
Solution.
public class Rectangle {
  private Vec2 topLeft;
  private Vec2 botRight;

  /***
   * Represents a rectangle in two-dimensional space.
   * @param topLeft - upper left corner
   * @param botRight - lower right corner
   */
  public Rectangle(Vec2 topLeft, Vec2 botRight) {
    this.topLeft = new Vec2(topLeft);
    this.botRight = new Vec2(botRight);
  }

  public Vec2 getTopLeft() {
    // copy the Vec2 so noone can modify the rectangle
    return new Vec2(topLeft);
  }

  public Vec2 getBotRight() {
    // copy the Vec2 so noone can modify the rectangle
    return new Vec2(botRight);
  }

  public static void main(String[] args) {
    Vec2 v = new Vec2(1.0, 2.0);
    Vec2 w = new Vec2(3.0, 4.0);
    Rectangle r = new Rectangle (v, w);
    System.out.println(r);
    v.setX(10.0);
    System.out.println(r);
    r.getTopLeft().setX(10.0);
    System.out.println(r);
  }

  @Override
  public String toString() {
    return "Rectangle: " + this.topLeft + " to " + this.botRight;
  }
}
6. Static Methods.

In exercise 4, we defined the addition and multiplication methods in the vector class such that the object itself was modified. Now we implement static methods which return a new object instead.

  1. Research in the internet what the keyword static signifies and what it causes when used on a method.

  2. Implement add, mul and mod according to the following schema:

    public static Vec2 add(final Vec2 v, final Vec2 w) {
      // TODO
    }
    
    The methods shall leave v and w unmodified and shall return a new Vec2 object. Test in your main function that Vec2.mul(v,w) indeed does not change the objects v and w.

  3. Implement an additional static method rotate which receives a Vec2 v and a double a and returns a new vector which represents the vector v rotated by a (in radians) clockwise. It might be helpful to inform yourself about the library class java.lang.Math.

202207281550

202206171400
Solution.
  1. Static methods in Java belong to a class itself instead of to an instance. This means the method can be called by Vec2.add(...); instead of Vec2 inst = new Vec2(); inst.add(...);.

  2. The following methods must be added to the class Vec2:

    public static Vec2 add(final Vec2 v, final Vec2 w) {
      return new Vec2(v.x + w.x, v.y + w.y);
    }
    public static Vec2 add(final Vec2 v, final double scalar) {
      return new Vec2(v.x + scalar, v.y + scalar);
    }
    public static Vec2 mul(final Vec2 v, final Vec2 w) {
      return new Vec2(v.x * w.x, v.y * w.y);
    }
    public static Vec2 mul(final Vec2 v, final double scalar) {
      return new Vec2(v.x * scalar, v.y * scalar);
    }
    public static Vec2 mod(final Vec2 v, final double scalar) {
      return new Vec2(v.x % scalar, v.y % scalar);
    }
    
  3. The following method must be added to the class Vec2:

    public static Vec2 rotate(final Vec2 v, double a) {
      // Rotation in two-dimensional space.
      double x = v.x * Math.cos(a) - v.y * Math.sin(a);
      double y = v.x * Math.sin(a) + v.y * Math.cos(a);
      return new Vec2(x,y);
    }
    

Object-oriented Programming

7. Visitor.

Extend the grammar of the small expression language by a let construct let x = e in b where x is a variable and e and b are expressions. Extend the class hierarchy of Section 8.10 appropriately to represent this new construct. Implement a Visitor class that computes the set of free variables of an expression.

The set of free variables is defined recursively:

  • \(\displaystyle \textup{fv}(\mathtt{Const}[c]) = \emptyset\)

  • \(\displaystyle \textup{fv}(\mathtt{Var}[v]) = \{v\}\)

  • \(\displaystyle \textup{fv}(\mathtt{Add}[l,r]) = \textup{fv}(l)\cup \textup{fv}(r)\)

  • \(\displaystyle \textup{fv}(\mathtt{Let}[x,e,b]) = \textup{fv}(b)\setminus \{x\}\)

You can expect the existence of Getters for all the relevant fields in Add, Const and Var. You will also have to extend the Env interface. It is sufficient to state the specification of the new method in Env, you don't have to give an implementation for Env.

202207281550

202206171400
Solution.

The Let class:

public class Let implements Exp {

    private String var;
    private Exp binding;
    private Exp body;

    public Let(String var, Exp binding, Exp body) {
        this.var = var;
        this.binding = binding;
        this.body = body;
    }

    public int eval(Env e) {
        Env eExtended = e.extend(this.var, this.binding.eval(e));
        return this.body.eval(eExtended);
    }

    public String toString() {
        return "let " + this.var
             + " = "  + this.binding
             + " in " + this.body;
    }

    <T> public T accept(ExpVisitor<T> v) {
        v.visit(this);
    }
}

The visitor:

public class FreeVariablesFinder implements ExpVisitor<Set<String>> {
  
    public Set<String> visit(Add e) {
        return e.getLeft().accept(this).addAll(e.getRight().accept(this));
    }

    public Set<String> visit(Var e) {
        return (new HashSet<String>()).add(e);
    }

    public Set<String> visit(Let e) {
        return (e.getBody().accept(this)).remove(e.getVar());
    }

    public Set<String> visit(Const e) {
        return new HashSet<String>();
    }

}

The extended Env:

interface Env {
    int get(String varName);

    /**
    * Returns a new environment object
    * which is equivalent to this one
    * extended by the mapping of `varName` to `value`.
    * `this` is not modified.
    */
    Env extend(String varName, int value);
}
8. Class Hierarchy.

Read Section 8.9. Assume you are designing a library for geometrical objects in C.

typedef enum { TRIANGLE, RECTANGLE, CIRCLE } geom_kind_t;

typedef struct { vec2_t p[3]; } geom_triangle_t;

typedef struct {
    vec2_t upper_left, lower_right;
} geom_rectangle_t;

typedef struct {
    vec2_t center;
    double radius;
} geom_circle_t;

typedef struct {
    color_t color;
    geom_kind_t kind;
    union {
        geom_triangle_t triangle;
        geom_rectangle_t rectangle;
        geom_circle_t circle;
    };
} geom_object_t;

color_t get_color(geom_object_t* obj) {
    return obj->color;
}

int is_inside(geom_object_t* obj, vec2_t* p) {
    switch (obj->kind) {
    case TRIANGLE: return ...;
    case RECTANGLE: return ...;
    case CIRCLE: return ...;
    }
}

void translate(geom_object_t* obj, vec2_t* v) {
    switch (obj->kind) {
    case TRIANGLE: 
        for (int i = 0; i < 3; i++)
            vec2_translate(obj->triangle.p[i], v);
        break;
    case RECTANGLE:
        vec2_translate(obj->rectangle.upper_left, v);
        vec2_translate(obj->rectangle.lower_right, v);
        break;
    case CIRCLE:
        vec2_translate(obj->circle.center, v);
        break;
    }
}
  1. Devise a suitable class hierarchy with an interface GeomObject on top.

  2. Declare the methods of GeomObject appropriately.

  3. Implement all sub-classes with fields, appropriate visibility, setters and getters, and constructors.

  4. Implement all methods getColor, isInside, translate in the appropriate sub-classes.

  5. Can you factor out some methods in a common super class?

202207281550

202206171400
Solution.
public interface GeomObject {

    void translate(Vec2 v);

    Color getColor();

    boolean isInside(Vec2 v);

}
public abstract class ColoredGeomObject implements GeomObject {

    private Color color;

    public Color(Color color) {
        this.color = color;
    }

    public Color getColor() {
        return color;
    }

}
public class Rectangle extends ColoredGeomObject {

    private Vec2 upperLeft, lowerRight;

    public Rectangle(Color color, Vec2 upperLeft, Vec2 lowerRight) {
        super(color);
        this.upperLeft = upperLeft;
        this.lowerRight = lowerRight;
    }

    public Vec2 getUpperLeft() {
        return this.upperLeft;
    }

    public void setUpperLeft(Vec2 upperLeft) {
        this.upperLeft = upperLeft;
    }

    public Vec2 getLowerRight() {
        return this.lowerRight;
    }

    public Vec2 setLowerRight(Vec2 lowerRight) {
        return this.lowerRight = lowerRight;
    }

    public boolean isInside(Vec2 v) {
        return this.upperLeft.getX() <= v.getX() && v.getX() <= this.lowerRight.getX()
        && this.lowerRight.getY() <= v.getY() && v.getY() <= this.upperLeft.getY();
    }

    public void translate(Vec2 v) {
        this.upperLeft.translate(v);
        this.lowerRight.translate(v);
    }

}
public class Circle extends ColoredGeomObject {

    private Vec2 center;
    private double radius;

    public Circle(Color color, Vec2 center, double radius) {
        super(color);
        this.center = center;
        this.radius = radius;
    }

    public Vec2 getCenter() {
        return super.center;
    }

    public void setCenter(Vec2 center) {
        this.center = center;
    }

    public double getRadius() {
        return this.radius;
    }

    public void setRadius(double radius) {
        this.radius = radius;
    }

    public isInside(Vec2 v) {
        return this.center.minus(v).abs() <= this.radius;
    }

}
public class Triangle extends ColoredGeomObject {

    private Vec2[] vertices;

    public Triangle(Color color, Vec2[] vertices) {
        super(color);
        this.vertices = vertices;
    }

    public Vec2[] getVertices() {
        return this.vertices;
    }

    public void setVertices(Vec2[] vertices) {
        this.vertices = vertices;
    }

    public boolean isInside(Vec2 v) {
        // idea:
        // - first normalize `this` to a counter-clockwise orientated triangle
        // - on the normalized triangle, if we replace any one vertex with v,
        //     the resulting triangle must also be counter-clockwise orientated
        Vec2 a = vertices[0];
        Vec2 b, c;
        if (computeOrientation() > 0) {
            b = vertices[1];
            c = vertices[2];
        } else {
            b = vertices[2];
            c = vertices[1];
        }
        Triangle abv = new Triangle(this.getColor(), new Vec2[]{a,b,v});
        Triangle bcv = new Triangle(this.getColor(), new Vec2[]{b,c,v});
        Triangle cav = new Triangle(this.getColor(), new Vec2[]{c,a,v});
        return abv.computeOrientation() > 0
            && bcv.computeOrientation() > 0
            && cav.computeOrientation() > 0;
    }

    double computeOrientation() {
        // triangle is counter-clockwise orientated iff result > 0
        return (vertices[1].getX() - vertices[0].getX()) * (vertices[2].getY() - vertices[1].getY())
            - (vertices[1].getY() - vertices[0].getY()) * (vertices[2].getX() - vertices[1].getX());
    }

}