class InnerTypesIncrementalHeuristic implements FieldCheckHeuristic {

  private final TypeManager manager;

  private final Set<RefType> typesToCheck = new HashSet<RefType>();

  private String newTypeOnQuery = null;

  private final Set<RefType> bothEndsTypes = new HashSet<RefType>();

  private final Set<RefType> notBothEndsTypes = new HashSet<RefType>();

  private int numPasses = 0;

  private final int passesInDirection;

  private boolean allNotBothEnds = false;

  public InnerTypesIncrementalHeuristic(TypeManager manager, int maxPasses) {
    this.manager = manager;
    this.passesInDirection = maxPasses / 2;
  }

  public boolean runNewPass() {
    numPasses++;
    if (numPasses == passesInDirection) {
      return switchToNotBothEnds();
    } else {
      if (newTypeOnQuery != null) {
        String topLevelTypeStr = Util.topLevelTypeString(newTypeOnQuery);
        boolean added;
        if (Scene.v().containsType(topLevelTypeStr)) {
          RefType refType = Scene.v().getRefType(topLevelTypeStr);
          added = typesToCheck.add(refType);
        } else {
          added = false;
        }
        newTypeOnQuery = null;
        return added;
      } else {
        return switchToNotBothEnds();
      }
    }
  }

  private boolean switchToNotBothEnds() {
    if (!allNotBothEnds) {
      numPasses = 0;
      allNotBothEnds = true;
      newTypeOnQuery = null;
      typesToCheck.clear();
      return true;
    } else {
      return false;
    }
  }

  public boolean validateMatchesForField(SparkField field) {<FILL_FUNCTION_BODY>}

  public boolean validFromBothEnds(SparkField field) {
    if (allNotBothEnds) {
      return false;
    }
    if (field instanceof ArrayElement) {
      return true;
    }
    SootField sootField = (SootField) field;
    RefType declaringType = sootField.getDeclaringClass().getType();
    if (bothEndsTypes.contains(declaringType)) {
      return true;
    } else if (notBothEndsTypes.contains(declaringType)) {
      return false;
    } else {
      if (SootUtil.hasRecursiveField(declaringType.getSootClass())) {
        notBothEndsTypes.add(declaringType);
        return false;
      } else {
        bothEndsTypes.add(declaringType);
        return true;
      }
    }
  }

  @Override
  public String toString() {
    return typesToCheck.toString();
  }
}

    if (field instanceof ArrayElement) {
      return true;
    }
    SootField sootField = (SootField) field;
    RefType declaringType = sootField.getDeclaringClass().getType();
    String declaringTypeStr = declaringType.toString();
    String topLevel = Util.topLevelTypeString(declaringTypeStr);
    RefType refType;
    if (Scene.v().containsType(topLevel)) {
      refType = Scene.v().getRefType(topLevel);
    } else {
      refType = null;
    }
    for (RefType checkedType : typesToCheck) {
      if (manager.castNeverFails(checkedType, refType)) {
        // System.err.println("validate " + declaringTypeStr);
        return true;
      }
    }
    if (newTypeOnQuery == null) {
      newTypeOnQuery = declaringTypeStr;
    }
    return false;
  
<no_super_class>