public class CandidateStatistics {
  public final Candidate candidate;
  public final int rank, uniqueRank;    // rank and uniqueRank are 1-indexed
  public final double score;
  
  public CandidateStatistics(Candidate candidate, int rank, int uniqueRank, double score) {
    this.candidate = candidate;
    this.rank = rank;
    this.uniqueRank = uniqueRank;
    this.score = score;
  }
  
  /**
   * Convert Pair<Candidate, Double> to CandidateStatistics
   */
  public static List<CandidateStatistics> getRankedCandidateStats(List<Pair<Candidate, Double>> rankedCandidates) {
    List<CandidateStatistics> answer = new ArrayList<>();
    Set<List<String>> foundPredictedEntities = new HashSet<>();
    for (int rank = 0; rank < rankedCandidates.size(); rank++) {
      Pair<Candidate, Double> entry = rankedCandidates.get(rank);
      Candidate candidate = entry.getFirst();
      foundPredictedEntities.add(candidate.predictedEntities);
      answer.add(new CandidateStatistics(candidate, rank + 1, foundPredictedEntities.size(), entry.getSecond()));
    }
    return answer;
  }
} public abstract class EvaluationCase {
  public final Evaluator evaluator;
  public final Example ex;
  public final CandidateStatistics pred, firstTrue, best;
  
  // IR scores compared to expected entities
  public final IRScore predIRScore, firstTrueIRScore, bestIRScore;
  
  // IR scores compared to best true
  public final IRScore predIRScoreOnBest, firstTrueIRScoreOnBest;
  
  protected EvaluationCase(Evaluator evaluator, Example ex, CandidateStatistics pred,
      CandidateStatistics firstTrue, CandidateStatistics best) {
    this.evaluator = evaluator;
    this.ex = ex;
    this.pred = pred;
    this.firstTrue = firstTrue;
    this.best = best;
    // Compute IR scores
    predIRScore = (pred == null) ? null : ex.expectedAnswer.getIRScore(pred.candidate);
    firstTrueIRScore = (firstTrue == null) ? null : ex.expectedAnswer.getIRScore(firstTrue.candidate);
    bestIRScore = (best == null) ? null : ex.expectedAnswer.getIRScore(best.candidate);
    if (best == null) {
      predIRScoreOnBest = firstTrueIRScoreOnBest = null;
    } else {
      List<TargetEntity> bestTrueEntites = new ArrayList<>();
      for (String entity : best.candidate.predictedEntities) {
        bestTrueEntites.add(new TargetEntityNearMatch(entity));
      }
      ExpectedAnswer bestTrueAnswer = new ExpectedAnswerInjectiveMatch(bestTrueEntites);
      predIRScoreOnBest = (pred == null) ? null : bestTrueAnswer.getIRScore(pred.candidate);
      firstTrueIRScoreOnBest = (firstTrue == null) ? null : bestTrueAnswer.getIRScore(firstTrue.candidate);
    }
  }
  
  /** Log TRUE : the first likely correct candidate */
  public void logTrue() {
    LogInfo.begin_track("TRUE (likely correct candidate):");
    if (firstTrue == null) {
      LogInfo.logs("<%s SUPER FAIL> Correct candidate not found!", evaluator.testSuiteName);
    } else {
      LogInfo.logs("<%s %s> Rank %d [Unique Rank %d]: (Total Feature Score = %s)", evaluator.testSuiteName,
          firstTrue.rank == 1 ? "SUCCESS" : "FAIL", firstTrue.rank,
          firstTrue.uniqueRank, firstTrue.score);
      logCandidate(firstTrue);
    }
    LogInfo.end_track();
  }
  
  /** Log PRED : the top scoring candidate */
  public void logPred() {
    if (pred != null) {
      LogInfo.begin_track("PRED (top scoring candidate):");
      LogInfo.logs("Rank 1 [Unique Rank 1]: (Total Feature Score = %s)", pred.score);
      logCandidate(pred);
      LogInfo.end_track();
    }
  }
  
  private void logCandidate(CandidateStatistics candidateStat) {
    Candidate candidate = candidateStat.candidate;
    LogInfo.logs("%s %s", candidate.pattern, candidate.ex.expectedAnswer.getIRScore(candidate));
    if (OpenSemanticParser.opts.logVerbosity >= 2)
      LogInfo.log(candidate.sampleEntities());
    if (OpenSemanticParser.opts.logVerbosity >= 3)
      evaluator.learner.logFeatureWeights(candidate);
  }
  
  public abstract void logFeatureDiff();
} public class EvaluationSuccess extends EvaluationCase {

  public EvaluationSuccess(Evaluator evaluator, Example ex, CandidateStatistics pred,
      CandidateStatistics firstTrue, CandidateStatistics best) {
    super(evaluator, ex, pred, firstTrue, best);
  }

  @Override
  public void logFeatureDiff() {
    // Do nothing
  }
} public class Evaluator {
  String testSuiteName;
  Learner learner;
  int numExamples = 0, numSuccess = 0, numNormalFail = 0, numSuperFail = 0, numFound = 0;
  List<EvaluationCase> successes, normalFails, superFails;
  double sumF1onExpectedEntities = 0, sumF1onBest = 0;
  Multiset<Integer> firstTrueUniqueRanks;
  
  public Evaluator(String testSuiteName, Learner learner) {
    this.testSuiteName = testSuiteName;
    this.learner = learner;
    successes = new ArrayList<>();
    normalFails = new ArrayList<>();
    superFails = new ArrayList<>();
    firstTrueUniqueRanks = new Multiset<>();
  }
  
  public EvaluationCase add(Example ex, CandidateStatistics pred, CandidateStatistics firstTrue, CandidateStatistics best) {
    numExamples++;
    EvaluationCase evaluationCase;
    if (firstTrue == null) {
      evaluationCase = new EvaluationSuperFail(this, ex, pred, firstTrue, best);
      superFails.add(evaluationCase);
      numSuperFail++;
      firstTrueUniqueRanks.add(Integer.MAX_VALUE);
    } else if (firstTrue.rank != 1) {
      evaluationCase = new EvaluationNormalFail(this, ex, pred, firstTrue, best);
      normalFails.add(evaluationCase);
      numNormalFail++;
      numFound++;
      firstTrueUniqueRanks.add(firstTrue.uniqueRank);
    } else {
      evaluationCase = new EvaluationSuccess(this, ex, pred, firstTrue, best);
      successes.add(evaluationCase);
      numSuccess++;
      numFound++;
      firstTrueUniqueRanks.add(firstTrue.uniqueRank);
    }
    if (evaluationCase.predIRScore != null)
      sumF1onExpectedEntities += evaluationCase.predIRScore.f1;
    if (evaluationCase.predIRScoreOnBest != null)
      sumF1onBest += evaluationCase.predIRScoreOnBest.f1;
    return evaluationCase;
  }
  
  public double[] getAccuracyAtK(int maxK) {
    double[] accuracyAtK = new double[maxK + 1];
    accuracyAtK[0] = 0.0;     // Accuracy at 0 is always 0 (used for padding)
    int sumCorrect = 0;
    for (int k = 1; k <= maxK; k++) {
      sumCorrect += firstTrueUniqueRanks.count(k);
      accuracyAtK[k] = sumCorrect * 1.0 / numExamples;
    }
    return accuracyAtK;
  }
  
  public void printDetails() {
    LogInfo.begin_track("### %s: %d Normal FAILS (correct candidate in other rank) ###", testSuiteName, numNormalFail);
    for (EvaluationCase fail : normalFails) fail.logFeatureDiff();
    LogInfo.end_track();
    LogInfo.begin_track("### %s: %d Super FAILS (correct candidate not found) ###", testSuiteName, numSuperFail);
    for (EvaluationCase fail : superFails) fail.logFeatureDiff();
    LogInfo.end_track();
  }

  public Evaluator putOutput(String prefix) {
    Execution.putOutput(prefix + ".numExamples", numExamples);
    Execution.putOutput(prefix + ".accuracy", 1.0 * numSuccess / numExamples);
    Execution.putOutput(prefix + ".accuracyFound", 1.0 * numSuccess / numFound);
    Execution.putOutput(prefix + ".oracle", 1.0 * numFound / numExamples);
    Execution.putOutput(prefix + ".averageF1onTargetEntities", sumF1onExpectedEntities * 1.0 / numExamples);
    Execution.putOutput(prefix + ".averageF1onBestCandidate", sumF1onBest * 1.0 / numExamples);
    Execution.putOutput(prefix + ".accuracyAtK", Fmt.D(ListUtils.subArray(getAccuracyAtK(10), 1)));
    return this;
  }
  
  public Evaluator printScores() {
    LogInfo.begin_track("%s Evaluation", testSuiteName);
    LogInfo.logs("Number of examples: %d", numExamples);
    LogInfo.logs("Correct candidate in rank #1: %d", numSuccess);
    LogInfo.logs("Correct candidate in other rank: %d", numNormalFail);
    LogInfo.logs("Correct candidate not found: %d", numSuperFail);
    LogInfo.logs("Oracle: %.3f%% ( %d / %d )", numFound * 100.0 / numExamples, numFound, numExamples);
    LogInfo.logs("Accuracy (vs all): %.3f%% ( %d / %d )", numSuccess * 100.0 / numExamples, numSuccess, numExamples);
    LogInfo.logs("Accuracy (vs found): %.3f%% ( %d / %d )", numSuccess * 100.0 / numFound, numSuccess, numFound);
    LogInfo.logs("Average F1 (vs target entities): %.3f%%", sumF1onExpectedEntities * 100.0 / numExamples);
    LogInfo.logs("Average F1 (vs best candidate): %.3f%%", sumF1onBest * 100.0 / numExamples);
    LogInfo.logs("Accuracy @ k : %s", Fmt.D(ListUtils.mult(100.0, ListUtils.subArray(getAccuracyAtK(10), 1))));
    LogInfo.end_track();
    return this;
  }
  
  public Evaluator printScores(boolean beVeryQuiet) {
    return beVeryQuiet ? this : printScores();
  }
  
} public class IterativeTester {
  private final OpenSemanticParser openSemanticParser;
  private final Dataset dataset;
  public String message = "";
  List<EvaluatorStatistics> trainStats, testStats;
  
  public boolean beVeryQuiet = false;
  public static final int MAX_K = 10;
  
  public IterativeTester(OpenSemanticParser openSemanticParser, Dataset dataset) {
    this.openSemanticParser = openSemanticParser;
    this.dataset = dataset;
    this.trainStats = new ArrayList<>();
    this.testStats = new ArrayList<>();
  }
  
  public void run() {
    int oldLogVerbosity = OpenSemanticParser.opts.logVerbosity;
    OpenSemanticParser.opts.logVerbosity = 0;
    trainStats.add(new EvaluatorStatistics(
        openSemanticParser.test(dataset.trainExamples, "[" + message + "] ITERATIVE TEST on TRAINING SET")
        .printScores(beVeryQuiet).putOutput("train")));
    testStats.add(new EvaluatorStatistics(
        openSemanticParser.test(dataset.testExamples, "[" + message + "] ITERATIVE TEST on TEST SET")
        .printScores(beVeryQuiet).putOutput("test")));
    OpenSemanticParser.opts.logVerbosity = oldLogVerbosity;
  }
  
  public void summarize() {
    LogInfo.begin_track("@@@ SUMMARY @@@");
    LogInfo.logs("%7s | %7s %7s %7s | %7s %7s %7s", "iter",
        "tracc", "trora", "traf1", "tsacc", "tsora", "tsaf1");
    for (int i = 0; i < trainStats.size(); i++) {
      EvaluatorStatistics t = trainStats.get(i), s = testStats.get(i);
      double tF1, sF1;
      if ("wiki".equals(Main.opts.dataset.split("[.]")[0])) {
        tF1 = t.avgF1onExpectedEntities;
        sF1 = s.avgF1onExpectedEntities;
      } else {
        tF1 = t.avgF1onBest;
        sF1 = s.avgF1onBest;
      }
      LogInfo.logs("%7s | %7.2f %7.2f %7.2f | %7.2f %7.2f %7.2f", i+1,
          t.accuracyAll, t.oracle, tF1,
          s.accuracyAll, s.oracle, sF1);
    }
    LogInfo.end_track();
  }

  public EvaluatorStatistics getLastTrainStat() {
    return trainStats.get(trainStats.size() - 1);
  }
  
  public EvaluatorStatistics getLastTestStat() {
    return testStats.get(testStats.size() - 1);
  }
  
  
  
} public class Dataset {
  public final List<Example> trainExamples = new ArrayList<>();
  public final List<Example> testExamples = new ArrayList<>();
  
  public Dataset() {
    // Do nothing
  }
  
  public Dataset(List<Example> train, List<Example> test) {
    trainExamples.addAll(train);
    testExamples.addAll(test);
  }

  public Dataset addTrainExample(Example ex) {
    trainExamples.add(ex);
    return this;
  }
  
  public Dataset addTestExample(Example ex) {
    testExamples.add(ex);
    return this;
  }
  
  public Dataset addFromDataset(Dataset that) {
    this.trainExamples.addAll(that.trainExamples);
    this.testExamples.addAll(that.testExamples);
    return this;
  }
  
  public Dataset addTrainFromDataset(Dataset that) {
    this.trainExamples.addAll(that.trainExamples);
    this.trainExamples.addAll(that.testExamples);
    return this;
  }
  
  public Dataset addTestFromDataset(Dataset that) {
    this.testExamples.addAll(that.trainExamples);
    this.testExamples.addAll(that.testExamples);
    return this;
  }
  
  /**
   * @return a new Dataset with the Examples shuffled up.
   * The train/test ratio remain the same.
   * The original Dataset is not modified.
   */
  public Dataset getNewShuffledDataset() {
    List<Example> allExamples = new ArrayList<>(trainExamples);
    allExamples.addAll(testExamples);
    Collections.shuffle(allExamples, new Random(42));
    List<Example> newTrain = allExamples.subList(0, trainExamples.size());
    List<Example> newTest = allExamples.subList(trainExamples.size(), allExamples.size());
    return new Dataset(newTrain, newTest);
  }
  
  /**
   * @return a new Dataset with the specified train/test ratio.
   */
  public Dataset getNewSplitDataset(double trainRatio) {
    List<Example> allExamples = new ArrayList<>(trainExamples);
    allExamples.addAll(testExamples);
    Collections.shuffle(allExamples, new Random(42));
    int trainEndIndex = (int) (allExamples.size() * trainRatio);
    List<Example> newTrain = allExamples.subList(0, trainEndIndex);
    List<Example> newTest = allExamples.subList(trainEndIndex, allExamples.size());
    return new Dataset(newTrain, newTest);
  }
  
  // ============================================================
  // Caching rewards
  // ============================================================
  
  public void cacheRewards() {
    List<Example> uncached = new ArrayList<>();
    for (Example ex : trainExamples)
      if (!ex.expectedAnswer.frozenReward) uncached.add(ex);
    for (Example ex : testExamples)
      if (!ex.expectedAnswer.frozenReward) uncached.add(ex);
    if (uncached.isEmpty()) return;
    LogInfo.begin_track("Cache rewards ...");
    for (Example ex : uncached) {
      LogInfo.begin_track("Computing rewards for example %s ...", ex);
      for (Candidate candidate : ex.candidates) {
        ex.expectedAnswer.reward(candidate);
      }
      ex.expectedAnswer.frozenReward = true;
      LogInfo.end_track();
    }
    LogInfo.end_track();
  }
  
  // ============================================================
  // Shorthands for creating datasets.
  // ============================================================
  
  public Example E(String phrase, ExpectedAnswer expectedAnswer) {
    return E(phrase, expectedAnswer, true);
  }
  
  public Example E(String phrase, ExpectedAnswer expectedAnswer, boolean isTrain) {
    Example ex = new Example(phrase, expectedAnswer);
    if (isTrain)
      addTrainExample(ex);
    else
      addTestExample(ex);
    return ex;
  }
  
  public ExpectedAnswer L(String... items) {
    return L(false, items);
  }
  
  public ExpectedAnswer L(boolean exact, String... items) {
    return new ExpectedAnswerInjectiveMatch(items);
  }
  
  public ExpectedAnswer LN(String... items) {
    return LN(false, items);
  }
  
  public ExpectedAnswer LN(boolean exact, String... items) {
    TargetEntity[] targetEntities = new TargetEntity[items.length];
    for (int i = 0; i < items.length; i++) targetEntities[i] = N(items[i]);
    return new ExpectedAnswerInjectiveMatch(items);
  }
  
  public TargetEntityPersonName N(String full) {
    String[] parts = full.split(" ");
    if (parts.length == 2)
      return new TargetEntityPersonName(parts[0], parts[1]);
    else if (parts.length == 3)
      return new TargetEntityPersonName(parts[0], parts[1], parts[2]);
    throw new RuntimeException("N(...) requires two or three words.");
  }

} public class Example {
  public String displayId;  // For debugging
  
  public final String phrase;
  public final ExpectedAnswer expectedAnswer;
  public KNode tree;  // Deterministic function of the phrase
  public List<CandidateGroup> candidateGroups;
  public List<Candidate> candidates;  // Candidate predictions
  public AveragedWordVector averagedWordVector;

  public Example(String phrase) {
    this(phrase, null);
  }
  
  public Example(String phrase, ExpectedAnswer expectedAnswer) {
    this.phrase = phrase;
    this.expectedAnswer = expectedAnswer;
  }
  
  @Override public String toString() {
    return "[" + phrase + "]";
  }
  
  public void initAveragedWordVector() {
    if (averagedWordVector == null)
      averagedWordVector = new AveragedWordVector(phrase);
  }
} public class ExampleCached extends Example {
  public final String hashcode, cacheDirectory, url;
  
  public ExampleCached(String phrase, String url) {
    this(phrase, null, null, url, null);
  }
  
  public ExampleCached(String phrase, String cacheDirectory, String hashcode, String url) {
    this(phrase, cacheDirectory, hashcode, url, null);
  }
  
  public ExampleCached(String phrase, String cacheDirectory, String hashcode, String url, ExpectedAnswer expectedAnswer) {
    super(phrase, expectedAnswer);
    this.url = url;
    this.hashcode = hashcode;
    this.cacheDirectory = cacheDirectory;
  }
  
  @Override public String toString() {
    StringBuilder sb = new StringBuilder("[").append(phrase).append("]")
        .append("[").append(cacheDirectory).append("/").append(hashcode).append("]");
    if (url != null)
      sb.append("[").append(url).append("]");
    return sb.toString();
  }
} public interface TargetEntity {
  public boolean match(String predictedEntity);
  public boolean matchAny(Collection<String> predictedEntities);
} @JsonIgnoreProperties(ignoreUnknown=true)
@JsonInclude(JsonInclude.Include.NON_NULL)
public class LingData {
  public static class Options {
    @Option(gloss = "What CoreNLP annotators to run")
    public List<String> annotators = Arrays.asList("tokenize", "ssplit", "pos", "lemma", "ner");

    @Option(gloss = "Whether to use CoreNLP annotators")
    public boolean useAnnotators = true;

    @Option(gloss = "Whether to be case sensitive")
    public boolean caseSensitive = true;
    
    @Option(gloss = "Linguistic cache filename")
    public String lingCacheFilename = null;
    
    @Option(gloss = "Frequency of saving linguistic cache periodically")
    public int saveLingCacheFrequency = 50000;
  }
  public static Options opts = new Options();
  public static StanfordCoreNLP pipeline = null;
  
  // Update this when changing LingData's structure.
  private static final String VERSION = "4";
  
  private static final Set<String> AUX_VERBS = new HashSet<>(Arrays.asList(
      "is", "are", "was", "were", "am", "be", "been", "will",
      "shall", "have", "has", "had", "would", "could", "should", 
      "do", "does", "did", "can", "may", "might", "must", "seem"));
  
  public static final Set<String> OPEN_CLASS_POS_TAGS = new HashSet<>(Arrays.asList(
      "CD", "FW", "JJ", "JJR", "JJS", "NN", "NNP", "NNPS", "NNS", "RB",
      "RBR", "RBS", "VB", "VBD", "VBG", "VBN", "VBP", "VBZ"));
  
  /**
   * OPEN = nouns, general verbs, adjectives, adverbs, numbers
   * AUX = auxiliary verbs (which is a special case of CLOSE)
   * CLOSE = other POS
   */
  public enum POSType { OPEN, AUX, CLOSE };

  // Tokenization of input.
  @JsonProperty
  public final List<String> tokens;
  @JsonProperty
  public final List<String> lemmaTokens;  // Lemmatized version

  // Syntactic information from JavaNLP.
  @JsonProperty
  public final List<String> posTags;  // POS tags
  @JsonProperty
  public final List<POSType> posTypes;  // type of POS tag
  @JsonProperty
  public final List<String> nerTags;  // NER tags
  @JsonProperty
  public final List<String> nerValues;  // NER values (contains times, dates, etc.)
  @JsonIgnore
  public final int length;

  public LingData(String utterance) {
    // Stanford tokenizer doesn't break hyphens.
    // Replace hyphens with spaces for utterances like
    // "Spanish-speaking countries" but not for "2012-03-28".
    StringBuilder buf = new StringBuilder(utterance);
    for (int i = 0; i < buf.length(); i++) {
      if (buf.charAt(i) == '-' && (i+1 < buf.length() && Character.isLetter(buf.charAt(i+1))))
        buf.setCharAt(i, ' ');
    }
    utterance = buf.toString();
    
    tokens = new ArrayList<>();
    posTags = new ArrayList<>();
    posTypes = new ArrayList<>();
    nerTags = new ArrayList<>();
    nerValues = new ArrayList<>();
    lemmaTokens = new ArrayList<>();

    if (opts.useAnnotators) {
      initModels();
      Annotation annotation = pipeline.process(utterance);

      for (CoreLabel token : annotation.get(CoreAnnotations.TokensAnnotation.class)) {
        String word = token.get(TextAnnotation.class);
        String wordLower = word.toLowerCase();
        if (opts.caseSensitive) {
          tokens.add(word);
        } else {
          tokens.add(wordLower);
        }
        String pos = token.get(PartOfSpeechAnnotation.class).intern();
        posTags.add(pos);
        posTypes.add(getPOSType(pos, word));
        
        nerTags.add(token.get(NamedEntityTagAnnotation.class).intern());
        lemmaTokens.add(token.get(LemmaAnnotation.class));
        nerValues.add(token.get(NormalizedNamedEntityTagAnnotation.class));
      }
      
    } else {
      // Create tokens crudely
      for (String token : utterance.trim().split("\\s+")) {
        tokens.add(token);
        lemmaTokens.add(token);
        try {
          Double.parseDouble(token);
          posTags.add("CD");
          posTypes.add(POSType.OPEN);
          nerTags.add("NUMBER");
          nerValues.add(token);
        } catch (NumberFormatException e ){
          posTags.add("UNK");
          posTypes.add(POSType.OPEN);
          nerTags.add("UNK");
          nerValues.add("UNK");
        }
      }
    }
    
    this.length = tokens.size();
  }
  
  private static POSType getPOSType(String pos, String word) {
    if (AUX_VERBS.contains(word.toLowerCase()) && pos.charAt(0) == 'V')
      return POSType.AUX;
    if (OPEN_CLASS_POS_TAGS.contains(pos))
      return POSType.OPEN;
    return POSType.CLOSE;
  }

  @JsonCreator
  public LingData(@JsonProperty("tokens") List<String> tokens,
                  @JsonProperty("lemmaTokens") List<String> lemmaTokens,
                  @JsonProperty("posTags") List<String> posTags,
                  @JsonProperty("posTypes") List<POSType> posTypes,
                  @JsonProperty("nerTags") List<String> nerTags,
                  @JsonProperty("nerValues") List<String> nerValues) {
    this.tokens = tokens;
    this.lemmaTokens = lemmaTokens;
    this.posTags = posTags;
    this.posTypes = posTypes;
    this.nerTags = nerTags;
    this.nerValues = nerValues;
    this.length = tokens.size();
  }
  
  public static void initModels() {
    initCoreNLPModels();
    BrownClusterTable.initModels();
    WordVectorTable.initModels();
    FrequencyTable.initModels();
    WordNetClusterTable.initModels();
    QueryTypeTable.initModels();
  }

  public static void initCoreNLPModels() {
    if (pipeline != null) return;
    LogInfo.begin_track("Initializing Core NLP Models ...");
    Properties props = new Properties();
    props.put("annotators", String.join(",", opts.annotators));
    if (opts.caseSensitive) {
      props.put("pos.model", "edu/stanford/nlp/models/pos-tagger/english-bidirectional/english-bidirectional-distsim.tagger");
      props.put("ner.model", "edu/stanford/nlp/models/ner/english.all.3class.distsim.crf.ser.gz,edu/stanford/nlp/models/ner/english.conll.4class.distsim.crf.ser.gz");
    } else {
      props.put("pos.model", "edu/stanford/nlp/models/pos-tagger/english-caseless-left3words-distsim.tagger");
      props.put("ner.model", "edu/stanford/nlp/models/ner/english.all.3class.caseless.distsim.crf.ser.gz,edu/stanford/nlp/models/ner/english.conll.4class.caseless.distsim.crf.ser.gz");
    }
    pipeline = new StanfordCoreNLP(props);
    LogInfo.end_track();
  }

  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;

    LingData that = (LingData) o;
    if (!lemmaTokens.equals(that.lemmaTokens)) return false;
    if (!nerTags.equals(that.nerTags)) return false;
    if (!posTags.equals(that.posTags)) return false;
    if (!tokens.equals(that.tokens)) return false;
    return true;
  }

  // Return a string representing the tokens between start and end.
  public String phrase(int start, int end) {
    return sliceSequence(tokens, start, end);
  }
  public String lemmaPhrase(int start, int end) {
    return sliceSequence(lemmaTokens, start, end);
  }

  private static String sliceSequence(List<String> items, int start, int end) {
    if (start >= end) throw new RuntimeException("Bad indices");
    if (end - start == 1) return items.get(start);
    StringBuilder out = new StringBuilder();
    for (int i = start; i < end; i++) {
      if (out.length() > 0) out.append(' ');
      out.append(items.get(i));
    }
    return out.toString();
  }

  // If all the tokens in [start, end) have the same nerValues, but not
  // start-1 and end+1 (in other words, [start, end) is maximal), then return
  // the normalizedTag.  Example: queryNerTag = "DATE".
  public String getNormalizedNerSpan(String queryTag, int start, int end) {
    String value = nerValues.get(start);
    if (!queryTag.equals(nerTags.get(start))) return null;
    if (start-1 >= 0 && value.equals(nerValues.get(start-1))) return null;
    if (end < nerValues.size() && value.equals(nerValues.get(end))) return null;
    for (int i = start+1; i < end; i++)
      if (!value.equals(nerValues.get(i))) return null;
    return value;
  }

  public String getCanonicalPos(int index) {
    return getCanonicalPos(posTags.get(index));
  }

  private String getCanonicalPos(String pos) {
    if (pos.startsWith("N")) return "N";
    if (pos.startsWith("V")) return "V";
    if (pos.startsWith("W")) return "W";
    return pos;
  }
  
  // ============================================================
  // Caching
  // ============================================================
  
  protected static Map<String, LingData> cache = new ConcurrentHashMap<>();
  
  public static LingData get(String string) {
    LingData data = cache.get(string);
    if (data == null) {
      data = new LingData(string);
      cache.put(string, data);
      if (opts.saveLingCacheFrequency > 0 && cache.size() % opts.saveLingCacheFrequency == 0) {
        LogInfo.logs("Linguistic Cache size: %d", cache.size());
        saveCache();
      }
    }
    return data;
  }

  public static LingData getNoCache(String string) {
    LingData data = cache.get(string);
    if (data == null) {
      data = new LingData(string);
    }
    return data;
  }
  
  private static String getCachePath(String version) {
    String path = opts.lingCacheFilename;
    if (path == null) {
      path = "cache/ling-" + Main.opts.dataset + ".v" + version + ".json.gz";
    }
    new File(path).getParentFile().mkdirs();
    return path;
  }
  
  private static int lastSavedCacheSize = 0; 
  
  public synchronized static void saveCache() {
    LogInfo.begin_track("Saving linguistic data to cache ...");
    if (cache.size() == lastSavedCacheSize) {
      LogInfo.log("Cache unchanged.");    // Do nothing
    } else {
      String cachePath = getCachePath(VERSION);
      try (FileOutputStream out = new FileOutputStream(cachePath);
          GZIPOutputStream so = new GZIPOutputStream(out)) {
        out.getChannel().lock();
        ObjectMapper mapper = new ObjectMapper();
        lastSavedCacheSize = cache.size();
        mapper.writeValue(so, cache);
        LogInfo.logs("Written cache to %s", cachePath);
      } catch (Exception e) {
        LogInfo.warnings("Cache cannot be saved to %s!", cachePath);
        LogInfo.warning(e);
        e.printStackTrace();
      }
    }
    LogInfo.end_track();
  }

  public static void loadCache() {
    LogInfo.begin_track("Loading linguistic data from cache ...");
    String cachePath = getCachePath(VERSION);
    try (GZIPInputStream si = new GZIPInputStream(new FileInputStream(cachePath))) {
      ObjectMapper mapper = new ObjectMapper();
      cache = mapper.readValue(si, new TypeReference<ConcurrentHashMap<String, LingData>>(){});
      lastSavedCacheSize = cache.size();
      LogInfo.logs("Cache loaded from %s", cachePath);
    } catch (FileNotFoundException e) {
      LogInfo.warnings("Cache cannot be loaded: File %s does not exist", cachePath);
    } catch (Exception e) {
      LogInfo.warnings("Cache cannot be loaded: Cache corruped!");
      LogInfo.warning(e);
    }
    LogInfo.end_track();
  }

  // ============================================================
  // Getters
  // ============================================================
  
  /**
   * @param lemmatized
   *     whether to use lemmatized tokens
   * @param onlyOpenPOS
   *     whether to return only tokens with open-class POS tags (noun, verb, adjective, adverb)
   * @return A set of tokens
   */
  public Set<String> getTokens(boolean lemmatized, boolean onlyOpenPOS) {
    Set<String> answer = new HashSet<>();
    for (int i = 0; i < length; i++) {
      if (!onlyOpenPOS || posTypes.get(i) == POSType.OPEN) {
        if (lemmatized) {
          answer.add(lemmaTokens.get(i));
        } else {
          answer.add(tokens.get(i));
        }
      }
    }
    return answer;
  }
} public interface Learner {
  
  // ============================================================
  // Log
  // ============================================================

  public void logParam();
  public void logFeatureWeights(Candidate candidate);
  public void logFeatureDiff(Candidate trueCandidate, Candidate predCandidate);
  public void shutUp();
  
  // ============================================================
  // Predict
  // ============================================================
  
  public List<Pair<Candidate, Double>> getRankedCandidates(Example example);
  
  // ============================================================
  // Learn
  // ============================================================
  
  public void learn(Dataset dataset, FeatureMatcher additionalFeatureMatcher);
  public void setIterativeTester(IterativeTester tester);
  
  // ============================================================
  // Persistence
  // ============================================================
  
  public void saveModel(String path);
  public void loadModel(String path);
  
} public class LearnerBaseline implements Learner {
  public static class Options {
    @Option public int baselineSuffixLength = 5;
    @Option public int baselineMaxNumPatterns = 10000;
    @Option public boolean baselineUseMaxSize = false;    // false = use most frequent
    @Option public IndexType baselineIndexType = IndexType.STAR;
    @Option public boolean baselineBagOfTags = true;
  }
  public static Options opts = new Options();
  
  public enum IndexType {NONE, STAR, FULL};
  
  protected IterativeTester iterativeTester;
  public boolean beVeryQuiet = false;
  
  /*
   * IDEA:
   * - Look at the training data and record the most frequent tree pattern (suffix)
   * - For a test example, find a suffix that matches -- maybe choose the longest one 
   */
  
  // Map from suffix to count
  Map<List<String>, Integer> goodPathCounts;
  
  // ============================================================
  // Log
  // ============================================================
  
  @Override
  public void logParam() {
    LogInfo.begin_track("Params");
    if (goodPathCounts == null) {
      LogInfo.log("No parameters.");
    } else {
      List<Map.Entry<List<String>, Integer>> entries = new ArrayList<>(goodPathCounts.entrySet());
      Collections.sort(entries, new ValueComparator<List<String>, Integer>(true));
      for (Map.Entry<List<String>, Integer> entry : entries) {
        LogInfo.logs("%8d : %s", entry.getValue(), entry.getKey());
      }
    }
    LogInfo.end_track();
  }

  @Override
  public void logFeatureWeights(Candidate candidate) {
    LogInfo.log("Using BASELINE Learner - no features");
  }
  
  @Override
  public void logFeatureDiff(Candidate trueCandidate, Candidate predCandidate) {
    LogInfo.log("Using BASELINE Learner - no features");
  }
  

  @Override
  public void shutUp() {
    beVeryQuiet = true;
  }
  
  // ============================================================
  // Predict
  // ============================================================
  
  @Override
  public List<Pair<Candidate, Double>> getRankedCandidates(Example example) {
    List<Pair<Candidate, Double>> answer = new ArrayList<>();
    for (Candidate candidate : example.candidates) {
      double score = getScore(candidate);
      answer.add(new Pair<Candidate, Double>(candidate, score));
    }
    Collections.sort(answer, new Pair.ReverseSecondComparator<Candidate, Double>());
    return answer;
  }
  
  
  protected double getScore(Candidate candidate) {
    List<String> suffix = getPathSuffix(candidate);
    Integer frequency = goodPathCounts.get(suffix);
    if (frequency == null) return 0;
    return opts.baselineUseMaxSize ? candidate.predictedEntities.size() : frequency;
  }
  
  // ============================================================
  // Learn
  // ============================================================
  
  @Override
  public void setIterativeTester(IterativeTester tester) {
    this.iterativeTester = tester;
  }
  
  @Override
  public void learn(Dataset dataset, FeatureMatcher additionalFeatureMatcher) {
    Map<List<String>, Integer> pathCounts = new HashMap<>();
    dataset.cacheRewards();
    // Learn good tree patterns (path suffix)
    if (!beVeryQuiet) LogInfo.begin_track("Learning tree patterns ...");
    for (Example ex : dataset.trainExamples) {
      for (Candidate candidate : ex.candidates) {
        if (candidate.getReward() > 0) {
          // Good candidate -- remember the tree pattern
          MapUtils.incr(pathCounts, getPathSuffix(candidate));
        }
      }
    }
    // Sort by count
    List<Map.Entry<List<String>, Integer>> entries = new ArrayList<>(pathCounts.entrySet());
    Collections.sort(entries, new ValueComparator<List<String>, Integer>(true));
    // Retain the top n paths
    int n = Math.min(opts.baselineMaxNumPatterns, entries.size());
    goodPathCounts = new HashMap<>();
    for (Map.Entry<List<String>, Integer> entry : entries.subList(0, n)) {
      goodPathCounts.put(entry.getKey(), entry.getValue());
    }
    if (!beVeryQuiet) LogInfo.logs("Found %d path patterns.", goodPathCounts.size());
    if (!beVeryQuiet) LogInfo.end_track();
    iterativeTester.run();
  }
  
  private List<String> getPathSuffix(Candidate candidate) {
    return getPathSuffix(candidate.pattern.getPath());
  }
  
  private List<String> getPathSuffix(List<PathEntry> path) {
    List<String> suffix = new ArrayList<>();
    int startIndex = Math.max(0, path.size() - opts.baselineSuffixLength);
    for (PathEntry entry : path.subList(startIndex, path.size())) {
      String strEntry = "";
      switch (opts.baselineIndexType) {
      case NONE: strEntry = entry.tag; break;
      case STAR: strEntry = entry.tag + (entry.isIndexed() ? "[*]" : ""); break;
      case FULL: strEntry = entry.toString(); break;
      }
      suffix.add(strEntry.intern());
    }
    if (opts.baselineBagOfTags)
      Collections.sort(suffix);
    return suffix;
  }
  
  // ============================================================
  // Persistence
  // ============================================================

  @Override
  public void saveModel(String path) {
    LogInfo.fail("Not implemented");
  }

  @Override
  public void loadModel(String path) {
    LogInfo.fail("Not implemented");
  }
  
} public class LearnerMaxEnt implements Learner {
  public static class Options {
    @Option(gloss = "Number of iterations to train")
    public int numTrainIters = 3;
    @Option(gloss = "L2 Regularization")
    public double beta = 0.01;
    @Option(gloss = "L1 Regularization")
    public double lambda = 0;
    @Option(gloss = "Only retain features with parameter weight of at least this magnitude")
    public double pruneSmallFeaturesThreshold = 0;
    @Option(gloss = "Keep features that occur at least this many times")
    public int featureMinimumCount = 0;
    @Option
    public boolean getOnly1CandidatePerGroup = false;
  }
  public static Options opts = new Options();

  protected Params params; // Parameters of the model
  protected AdvancedWordVectorParams advancedWordVectorParams;
  protected IterativeTester iterativeTester;
  
  public boolean beVeryQuiet = false;
  
  // ============================================================
  // Log
  // ============================================================
  
  @Override
  public void logParam() {
    params.log();
    if (advancedWordVectorParams != null) {
      advancedWordVectorParams.log();
    }
  }
  
  @Override
  public void logFeatureWeights(Candidate candidate) {
    LogInfo.begin_track("Features: [sum = %s]", Fmt.D(getScore(candidate)));
    FeatureVector.logFeatureWeights("normal", candidate.getCombinedFeatures(), params);
    if (advancedWordVectorParams != null) {
      advancedWordVectorParams.logFeatureWeights(candidate);
    }
    LogInfo.end_track();
  }

  @Override
  public void logFeatureDiff(Candidate trueCandidate, Candidate predCandidate) {
    double trueScore = getScore(trueCandidate), predScore = getScore(predCandidate);
    LogInfo.begin_track("(TRUE - PRED) Features: [sum = %s = %s - %s]",
        Fmt.D(trueScore - predScore), Fmt.D(trueScore), Fmt.D(predScore));
    FeatureVector.logFeatureDiff("normal", trueCandidate.getCombinedFeatures(),
        predCandidate.getCombinedFeatures(), params);
    if (advancedWordVectorParams != null) {
      advancedWordVectorParams.logFeatureDiff(trueCandidate, predCandidate);
    }
    LogInfo.end_track();
  }
  
  @Override
  public void shutUp() {
    beVeryQuiet = true;
  } 
  
  // ============================================================
  // Predict
  // ============================================================
  
  /**
   * Return a list of (candidate, score) pairs sorted by score.
   */
  @Override
  public List<Pair<Candidate, Double>> getRankedCandidates(Example example) {
    List<Pair<Candidate, Double>> answer = new ArrayList<>();
    for (Candidate candidate : getCandidates(example)) {
      answer.add(new Pair<Candidate, Double>(candidate, getScore(candidate)));
    }
    Collections.sort(answer, new Pair.ReverseSecondComparator<Candidate, Double>());
    return answer;
  }
  
  protected double getScore(Candidate candidate) {
    return getScore(candidate, AllFeatureMatcher.matcher);
  }
  
  protected double getScore(Candidate candidate, FeatureMatcher matcher) {
    double score = candidate.features.dotProduct(params, matcher);
    score += candidate.group.features.dotProduct(params, matcher);
    if (advancedWordVectorParams != null) {
      score += advancedWordVectorParams.getScore(candidate);
    }
    return score;
  }
  
  // ============================================================
  // Learn
  // ============================================================

  @Override
  public void setIterativeTester(IterativeTester tester) {
    iterativeTester = tester;
  }
  
  @Override
  public void learn(Dataset dataset, FeatureMatcher additionalFeatureMatcher) {
    dataset.cacheRewards();
    // Select features based on count
    FeatureMatcher featureMatcher;
    if (opts.featureMinimumCount > 0) {
      FeatureCountPruner pruner = new FeatureCountPruner(beVeryQuiet);
      LogInfo.begin_track("Removing features with count < %d ...", opts.featureMinimumCount);
      for (Example example : dataset.trainExamples)
        pruner.add(example);
      pruner.applyThreshold(opts.featureMinimumCount);
      LogInfo.end_track();
      featureMatcher = pruner;
    } else {
      featureMatcher = AllFeatureMatcher.matcher;
    }
    // Additional feature filter (for ablation)
    if (additionalFeatureMatcher != null)
      featureMatcher = additionalFeatureMatcher;
    // Learn parameters
    stochasticGradientDescent(dataset.trainExamples, featureMatcher);
    // Prune features will small weights
    params.prune(opts.pruneSmallFeaturesThreshold);
    if (!beVeryQuiet)
      params.write(Execution.getFile("params"));
  }
  
  protected int trainIter;      // 1, 2, ..., opts.numTrainIters

  /**
   * Perform stochastic gradient descent to learn the parameters using the maximum entropy model.
   */
  protected void stochasticGradientDescent(Collection<Example> examples, FeatureMatcher featureMatcher) {
    params = new Params();
    advancedWordVectorParams = FeatureType.usingAdvancedWordVectorFeature() ? 
        AdvancedWordVectorParams.create() : null;
    
    for (trainIter = 1; trainIter <= opts.numTrainIters; trainIter++) {
      if (!beVeryQuiet) {
        LogInfo.begin_track("Iteration %d/%d", trainIter, opts.numTrainIters);
        Execution.putOutput("currIter", trainIter);
      }
      for (Example example : examples) {
        if (!beVeryQuiet) Execution.putOutput("currExample", example.displayId);
        boolean updated = gradientUpdate(getCandidates(example), featureMatcher);
        if (!updated) {
          if (!beVeryQuiet) LogInfo.logs("Skip %s ...", example);
        } else {
          if (!beVeryQuiet) LogInfo.logs("Computed gradient for example %s ...", example);
          performL1Regularization(opts.lambda / examples.size());
        }
      }
      if (iterativeTester != null) {
        iterativeTester.message = "Iteration " + trainIter + "/" + opts.numTrainIters;
        iterativeTester.run();
      }
      if (!beVeryQuiet)
        LogInfo.end_track();
    }
    
    // Summarize
    if (iterativeTester != null && !beVeryQuiet) {
      iterativeTester.summarize();
    }
  }
  
  protected List<Candidate> getCandidates(Example example) {
    if (!opts.getOnly1CandidatePerGroup) {
      return example.candidates;
    } else {
      List<Candidate> candidates = new ArrayList<>();
      for (CandidateGroup group : example.candidateGroups) {
        if (group.numCandidate() > 0) {
          candidates.add(group.getCandidates().get(0));
        }
      }
      return candidates;
    }
  }
  
  protected void performL1Regularization(double cutoff) {
    if (cutoff <= 0) return;
    params.applyL1Regularization(cutoff);
    if (advancedWordVectorParams != null)
      advancedWordVectorParams.applyL1Regularization(cutoff);
  }

  /**
   * Compute the gradient and update the parameters.
   * If there are no good candidates, do not update the parameters and return false.
   * Otherwise, return true.
   * 
   * If the score function is g(x,y,params), then the gradient is
   *    sum_y [ { gradient of g(x,y,params) } * expectationDiff(x,y,params) ]
   * where expectationDiff(x,y,params) is
   *    normalized (exp[g(x,y,params)]*R(y)) - normalized (exp[g(x,y,params)])
   */
  protected boolean gradientUpdate(List<Candidate> candidates, FeatureMatcher featureMatcher) {
    double[] expectationDiff = computeExpectationDiff(candidates, featureMatcher);
    if (expectationDiff == null) {
      // No good candidate -- skip example
      return false;
    }
    
    // Compute the gradient
    Map<String, Double> gradient = new HashMap<>();
    for (int i = 0; i < expectationDiff.length; i++) {
      Candidate candidate = candidates.get(i);
      candidate.group.features.increment(expectationDiff[i], gradient, featureMatcher);
      candidate.features.increment(expectationDiff[i], gradient, featureMatcher);
    }
    // Regularization
    if (opts.beta != 0) {
      for (String featureName : gradient.keySet()) {
        MapUtils.incr(gradient, featureName, (- opts.beta) * params.getWeight(featureName));
      }
    }
    // Perform gradient updates
    params.update(gradient);
    
    if (advancedWordVectorParams != null) {
      // Compute the gradient
      AdvancedWordVectorGradient advGradient = advancedWordVectorParams.createGradient();
      for (int i = 0; i < expectationDiff.length; i++) {
        Candidate candidate = candidates.get(i);
        advGradient.addToGradient(candidate, expectationDiff[i]);
      }
      // Regularization
      if (opts.beta != 0) {
        advGradient.addL2Regularization(opts.beta);
      }
      advancedWordVectorParams.update(advGradient);
    }
    
    return true;
  }
  
  /**
   * For each candidate i, compute
   *   expectationDiff[i] = normalized (exp[g(x,y[i],params)]*R(y)) - normalized (exp[g(x,y[i],params)])
   * 
   * Return null if any denominator for normalization is 0.
   */
  protected double[] computeExpectationDiff(List<Candidate> candidates, FeatureMatcher featureMatcher) {
    int n = candidates.size();
    double expScore[] = new double[n], expScoreTimesReward[] = new double[n];
    for (int i = 0; i < n; i++) {
      Candidate candidate = candidates.get(i);
      double prediction = getScore(candidate, featureMatcher);
      expScore[i] = prediction;
      expScoreTimesReward[i] = expScore[i] + Math.log(candidate.getReward());
    }

    // Exponentiate and normalize.
    // Skip this example if there are no good candidates.
    if (!NumUtils.expNormalize(expScore)) return null;
    if (!NumUtils.expNormalize(expScoreTimesReward)) return null;
    
    // Sum up the expectations
    double[] expectationDiff = new double[n];
    for (int i = 0; i < n; i++) {
      expectationDiff[i] = expScoreTimesReward[i] - expScore[i];
    }
    return expectationDiff;
  }
  
  // ============================================================
  // Persistence
  // ============================================================

  @Override
  public void saveModel(String path) {
    params.write(path);
  }

  @Override
  public void loadModel(String path) {
    params = new Params();
    params.read(path);
  }
} public class LearnerMaxEntWithBeamSearch extends LearnerMaxEnt {
  public static class Options {
    @Option public int beamSize = 500;
    @Option public int beamTrainStartIter = 1;
    @Option public String beamCandidateType = "cutrange";
  }
  public static Options opts = new Options();
  
  @Override
  protected List<Candidate> getCandidates(Example example) {
    if (trainIter <= opts.beamTrainStartIter) {
      return super.getCandidates(example);
    } else {
      return getBeamSearchedCandidates(example);
    }
  }
  
  protected List<Candidate> getBeamSearchedCandidates(Example example) {
    List<Pair<Candidate, Double>> rankedCandidates = super.getRankedCandidates(example);
    rankedCandidates = rankedCandidates.subList(0, Math.min(opts.beamSize, rankedCandidates.size()));
    List<Candidate> derivedCandidates = new ArrayList<>();
    for (Pair<Candidate, Double> entry : rankedCandidates) {
      derivedCandidates.addAll(getDerivedCandidates(entry.getFirst()));
    }
    return derivedCandidates;
  }
  
  protected List<Candidate> getDerivedCandidates(Candidate original) {
    switch (opts.beamCandidateType) {
    case "cutrange":
      LogInfo.fails("... not implemented yet ...");
      //return TreePatternAndRange.generateCutRangeCandidates(original);
      return null;
    case "endcut":
      LogInfo.fails("... not implemented yet ...");
      return null;
    default:
      LogInfo.fails("Unrecognized beam candidate type: %s", opts.beamCandidateType);
      return null;
    }
  }
  
  @Override
  public List<Pair<Candidate, Double>> getRankedCandidates(Example example) {
    List<Pair<Candidate, Double>> answer = new ArrayList<>();
    for (Candidate candidate : getBeamSearchedCandidates(example)) {
      double score = candidate.features.dotProduct(params);
      answer.add(new Pair<Candidate, Double>(candidate, score));
    }
    Collections.sort(answer, new Pair.ReverseSecondComparator<Candidate, Double>());
    return answer;
  }

} public class Candidate {
  public final Example ex;
  public final CandidateGroup group;
  public final TreePattern pattern;
  public final List<String> predictedEntities;
  public FeatureVector features;
  
  public Candidate(CandidateGroup group, TreePattern pattern) {
    this.pattern = pattern;
    this.group = group;
    group.candidates.add(this);
    // Perform shallow copy
    this.ex = group.ex;
    this.predictedEntities = group.predictedEntities;
  }
  
  public int numEntities() {
    return group.numEntities();
  }
  
  public double getReward() {
    return group.ex.expectedAnswer.reward(this);
  }
  
  public Map<String, Double> getCombinedFeatures() {
    Map<String, Double> map = new HashMap<>();
    features.increment(1, map);
    group.features.increment(1, map);
    return map;
  }
  
  // ============================================================
  // Debug Print
  // ============================================================
  
  public String sampleEntities() {
    return group.sampleEntities();
  }
  
  public String allEntities() {
    return group.allEntities();
  }
} public class CandidateGenerator {
  public static class Options {
    @Option(gloss = "Maximum number of XPath entries to toggle the indices")
    public int maxTweakDepth = 8;
    
    @Option(gloss = "Minimum number of selected entities to be considered a valid candidate")
    public int minNumCandidateEntity = 2;
    
    @Option(gloss = "Use the advanced tree traverser")
    public boolean useAdvancedTreeTraverser = false;
    
    @Option(gloss = "Maximum number of XPath entries that can be toggled to wildcard")
    public int allowWildcards = 0;
    
    @Option(gloss = "Maximum number of XPath entries that can be end-cut")
    public int allowEndCuts = 0;
    
    @Option(gloss = "Maximum depth of XPath entries that can be advancedly tweaked")
    public int maxAdvancedTweakDepth = 4;
  }
  public static Options opts = new Options();
  
  public final List<String> BLACKLISTED_TAGS = Arrays.asList(
    "html", "head", "body", "script", "noscript", "link", "style"
  );
  
  public void process(Example ex) {
    if (ex.candidates != null) {
      LogInfo.warnings("Example %s already has a candidate list", ex);
      return;
    }
    LogInfo.begin_track("Extracting candidates ...");
    ex.candidateGroups = new ArrayList<>();
    ex.candidates = new ArrayList<>();
    new CandidatePopulator(ex).populateCandidates();
    LogInfo.logs("Found %d candidates (%d groups)", ex.candidates.size(), ex.candidateGroups.size());
    LogInfo.end_track();
    LogInfo.begin_track("Extracting features ...");
    for (CandidateGroup group : ex.candidateGroups)
      FeatureExtractor.featureExtractor.extract(group);
    for (Candidate candidate : ex.candidates)
      FeatureExtractor.featureExtractor.extract(candidate);
    LogInfo.end_track();
  }
  
  // ============================================================
  // Find candidates
  // ============================================================
  
  class CandidatePopulator {
    Example ex;
    
    public CandidatePopulator(Example ex) {
      this.ex = ex;
    }

    void populateCandidates() {
      populateCandidates(ex.tree);
    }
    
    private void populateCandidates(KNode rootNode) {
      // Only start from the top <html> tags
      if (rootNode.type != KNode.Type.TAG || !rootNode.value.equals("html")) {
        for (KNode child : rootNode.getChildren()) {
          populateCandidates(child);
        }
        return;
      }
      // Traverse the knowledge tree and collect all possible paths
      TreeTraverser traverser = opts.useAdvancedTreeTraverser ? new AdvancedTreeTraverser(rootNode)
          : new BasicTreeTraverser(rootNode);
      Map<List<KNode>, CandidateGroup> nodesToCandidateGroup = new HashMap<>();
      for (List<PathEntry> path : traverser.getFoundPaths()) {
        // Execute the path and check if the path is valid.
        List<KNode> nodes = new ArrayList<>();
        PathUtils.executePath(path, rootNode, nodes);
        if (nodes.size() > opts.minNumCandidateEntity) {
          CandidateGroup group = nodesToCandidateGroup.get(nodes);
          if (group == null) {
            ex.candidateGroups.add(group = new CandidateGroup(ex, nodes));
            nodesToCandidateGroup.put(nodes, group);
          }
          ex.candidates.add(group.addCandidate(new TreePattern(rootNode, path, group.selectedNodes)));
        }
      }
    }
  }
  
  interface TreeTraverser {
    public Collection<List<PathEntry>> getFoundPaths();
  }

  class BasicTreeTraverser implements TreeTraverser {
    List<PathEntry> ancestors;
    Set<List<PathEntry>> foundPaths;
    
    public BasicTreeTraverser(KNode rootNode) {
      ancestors = new ArrayList<>();
      foundPaths = new HashSet<>();
      traverseTree(rootNode);
    }
    
    private void traverseTree(KNode currentNode) {
      if (currentNode.parent.countChildren(currentNode.value) > 1)
        ancestors.add(new PathEntry(currentNode.value, currentNode.getChildIndexOfSameTag()));
      else
        ancestors.add(new PathEntry(currentNode.value));
      // Process current node
      if (!isBlacklisted(currentNode))
        tweakPaths(1);
      // Traverse children
      for (KNode child : currentNode.getChildren()) {
        if (child.type == KNode.Type.TAG) traverseTree(child);
      }
      ancestors.remove(ancestors.size() - 1);
    }
    
    private boolean isBlacklisted(KNode node) {
      if (node.fullText == null || node.fullText.isEmpty()) return true;
      if (BLACKLISTED_TAGS.contains(node.value)) return true;
      return false;
    }
    
    /**
     * Toggle the indices of the xpath entries.
     * For example, /html/body/div[3]/a[1] will produce
     * - /html/body/div[3]/a[1]
     * - /html/body/div[3]/a
     * - /html/body/div/a[1]
     * - /html/body/div/a
     * 
     * Implemented using recursion on depth:
     * The toggled xpath entry is xpath[xpath.length - depth]
     * (depth = 1, 2, ..., opts.maxTweakDepth)
     * 
     * Exception: the first entry (html) will not be toggled.
     */
    private void tweakPaths(int depth) {
      if (depth > opts.maxTweakDepth || depth >= ancestors.size()) {
        foundPaths.add(new ArrayList<>(ancestors));
        return;
      }
      tweakPaths(depth + 1);
      PathEntry swap = ancestors.get(ancestors.size() - depth);
      if (swap.index != -1) {
        ancestors.set(ancestors.size() - depth, swap.getNoIndexVersion());
        tweakPaths(depth + 1);
        ancestors.set(ancestors.size() - depth, swap);
      }
    }
    
    @Override
    public Collection<List<PathEntry>> getFoundPaths() {
      return foundPaths;
    }
  }
  
  // ============================================================
  // Advanced Tree Traverser
  // ============================================================
  
  class PathEntryAugmented {
    public final String tag;
    public final int childIndex, childIndexOfTag;     // 0-indexed
    public final int numSiblings, numSiblingsOfTag;   // including self too
    
    public PathEntryAugmented(KNode node) {
      this.tag = node.value;
      int countChildIndex = -1, countChildIndexOfTag = -1, countNumSiblings = 0, countNumSiblingsOfTag = 0;
      for (KNode sibling : node.parent.getChildren()) {
        if (sibling == node) {
          countChildIndex = countNumSiblings;
          countChildIndexOfTag = countNumSiblingsOfTag;
        }
        if (sibling.type == KNode.Type.TAG) {
          countNumSiblings++;
          if (node.value.equals(sibling.value)) countNumSiblingsOfTag++;
        }
      }
      childIndex = countChildIndex;
      childIndexOfTag = countChildIndexOfTag;
      numSiblings = countNumSiblings;
      numSiblingsOfTag = countNumSiblingsOfTag;
      if (countChildIndex == -1 || countChildIndexOfTag == -1)
        LogInfo.fails("WTF? %s %s %s", node, tag, node.fullText);
    }
    
    @Override
    public String toString() {
      return String.format("%s[%d/%d]", tag, childIndexOfTag, numSiblingsOfTag);
    }
    
    @Override
    public boolean equals(Object obj) {
      if (obj == this)
        return true;
      if (obj == null || obj.getClass() != this.getClass())
        return false;
      PathEntryAugmented that = (PathEntryAugmented) obj;
      return (this.tag.equals(that.tag)
          && this.childIndex == that.childIndex
          && this.childIndexOfTag == that.childIndexOfTag
          && this.numSiblings == that.numSiblings
          && this.numSiblingsOfTag == that.numSiblingsOfTag);
    }
    
    @Override
    public int hashCode() {
      return tag.hashCode() | childIndex << 24 | childIndexOfTag << 16 | numSiblings << 8 | numSiblingsOfTag;
    }
  }
  
  class AdvancedTreeTraverser implements TreeTraverser {
    List<PathEntryAugmented> ancestors;
    Set<List<PathEntryAugmented>> foundRawPaths;
    List<PathEntryAugmented> currentRawPath;
    List<PathEntry> currentTweakedPath;
    Set<List<PathEntry>> foundTweakedPaths;
    
    public AdvancedTreeTraverser(KNode rootNode) {
      ancestors = new ArrayList<>();
      foundRawPaths = new HashSet<>();
      foundTweakedPaths = new HashSet<>();
      traverseTree(rootNode);
      LogInfo.logs("Found %d raw paths", foundRawPaths.size());
      for (List<PathEntryAugmented> rawPath : foundRawPaths) {
        //LogInfo.log(rawPath);
        currentRawPath = rawPath;
        createInitialTweakedPath();
        tweakPaths(1);
      }
      LogInfo.logs("Found %d tweaked paths", foundTweakedPaths.size());
    }
    
    private void traverseTree(KNode currentNode) {
      ancestors.add(new PathEntryAugmented(currentNode));
      // Process current node
      if (!isBlacklisted(currentNode))
        savePath();
      // Traverse children
      for (KNode child : currentNode.getChildren()) {
        if (child.type == KNode.Type.TAG) traverseTree(child);
      }
      ancestors.remove(ancestors.size() - 1);
    }
    
    private boolean isBlacklisted(KNode node) {
      if (node.fullText == null || node.fullText.isEmpty()) return true;
      if (BLACKLISTED_TAGS.contains(node.value)) return true;
      return false;
    }
    
    private void savePath() {
      foundRawPaths.add(new ArrayList<>(ancestors));
    }
    
    int numWildCards = 0;
    int numEndCuts = 0;
    
    private void createInitialTweakedPath() {
      currentTweakedPath = new ArrayList<>();
      for (PathEntryAugmented entry : currentRawPath) {
        if (entry.numSiblingsOfTag == 1) {
          currentTweakedPath.add(new PathEntry(entry.tag));
        } else {
          currentTweakedPath.add(new PathEntry(entry.tag, entry.childIndexOfTag));
        }
      }
      numWildCards = numEndCuts = 0;
    }
    
    
    /**
     * Tweak currentTweakedPath[n - depth]
     * (depth = 1, 2, ..., opts.maxTweakDepth)
     */
    private void tweakPaths(int depth) {
      int n = currentTweakedPath.size();
      if (depth > opts.maxTweakDepth || depth >= n) {
        foundTweakedPaths.add(new ArrayList<>(currentTweakedPath));
        return;
      }
      tweakPaths(depth + 1);
      PathEntry swap = currentTweakedPath.get(n - depth);
      if (swap.index != -1) {
        currentTweakedPath.set(n - depth, swap.getNoIndexVersion());
        tweakPaths(depth + 1);
        currentTweakedPath.set(n - depth, swap);
      }
      if (depth <= opts.maxAdvancedTweakDepth && numEndCuts < opts.allowEndCuts) {
        int numSiblings = swap.tag.equals("*") ? currentRawPath.get(n - depth).numSiblings : 
          currentRawPath.get(n - depth).numSiblingsOfTag;
        if (numSiblings > 1) {
          numEndCuts++;
          currentTweakedPath.set(n - depth, new PathEntryWithRange(swap.tag, 1, 0));
          tweakPaths(depth + 1);
          currentTweakedPath.set(n - depth, new PathEntryWithRange(swap.tag, 0, 1));
          tweakPaths(depth + 1);
          currentTweakedPath.set(n - depth, swap);
          numEndCuts--;
        }
      }
      if (depth <= opts.maxAdvancedTweakDepth && numWildCards < opts.allowWildcards && !swap.tag.equals("*")) {
        numWildCards++;
        if (currentRawPath.get(n - depth).numSiblings == 1) {
          currentTweakedPath.set(n - depth, new PathEntry("*"));
        } else {
          currentTweakedPath.set(n - depth, new PathEntry("*", currentRawPath.get(n - depth).childIndex));
        }
        tweakPaths(depth);
        currentTweakedPath.set(n - depth, swap);
        numWildCards--;
      }
    }
    
    @Override
    public Collection<List<PathEntry>> getFoundPaths() {
      //debugPrint();
      return foundTweakedPaths;
    }
    
    protected void debugPrint() {
      if (CandidateGenerator.iter == 0) {
        LogInfo.begin_track("Found paths");
        List<String> paths = new ArrayList<>();
        for (List<PathEntry> path : foundTweakedPaths) {
          paths.add(PathUtils.getXPathString(path));
        }
        Collections.sort(paths);
        for (String path : paths) {
          LogInfo.log(path);
        }
        LogInfo.end_track();
      }
      CandidateGenerator.iter++;
    }
    
  }

  private static int iter = 0;
} public abstract class FeaturePostProcessor {

  public abstract void process(Candidate candidate);
  public abstract void process(CandidateGroup group);
  
  public static void checkFeaturePostProcessorOptionsSanity() {
    if (FeaturePostProcessorConjoin.opts.useConjoin) {
      LogInfo.begin_track("Feature post-processor: Conjoin");
      FeaturePostProcessorConjoin.debugPrintOptions();
      LogInfo.end_track();
    }
  }
  
} public abstract class FeatureType {
  public static class Options {
    @Option(gloss = "Set of feature domains to exclude")
    public List<String> excludeFeatureDomains = new ArrayList<>();

    @Option(gloss = "Set of feature domains to include")
    public List<String> includeFeatureDomains = new ArrayList<>();
    
    @Option(gloss = "If true, look at excludeFeatureDomains, otherwise look at includeFeatureDomains")
    public boolean useAllFeatures = true;
    
    @Option(gloss = "Number of ancestors of the selected nodes to look at when firing features")
    public int maxAncestorCount = 5;
    
    @Option(gloss = "Number of bins for binning real-valued features")
    public int numBins = 10;
    
    @Option(gloss = "Use bins instead of percent features")
    public boolean useBinsForPercents = false;
    
    @Option(gloss = "Use two features to represent percentage")
    public boolean useQuadraticPercents = false;
    
    @Option(gloss = "Bin entropy features")
    public boolean binEntropyFeatures = false;
    
    @Option(gloss = "Add majoriy percentage feature")
    public boolean addMajorityPercentageFeature = true;
    
    @Option(gloss = "Add [diverse] feature if majority ratio < minMajorityRatio")
    public boolean addDiverseFeature = false;

    @Option(gloss = "Minimum majority ratio (max = 1.0) to use the majority feature")
    public double minMajorityRatio = 0.0;
    
    @Option(gloss = "Use all features instead of aggregation")
    public boolean noAggregation = false;
    
    @Option(gloss = "Bin the mean and deviation features")
    public boolean useDiscreteMeanAndDeviation = true;
  }
  public static Options opts = new Options();
  
  // ============================================================
  // Common methods
  // ============================================================
  
  public abstract void extract(Candidate candidate);
  public abstract void extract(CandidateGroup group);
  
  public static Set<String> registeredNonBasicDomains = new HashSet<>(Arrays.asList(
      // (Structural) Node-based
      "self-or-ancestors", "node-range",
      // (Structural) Path-based
      "path-tail",
      // (Denotation) Naive Entity-based
      "entity",
      // (Denotation) Linguistic Entity-based
      "ling", "cluster", "wordvec",
      // (Denotation) Freebase
      "fb",
      // (Denotation) Token frequency
      "token-freq",
      // (Denotation) Query x Entity
      "query-entity",
      // (Structural) Hole
      "hole",
      // (Denotation) Header and Proximity
      "header"
      ));
  
  public static void checkFeatureTypeOptionsSanity() {
    if (opts.useAllFeatures && !opts.includeFeatureDomains.isEmpty())
      LogInfo.fail("includeFeatureDomains should be empty if useAllFeatures is true.");
    if (opts.useAllFeatures && !opts.includeFeatureDomains.isEmpty())
      LogInfo.fail("excludeFeatureDomains should be empty if useAllFeatures is false.");
    for (String domain : opts.includeFeatureDomains)
      if (!registeredNonBasicDomains.contains(domain))
        LogInfo.fails("Domain \"%s\" in includeFeatureDomains does not exist", domain);
    for (String domain : opts.excludeFeatureDomains)
      if (!registeredNonBasicDomains.contains(domain))
        LogInfo.fails("Domain \"%s\" in excludeFeatureDomains does not exist", domain);
    LogInfo.begin_track("feature domains in use");
    for (String domain : registeredNonBasicDomains)
      if (isAllowedDomain(domain)) LogInfo.logs("DOMAIN ON : %s", domain);
    LogInfo.end_track();
    LogInfo.begin_track("feature domains NOT in use");
    for (String domain : registeredNonBasicDomains)
      if (!isAllowedDomain(domain)) LogInfo.logs("DOMAIN OFF: %s", domain);
    LogInfo.end_track();
  }
  
  public static boolean isAllowedDomain(String domain) {
    if (opts.useAllFeatures)
      return !opts.excludeFeatureDomains.contains(domain);
    else
      return opts.includeFeatureDomains.contains(domain);
  }
  
  public static boolean usingAdvancedWordVectorFeature() {
    return isAllowedDomain("wordvec");
  }
  
  // ============================================================
  // Helper Methods
  // ============================================================

  /**
   * Add features ">= 1", ">= 2", ">= 4", ">= 8", etc.
   */
  protected void addQuantizedFeatures(FeatureVector v, String domain, String name, double value) {
    value = Math.min(value, Integer.MAX_VALUE);
    for (int i = 1; i <= value; i *= 2)
      v.add(domain, name + " >= " + i);
  }

  /**
   * Add features ">= 0%", ">= 20%", ">= 40%", etc.
   */
  protected void addPercentFeatures(FeatureVector v, String domain, String name, double value) {
    if (opts.useBinsForPercents) {
      addBinFeatures(v, domain, name, value);
      return;
    } else if (opts.useQuadraticPercents) {
      if (value > 1) {
        LogInfo.logs("WTF? %s %s %f", domain, name, value);
        value = 1;
      }
      if (value < 0) {
        LogInfo.logs("WTF? %s %s %f", domain, name, value);
        value = 0;
      }
      v.add(domain, name, value);
      v.add(domain, name + "^2", value * value);
      return;
    }
    value = value * 100;
    if (value > 100) value = 100;
    for (int i = 0; i <= value; i += 20)
      v.add(domain, name + " >= " + i + "%");
  }
  
  /**
   * Add features "in [0/10,1/10]", "in [1/10,2/10]", ...
   * Values outside range [0,1] become 0 or 1.
   */
  private void addBinFeatures(FeatureVector v, String domain, String name, double value) {
    if (value < 0) value = 0;
    if (value >= 0.9999) value = 0.9999;
    int bin = ((int) (value * opts.numBins));
    v.add(domain, String.format("%s in [%d/%d,%d/%d]", name, bin, opts.numBins, bin + 1, opts.numBins)); 
  }
  
  /**
   * Add features "~ [word]" for all words in value.
   */
  protected void addBagOfWordFeatures(FeatureVector v, String domain, String name, String value) {
    for (String word : LingUtils.getBagOfWords(value)) {
      v.add(domain, name + " ~ " + word);
    }
  }
  
  /**
   * Add features "~ [word1]|[word2]" for all word1 in value1 and word2 in value2.
   */
  protected void addBagOfWordFeatures(FeatureVector v, String domain, String name, String value1, String value2) {
    Set<String> bag1 = LingUtils.getBagOfWords(value1),
                bag2 = LingUtils.getBagOfWords(value2);
    for (String word1 : bag1) {
      for (String word2 : bag2) {
        v.add(domain, name + " ~ " + word1 + "|" + word2);
      }
    }
  }

  /**
   * Add distinct values from the specified Multiset. (Basically, add all keys of the Multiset)
   * 
   * @param bagOfWords    whether to add features for each word of the distinct values
   */
  protected <T> void addDistinctElementFeatures(FeatureVector v, String domain, String name, Multiset<T> multiset,
      boolean bagOfWords) {
    for (T element : multiset.elementSet()) {
      if (bagOfWords) {
        addBagOfWordFeatures(v, domain, name, (String) element);
      } else {
        v.add(domain, name + " = " + element);
      }
    }
  }
  
  // ============================================================
  // KNode-based features
  // ============================================================
  
  /**
   * Add features of the form
   *   [...]-tag = ___
   *   [...]-id = ___
   *   [...]-class = ___ (each class = 1 feature)
   * based on the given KNode
   * 
   * @param bagOfWords    whether to add features for each word in the id and class
   */
  protected void addTagIdClassFeatures(FeatureVector v, String domain, String name, KNode node, boolean bagOfWords) {
    if (node.type != KNode.Type.TAG) return;
    // [...]-tag
    v.add(domain, name + "-tag = " + node.value);
    // [...]-id
    String id = node.getAttribute("id");
    if (!id.isEmpty()) {
      if (bagOfWords)
        addBagOfWordFeatures(v, domain, name + "-id", node.getAttribute("id"));
      else
        v.add(domain, name + "-id = " + id.replaceAll("[0-9]+", "0"));
    }
    // [...]-class
    String classes = node.getAttribute("class");
    if (!classes.isEmpty()) {
      if (bagOfWords)
        addBagOfWordFeatures(v, domain, name + "-class", node.getAttribute("class"));
      else
        for (String className : classes.split("\\s+"))
          v.add(domain, name + "-class = " + className.replaceAll("[0-9]+", "0"));
    }
  }
  
  // ============================================================
  // Discrete Statistics
  // ============================================================

  /**
   * Return true if the Multiset has any repeated entry
   */
  protected boolean hasDuplicateEntry(Multiset<?> multiset) {
    return multiset.entrySet().size() != multiset.size();
  }
  
  /**
   * Return the maximum amount of duplication
   */
  protected <T> int maxDuplication(Multiset<T> multiset) {
    int max = 0;
    for (Map.Entry<T, Integer> entry : multiset.entrySet())
      max = Math.max(max, entry.getValue());
    return max;
  }
  
  /**
   * Add feature [...]-max-duplication
   */
  protected <T> void addDuplicationFeatures(FeatureVector v, String domain, String name, Multiset<T> multiset) {
    int maxDuplication = maxDuplication(multiset);
    addQuantizedFeatures(v, domain, name + "-max-duplication", maxDuplication);
  }

  /**
   * Find the majority value (value that occurs the most often). If more than
   * one values share the same majority count, assign null instead.
   */
  protected <T> T getAbsoluteMajority(Multiset<T> multiset) {
    T majority = null;
    int majorityCount = 0;
    for (Map.Entry<T, Integer> entry : multiset.entrySet()) {
      if (entry.getValue() > majorityCount) {
        majority = entry.getKey();
        majorityCount = entry.getValue();
      } else if (entry.getValue() == majorityCount) {
        majority = null;
      }
    }
    return majority;
  }
  
  /**
   * Compute the entropy of the Multiset
   * 
   * The entropy is H(x) = -sum[p(x) log p(x)]
   * where p(x) = count(x) / size(multiset)
   */
  protected <T> double getEntropy(Multiset<T> multiset) {
    if (multiset.elementSet().size() == 1) return 0.0;
    double entropy = 0.0;
    for (Map.Entry<T, Integer> entry : multiset.entrySet()) {
      double p = 1.0 * entry.getValue() / multiset.size();
      entropy -= p * Math.log(p);
    }
    return entropy;
  }
  
  protected <T> double getNormalizedEntropy(Multiset<T> multiset) {
    if (multiset.size() <= 1) return 0.0;
    return getEntropy(multiset) / Math.log(multiset.size());
  }
  
  /**
   * Add feature [...]-entropy
   */
  protected <T> void addEntropyFeatures(FeatureVector v, String domain, String name, Multiset<T> multiset) {
    double entropy = getEntropy(multiset);
    if (entropy > 0 && multiset.size() > 1) {
      double normalizedEntropy = entropy / Math.log(multiset.size());
      if (opts.binEntropyFeatures)
        addBinFeatures(v, domain, name + "-normalized-entropy", normalizedEntropy);
      else
        v.add(domain, name + "-normalized-entropy", normalizedEntropy);
    }
  }
  
  /**
   * Add features 
   *   [...]-percent-distinct
   *   [...]-identical
   *   [...]-single
   *   [...]-majority
   * 
   * Common cases:
   * - Only one object (and therefore one majority value) --> [...]-distinct + [...]-single + ([...]-majority)
   * - Multiple objects with one majority value --> [...]-majority
   * - Multiple objects with distinct values --> [...]-distinct
   * 
   * @param bagOfWords
   *      break keys of multiset into bag of words (default = false)
   * @param addMajorityEvenIfSingle
   *      add [...]-majority feature even if there is only 1 element in the multiset (default = true)
   */
  protected <T> void addVotingFeatures(FeatureVector v, String domain, String name, Multiset<T> multiset,
      boolean bagOfWords, boolean addMajorityEvenIfSingle) {
    if (opts.noAggregation) {
      for (Map.Entry<T, Integer> entry : multiset.entrySet()) {
        for (int i = 0; i < entry.getValue(); i++)
          v.add(domain, name + " = " + entry.getKey());
      }
      return;
    }
    if (multiset.isEmpty()) return;
    addEntropyFeatures(v, domain, name, multiset);
    //addPercentFeatures(v, domain, name + "-percent-distinct", multiset.elementSet().size() * 1.0 / multiset.size());
    T majority = getAbsoluteMajority(multiset);
    if (majority == null) return;
    double majorityRatio = multiset.count(majority) * 1.0 / multiset.size();
    if (opts.addMajorityPercentageFeature) {
      addPercentFeatures(v, domain, name + "-majority-ratio", majorityRatio);
    }
    if (majorityRatio < opts.minMajorityRatio) {
      if (opts.addDiverseFeature)
        v.add(domain, name + "-diverse");
      return;
    }
    if (majorityRatio >= 0.9) {
      if (multiset.size() > 1) {
        v.add(domain, name + "-identical");
      } else {
        v.add(domain, name + "-single");
      }
    }
    // Majority value
    if (bagOfWords) {
      addBagOfWordFeatures(v, domain, name + "-majority", (String) majority);
    } else {
      if (multiset.size() > 1 || addMajorityEvenIfSingle) {
        v.add(domain, name + "-majority = " + majority);
      }
    }
  }

  protected <T> void addVotingFeatures(FeatureVector v, String domain, String name, Multiset<T> multiset,
      boolean bagOfWords) {
    addVotingFeatures(v, domain, name, multiset, bagOfWords, true);
  }

  protected <T> void addVotingFeatures(FeatureVector v, String domain, String name, Multiset<T> multiset) {
    addVotingFeatures(v, domain, name, multiset, false, true);
  }
    
  // ============================================================
  // Continuous statistics
  // ============================================================

  protected <T extends Number> void addMeanDeviationFeatures(FeatureVector v, String domain, String name,
      Multiset<T> multiset) {
    double mean = 0.0, variance = 0.0;
    for (T element : multiset.elementSet()) {
      double value = element.doubleValue();
      mean += value;
      variance += value * value;
    }
    mean = mean / multiset.size();
    variance = variance / multiset.size() - mean * mean;
    if (opts.useDiscreteMeanAndDeviation) {
      addQuantizedFeatures(v, domain, name + "-mean", mean);
      addQuantizedFeatures(v, domain, name + "-deviation", Math.sqrt(variance));
    } else {
      v.add(domain, name + "-mean", mean);
      v.add(domain, name + "-deviation", Math.sqrt(variance));
    }
  }
  
  // ============================================================
  // Linguistics
  // ============================================================
  
  /**
   * Add features "[...]-lemma ~ [lemma]" for all lemmas in the specified phrase.
   */
  protected void addLemmaFeatures(FeatureVector v, String domain, String name, String phrase, boolean addOnlyOpenPOS) {
    Set<String> lemmas = LingData.get(phrase).getTokens(true, addOnlyOpenPOS);
    for (String lemma : lemmas) {
      v.add(domain, name + "-lemma ~ " + lemma);
    }
  }
  protected void addLemmaFeatures(FeatureVector v, String domain, String name, String phrase) {
    addLemmaFeatures(v, domain, name, phrase, false);
  }

  /**
   * Add features "[...]-lemma ~ [lemma1]|[lemma2]" for all pairs of lemmas in the specified phrases.
   */
  protected void addLemmaFeatures(FeatureVector v, String domain, String name, String phrase1, String phrase2, boolean addOnlyOpenPOS) {
    Set<String> lemmas1 = LingData.get(phrase1).getTokens(true, addOnlyOpenPOS),
                lemmas2 = LingData.get(phrase1).getTokens(true, addOnlyOpenPOS);
    for (String lemma1 : lemmas1) {
      for (String lemma2 : lemmas2) {
        v.add(domain, name + "-lemma ~ " + lemma1 + "|" + lemma2);
        if (lemma1.equals(lemma2)) {
          v.add(domain, name + "-lemma SAME");
        }
      }
    }
  }
  protected void addLemmaFeatures(FeatureVector v, String domain, String name, String phrase1, String phrase2) {
    addLemmaFeatures(v, domain, name, phrase1, phrase2, false);
  }
  
  /**
   * Add features "[...]-cluster ~ [cluster_prefix]" for all tokens in the phrase.
   */
  protected void addClusterFeatures(FeatureVector v, String domain, String name, String phrase) {
    List<String> tokens = LingData.get(phrase).tokens;
    for (String token : tokens) {
      String cluster = BrownClusterTable.getCluster(token);
      if (cluster == null) continue;
      v.add(domain, name + "-cluster = " + cluster);
      for (String prefix : BrownClusterTable.getDefaultClusterPrefixes(cluster)) {
        v.add(domain, name + "-cluster ~ " + prefix);
      }
    }
  }
  
  /**
   * Add features "[...]-cluster ~ [cluster_prefix_1]|[cluster_prefix_2]" for all pairs of tokens in the specified phrases.
   */
  protected void addClusterFeatures(FeatureVector v, String domain, String name, String phrase1, String phrase2) {
    List<String> tokens1 = LingData.get(phrase1).tokens;
    List<String> tokens2 = LingData.get(phrase2).tokens;
    for (String token1 : tokens1) {
      String cluster1 = BrownClusterTable.getCluster(token1);
      if (cluster1 == null) continue;
      for (String token2 : tokens2) {
        String cluster2 = BrownClusterTable.getCluster(token2);
        if (cluster2 == null) continue;
        v.add(domain, name + "-cluster = " + cluster1 + "|" + cluster2);
        for (String prefix : BrownClusterTable.getDefaultClusterPrefixes(cluster1, cluster2)) {
          v.add(domain, name + "-cluster ~ " + prefix);
        }
      }
    }
  }
  
} public class KnowledgeTreeBuilder {
  public static class Options {
    @Option(gloss = "Maximum number of search results to keep per query") public int maxResultsPerSearch = 1;
    @Option public int maxFullTextLength = 140;
    @Option public boolean ignoreTextNodes = false;
    @Option public boolean useWikipedia = false;
    @Option public boolean useFakeGoogle = false;
    @Option(gloss = "level of entity string normalization when creating the knowledge tree "
                  + "(0 = none / 1 = whitespace / 2 = simple / 3 = aggressive)")
    public int earlyNormalizeEntities = 1;
    @Option public boolean alsoNormalizeBR = true;
    @Option public boolean onlyNormalizeBR = false;
  }
  public static Options opts = new Options();

  public void buildKnowledgeTree(Example ex) {
    LogInfo.begin_track("KnowledgeTreeBuilder %s", ex);
    
    if (ex instanceof ExampleCached) {
      
      ExampleCached cex = (ExampleCached) ex;
      if (cex.hashcode != null && cex.cacheDirectory != null) {
        // Use the cached web page
        LogInfo.begin_track("[CACHED %s]", cex.hashcode);
        ex.tree = new KNode(null, KNode.Type.QUERY, cex.phrase);
        Document doc = WebUtils.getWebpageFromHashcode(cex.cacheDirectory, cex.hashcode);
        buildKnowledgeTreeFromDocument(doc, ex.tree.createChild(KNode.Type.URL, cex.url));
        LogInfo.end_track();
      } else {
        // Download from the Internet
        LogInfo.begin_track("[URL %s]", cex.url);
        ex.tree = new KNode(null, KNode.Type.QUERY, cex.phrase);
        Document doc = WebUtils.getWebpage(cex.url);
        buildKnowledgeTreeFromDocument(doc, ex.tree.createChild(KNode.Type.URL, cex.url));
        LogInfo.end_track();
      }
      
    } else if (opts.useWikipedia) {
      
      // Cheat on Wikipedia
      String query = ex.phrase;
      String url = "http://en.wikipedia.org/wiki/" + query.replaceAll(" ", "_");
      LogInfo.begin_track("[WIKIPEDIA %s]", url);
      ex.tree = new KNode(null, KNode.Type.QUERY, query);
      Document doc = WebUtils.getWebpage(url);
      buildKnowledgeTreeFromDocument(doc, ex.tree.createChild(KNode.Type.URL, url));
      LogInfo.end_track();
      
    } else {
      
      // Perform a Google search
      String query = "list of " + ex.phrase;
      List<SearchResult> results;
      if (opts.useFakeGoogle) {
        results = WebUtils.fakeGoogleSearch(query);
      } else {
        results = WebUtils.googleSearch(query);
      }
      if (results.size() > opts.maxResultsPerSearch)
        results = results.subList(0, opts.maxResultsPerSearch);
      LogInfo.logs("%s search results", results.size());
  
      // Fetch the web pages of all the top pages.
      ex.tree = new KNode(null, KNode.Type.QUERY, query);
      for (SearchResult result : results) {
        LogInfo.begin_track("%s", result);
        Document doc = WebUtils.getWebpage(result.url);
        buildKnowledgeTreeFromDocument(doc, ex.tree.createChild(KNode.Type.URL, result.url));
        LogInfo.end_track();
      }
      
    }

    LogInfo.end_track();
  }
  
  /**
   * Build a knowledge tree from jsoup Document object and attach the result to |root|.
   * @param doc    The jsoup Document. The first child of |doc| should be an <html> tag.
   * @param root   The parent of the created tree's root node.
   */
  public void buildKnowledgeTreeFromDocument(Document doc, KNode root) {
    if (!doc.child(0).tagName().equals("html")) {
      LogInfo.fail(doc.child(0).tagName());
    }
    HTMLFixer fixer = new HTMLFixer(doc);
    fixer.fixAllTables();
    if (!opts.onlyNormalizeBR) {
      convertElementToKTree(doc.child(0), root);
    }
    if (opts.alsoNormalizeBR) {
      fixer.fixAllBRs();
      convertElementToKTree(doc.child(0), root);
    }
    for (KNode htmlNode : root.getChildren()) {
      htmlNode.generateTimestamp();
    }
  }
  
  /**
   * Convert jsoup Element (= an HTML tag and its content) into a knowledge tree.
   * Contents inside style tag (CSS) and script tag (JavaScript) are ignored.
   * 
   * @param elt       The jsoup Element corresponding to the root of the tree
   * @param parent    The parent of the created tree's root node.
   */
  public void convertElementToKTree(Element elt, KNode parent) {
    String eltText = LingUtils.normalize(elt.text(), opts.earlyNormalizeEntities);
    KNode currentNode = parent.createChild(KNode.Type.TAG, elt.tagName(),
        eltText.length() > opts.maxFullTextLength ? null : eltText);

    // Add children
    for (Node child : elt.childNodes()) {
      if (child instanceof Element) {
        convertElementToKTree((Element) child, currentNode);
      } else if (child instanceof TextNode) {
        if (!opts.ignoreTextNodes) {
          String text = LingUtils.normalize(((TextNode) child).text(), opts.earlyNormalizeEntities);
          if (!text.isEmpty()) {
            //currentNode.createChild(KNode.Type.TEXT, text, text);
            currentNode.createChild(KNode.Type.TAG, "text",
                text.length() > opts.maxFullTextLength ? null : text);
          }
        }
      }
    }
    
    // Add attributes
    for (Attribute attr : elt.attributes()) {
      currentNode.createAttribute(attr.getKey(), attr.getValue());
    }
  }
  
  // ============================================================
  // Test Suite
  // ============================================================
  
  public static void main(String[] args) {
    KnowledgeTreeBuilder builder = new KnowledgeTreeBuilder();
    /*{
      ExampleCached ex = new ExampleCached("snooker tournaments", "frozen.cache/wiki/",
          "e88739bb552c5abef23b24fbf6e2e911cd3d2bac", null, null);
      builder.buildKnowledgeTree(ex);
      KNodeUtils.printTree(ex.tree.getChildren().get(0).getChildren().get(0));
    }*/
    {
      ExampleCached ex = new ExampleCached("Slovenian film", "frozen.cache/wiki/",
          "62f4c2c17afec7e54d6362f280a1e6ab65444e73", null, null);
      builder.buildKnowledgeTree(ex);
      KNodeUtils.printTree(ex.tree);
    }
    /*{
      ExampleCached ex = new ExampleCached("oxymorons", "frozen.cache/02/",
          "1bdfe640b5f5680f328e90a77136fd883a3b0105", null, null);
      builder.buildKnowledgeTree(ex);
      KNodeUtils.printTree(ex.tree.getChildren().get(0).getChildren().get(0));
    }*/
  }
  
} public class Parallelizer {
  public static class Options {
    @Option(gloss = "Number of threads for execution")
    public int numThreads = 1;
  }
  public static Options opts = new Options();
  
  public static int getNumThreads() {
    int numThreads = Runtime.getRuntime().availableProcessors();
    if (opts.numThreads > 0 && numThreads > opts.numThreads)
      numThreads = opts.numThreads;
    return numThreads;
  }
  
  public static void run(List<Runnable> tasks) {
    LogInfo.begin_threads();
    ExecutorService service = Executors.newFixedThreadPool(getNumThreads());
    try {
      for (Runnable task : tasks) {
        service.submit(task);
      }
      service.shutdown();
      service.awaitTermination(1, TimeUnit.DAYS);
    } catch (InterruptedException e) {
      LogInfo.fail(e);
    }
    LogInfo.end_threads();
  }
  
  public static <T, S extends Callable<T>> List<Future<T>> runAndReturnStuff(List<S> tasks) {
    LogInfo.begin_threads();
    List<Future<T>> results = null;
    ExecutorService service = Executors.newFixedThreadPool(getNumThreads());
    try {
      // Invoke all trainers
      results = service.invokeAll(tasks);
      service.shutdown();
      service.awaitTermination(1, TimeUnit.DAYS);
    } catch (InterruptedException e) {
      LogInfo.fail(e);
    }
    LogInfo.end_threads();
    return results;
  }
  
}
import java.util.*;
import edu.stanford.nlp.semparse.open.core.eval.CandidateStatistics;
import edu.stanford.nlp.semparse.open.core.eval.EvaluationCase;
import edu.stanford.nlp.semparse.open.core.eval.EvaluationSuccess;
import edu.stanford.nlp.semparse.open.core.eval.Evaluator;
import edu.stanford.nlp.semparse.open.core.eval.IterativeTester;
import edu.stanford.nlp.semparse.open.dataset.Dataset;
import edu.stanford.nlp.semparse.open.dataset.Example;
import edu.stanford.nlp.semparse.open.dataset.ExampleCached;
import edu.stanford.nlp.semparse.open.dataset.entity.TargetEntity;
import edu.stanford.nlp.semparse.open.ling.LingData;
import edu.stanford.nlp.semparse.open.model.Learner;
import edu.stanford.nlp.semparse.open.model.LearnerBaseline;
import edu.stanford.nlp.semparse.open.model.LearnerMaxEnt;
import edu.stanford.nlp.semparse.open.model.LearnerMaxEntWithBeamSearch;
import edu.stanford.nlp.semparse.open.model.candidate.Candidate;
import edu.stanford.nlp.semparse.open.model.candidate.CandidateGenerator;
import edu.stanford.nlp.semparse.open.model.feature.FeaturePostProcessor;
import edu.stanford.nlp.semparse.open.model.feature.FeatureType;
import edu.stanford.nlp.semparse.open.model.tree.KnowledgeTreeBuilder;
import edu.stanford.nlp.semparse.open.util.Parallelizer;
import fig.basic.LogInfo;
import fig.basic.Option;
import fig.basic.Pair;
import fig.exec.Execution;
package edu.stanford.nlp.semparse.open.core;



public class OpenSemanticParser {
  public static class Options {
    @Option(gloss = "Whether to test on training and test data every training iteration")
    public boolean testEveryIteration = true;
    @Option(gloss = "Log parameters after training")
    public boolean logParams = true;
    /**
     * 0 = no log whatsoever
     * 1 = log only tree patterns and scores
     * 2 = add predicted entities and answer keys
     * 3 = add feature vectors for all examples
     */
    @Option(gloss = "Verbosity of the log")
    public int logVerbosity = 3;
    @Option(gloss = "Don't print feature weights for correct answers")
    public boolean ignoreCorrectAnswers = true;
    @Option(gloss = "Learner name (maxent / base / beam)")
    public String learner = "maxent";
    @Option(gloss = "Whether to cheat and use only the candidates that contain the seed answer")
    public boolean useSeed = false;
  }
  public static Options opts = new Options();
  
  private Learner learner;
  private IterativeTester iterativeTester;
  private KnowledgeTreeBuilder knowledgeTreeBuilder = new KnowledgeTreeBuilder();
  private CandidateGenerator candidateGenerator = new CandidateGenerator();
  private static boolean initialized = false;
  
  public static void init() {
    if (initialized) return;
    // Load JavaNLP and other linguistics stuff
    LingData.initModels();
    // Try to load cache
    LingData.loadCache();
    // Check the feature options
    FeatureType.checkFeatureTypeOptionsSanity();
    FeaturePostProcessor.checkFeaturePostProcessorOptionsSanity();
    initialized = true;
  }
  
  public static void cleanUp() {
    // Try to save cache
    LingData.saveCache();
  }
  
  private Learner getLearner() {
    switch (opts.learner) {
      case "maxent":
        //LogInfo.log("Using MaxEnt learner ...");
        return new LearnerMaxEnt();
      case "base":
      case "baseline":
        //LogInfo.log("Using baseline learner ...");
        return new LearnerBaseline();
      case "beam":
      case "beamsearch":
        //LogInfo.logs("Using MaxEnt learner with beam search (beam size = %d) ...",
        //    LearnerMaxEntWithBeamSearch.opts.beamSize);
        return new LearnerMaxEntWithBeamSearch();
    }
    LogInfo.fails("Unknown learner: %s", opts.learner);
    return null;
  }
  
  // ============================================================
  // Preprocessing
  // ============================================================
  
  /**
   * Extract the data (trees / candidates / features) in advance and cache them.
   * It is not necessary to call this function before calling train() or test(), though.
   */
  public void preTrain(Dataset dataset) {