package javakurs.musterloesung.uebung11;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * {@link TopDownParser} uses a top-down strategy to parse an input sentence.
 *
 * @author Bernd Kiefer, DFKI
 * @author Joerg Steffen, DFKI
 * @version $Id: TopDownParserBase.java,v 1.1 2011/01/26 15:50:17 steffen Exp $
 */
public abstract class TopDownParserBase {

  /**
   * Contains the underlying grammar.
   */
  private Grammar grammar;


  /**
   * Contains a flag indicating if the result of the expand method should be
   * cached.
   */
  private boolean cacheFlag;


  /**
   * Creates a new instance of {@link TopDownParser} using the given grammar.
   *
   * @param grammarFile
   *          the file name of the grammar
   */
  public TopDownParserBase(String grammarFile) {

    this.grammar = new Grammar();
    this.grammar.readFromFile(grammarFile, "UTF-8");
    this.grammar.calculateFirstMap();
    this.cacheFlag = true;
  }


  /**
   * Returns the cache flag.
   *
   * @return a flag indicating if the result of the expand method should be
   *         cached
   */
  public boolean isCacheFlag() {

    return this.cacheFlag;
  }


  /**
   * Sets the cache flag to the given parameter.
   *
   * @param cacheFlag
   *          a flag indicating if the result of the expand method should be
   *          cached
   */
  public void setCacheFlag(boolean cacheFlag) {

    this.cacheFlag = cacheFlag;
  }


  /**
   * Checks if the given input sequence can be matched with the grammar of this
   * top-down parser.
   *
   * @param input
   *          the input sequence
   * @return a flag indicating if the input sequence could be matched
   */
  public boolean recognize(List<String> input) {

    // reset cache if it's to be used
    if (this.isCacheFlag()) {
      this.resetCache();
    }

    // get possible end positions, starting at position 0 with the start symbol
    // of the grammar
    Set<Integer> possibleEndPositions =
      this.expand(this.grammar.getStartSymbol(), 0, input);

    // if the last position is among the possible end positions, the input
    // could be matched
    return possibleEndPositions.contains(input.size());
  }


  /**
   * Expands the symbol {@code toRecognize} recursively top-down and returns the
   * full set of end positions to which this symbol can expand.
   *
   * The set of possible end positions corresponds to the substrings of the
   * input to which {@code toRecognize} can expand when starting at position
   * {@code currentPos}.
   *
   * @param toRecognize
   *          the symbol to recognize from position {@code currentPos} in the
   *          input
   * @param currentPos
   *          the position in the input to start recognition at
   * @param inputTerminals
   *          the terminals of the input string
   * @return the end positions that correspond to the possible expansions given
   *         the symbol to recognize and the current part of the input string
   */
  protected Set<Integer> expand(
      String toRecognize, int currentPos, List<String> inputTerminals) {

    Set<Integer> endPositions = new HashSet<Integer>();

    // expanding when we are already at the end is not possible
    if (currentPos == inputTerminals.size()) {
      return endPositions;
    }

    // if toRecognize is a terminal, we just have to check if it's the right one
    if (this.grammar.isTerminal(toRecognize)) {
      if (toRecognize.equals(inputTerminals.get(currentPos))) {
        endPositions.add(currentPos + 1);
      }
      // this is all we can do now
      return endPositions;
    }

    // toRecognize is a non-terminal
    if (this.cacheFlag) {
      return this.expandNonTerminalWithCache(
        toRecognize, currentPos, inputTerminals);
    }
    return this.expandNonTerminal(toRecognize, currentPos, inputTerminals);
  }


  /**
   * Expands the non-terminal {@code toRecognize} recursively top-down and
   * returns the full set of end positions to which this symbol can expand.
   *
   * The set of possible end positions corresponds to the substrings of the
   * input to which {@code toRecognize} can expand when starting at position
   * {@code currentPos}.
   *
   * @param toRecognize
   *          the non-terminal to recognize from position {@code currentPos} in
   *          the input
   * @param currentPos
   *          the position in the input to start recognition at
   * @param inputTerminals
   *          the terminals of the input string
   * @return the end positions that correspond to the possible expansions given
   *         the symbol to recognize and the current part of the input string
   */
  protected Set<Integer> expandNonTerminal(
      String toRecognize, int currentPos, List<String> inputTerminals) {

    Set<Integer> endPositions = new HashSet<Integer>();

    // determine the possible end positions for all productions
    for (Rule oneRule : this.grammar.getRulesTopDown(
          toRecognize, inputTerminals.get(currentPos))) {

      // here we collect the positions reachable when applying this rule
      Set<Integer> reachPos = new HashSet<Integer>();
      reachPos.add(currentPos);

      // recognize all non-terminals and check all terminals against the
      // input positions
      for (String oneSymbol : oneRule.getRhs()) {

        // here we collect the new (intermediate) reachable positions
        Set<Integer> newReachPos = new HashSet<Integer>();
        // expand the next symbol from all current positions
        for (int onePos : reachPos) {
          newReachPos.addAll(this.expand(oneSymbol, onePos, inputTerminals));
        }
        // update reachable positions
        reachPos = newReachPos;
        // if this set gets empty, we can not fully expand this production
        if (reachPos.isEmpty()) {
          break;
        }
      }
      // add the end positions for this production to the result set
      endPositions.addAll(reachPos);
    }

    return endPositions;
  }


  /**
   * Expands the non-terminal {@code toRecognize} recursively top-down using a
   * cache and returns the full set of end positions to which this symbol can
   * expand.
   *
   *
   * The set of possible end positions corresponds to the substrings of the
   * input to which {@code toRecognize} can expand when starting at position
   * {@code currentPos}.
   *
   * @param toRecognize
   *          the non-terminal to recognize from position {@code currentPos} in
   *          the input
   * @param currentPos
   *          the position in the input to start recognition at
   * @param inputTerminals
   *          the terminals of the input string
   * @return the end positions that correspond to the possible expansions given
   *         the symbol to recognize and the current part of the input string
   */
  protected abstract Set<Integer> expandNonTerminalWithCache(
     String toRecognize, int currentPos, List<String> inputTerminals);

  /**
   * Resets the cache.
   */
  protected abstract void resetCache();
}
