title: How to implement the methods in the absence of instance variables and generics
body: <p>I'm working on a project where I need to replace the old ExpFoo with a new ExpFoo. </p>
  
  <p>An example would be an ExpFoo ((x * y) + (x * z)) is given and we have new IntFoo, 2, which will replace the Varfoo, x. And we have a PlusFoo (a + b), which will replace the Varfoo, y.</p>
  
  <p>So the result will be: ((2 * (a + b) + (2 * z))</p>
  
  <p>Here's how it looks on the Main class:</p>
  
  <pre><code>import java.util.Arrays;
  
  public class Main {
  
  public static void main(String[] args) {
  
      ExpFoo e1 = new IntFoo(1);
      ExpFoo e2 = new IntFoo(2);
      ExpFoo e5 = new IntFoo(5);
      ExpFoo x = new VarFoo("x");
      ExpFoo plus = new PlusFoo(e1, e2);
      ExpFoo times = new TimesFoo(e5, x);
      ExpFoo bigTimes = new TimesFoo(plus, times);
  
      ExpFoo[] exps = { e1, e2, e5, x, plus, times, bigTimes };
      System.out.println(Arrays.toString(exps));
  
      Replacement r = new Replacement();
      r.put(new VarFoo("x"), new PlusFoo(e1, e5));
      System.out.println(r);
  
      for (ExpFoo exp : exps) {
          System.out.println(exp + " has " + exp.numberOfNodes() + " nodes and after applying " + r  + " the value " + exp.computeValue(r));
      }
  
      ExpFoo ex1 = new PlusFoo(new TimesFoo(new VarFoo("x"), new VarFoo("y")),new TimesFoo(new VarFoo("x"), new VarFoo("z")));
      Replacement repl = new Replacement();
      repl.put(new VarFoo("x"), new IntFoo(2));
      repl.put(new VarFoo("y"), new PlusFoo(new VarFoo("a"), new VarFoo("b")));
      ExpFoo ex2 = ex1.applyReplacement(repl);
      System.out.println("ex1: " + ex1);
      System.out.println("ex2: " + ex2);
  
  }
  }
  </code></pre>
  
  <p>I have two issues: <br/></p>
  
  <ol>
  <li>I cannot get the values of times and bigTimes.</li>
  <li>I cannot get applyReplacement(repl) to work.</li>
  </ol>
  
  <p>For the first issue, I couldn't get the values of <code>ExpFoo times = new TimesFoo(e5, x);</code> and
      <code>ExpFoo bigTimes = new TimesFoo(plus, times);</code> to use <code>exp.computeValue(r)</code> because I couldn't work out on how to calculate 1 + 5 to 6. <br/></p>
  
  <p>All I've got was an exception that says: <strong>UnsupportedOperationException: Cannot compute the value of a varfoo without a replacement!</strong></p>
  
  <p>For times, it should return as  <strong>(5 * x) has 3 nodes and after applying [x:=(1 + 5)] the value 30</strong><br/>
  For bigTimes, it should return as <strong>((1 + 2) * (5 * x)) has 7 nodes and after applying [x:=(1 + 5)] the value 90</strong></p>
  
  <p>For the second issue, I'm having a problem with 
  <code>ExpFoo ex2 = ex1.applyReplacement(repl);</code> <br/></p>
  
  <p>It returns an exception <strong>TimesExpFoo cannot be cast to class com.company.VarFoo</strong> I couldn't get it to work. 
  It should return as <strong>((2 * (a + b) + (2 * z))</strong></p>
  
  <p>I'm not allowed to create instance variables to all the classes except Replacement. </p>
  
  <p>I cannot use generics in all classes either.</p>
  
  <p>Here's the illustration on how it works, the Replacement class is separated in all classes.</p>
  
  <p><a href="https://i.stack.imgur.com/DO8Oq.jpg" rel="nofollow noreferrer">UML image here</a></p>
  
  <p>For the classes, this is what I've done so far. </p>
  
  <p>Varfoo class:</p>
  
  <pre><code>import java.util.Set;
  
  /**
  * A VarFoo is a symbolic ExpFoo that stands for a value that has not yet
  * been fixed. A VarFoo has a name of the format
  * letter (letter | digit)^*
  * (where '(letter | digit)^*' stands for 'a string of length 0 or more that
  * contains only letters and digits').
  * Here the class methods Character.isLetter(char) and
  * Character.isLetterOrDigit(char) determine whether a character is
  * a letter/a letter or a digit, respectively.
  * Instances of this class are immutable.
  */
  public class VarFoo implements ExpFoo {
  
  /**
   * Name of this VarFoo. Non-null, of the format
   * &lt;p&gt;
   * letter (letter | digit)*
   */
  private String name;
  
  /**
   * Constructs a new VarFoo with the specified name.
   *
   * @param name must not be null; must be a String of the format letter
   *             (letter | digit)^*
   */
  
  public VarFoo(String name) {
      this.name = name;
  }
  
  @Override
  public int numberOfNodes() {
      return 1;
  }
  
  @Override
  public int computeValue() {
      throw new UnsupportedOperationException("Cannot compute the value of a varfoo without a replacement!");
  }
  
  @Override
  public int computeValue(Replacement repl) {
      //TODO;
  }
  
  @Override
  public ExpFoo applyReplacement(Replacement s) {
      //TODO
  }
  
  @Override
  public boolean isVarFooFree() {
      // TODO
      return true;
  }
  
  @Override
  public Set&lt;VarFoo&gt; getVarfoo() {
      return null;
  }
  
  @Override
  public void collectVarfoo(Set&lt;VarFoo&gt; vars) {
      for (char c : name.toCharArray()) {
          if (Character.isAlphabetic(c)){
              vars.add(new VarFoo(name));
          }
      }
  }
  
  @Override
  public String toString() {
      return name;
  }
  
  /**
   * The method returns true if o is an instance of class VarFoo
   * whose name is equal to the name of this VarFoo; otherwise it
   * returns false.
   *
   * @return whether this VarFoo and Object o are equal
   */
  @Override
  public boolean equals(Object o) {
      if (o == null) return false;
      if (!(o instanceof VarFoo))
          return false;
      if (o == this)
          return true;
      return name.equals(((VarFoo) o).name);
  }
  
  @Override
  public int hashCode() {
      int prime = 31;
      int result = 1;
      result = prime * result + ((name == null) ? 0 : name.hashCode());
      return result;
  
  
  }
  }
  </code></pre>
  
  <p>Replacement class:</p>
  
  <pre><code>import java.util.HashMap;
  import java.util.Map;
  
  /**
  * A Replacement represents a mapping of finitely many VarFoo to
  * ExpFoo. One can construct an empty Replacement, update a Replacement
  * by adding/replacing/forgetting mappings of VarFoo to ExpFoo, and
  * query Replacements for the value to which they map a varfoo, whether they
  * have a mapping for a specific varfoo, and for a String representation.
  */
  public class Replacement {
  
  private Map&lt;VarFoo, ExpFoo&gt; replacementMap;
  
  /**
   * Constructs an empty Replacement (i.e., a Replacement that does not
   * hold mappings for any varfoo(s).
   */
  public Replacement() {
      replacementMap = new HashMap&lt;&gt;();
  }
  
  /* Mutators */
  
  /**
   * Associates the specified ExpFoo with the specified Varfoo in this
   * Replacement. If the Replacement previously contained a mapping for the
   * Varfoo, the old ExpFoo is replaced.
   *
   * @param var the Varfoo with which exp is to be associated
   * @param exp the ExpFoo to which var is to be mapped
   * @return the ExpFoo to which var was mapped so far, or null if var did
   * not yet have a mapping in this Replacement
   * @throws NullPointerException if var or exp is null
   */
  public ExpFoo put(VarFoo var, ExpFoo exp) {
      return replacementMap.put(var, exp);
  }
  
  /**
   * Forgets the mapping for the specified Varfoo. Does not modify this
   * Replacement if it does not have a mapping for the specified Varfoo.
   *
   * @param var the Varfoo for which we want to forget the mapping
   * @return whether a mapping for var was forgotten due to the method call
   * @throws NullPointerException may be thrown if var is null
   */
  public boolean forget(VarFoo var) {
      if (var == null) {
          return true;
      }
      else {
          replacementMap.clear();
          return true;
      }
  }
  
  /* Accessors */
  
  /**
   * Returns the value to which the specified Varfoo is mapped, or null if
   * this Replacement contains no mapping for the specified Varfoo.
   *
   * @param var the Varfoo for which we want the corresponding ExpFoo to
   *            which it is mapped
   * @return the ExpFoo to which this Replacement maps var, or var if
   * this Replacement does not have a mapping for var
   * @throws NullPointerException may be thrown if var is null
   */
  public ExpFoo get(VarFoo var) {
      return replacementMap.get(var);
  }
  
  /**
   * Returns whether this Replacement has an explicit mapping of var to an
   * ExpFoo.
   *
   * @param var the Varfoo for which we want to know if this Replacement
   *            has a mapping
   * @return whether this Replacement has an explicit mapping of var to an
   * ExpFoo
   * @throws NullPointerException may be thrown if the parameter is null
   */
  public boolean hasMappingFor(VarFoo var) {
      return replacementMap.containsValue(var);
  }
  
  @Override
  public String toString() {
      String s = "";
      for (Map.Entry&lt;VarFoo, ExpFoo&gt; ReplacementKey : replacementMap.entrySet()) {
          s = "[" + ReplacementKey.getKey() + ":=" + ReplacementKey.getValue() + "]";
      }
      return s;
  }
  }
  </code></pre>
  
  <p>ExpFoo class:</p>
  
  <pre><code>import java.util.LinkedHashSet;
  import java.util.Set;
  
  /**
  * Basic interface for arithmetic ExpFoo. Implementations are expected to
  * be immutable, i.e., after object creation, the object's state cannot change,
  * and there are no mutator methods in any class that implements this interface.
  */
  public interface ExpFoo {
  
  /**
   * Computes the number of sub-ExpFoo of this ExpFoo (its "size").
   *
   * @return the number of nodes of this ExpFoo.
   */
  int numberOfNodes();
  
  /**
   * Computes the int value represented by this ExpFoo object. This
   * ExpFoo object must not contain Varfoos.
   *
   * @return the int value represented by this ExpFoo
   */
  int computeValue();
  
  /**
   * Computes the int value represented by this ExpFoo.
   *
   * @param repl
   *            to be used to assign values to this ExpFoo; must not be
   *            null
   * @return the int value represented by this ExpFoo
   * @throws UnsupportedOperationException
   *             if the ExpFoo with repl applied to it still has
   *             Varfoo
   * @throws NullPointerException
   *             if s is null
   */
  default int computeValue(Replacement repl) {
      ExpFoo specialised = applyReplacement(repl);
      return specialised.computeValue();
  }
  
  /**
   * Returns whether this ExpFoo is VarFoo-free, i.e., none of its
   * direct or indirect sub-ExpFoo is a VarFoo object.
   *
   * @return whether this ExpFoo is VarFoo-free, i.e., none of its
   *         direct or indirect sub-ExpFoo is a VarFoo object.
   */
  boolean isVarFooFree();
  
  /**
   * Returns the Set of Varfoo of this ExpFoo. The returned Set may be
   * modified.
   *
   * @return the Set of Varfoo of this ExpFoo
   */
  default Set&lt;VarFoo&gt; getVarfoo() {
      Set&lt;VarFoo&gt; result = new LinkedHashSet&lt;&gt;();
      collectVarfoo(result);
      return result;
  }
  
  /**
   * Adds all Varfoo in this ExpFoo to vars
   *
   * @param vars
   *            Varfoo will be added here; parameter must not be null
   * @throws NullPointerException
   *             if vars is null
   */
  void collectVarfoo(Set&lt;VarFoo&gt; vars);
  
  /**
   * Applies a Replacement to this ExpFoo and returns the result.
   *
   * @param r
   *            a Replacement to be applied to this ExpFoo; must not be
   *            null
   * @return a version of this ExpFoo where all Varfoo have been
   *         replaced by the values stored in s for the Varfoo
   * @throws NullPointerException
   *             if s is null
   */
  ExpFoo applyReplacement(Replacement r);
  }
  </code></pre>
  
  <p>BinaryFoo class:</p>
  
  <pre><code>import java.util.Set;
  
  /**
  * Abstract class for ExpFoos with two direct subExpFoos. Provides an
  * implementation for numberOfNodes() method. Instances of this class are immutable.
  */
  public abstract class BinaryFoo implements ExpFoo {
  
  /** the left subExpFoo; non-null */
  private ExpFoo left;
  
  /** the right subExpFoo; non-null */
  private ExpFoo right;
  
  /** String representation of the operator symbol; non-null */
  private String operatorSymbol;
  
  /**
   * Constructs a BinaryFoo with left and right as direct
   * subExpFoo and with operatorSymbol as the String representation of
   * the operator.
   *
   * @param left
   *            the left subExpFoo; non-null
   * @param right
   *            the right subExpFoo; non-null
   * @param operatorSymbol
   *            String representation of the operator symbol; non-null
   */
  public BinaryFoo(ExpFoo left, ExpFoo right,
                   String operatorSymbol) {
      if (left == null) {
          throw new NullPointerException("Illegal null value for left!");
      }
      if (right == null) {
          throw new NullPointerException("Illegal null value for right!");
      }
      if (operatorSymbol == null) {
          throw new NullPointerException(
                  "Illegal null value for operatorSymbol!");
      }
      this.left = left;
      this.right = right;
      this.operatorSymbol = operatorSymbol;
  }
  
  /**
   * Getter for the left subExpFoo.
   *
   * @return the left subExpFoo
   */
  public ExpFoo getLeft() {
      return left;
  }
  
  /**
   * Getter for the right subExpFoo.
   *
   * @return the right subExpFoo
   */
  public ExpFoo getRight() {
      return right;
  }
  
  /**
   * Getter for the operator symbol.
   *
   * @return the operator symbol
   */
  public String getOperatorSymbol() {
      return operatorSymbol;
  }
  
  @Override
  public int numberOfNodes() {
      return 1 + left.numberOfNodes() + right.numberOfNodes();
  }
  
  @Override
  public void collectVariables(Set&lt;VarFoo&gt; vars) {
      vars.add((VarFoo)left);
      vars.add((VarFoo)right);
  }
  
  @Override
  public boolean isVarFooFree() {
      // TODO
      return false;
  }
  
  @Override
  public String toString() {
      return "(" + left + " " + operatorSymbol + " " + right + ")";
  }
  
  @Override
  public boolean equals(Object o) {
      if (!(o instanceof BinaryFoo)) {
          return false;
      }
      BinaryFoo other = (BinaryFoo) o;
      // relies on instance variables being non-null
      return operatorSymbol.equals(other.operatorSymbol)
              &amp;&amp; left.equals(other.left) &amp;&amp; right.equals(other.right);
  }
  
  @Override
  public int hashCode() {
      int result = (left == null) ? 0 : left.hashCode();
      result += (right == null) ? 0 : right.hashCode();
      return result;
  }
  }
  </code></pre>
  
  <p>TimesFoo class:</p>
  
  <pre><code>/**
  * Represents an ExpFoo of the form e1 * e2.
  * Instances of this class are immutable.
  */
  public class TimesFoo extends BinaryFoo {
  
  /**
   * Constructs a TimesFoo with left and right as direct
   * subExpFoo.
   */
  public TimesFoo(ExpFoo left, ExpFoo right) {
      super(left, right, "*");
  }
  
  @Override
  public int computeValue() {
      return getLeft().computeValue() * getRight().computeValue();
  }
  
  @Override
  public int computeValue(Replacement subst) {
      return computeValue();
  }
  
  @Override
  public ExpFoo applyReplacement(Replacement r) {
      ExpFoo e = s.get((VarFoo)getVarFoo());
      return e;
  }
  
  @Override
  public boolean equals(Object o) {
      if (!(o instanceof TimesFoo)) {
          return false;
      }
      return super.equals(o);
  }
  
  @Override
  public int hashCode() {
      return super.hashCode();
  }
  }
  </code></pre>
  
  <p>PlusFoo class:</p>
  
  <pre><code>/**
  * Represents an ExpFoo of the form e1 + e2.
  * Instances of this class are immutable.
  */
  public class PlusFoo extends BinaryFoo {
  
  /**
   * Constructs a PlusFoo with left and right as direct subExpFoos.
   *
   * @param left  the left subExpFoo; non-null
   * @param right the right subExpFoo; non-null
   */
  public PlusFoo(ExpFoo left, ExpFoo right) {
      super(left, right, "+");
  }
  
  @Override
  public int computeValue() {
      return getLeft().computeValue() + getRight().computeValue();
  }
  
  @Override
  public ExpFoo applyReplacement(Replacement r) {
      ExpFoo e = s.get((VarFoo)getVarFoo());
      return e;
  }
  
  @Override
  public int computeValue(Replacement repl) {
      return computeValue();
  }
  
  @Override
  public boolean equals(Object o) {
      if (!(o instanceof PlusFoo)) {
          return false;
      }
      return super.equals(o);
  }
  
  @Override
  public int hashCode() {
      return super.hashCode();
  }
  }
  </code></pre>
  
  <p>IntFoo class:</p>
  
  <pre><code>import java.util.Objects;
  import java.util.Set;
  
  /**
  * ExpFoo that represents an int value.
  */
  public class IntFoo implements ExpFoo {
  
  /**
   * Stores the encapsulated value.
   */
  private int value;
  
  /**
   * Constructs a new IntFoo encapsulating value.
   *
   * @param value to be encapsulated in this IntFoo
   */
  public IntFoo(int value) {
      this.value = value;
  }
  
  /**
   * @return the int value this IntFoo stands for
   */
  public int getValue() {
      return value;
  }
  
  @Override
  public int numberOfNodes() {
      return 1;
  }
  
  @Override
  public int computeValue(Replacement repl) {
      return computeValue();
  }
  
  @Override
  public int computeValue() {
      return value;
  }
  
  @Override
  public ExpFoo applyReplacement(Replacement r) {
      VarFoo var = new Variable(name); //error
      ExpFoo e = s.get(var);
      return e;
  }
  
  @Override
  public boolean isVarFooFree() {
      // TODO
      return false;
  }
  
  @Override
  public Set&lt;VarFoo&gt; getVarfoo() {
      return null;
  }
  
  @Override
  public void collectVarfoo(Set&lt;VarFoo&gt; vars) {
  
  }
  
  @Override
  public String toString() {
      return "" + value;
  }
  
  @Override
  public boolean equals(Object o) {
      if (o == null) return false;
      if (!(o instanceof IntFoo))
          return false;
      if (o == this)
          return true;
      return value == (((IntFoo) o).value);
  }
  
  @Override
  public int hashCode() {
      return Objects.hash(value);
  }
  }
  </code></pre>