package javakurs.musterloesung.uebung11;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 * {@link Grammar} implements the abstract methods of {@link GrammarBase}.
 *
 * @author Joerg Steffen, DFKI
 * @version $Id: Grammar.java,v 1.1 2011/01/26 15:50:16 steffen Exp $
 */
public class Grammar extends GrammarBase {

  /**
   * Caches the results of the getRulesTopDown method.
   */
  private Map<String, List<Rule>> ruleCache;


  /**
   * Creates a new instance of {@link Grammar}.
   */
  public Grammar() {

    super();
    this.ruleCache = new HashMap<String, List<Rule>>();
  }


  /**
   * {@inheritDoc}
   */
  @Override
  public void calculateFirstMap() {

    SortedSet<String> activeNonTerminals = new TreeSet<String>();

    // get initial active non-terminals
    for (Rule oneRule : this.rules) {

      // check if rhs of rule starts with a terminal
      if (this.isTerminal(oneRule.getRhs(0))) {

        // add terminal to 'first' terminals of the lhs non-terminal
        Set<String> lhsFirstTerminals =
          this.nonTerm2firstTerms.get(oneRule.getLhs());
        if (null == lhsFirstTerminals) {
          // create new empty set
          lhsFirstTerminals = new HashSet<String>();
          this.nonTerm2firstTerms.put(oneRule.getLhs(), lhsFirstTerminals);
        }
        lhsFirstTerminals.add(oneRule.getRhs(0));

        // add lhs non-terminal to list of active non-terminals
        activeNonTerminals.add(oneRule.getLhs());
      }
    }

    // process active non-terminals
    while (!activeNonTerminals.isEmpty()) {
      // get next active non-terminal and change it to inactive by removing it
      // from the set
      String oneActiveNonTerm = activeNonTerminals.first();
      activeNonTerminals.remove(oneActiveNonTerm);
      // iterate over the rules and check if some lhs non-terminals become
      // active
      for (Rule oneRule : this.rules) {
        if (oneRule.getRhs(0).equals(oneActiveNonTerm)) {
          // rhs of rule starts with the active non-terminal, so update the
          // first map of the lhs non-terminal
          Set<String> firstSet = this.nonTerm2firstTerms.get(oneRule.getLhs());
          if (null == firstSet) {
            // create new empty set
            firstSet = new HashSet<String>();
            this.nonTerm2firstTerms.put(oneRule.getLhs(), firstSet);
          }
          if (firstSet.addAll(this.nonTerm2firstTerms.get(oneActiveNonTerm))) {
            // set was changed, so the lhs non-terminal becomes active
            activeNonTerminals.add(oneRule.getLhs());
          }
        }
      }
    }
  }


  /**
   * {@inheritDoc}
   */
  @Override
  public List<Rule> getRulesTopDown(String nonTerminal, String firstTerminal) {

    // create unique key for input parameters
    String key = new StringBuilder()
      .append(nonTerminal).append(" ").append(firstTerminal).toString();

    List<Rule> result = null;
    // try to get result from cache
    result = this.ruleCache.get(key);
    if (null != result) {
      return result;
    }

    // result not found in cache
    result = new ArrayList<Rule>();

    for (Rule oneRule : this.rules) {
      // search for rules with the matching lhs
      if (!oneRule.getLhs().equals(nonTerminal)) {
        continue;
      }
      if (this.isTerminal(oneRule.getRhs(0))) {
        // if the first rhs element is a terminal, it has to be the given
        // terminal;
        if (oneRule.getRhs(0).equals(firstTerminal)) {
          result.add(oneRule);
        }
      }
      else {
        // if the first rhs element is a non-terminal, it has to have the given
        // terminal in its 'first' set
        if (this.getFirstTerminals(oneRule.getRhs(0)).contains(firstTerminal)) {
          result.add(oneRule);
        }
      }
    }

    // cache result
    this.ruleCache.put(key, result);

    return result;
  }
}
