public abstract class Category {
  private final String asString;
  private final int id;
  private final static String WILDCARD_FEATURE = "X"; 
  private final static Set<String> bracketAndQuoteCategories = ImmutableSet.of("LRB", "RRB", "LQU", "RQU");

  private Category(String asString, String semanticAnnotation) {
    this.asString = asString + (semanticAnnotation == null ? "" : "{" + semanticAnnotation + "}");
    this.id = numCats.getAndIncrement();
  }

  public enum Slash {
    FWD, BWD, EITHER;
    public String toString()
    {
      String result = "";

      switch (this)
      {
      case FWD: result = "/"; break;
      case BWD: result = "\\"; break;
      case EITHER: result = "|"; break;

      }

      return result;
    }

    public static Slash fromString(String text) {
      if (text != null) {
        for (Slash slash : values()) {
          if (text.equalsIgnoreCase(slash.toString())) 
          {
            return slash;
          }
        }
      }
      throw new IllegalArgumentException("Invalid slash: " + text);
    }

    public boolean matches(Slash other)
    {
      return this == EITHER || this == other;
    }
  }

  private static AtomicInteger numCats = new AtomicInteger();
  private final static Map<String, Category> cache = new HashMap<String, Category>();
  public static final Category COMMA = Category.valueOf(",");
  public static final Category SEMICOLON = Category.valueOf(";");
  public static final Category CONJ = Category.valueOf("conj");
  public final static Category N = valueOf("N"); 
  public static final Category LQU = Category.valueOf("LQU");
  public static final Category LRB = Category.valueOf("LRB");
  public static final Category NP = Category.valueOf("NP");
  public static final Category PP = Category.valueOf("PP");
  public static final Category PREPOSITION = Category.valueOf("PP/NP");
  public static final Category PR = Category.valueOf("PR");

  public static Category valueOf(String cat) {

    Category result = cache.get(cat);
    if (result == null) {

      String name = Util.dropBrackets(cat);
      result = cache.get(name);

      if (result == null) {
        result = Category.valueOfUncached(name);
        if (name != cat) {
          synchronized(cache) {
            cache.put(name, result);
          }
        }
      }

      synchronized(cache) {
        cache.put(cat, result);
      }
    }

    return result;
  }

  /**
   * Builds a category from a string representation.
   */
  private static Category valueOfUncached(String source)
  {
    // Categories have the form: ((X/Y)\Z[feature]){ANNOTATION}
    String newSource = source;

    String semanticAnnotation;
    if (newSource.endsWith("}")) {
      int openIndex = newSource.lastIndexOf("{");
      semanticAnnotation = newSource.substring(openIndex + 1, newSource.length() - 1);
      newSource = newSource.substring(0, openIndex);
    } else {
      semanticAnnotation = null;
    }

    if (newSource.startsWith("("))
    {
      int closeIndex = Util.findClosingBracket(newSource);

      if (Util.indexOfAny(newSource.substring(closeIndex), "/\\|") == -1)
      {
        // Simplify (X) to X
        newSource = newSource.substring(1, closeIndex);
        Category result = valueOfUncached(newSource);

        return result;
      }
    }

    int endIndex = newSource.length();

    int opIndex =  Util.findNonNestedChar(newSource, "/\\|");


    if (opIndex == -1)
    {
      // Atomic Category
      int featureIndex = newSource.indexOf("[");
      List<String> features = new ArrayList<String>();

      String base = (featureIndex == -1 ? newSource : newSource.substring(0, featureIndex));

      while (featureIndex > -1)
      {
        features.add(newSource.substring(featureIndex + 1, newSource.indexOf("]", featureIndex)));
        featureIndex = newSource.indexOf("[", featureIndex + 1);
      }

      if (features.size() > 1) {
        throw new RuntimeException("Can only handle single features: " + source);
      }

      Category c = new AtomicCategory(base, features.size() == 0 ? null : features.get(0), semanticAnnotation);
      return c;
    }
    else
    {
      // Functor Category

      Category left = valueOf(newSource.substring(0, opIndex));
      Category right = valueOf(newSource.substring(opIndex + 1, endIndex));
      return new FunctorCategory(left, 
          Slash.fromString(newSource.substring(opIndex, opIndex + 1)), 
          right,
          semanticAnnotation
      );
    }
  }  

  public String toString() {
    return asString;
  }

  @Override
  public boolean equals(Object other) {
    return this == other;
  }

  @Override 
  public int hashCode() {
    return id;
  }

  abstract boolean isTypeRaised();
  abstract boolean isForwardTypeRaised();
  abstract boolean isBackwardTypeRaised();

  public abstract boolean isModifier();
  public abstract boolean matches(Category other);
  public abstract Category getLeft();
  public abstract Category getRight();
  abstract Slash getSlash();
  abstract String getFeature();

  abstract String toStringWithBrackets();
  public abstract Category dropPPandPRfeatures();

  static class FunctorCategory extends Category {
    private final Category left;
    private final Category right;
    private final Slash slash;
    private final boolean isMod;

    private FunctorCategory(Category left, Slash slash, Category right, String semanticAnnotation) {
      super(left.toStringWithBrackets() + slash + right.toStringWithBrackets(), semanticAnnotation);
      this.left = left;
      this.right = right;
      this.slash = slash;
      this.isMod = left.equals(right);

      // X|(X|Y)
      this.isTypeRaised = right.isFunctor() && right.getLeft().equals(left);
    }

    @Override
    public boolean isModifier()
    {
      return isMod;
    }

    @Override
    public boolean matches(Category other)
    {
      return other.isFunctor() && left.matches(other.getLeft()) && right.matches(other.getRight()) && slash.matches(other.getSlash());
    }

    @Override
    public Category getLeft()
    {
      return left;
    }

    @Override
    public Category getRight()
    {
      return right;
    }

    @Override
    Slash getSlash()
    {
      return slash;
    }

    @Override
    String getFeature()
    {
      throw new UnsupportedOperationException();
    }

    @Override
    String toStringWithBrackets()
    {
      return "(" + toString() + ")";
    }

    @Override
    public boolean isFunctor()
    {
      return true;
    }

    @Override
    public boolean isPunctuation()
    {
      return false;
    }

    @Override
    String getType()
    {
      throw new UnsupportedOperationException();
    }

    @Override
    String getSubstitution(Category other)
    {
      String result = getRight().getSubstitution(other.getRight());
      if (result == null) {
        // Bit of a hack, but seems to reproduce CCGBank in cases of clashing features.
        result = getLeft().getSubstitution(other.getLeft());
      }
      return result;
    }

    private final boolean isTypeRaised;
    @Override
    public boolean isTypeRaised()
    {
      return isTypeRaised;
    }

    @Override
    public boolean isForwardTypeRaised()
    {
      // X/(X\Y)
      return isTypeRaised() && getSlash() == Slash.FWD;
    }

    @Override
    public boolean isBackwardTypeRaised()
    {
      // X\(X/Y)
      return isTypeRaised() && getSlash() == Slash.BWD;
    }

    @Override
    boolean isNounOrNP()
    {
      return false;
    }

    @Override
    public Category addFeature(String preposition)
    {
      throw new RuntimeException("Functor categories cannot take features");
    }

    @Override
    public int getNumberOfArguments()
    {
      return 1 + left.getNumberOfArguments();
    }

    @Override
    public Category replaceArgument(int argNumber, Category newCategory)
    {
      if (argNumber == getNumberOfArguments()) {
        return Category.make(left, slash, newCategory);
      } else {
        return Category.make(left.replaceArgument(argNumber, newCategory), slash, right);
      }
    }

    @Override
    public Category getArgument(int argNumber)
    {
      if (argNumber == getNumberOfArguments()) {
        return right;
      } else {
        return left.getArgument(argNumber);
      }
    }

    @Override
    public Category getHeadCategory()
    {
      return left.getHeadCategory();
    }

    @Override
    public boolean isFunctionIntoModifier()
    {
      return isModifier() || left.isModifier();
    }

    @Override
    public boolean isFunctionInto(Category into)
    {
      return into.matches(this) || left.isFunctionInto(into);
    }

    @Override
    public Category dropPPandPRfeatures()
    {
      return Category.make(left.dropPPandPRfeatures(), slash, right.dropPPandPRfeatures());
    }
  }

  abstract String getSubstitution(Category other);


  static class AtomicCategory extends Category {

    private AtomicCategory(String type, String feature, String semanticAnnotation)
    {
      super(type + (feature == null ? "" : "[" + feature + "]"), semanticAnnotation);
      this.type = type;
      this.feature = feature;
      isPunctuation = !type.matches("[A-Za-z]+") || bracketAndQuoteCategories.contains(type);
    }

    private final String type;
    private final String feature;
    @Override
    public boolean isModifier()
    {
      return false;
    }

    @Override
    public boolean matches(Category other)
    {
      return !other.isFunctor() && type.equals(other.getType()) && 
      (feature == null || feature.equals(other.getFeature()) || WILDCARD_FEATURE.equals(getFeature()) || WILDCARD_FEATURE.equals(other.getFeature())
          || feature.equals("nb") // Ignoring the NP[nb] feature, which isn't very helpful. For example, it stops us coordinating "John and a girl",
          // because "and a girl" ends up with a NP[nb]\NP[nb] tag.
      );
    }

    @Override
    public Category getLeft()
    {
      throw new UnsupportedOperationException();
    }

    @Override
    public Category getRight()
    {
      throw new UnsupportedOperationException();
    }

    @Override
    Slash getSlash()
    {
      throw new UnsupportedOperationException();
    }

    @Override
    String getFeature()
    {
      return feature;
    }

    @Override
    String toStringWithBrackets()
    {
      return toString();
    }

    @Override
    public boolean isFunctor()
    {
      return false;
    }

    private final boolean isPunctuation;
    @Override
    public boolean isPunctuation()
    {
      return isPunctuation ;
    }

    @Override
    String getType()
    {
      return type;
    }

    @Override
    String getSubstitution(Category other)
    {
      if (WILDCARD_FEATURE.equals(getFeature())) {
        return other.getFeature();
      } else if (WILDCARD_FEATURE.equals(other.getFeature())) {
        return feature;
      }
      return null;
    }

    @Override
    public boolean isTypeRaised()
    {
      return false;
    }

    public boolean isForwardTypeRaised()
    {
      return false;
    }

    public boolean isBackwardTypeRaised()
    {
      return false;
    }

    @Override
    boolean isNounOrNP()
    {
      return type.equals("N") || type.equals("NP");
    }

    @Override
    public Category addFeature(String newFeature)
    {
      if (feature != null) throw new RuntimeException("Only one feature allowed. Can't add feature: " + newFeature + " to category: " + this);
      newFeature = newFeature.replaceAll("/", "");
      newFeature = newFeature.replaceAll("\\\\", "");
      return valueOf(type + "[" + newFeature + "]");
    }

    @Override
    public int getNumberOfArguments()
    {
      return 0;
    }

    @Override
    public Category replaceArgument(int argNumber, Category newCategory)
    {
      if (argNumber == 0) return newCategory;
      throw new RuntimeException("Error replacing argument of category");
    }

    @Override
    public Category getArgument(int argNumber)
    {
      if (argNumber == 0) return this;
      throw new RuntimeException("Error getting argument of category");
    }

    @Override
    public Category getHeadCategory()
    {
      return this;
    }

    @Override
    public boolean isFunctionIntoModifier()
    {
      return false;
    }

    @Override
    public boolean isFunctionInto(Category into)
    {
      return into.matches(this);
    }

    @Override
    public Category dropPPandPRfeatures()
    {
      if (type.equals("PP") || type.equals("PP")) {
        return valueOf(type);
      } else {
        return this;
      }
    }    
  }

  public static Category make(Category left, Slash op, Category right)
  {
    return valueOf(left.toStringWithBrackets() + op + right.toStringWithBrackets());
  }

  abstract String getType();

  abstract boolean isFunctor();

  abstract boolean isPunctuation();

  /**
   * Returns the Category created by substituting all [X] wildcard features with the supplied argument.
   */
  Category doSubstitution(String substitution)
  {
    if (substitution == null) return this;
    return valueOf(toString().replaceAll(WILDCARD_FEATURE, substitution));
  }

  /**
   * A unique numeric identifier for this category.
   */
  int getID()
  {
    return id;
  }

  abstract boolean isNounOrNP();

  public abstract Category addFeature(String preposition);

  public abstract int getNumberOfArguments();
  public abstract Category getHeadCategory();
  public abstract boolean isFunctionInto(Category into);


  /**
   * Replaces the argument with the given index with the new Category. Arguments are count from the left, starting with 0 for the head Category.
   * e.g. (((S\NP)/NP)/PP)/PR @replaceArgument(3, PP[in]) =  (((S\NP)/NP)/PP[in])/PR
   */
  public abstract Category replaceArgument(int argNumber, Category newCategory);

  public abstract Category getArgument(int argNumber);
  public abstract boolean isFunctionIntoModifier();


} public abstract class InputReader
{

  static class InputWord {

    private InputWord(String word, String pos, String ner)
    {
      this.word = word;
      this.pos = pos;
      this.ner = ner;
    }
    public InputWord(String word)
    {
      this (word, null, null);
    }
    public final String word;
    public final String pos;
    public final String ner;
  }
  
  public Iterable<InputToParser> readFile(File input) throws IOException {
    final Iterator<String> inputIt = Util.readFileLineByLine(input);
    
    
    return new Iterable<InputToParser>() {

      @Override
      public Iterator<InputToParser> iterator()
      {
        return new Iterator<InputToParser>() {

          private InputToParser next = getNext();
          @Override
          public boolean hasNext()
          {
            return next != null;
          }

          private InputToParser getNext()
          {         
            while (inputIt.hasNext()) {
              String nextLine = inputIt.next();
              if (!nextLine.startsWith("#") && !nextLine.isEmpty()) {
                // Skip commented or empty lines;                
                return readInput(nextLine);
              }
            }
            
            return null;
          }
 
          @Override
          public InputToParser next()
          {
            InputToParser result = next;
            next = getNext();
            return result;
          }

          @Override
          public void remove()
          {
            throw new UnsupportedOperationException();
          }
          
        };
      }
      
    };
  }
  
  public abstract InputToParser readInput(String line);
  
  public static class InputToParser {
    private final List<InputWord> words;
    private boolean isAlreadyTagged;
    InputToParser(List<InputWord> words, List<Category> goldCategories, List<List<SyntaxTreeNodeLeaf>> inputSupertags, boolean isAlreadyTagged)
    {
      this.words = words;
      this.goldCategories = goldCategories;
      this.inputSupertags = inputSupertags;
      this.isAlreadyTagged = isAlreadyTagged;
    }
    private final List<Category> goldCategories;
    private final List<List<SyntaxTreeNodeLeaf>> inputSupertags;
    public int length()
    {
      return words.size();
    }
    
    /**
     * If true, the Parser should not supertag the data itself, and use getInputSupertags() instead.
     */
    public boolean isAlreadyTagged()
    {
      return isAlreadyTagged;
    }
    public List<List<SyntaxTreeNodeLeaf>> getInputSupertags()
    {
      return inputSupertags;
    }
    
    public List<SyntaxTreeNodeLeaf> getInputSupertags1best()
    {
      List<SyntaxTreeNodeLeaf> result = new ArrayList<SyntaxTreeNodeLeaf>();
      for (List<SyntaxTreeNodeLeaf> tagsForWord : inputSupertags) {
        result.add(tagsForWord.get(0));
      }
      return result;
    }
    public boolean haveGoldCategories()
    {
      return getGoldCategories() != null;
    }
    
    public List<Category> getGoldCategories()
    {
      return goldCategories;
    }

    public List<InputWord> getInputWords() {
      return words;
     
    }
    
    public String getWordsAsString()
    {
      StringBuilder result = new StringBuilder();
      for (InputWord word : words) {
        result.append(word.word + " ");
      }
      
      return result.toString().trim();
    }

    public static InputToParser fromTokens(List<String> tokens) {
      List<InputWord> inputWords = new ArrayList<InputWord>(tokens.size());
      for (String word : tokens) {
        inputWords.add(new InputWord(word, null, null));
      }
      return new InputToParser(inputWords, null, null, false);
    }
    
  }
  

  private static class RawInputReader extends InputReader {

    @Override
    public InputToParser readInput(String line)
    {
      //TODO quotes
      return InputToParser.fromTokens(Arrays.asList(line.replaceAll("\"", "").replaceAll("  +", " ").trim().split(" ")));
    }
  }

  /**
   *  Reads input tagged with a distribution of supertags. The format can be produced running the C&C supertagger with the output format: %w\t%p\t%S|\n
   *  
   *  Example:
   *  Pierre  NNP     0       N/N     0.99525070603732        N       0.0026450007306822|Vinken       NNP     0       N       0.70743834018551        S/S...
   */
  private static class SuperTaggedInputReader extends InputReader {

    private SuperTaggedInputReader(SyntaxTreeNodeFactory nodeFactory)
    {
      this.nodeFactory = nodeFactory;
    }

    private final SyntaxTreeNodeFactory nodeFactory;
    
    @Override
    public InputToParser readInput(String line) {
    // Pierre  NNP     0       N/N     0.99525070603732        N       0.0026450007306822|Vinken       NNP     0       N       0.70743834018551        S/S     0.14043752457392
      List<List<SyntaxTreeNodeLeaf>> supertags = new ArrayList<List<SyntaxTreeNodeLeaf>>();

      String[] split = line.split("\\|");
      List<InputWord> words = new ArrayList<InputWord>(split.length);
      for (String wordTags :  split) {
        
        List<SyntaxTreeNodeLeaf> entries = new ArrayList<SyntaxTreeNodeLeaf>();
        String[] fields = wordTags.split("(\t| )+");
        
        String word = fields[0];
        if (fields.length < 5) throw new InputMismatchException("Expected input using the C&C with output format --ofmt \"%w\\t%p\\t%S|\\n\" but was: " + line);

        words.add(new InputWord(word));
        
        for (int i=3; i < fields.length; i=i+2) {
          Category cat = Category.valueOf(fields[i]);
          entries.add(nodeFactory.makeTerminal(word, cat, fields[1], null, Math.log(Double.valueOf(fields[i + 1])), entries.size()));
        }
        supertags.add(entries);
      }
      
      return new InputToParser(words, null, supertags, true);
    }
    
  }
  
  private static class GoldInputReader extends InputReader {

    private SyntaxTreeNodeFactory nodeFactory;

    @Override
    public InputToParser readInput(String line)
    {
      List<Category> result = new ArrayList<Category>();
      String[] goldEntries = line.split(" ");
      List<InputWord> words = new ArrayList<InputWord>(goldEntries.length);
      List<List<SyntaxTreeNodeLeaf>> supertags = new ArrayList<List<SyntaxTreeNodeLeaf>>();
      for (String entry : goldEntries) {
        String[] goldFields = entry.split("\\|");
        
        if (goldFields[0].equals("\"")) continue ; //TODO quotes
        if (goldFields.length < 3) throw new InputMismatchException("Invalid input: expected \"word|POS|SUPERTAG\" but was: " + entry);

        String word = goldFields[0];
        String pos = goldFields[1];
        Category category = Category.valueOf(goldFields[2]);
        words.add(new InputWord(word));
        result.add(category);
        supertags.add(Arrays.asList(nodeFactory.makeTerminal(word, category, pos, null, 1.0, supertags.size())));
      }
      return new InputToParser(words, result, supertags, false);
    }    
    
    private GoldInputReader(SyntaxTreeNodeFactory nodeFactory)
    {
      this.nodeFactory = nodeFactory;
    }
  }
  
  private static class POSTaggedInputReader extends InputReader
  {

    @Override
    public InputToParser readInput(String line)
    {
      String[] taggedEntries = line.split(" ");
      List<InputWord> inputWords = new ArrayList<InputWord>(taggedEntries.length);
      for (String entry : taggedEntries) {
        String[] taggedFields = entry.split("\\|");
        
        if (taggedFields.length < 2) throw new InputMismatchException("Invalid input: expected \"word|POS\" but was: " + entry);
        if (taggedFields[0].equals("\"")) continue ; //TODO quotes
        inputWords.add(new InputWord(taggedFields[0], taggedFields[1], null));
      }
      return new InputToParser(inputWords, null, null, false);
    }    
  }
  
  private static class POSandNERTaggedInputReader extends InputReader
  {
    @Override
    public InputToParser readInput(String line)
    {
      String[] taggedEntries = line.split(" ");
      List<InputWord> inputWords = new ArrayList<InputWord>(taggedEntries.length);
      for (String entry : taggedEntries) {
        String[] taggedFields = entry.split("\\|");
        
        if (taggedFields[0].equals("\"")) continue ; //TODO quotes
        if (taggedFields.length < 3) throw new InputMismatchException("Invalid input: expected \"word|POS|NER\" but was: " + entry + "\n" +
        		"The C&C can produce this format using: \"bin/pos -model models/pos | bin/ner -model models/ner -ofmt \"%w|%p|%n \\n\"\"" );
        inputWords.add(new InputWord(taggedFields[0], taggedFields[1], taggedFields[2]));
      }
      return new InputToParser(inputWords, null, null, false);
    }    
  }

  public static InputReader make(InputFormat inputFormat, SyntaxTreeNodeFactory nodeFactory)
  {
    switch (inputFormat) {
    case SUPERTAGGED : return new SuperTaggedInputReader(nodeFactory);  
    case TOKENIZED : return new RawInputReader();  
    case GOLD : return new GoldInputReader(nodeFactory);  
    case POSTAGGED : return new POSTaggedInputReader();  
    case POSANDNERTAGGED : return new POSandNERTaggedInputReader();  
    default : throw new Error("Unknown input format: " + inputFormat);
    }
  }
} public static class InputToParser {
  private final List<InputWord> words;
  private boolean isAlreadyTagged;
  InputToParser(List<InputWord> words, List<Category> goldCategories, List<List<SyntaxTreeNodeLeaf>> inputSupertags, boolean isAlreadyTagged)
  {
    this.words = words;
    this.goldCategories = goldCategories;
    this.inputSupertags = inputSupertags;
    this.isAlreadyTagged = isAlreadyTagged;
  }
  private final List<Category> goldCategories;
  private final List<List<SyntaxTreeNodeLeaf>> inputSupertags;
  public int length()
  {
    return words.size();
  }
    
  /**
   * If true, the Parser should not supertag the data itself, and use getInputSupertags() instead.
   */
  public boolean isAlreadyTagged()
  {
    return isAlreadyTagged;
  }
  public List<List<SyntaxTreeNodeLeaf>> getInputSupertags()
  {
    return inputSupertags;
  }
    
  public List<SyntaxTreeNodeLeaf> getInputSupertags1best()
  {
    List<SyntaxTreeNodeLeaf> result = new ArrayList<SyntaxTreeNodeLeaf>();
    for (List<SyntaxTreeNodeLeaf> tagsForWord : inputSupertags) {
      result.add(tagsForWord.get(0));
    }
    return result;
  }
  public boolean haveGoldCategories()
  {
    return getGoldCategories() != null;
  }
    
  public List<Category> getGoldCategories()
  {
    return goldCategories;
  }

  public List<InputWord> getInputWords() {
    return words;
     
  }
    
  public String getWordsAsString()
  {
    StringBuilder result = new StringBuilder();
    for (InputWord word : words) {
      result.append(word.word + " ");
    }
      
    return result.toString().trim();
  }

  public static InputToParser fromTokens(List<String> tokens) {
    List<InputWord> inputWords = new ArrayList<InputWord>(tokens.size());
    for (String word : tokens) {
      inputWords.add(new InputWord(word, null, null));
    }
    return new InputToParser(inputWords, null, null, false);
  }
    
} public abstract class ParsePrinter
{
  public final static ParsePrinter CCGBANK_PRINTER = new CCGBankPrinter();
  public final static ParsePrinter HTML_PRINTER = new HTMLPrinter();
  public final static ParsePrinter PROLOG_PRINTER = new PrologPrinter();
  public final static ParsePrinter EXTENDED_CCGBANK_PRINTER = new ExtendedCCGBankPrinter();
  public final static ParsePrinter SUPERTAG_PRINTER = new SupertagPrinter();


  public String print(List<SyntaxTreeNode> parses, int id)
  {
    StringBuilder result = new StringBuilder();



    if (parses == null) {
      if (id > -1) printHeader(id, result);
      printFailure(result);
    } else {
      boolean isFirst = true;
      for (SyntaxTreeNode parse : parses) {
        if (isFirst) {
          isFirst = false;
        } else {
          // Separate N-best lists
          result.append("\n");
        }
        if (id > -1) printHeader(id, result);
        printParse(parse, id, result);
      }
    }

    printFooter(result);
    return result.toString();
  }

  public String print(SyntaxTreeNode entry, int id) {
    StringBuilder result = new StringBuilder();
    if (id > -1) printHeader(id, result);

    if (entry == null) {
      printFailure(result);
    } else {
      printParse(entry, id, result);
    }


    printFooter(result);
    return result.toString();
  }


  abstract void printFileHeader(StringBuilder result);
  abstract void printFailure(StringBuilder result);
  abstract void printHeader(int id, StringBuilder result);
  abstract void printFooter(StringBuilder result);
  abstract void printParse(SyntaxTreeNode parse, int sentenceNumber, StringBuilder result);

  abstract static class ParsePrinterVisitor implements SyntaxTreeNodeVisitor {
    final StringBuilder result;

    private ParsePrinterVisitor(StringBuilder result)
    {
      this.result = result;
    }

  }


  private static class CCGBankPrinter extends ParsePrinter {

    @Override
    void printFailure(StringBuilder result) {
      result.append("(<L NP NN NN fail N>)");
    }

    class CCGBankParsePrinterVisitor extends ParsePrinterVisitor {
      // (<T S[dcl] 0 2> (<T S[dcl] 1 2> (<T NP 0 2> (<T NP 0 2> (<T NP 0 2> (<T NP 0 1> (<T N 1 2> (<L N/N NNP NNP Pierre N_73/N_73>) (<L N NNP NNP Vinken N>) ) ) (<L , , , , ,>) )

      CCGBankParsePrinterVisitor(StringBuilder result) {
        super(result);
      }

      @Override
      public void visit(SyntaxTreeNodeBinary node)
      {
        result.append("(<T ");
        result.append(node.getCategory().toString());
        result.append(" " + (node.headIsLeft ? "0" : "1") + " 2> ");
        node.leftChild.accept(this);
        node.rightChild.accept(this);

        result.append(") ");

      }

      @Override
      public void visit(SyntaxTreeNodeUnary node)
      {
        result.append("(<T ");
        result.append(node.getCategory().toString());
        result.append(" 0 1> ");
        node.child.accept(this);
        result.append(") ");
      }

      @Override
      public void visit(SyntaxTreeNodeLeaf node)
      {
        result.append("(<L ");
        result.append(node.getCategory().toString());
        if (node.getPos() == null) {
          result.append(" POS POS ");
        } else {
          result.append(" " +node.getPos() + " " + node.getPos() + " ");
        }
        result.append(normalize(node.getWord()));
        result.append(" ");
        result.append(node.getCategory().toString());
        result.append(">) ");        
      }
    }

    /**
     * Normalizes words - e.g. converting brackets to CCGBank format.
     */
    private static String normalize(String word)
    {
      if (word.length() > 1) {
        return word;
      } else if (word.equals("{")) {
        return "-LRB-";
      } else if (word.equals("}")) {
        return "-RRB-";
      } else if (word.equals("(")) {
        return "-LRB-";
      } else if (word.equals(")")) {
        return "-RRB-";
      }
      return word;
    }

    @Override
    void printHeader(int id, StringBuilder result)
    {
      result.append("ID=" + id + "\n");
    }

    @Override
    void printFooter(StringBuilder result)
    {
    }

    @Override
    void printParse(SyntaxTreeNode parse, int sentenceNumber, StringBuilder result)
    {
      parse.accept(new CCGBankParsePrinterVisitor(result));
    }

    @Override
    void printFileHeader(StringBuilder result)
    {
    }
  }

  private static class HTMLPrinter extends ParsePrinter {
    @Override
    void printFailure(StringBuilder result)
    {
      result.append("<p>Parse failed!</p>");
    }

    @Override
    void printHeader(int id, StringBuilder result)
    {

      result.append("<html>\n" + 
      "<body>\n");
    }

    @Override
    void printFooter(StringBuilder result)
    {

      result.append("</body>\n" + 
      "</html>");
    }

    @Override
    void printParse(SyntaxTreeNode parse, int sentenceNumber, StringBuilder result)
    {
      result.append("<table>");
      for (List<SyntaxTreeNode> row : getRows(parse)) {
        result.append("<tr>");
        int indent = 0;
        while (indent < row.size()) {
          SyntaxTreeNode cell = row.get(indent);

          if (cell == null) {
            result.append("<td></td>");
            indent = indent + 1;
          }else if (cell.isLeaf()) {
            result.append(makeCell(((SyntaxTreeNodeLeaf) cell).getWord(), cell.getCategory()));
            indent = indent + 1;
          } else {
            int width =  getWidth(cell);
            result.append(makeCell(cell.getCategory(), width));
            indent = indent + width;
          }
        }
        result.append("</tr>\n");
      }
      result.append("</table>");
    }

    List<List<SyntaxTreeNode>> getRows(SyntaxTreeNode parse) {
      List<List<SyntaxTreeNode>> result = new ArrayList<List<SyntaxTreeNode>>();
      getRows(parse, result, 0);
      return result;
    }

    int getWidth(SyntaxTreeNode node) {
      if (node.getChildren().size() == 0) {
        return 1;
      } else {
        int result = 0;

        for (SyntaxTreeNode child : node.getChildren()) {
          result = result + getWidth(child); 
        }

        return result;
      }
    }
    @Override
    void printFileHeader(StringBuilder result)
    {
    }

    int getRows(SyntaxTreeNode node, List<List<SyntaxTreeNode>> result, int minIndentation) {

      int maxChildLevel = 0;
      int i = minIndentation;
      for (SyntaxTreeNode child : node.getChildren()) {
        maxChildLevel = Math.max(getRows(child, result, i), maxChildLevel);
        i = i + getWidth(child);
      }

      int level;
      if (node.getChildren().size() > 0) {
        level = maxChildLevel + 1;
      } else {
        level = 0;
      }

      while (result.size() < level + 1) {
        result.add(new ArrayList<SyntaxTreeNode>());
      }
      while (result.get(level).size() < minIndentation + 1) {
        result.get(level).add(null);
      }

      result.get(level).set(minIndentation, node);
      return level;
    }

    private String makeCell(Category category, int width) {
      return "<td colspan=" + width + "><center><hr>" + category.toString() + "</center></td>";
    }
    private String makeCell(String word, Category category) {
      return "<td><center>" + word + "<hr>" + category + "</center></td>";
    }
  }

  public static class SupertagPrinter extends ParsePrinter {

    @Override
    void printFileHeader(StringBuilder result)
    {
    }

    @Override
    void printFailure(StringBuilder result)
    {
    }

    @Override
    void printHeader(int id, StringBuilder result)
    {
    }

    @Override
    void printFooter(StringBuilder result)
    {
    }

    @Override
    void printParse(SyntaxTreeNode parse, int sentenceNumber, StringBuilder result)
    {
      // word|pos|tag word|pos|tag word|pos|tag
      boolean isFirst = true;
      for (SyntaxTreeNodeLeaf word : parse.getWords()) {
        if (isFirst) {
          isFirst = false;
        } else {
          result.append(" ");
        }

        result.append(word.getWord() + "|" + (word.getPos() == null ? "" : word.getPos()) + "|" + word.getCategory());
      }
    }
  }


  public static class PrologPrinter extends ParsePrinter {

    /*
ccg(2,
 ba('S[dcl]',
  lf(2,1,'NP'),
  fa('S[dcl]\NP',
   lf(2,2,'(S[dcl]\NP)/NP'),
   lex('N','NP',
    lf(2,3,'N'))))).

w(2, 1, 'I', 'I', 'PRP', 'I-NP', 'O', 'NP').
w(2, 2, 'like', 'like', 'VBP', 'I-VP', 'O', '(S[dcl]\NP)/NP').
w(2, 3, 'cake', 'cake', 'NN', 'I-NP', 'O', 'N').

     */

    private static String getRuleName(RuleType combinator) {
      // fa ba fc bx gfc gbx  conj
      switch (combinator) 
      {
      case FA : return "fa";
      case BA : return "ba";
      case FC : return "fc";
      case BX : return "bx";
      case CONJ : return "conj";
      case RP : return "rp";
      case LP : return "lp";
      case GFC : return "gfc";
      case GBX : return "gbx";
      }

      throw new RuntimeException("Unknown rule type: " + combinator);
    }

    @Override
    void printFileHeader(StringBuilder result)
    {
      result.append(":- multifile w/8, ccg/2, id/2.\n" + 
          ":- discontiguous w/8, ccg/2, id/2.\n" + 
          ":- dynamic w/8, ccg/2, id/2.\n" + 
          "\n" + 
      "");
    }


    @Override
    void printFailure(StringBuilder result)
    {
    }

    @Override
    void printHeader(int id, StringBuilder result)
    {
    }

    @Override
    void printFooter(StringBuilder result)
    {
    }

    @Override
    void printParse(SyntaxTreeNode parse, int sentenceNumber, StringBuilder result)
    {
      printDerivation(parse, sentenceNumber, result);
      result.append("\n");

      int i = 0;
      for (SyntaxTreeNodeLeaf word : parse.getWords()) {
        //w(2, 1, 'I', 'I', 'PRP', 'I-NP', 'I-PER', 'NP').
        i++;
        result.append("w(" + sentenceNumber + ", " + i + ", '" + word.getWord() + "', '" + MorphaStemmer.stemToken(word.getWord(), word.getPos()) + "', '" + word.getPos() + "', 'O" + "', '" + word.getNER()  + "', '" + word.getCategory() + "').\n");
      }
    }

    private void printDerivation(SyntaxTreeNode parse, int id, StringBuilder result)
    {
      result.append("ccg(" + id);
      parse.accept(new DerivationPrinter(result, id));
      result.append(").\n");
    }

    private class DerivationPrinter extends ParsePrinterVisitor {
      int currentIndent = 1;
      int wordNumber = 1;
      final int sentenceNumber;
      DerivationPrinter(StringBuilder result, int sentenceNumber) {
        super(result);
        this.sentenceNumber = sentenceNumber;
      }

      @Override
      public void visit(SyntaxTreeNodeBinary node)
      {
        // ba('S[dcl]',
        result.append(",\n");
        printIndent(currentIndent);
        result.append(getRuleName(node.getRuleType()) + "('" + node.getCategory() + "'");
        currentIndent++;    
        node.leftChild.accept(this);
        node.rightChild.accept(this);
        result.append(")");
        currentIndent--;
      }

      @Override
      public void visit(SyntaxTreeNodeUnary node)
      {
        // lex('N','NP',
        result.append(",\n");
        printIndent(currentIndent);
        result.append(getUnaryRuleName(node.child.getCategory(), node.getCategory()) + "('" + node.child.getCategory() + "','" +node.getCategory() + "'");
        currentIndent++;        
        node.child.accept(this);
        result.append(")");
        currentIndent--;
      }

      @Override
      public void visit(SyntaxTreeNodeLeaf node)
      {
        //   lf(2,2,'(S[dcl]\NP)/NP'),
        result.append(",\n");
        printIndent(currentIndent);
        result.append("lf(" + sentenceNumber + "," + wordNumber + ",'" + node.getCategory() + "')");
        wordNumber++;
      }
      private void printIndent(int currentIndent)
      {
        result.append(Strings.repeat(" ", currentIndent));
      }
    }

  }

  static String getUnaryRuleName(Category initial, Category result) {
    if ((Category.NP.matches(initial) || Category.PP.matches(initial)) && result.isTypeRaised()) {
      return "tr";
    } else {
      return "lex";
    }
  }

  static class ExtendedCCGBankPrinter extends ParsePrinter {


    @Override
    void printFailure(StringBuilder result) {
    }

    class CCGBankParsePrinterVisitor extends ParsePrinterVisitor {
      // (<T S[wq] fa 0 2> (<L S[wq]/(S[dcl]\\NP) Who who WP O I-NP S[wq]/(S[dcl]\\NP)>) (<T S[dcl]\\NP rp 0 2> (<T S[dcl]\\NP ba 0 2> (<T S[dcl]\\NP fa 0 2> (<L (S[dcl]\\NP)/NP is be VBZ O I-VP (S[dcl]\\NP)/NP>) (<T NP ba 0 2> (<T NP[nb] fa 1 2> (<L NP[nb]/N the the DT O I-NP NP[nb]/N>) (<L N leader leader NN O I-NP N>)) (<T NP\\NP fa 0 2> (<L (NP\\NP)/NP of of IN O I-PP (NP\\NP)/NP>) (<T NP lex 0 1> (<L N Libya Libya NNP I-LOC I-NP N>))))) (<T (S\\NP)\\(S\\NP) fa 0 2> (<L ((S\\NP)\\(S\\NP))/NP in in IN O I-PP ((S[X]\\NP)\\(S[X]\\NP))/NP>) (<T NP lex 0 1> (<L N 2011 2011 CD I-DAT I-NP N>)))) (<L . ? ? . O O .>)))

      CCGBankParsePrinterVisitor(StringBuilder result) {
        super(result);
      }

      @Override
      public void visit(SyntaxTreeNodeBinary node)
      {
        result.append("(<T ");
        result.append(node.getCategory().toString());
        result.append(" " + PrologPrinter.getRuleName(node.getRuleType()) + " " + (node.headIsLeft ? "0" : "1") + " 2> ");
        node.leftChild.accept(this);
        node.rightChild.accept(this);

        result.append(") ");

      }

      @Override
      public void visit(SyntaxTreeNodeUnary node)
      {
        result.append("(<T ");
        result.append(node.getCategory().toString());
        result.append(" ");
        result.append(getUnaryRuleName(node.child.getCategory(), node.getCategory()) + " 0 1> ");
        node.child.accept(this);

        result.append(") ");

      }

      @Override
      public void visit(SyntaxTreeNodeLeaf node)
      {
        result.append("(<L ");
        result.append(node.getCategory().toString());
        result.append(" ");
        result.append(CCGBankPrinter.normalize(node.getWord()));
        result.append(" ");
        result.append(MorphaStemmer.stemToken(CCGBankPrinter.normalize(node.getWord()), node.getPos()));

        if (node.getPos() == null) {
          result.append(" NN ");
        } else {
          result.append(" " +node.getPos() + " ");
        }
        result.append(node.getNER());
        result.append(" O "); //ignoring chunking tags
        result.append(node.getCategory().toString());
        result.append(">) ");        
      }
    }

    @Override
    void printHeader(int id, StringBuilder result)
    {
      result.append("ID=" + id + "\n");
    }

    @Override
    void printFooter(StringBuilder result)
    {
    }

    @Override
    void printParse(SyntaxTreeNode parse, int sentenceNumber, StringBuilder result)
    {
      parse.accept(new CCGBankParsePrinterVisitor(result));
    }

    @Override
    void printFileHeader(StringBuilder result)
    {
    }

  }

  public static class DependenciesPrinter extends ParsePrinter {

    @Override
    void printFileHeader(StringBuilder result)
    {
      result.append("Empty header\n");
      result.append("To keep C&C evaluate script happy\n");
      result.append("\n");
    }

    @Override
    void printFailure(StringBuilder result)
    {
    }

    @Override
    void printHeader(int id, StringBuilder result)
    {
    }

    @Override
    void printFooter(StringBuilder result)
    {
    }

    @Override
    void printParse(SyntaxTreeNode parse, int sentenceNumber, StringBuilder result)
    {
      /*
Pierre_1 (N{Y}/N{Y}<1>){_} 1 Vinken_2 0
61_4 (N{Y}/N{Y}<1>){_} 1 years_5 0
old_6 ((S[adj]{_}\NP{Y}<1>){_}\NP{Z}<2>){_} 2 years_5 0
old_6 ((S[adj]{_}\NP{Y}<1>){_}\NP{Z}<2>){_} 1 Vinken_2 6
the_10 (NP[nb]{Y}/N{Y}<1>){_} 1 board_11 0
join_9 ((S[b]{_}\NP{Y}<1>){_}/NP{Z}<2>){_} 2 board_11 0
nonexecutive_14 (N{Y}/N{Y}<1>){_} 1 director_15 0
a_13 (NP[nb]{Y}/N{Y}<1>){_} 1 director_15 0
as_12 (((S[X]{Y}\NP{Z}){Y}\(S[X]{Y}<1>\NP{Z}){Y}){_}/NP{W}<2>){_} 3 director_15 0
as_12 (((S[X]{Y}\NP{Z}){Y}\(S[X]{Y}<1>\NP{Z}){Y}){_}/NP{W}<2>){_} 2 join_9 0
Nov._16 (((S[X]{Y}\NP{Z}){Y}\(S[X]{Y}<1>\NP{Z}){Y}){_}/N[num]{W}<2>){_} 3 29_17 0
Nov._16 (((S[X]{Y}\NP{Z}){Y}\(S[X]{Y}<1>\NP{Z}){Y}){_}/N[num]{W}<2>){_} 2 join_9 0
will_8 ((S[dcl]{_}\NP{Y}<1>){_}/(S[b]{Z}<2>\NP{Y*}){Z}){_} 2 join_9 0
will_8 ((S[dcl]{_}\NP{Y}<1>){_}/(S[b]{Z}<2>\NP{Y*}){Z}){_} 1 Vinken_2 0
join_9 ((S[b]{_}\NP{Y}<1>){_}/NP{Z}<2>){_} 1 Vinken_2 0 ((S[dcl]{X}\NP{Y}<15>){X}/(S[b]{Z}<16>\NP{Y*}){Z}){X}
<c> Pierre|NNP|N/N Vinken|NNP|N ,|,|, 61|CD|N/N years|NNS|N old|JJ|(S[adj]\NP)\NP ,|,|, will|MD|(S[dcl]\NP)/(S[b]\NP) join|VB|(S[b]\NP)/NP the|DT|NP[nb]/N board|NN|N as|IN|((S\NP)\(S\NP))/NP a|DT|NP[nb]/N nonexecutive|JJ|N/N director|NN|N Nov.|NNP|((S\NP)\(S\NP))/N[num] 29|CD|N[num] .|.|.
       */
      String depParse;

      depParse = CCGBankDependencies.getDependenciesAsString(Arrays.asList(parse), sentenceNumber);
      for (String line : depParse.split("\n")) {
        if (!line.startsWith("#") && !line.trim().isEmpty()) {
          result.append(line);
          result.append("\n");  
        }
      }
      result.append("<c>");
      for (SyntaxTreeNodeLeaf word : parse.getWords()) {
        result.append(" " + word.getWord() + "|" + (word.getPos() == null ? "" : word.getPos()) + "|" + word.getCategory());
      }
      result.append("\n");
    }

  }
} public interface Parser
{

  /**
   * Parses a sentence, interpreting the line according to the InputReader, and returns an N-best list.
   */
  public abstract List<SyntaxTreeNode> parse(String line);

  /**
   * Ignores the InputReader and parses the supplied list of words.
   */
  public abstract List<SyntaxTreeNode> parseTokens(List<String> words);

  /**
   * 
   */
  public abstract Iterator<List<SyntaxTreeNode>> parseFile(File file, final SuperTaggingResults results)
      throws IOException;

  public abstract List<SyntaxTreeNode> parseSentence(SuperTaggingResults results, InputToParser input);

  public abstract List<SyntaxTreeNode> doParsing(InputToParser input);

  List<SyntaxTreeNode> parse(SuperTaggingResults results, String line);

  Multimap<Integer, Long> getSentenceLengthToParseTimeInNanos();

  long getParsingTimeOnlyInMillis();

  long getTaggingTimeOnlyInMillis();

} public class ParserAStar implements Parser
{

  public ParserAStar(
      Tagger tagger, int maxSentenceLength, int nbest, double nbestBeam, InputFormat inputFormat, List<String> validRootCategories, 
      File unaryRulesFile,
      File extraCombinatorsFile,
      File seenRulesFile) 
  throws IOException {
    this.tagger = tagger;
    this.maxLength = maxSentenceLength;
    this.nbest = nbest;
    this.nodeFactory = new SyntaxTreeNodeFactory(maxSentenceLength, 0);
    this.reader = InputReader.make(inputFormat, nodeFactory);
    this.unaryRules = loadUnaryRules(unaryRulesFile);
    this.seenRules = new SeenRules(seenRulesFile);
    this.nbestBeam = Math.log(nbestBeam);
    
    List<Combinator> combinators = new ArrayList<Combinator>(Combinator.STANDARD_COMBINATORS);
    
    if (extraCombinatorsFile.exists()) {
      combinators.addAll(Combinator.loadSpecialCombinators(extraCombinatorsFile));
    }
    this.binaryRules = ImmutableList.copyOf(combinators);    
    
    List<Category> cats = new ArrayList<Category>();
    for (String cat : validRootCategories) {
      cats.add(Category.valueOf(cat));
    }
    possibleRootCategories = ImmutableSet.copyOf(cats);
  }
  
  private final int maxLength;
  
  private final Collection<Combinator> binaryRules;
  private final Multimap<Category, Category> unaryRules;
  private final int nbest;
  private final double nbestBeam;
  
  private final Tagger tagger;
  private final SyntaxTreeNodeFactory nodeFactory;

  private final InputReader reader;
  
  private final SeenRules seenRules;

  private final Collection<Category> possibleRootCategories;
  
  // Included to try to help me suck less at log probabilities...
  private final static double CERTAIN = 0.0;
  private final static double IMPOSSIBLE = Double.NEGATIVE_INFINITY;
  
  private final Multimap<Integer, Long> sentenceLengthToParseTimeInNanos = HashMultimap.create();
  
  @Override
  public Multimap<Integer, Long> getSentenceLengthToParseTimeInNanos()
  {
    return sentenceLengthToParseTimeInNanos;
  }

  private final Stopwatch parsingTimeOnly = Stopwatch.createUnstarted();
  private final Stopwatch taggingTimeOnly = Stopwatch.createUnstarted();

  /**
   * Loads file containing unary rules
   */
  private Multimap<Category, Category> loadUnaryRules(File file) throws IOException {
    Multimap<Category, Category> result = HashMultimap.create();
    for (String line : Util.readFile(file)) {
      // Allow comments.
      if (line.indexOf("#") > -1) line = line.substring(0, line.indexOf("#"));
      line = line.trim();
      if (line.isEmpty()) continue;
     
      String[] fields = line.split("\\s+");
      if (fields.length != 2) throw new Error("Expected 2 categories on line in UnaryRule file: " + line);
      result.put(Category.valueOf(fields[0]), Category.valueOf(fields[1]));
    }
    
    return ImmutableMultimap.copyOf(result);
  }


  /* (non-Javadoc)
   * @see uk.ac.ed.easyccg.syntax.ParserInterface#parse(java.lang.String)
   */
  @Override
  public List<SyntaxTreeNode> parse(String line) {
    InputToParser input = reader.readInput(line);
    List<SyntaxTreeNode> parses = doParsing(input);   
    return parses;
  }
  
  /* (non-Javadoc)
   * @see uk.ac.ed.easyccg.syntax.ParserInterface#parse(java.lang.String)
   */
  @Override
  public List<SyntaxTreeNode> parse(SuperTaggingResults results, String line) {
    InputToParser input = reader.readInput(line);
    List<SyntaxTreeNode> parses = parseSentence(results, input);   
    return parses;
  }

  /* (non-Javadoc)
   * @see uk.ac.ed.easyccg.syntax.ParserInterface#parseTokens(java.util.List)
   */
  @Override
  public List<SyntaxTreeNode> parseTokens(List<String> words) {
    InputToParser input = InputToParser.fromTokens(words);
    List<SyntaxTreeNode> parses = doParsing(input);
    
    return parses;
  }
  
  public static class SuperTaggingResults {
    public AtomicInteger parsedSentences = new AtomicInteger();
    public AtomicInteger totalSentences = new AtomicInteger();
    
    public AtomicInteger rightCats = new AtomicInteger();
    public AtomicInteger totalCats = new AtomicInteger();
    
    public AtomicInteger exactMatch = new AtomicInteger();    
  }
  
  /* (non-Javadoc)
   * @see uk.ac.ed.easyccg.syntax.ParserInterface#parseFile(java.io.File, uk.ac.ed.easyccg.syntax.Parser.SuperTaggingResults)
   */
  @Override
  public Iterator<List<SyntaxTreeNode>> parseFile(File file, final SuperTaggingResults results) throws IOException {

    final Iterator<InputToParser> input = reader.readFile(file).iterator();
    return new Iterator<List<SyntaxTreeNode>>() {

      @Override
      public boolean hasNext()
      {
        return input.hasNext();
      }

      @Override
      public List<SyntaxTreeNode> next()
      {
        return parseSentence(results, input.next());
      }

      @Override
      public void remove()
      {
        throw new UnsupportedOperationException();
      }
    };
    
  }

  /* (non-Javadoc)
   * @see uk.ac.ed.easyccg.syntax.ParserInterface#parseSentence(uk.ac.ed.easyccg.syntax.Parser.SuperTaggingResults, uk.ac.ed.easyccg.syntax.InputReader.InputToParser)
   */
  @Override
  public List<SyntaxTreeNode> parseSentence(SuperTaggingResults results,
      InputToParser input)
  {
    results.totalSentences.incrementAndGet();

    if (input.length() >= maxLength) {
      System.err.println("Skipping sentence of length " + input.length());
      return null;
    }
    
    List<SyntaxTreeNode> parses = doParsing(input);
    
    if (parses != null) {
      results.parsedSentences.incrementAndGet();

      if (input.haveGoldCategories()) {
        List<Category> gold = input.getGoldCategories();
        
        int bestCorrect = -1;

        for (SyntaxTreeNode parse : parses) {
          List<Category> supertags = getSupertags(parse);
          int correct = countCorrect(gold, supertags);
          if (correct > bestCorrect) {
            bestCorrect = correct;
          }
        }
        
        results.rightCats.addAndGet(bestCorrect);
        results.totalCats.addAndGet(gold.size());
        
        if (bestCorrect == gold.size()) {
          results.exactMatch.incrementAndGet();
        }
      }

    } else {
      System.err.println("FAILED TO PARSE! " + input.getWordsAsString());
    }
    return parses;
  }

  /* (non-Javadoc)
   * @see uk.ac.ed.easyccg.syntax.ParserInterface#doParsing(uk.ac.ed.easyccg.syntax.InputReader.InputToParser)
   */
  @Override
  public List<SyntaxTreeNode> doParsing(InputToParser input)
  {
    if (input.length() > maxLength) {
      System.err.println("Skipping sentence of length " + input.length());
      return null;
    }
    
    Stopwatch stopWatch = Stopwatch.createStarted();
    
    List<List<SyntaxTreeNodeLeaf>> supertags;
    
    if (input.isAlreadyTagged()) {
      supertags = input.getInputSupertags();
    } else {
      try{
        taggingTimeOnly.start();
        supertags = tagger.tag(input.getInputWords());
      } finally {
        taggingTimeOnly.stop();
      }
    }
    
    try{
      parsingTimeOnly.start();
      List<SyntaxTreeNode> parses = parseAstar(supertags);
      return parses;
    } finally {
      parsingTimeOnly.stop();
      stopWatch.stop();    
      sentenceLengthToParseTimeInNanos.put(input.length(), stopWatch.elapsed(TimeUnit.NANOSECONDS));
    }
  }

  
  private int countCorrect(List<Category> gold, List<Category> predicted)
  {
    int rightCats = 0;
    for (int i=0; i<gold.size(); i++) {
      if (predicted.get(i).equals(gold.get(i))) {
        rightCats++;
      }
    }
    return rightCats;
  }


  static class AgendaItem implements Comparable<AgendaItem> {
    private final SyntaxTreeNode parse;
    AgendaItem(SyntaxTreeNode parse, double outsideProbabilityUpperBound, int startOfSpan, int spanLength)
    {
      this.parse = parse;
      this.startOfSpan = startOfSpan;
      this.spanLength = spanLength;
      this.cost = parse.probability + outsideProbabilityUpperBound;
      
    }
    private final int startOfSpan;
    private final int spanLength;
    private final double cost;
    
    /**
     * Comparison function used to order the agenda.
     */
    @Override
    public int compareTo(AgendaItem o)
    {
      int result = Double.compare(o.cost, cost);
      
      if (result != 0 && Math.abs(o.cost - cost) < 0.0000001) {
        // Allow some tolerance on comparisons of Doubles.
        result = 0;
      }
      
      if (result == 0) {
        // All other things being equal, it works best to prefer parser with longer dependencies (i.e. non-local attachment).
        return parse.totalDependencyLength - o.parse.totalDependencyLength;
      } else {
        return result;
      }
    }
  } 

  /**
   * Takes supertagged input and returns a set of parses.
   * 
   * Returns null if the parse fails.
   */
  private List<SyntaxTreeNode> parseAstar(List<List<SyntaxTreeNodeLeaf>> supertags) {

    final int sentenceLength = supertags.size();
    final PriorityQueue<AgendaItem> agenda = new PriorityQueue<ParserAStar.AgendaItem>();
    final ChartCell[][] chart = new ChartCell[sentenceLength][sentenceLength];

    final double[][] outsideProbabilitiesUpperBound = computeOutsideProbabilities(supertags);
    
    
    for (int word = 0; word < sentenceLength; word++) {
      for (SyntaxTreeNode entry : supertags.get(word)) {
        agenda.add(new AgendaItem(entry, outsideProbabilitiesUpperBound[word][word + 1], word, 1));
      }
    }
        
   
    while (chart[0][sentenceLength - 1] == null || 
           (chart[0][sentenceLength - 1].getEntries().size() < nbest 
           && agenda.peek() != null && agenda.peek().cost > chart[0][sentenceLength - 1].bestValue + nbestBeam
           )) {
      // Add items from the agenda, until we have enough parses.
      
      final AgendaItem agendaItem = agenda.poll();
      if (agendaItem == null) {
        break ;
      }
      
      // Try to put an entry in the chart.
      ChartCell cell = chart[agendaItem.startOfSpan][agendaItem.spanLength - 1];
      if (cell == null) {
        cell = nbest > 1 ? new CellNBest() : new Cell1Best();
        chart[agendaItem.startOfSpan][agendaItem.spanLength - 1] = cell;
      }

      
      if (cell.add(agendaItem.parse)) {
        // If a new entry was added, update the agenda.

        //See if any Unary Rules can be applied to the new entry.
        for (Category unaryRuleProduction : unaryRules.get(agendaItem.parse.getCategory())) {
          if (agendaItem.spanLength == sentenceLength) {
            break ;
          }
          
          agenda.add(new AgendaItem(nodeFactory.makeUnary(unaryRuleProduction, agendaItem.parse), 
              outsideProbabilitiesUpperBound[agendaItem.startOfSpan][agendaItem.startOfSpan + agendaItem.spanLength],                             
              agendaItem.startOfSpan, agendaItem.spanLength));
        }
        
        // See if the new entry can be the left argument of any binary rules.
        for (int spanLength = agendaItem.spanLength + 1; spanLength < 1 + sentenceLength - agendaItem.startOfSpan; spanLength++) {
          SyntaxTreeNode leftEntry = agendaItem.parse;
          ChartCell rightCell = chart[agendaItem.startOfSpan + agendaItem.spanLength][spanLength - agendaItem.spanLength - 1];
          if (rightCell == null) continue ;
          for (SyntaxTreeNode rightEntry : rightCell.getEntries()) {
            updateAgenda(agenda, agendaItem.startOfSpan, spanLength, leftEntry, rightEntry, sentenceLength, outsideProbabilitiesUpperBound[agendaItem.startOfSpan][agendaItem.startOfSpan + spanLength]);
          }
        }
        
        // See if the new entry can be the right argument of any binary rules.
        for (int startOfSpan = 0; startOfSpan < agendaItem.startOfSpan; startOfSpan++) {
          int spanLength = agendaItem.startOfSpan + agendaItem.spanLength - startOfSpan; 
          SyntaxTreeNode rightEntry = agendaItem.parse;
          ChartCell leftCell = chart[startOfSpan][spanLength - agendaItem.spanLength - 1];
          if (leftCell == null) continue ;
          for (SyntaxTreeNode leftEntry : leftCell.getEntries()) {
            updateAgenda(agenda, startOfSpan, spanLength, leftEntry, rightEntry, sentenceLength, outsideProbabilitiesUpperBound[startOfSpan][startOfSpan + spanLength]);
          }
        }
      }      
    }

    if (chart[0][sentenceLength - 1] == null) {
      // Parse failure.
      return null;
    }
    
    // Read the parses out of the final cell.
    List<SyntaxTreeNode> parses = new ArrayList<SyntaxTreeNode>(chart[0][sentenceLength - 1].getEntries());
    
    // Sort the parses by probability.
    Collections.sort(parses);
    
    return parses;

  }

  /**
   * Computes an upper bound on the outside probabilities of a span, for use as a heuristic in A*.
   * The upper bound is simply the product of the probabilities for the most probable supertag for 
   * each word outside the span.
   */
  private double[][] computeOutsideProbabilities(List<List<SyntaxTreeNodeLeaf>> supertags)
  {
    int sentenceLength = supertags.size();
    final double[][] outsideProbability = new double[sentenceLength + 1][sentenceLength + 1];
    
    final double[] fromLeft = new double[sentenceLength + 1];
    final double[] fromRight = new double[sentenceLength + 1];

    
    fromLeft[0] = CERTAIN;
    fromRight[sentenceLength] = CERTAIN;
        
    for (int i=0 ; i<sentenceLength - 1; i++) {
      int j = sentenceLength - i;
      // The supertag list for words is sorted, so the most probably entry is at index 0.
      fromLeft[i + 1] = fromLeft[i] + supertags.get(i).get(0).probability;
      fromRight[j - 1] = fromRight[j] + supertags.get(j - 1).get(0).probability;
    }
    
    for (int i=0; i<sentenceLength+1; i++) {
      for (int j=i; j<sentenceLength + 1; j++) {
        outsideProbability[i][j] = fromLeft[i] + fromRight[j];
      }
    }
    
    return outsideProbability;
  }

  /**
   * Updates the agenda with the result of all combinators that can be applied to leftChild and rightChild.
   */
  private void updateAgenda(
      final PriorityQueue<AgendaItem> agenda, 
      final int startOfSpan,
      final int spanLength,
      final SyntaxTreeNode leftChild, 
      final SyntaxTreeNode rightChild, 
      final int sentenceLength, 
      double outsideProbabilityUpperBound)
  {

    if (!seenRules.isSeen(leftChild.getCategory(), rightChild.getCategory())) {
      return;
    }
    
    for (RuleProduction production : getRules(leftChild.getCategory(), rightChild.getCategory())) {
      if ((leftChild.getRuleType() == RuleType.FC || leftChild.getRuleType() == RuleType.GFC) && 
          (production.ruleType == RuleType.FA || production.ruleType == RuleType.FC || production.ruleType == RuleType.GFC)) {
        // Eisner normal form constraint.
        continue;
      } else if ((rightChild.getRuleType() == RuleType.BX || leftChild.getRuleType() == RuleType.GBX) && 
                (production.ruleType == RuleType.BA || production.ruleType == RuleType.BX || leftChild.getRuleType() == RuleType.GBX)) {
        // Eisner normal form constraint.
        continue;
      } else if (leftChild.getRuleType() == RuleType.UNARY && 
                 production.ruleType == RuleType.FA && leftChild.getCategory().isForwardTypeRaised()) {
        // Hockenmaier normal form constraint.
        continue;
      } else if (rightChild.getRuleType() == RuleType.UNARY && 
                 production.ruleType == RuleType.BA && rightChild.getCategory().isBackwardTypeRaised()) {
        // Hockenmaier normal form constraint.
        continue;
      }else if (spanLength == sentenceLength && !possibleRootCategories.contains(production.category)) {
        // Enforce that the root node must have one of a pre-specified list of categories.
        continue ;
      } else {
        agenda.add(new AgendaItem(
            nodeFactory.makeBinary(production.category, leftChild, rightChild, production.ruleType, production.headIsLeft),
            outsideProbabilityUpperBound, startOfSpan, spanLength));
      }
    }
  }
  
  private final Map<Category, Map<Category, Collection<RuleProduction>>> ruleCache = new HashMap<Category, Map<Category, Collection<RuleProduction>>>();
  /**
   * Returns the set of binary rule productions between these two categories.
   */
  private Collection<RuleProduction> getRules(Category left, Category right) {
    Map<Category, Collection<RuleProduction>> rightToRules = ruleCache.get(left);
    if (rightToRules == null) {
      rightToRules = new HashMap<Category, Collection<RuleProduction>>();
      ruleCache.put(left, rightToRules);
    }
  
    Collection<RuleProduction> result = rightToRules.get(right);
    if (result == null) {
      result = Combinator.getRules(left, right, binaryRules);
      rightToRules.put(right, ImmutableList.copyOf(result));
    } 
    
    return result;
  }
  
  /**
   * Converts a parse into a list of supercategories.
   */
  
  private static List<Category> getSupertags(SyntaxTreeNode parse)
  {
    GetSupertagsVisitor v = new GetSupertagsVisitor();
    parse.accept(v);
    return v.result;
  }

  @Override
  public long getParsingTimeOnlyInMillis()
  {
    return parsingTimeOnly.elapsed(TimeUnit.MILLISECONDS);
  }

  @Override
  public long getTaggingTimeOnlyInMillis()
  {
    return taggingTimeOnly.elapsed(TimeUnit.MILLISECONDS);
  }
  
  private static class GetSupertagsVisitor implements SyntaxTreeNodeVisitor {
    List<Category> result = new ArrayList<Category>();

    @Override
    public void visit(SyntaxTreeNodeBinary node)
    {
      node.leftChild.accept(this);
      node.rightChild.accept(this);
    }

    @Override
    public void visit(SyntaxTreeNodeUnary node)
    {
      node.child.accept(this);
    }

    @Override
    public void visit(SyntaxTreeNodeLeaf node)
    {
      result.add(node.getCategory());
    }
  }



  /**
   * Chart Cell used for N-best parsing. It allows multiple entries with the same category, if they are not equivalent.
   */
  private class CellNBest extends ChartCell {
    private final Table<Category, Integer, SyntaxTreeNode> keyToProbability= HashBasedTable.create();
    public Collection<SyntaxTreeNode> getEntries() {
      return keyToProbability.values();
    }
    @Override
    void addEntry(Category category, int hash, SyntaxTreeNode newEntry)
    {
      keyToProbability.put(category, hash, newEntry);
    }
    @Override
    boolean isFull(Category category, int hash)
    {
      return keyToProbability.row(category).size() == nbest || keyToProbability.contains(category, hash);
    }
    @Override
    SyntaxTreeNode getEntry(Category category, int hash)
    {
      return keyToProbability.get(category, hash);
    }
  }

  /**
   * Chart Cell used for 1-best parsing.
   */
  private static class Cell1Best extends ChartCell {
    private final Map<Category, SyntaxTreeNode> keyToProbability = new HashMap<Category, SyntaxTreeNode>();
    public Collection<SyntaxTreeNode> getEntries() {
      return keyToProbability.values();
    }
    @Override
    void addEntry(Category category, int hash, SyntaxTreeNode newEntry)
    {
      keyToProbability.put(category, newEntry);
    }
    @Override
    boolean isFull(Category category, int hash)
    {
      return keyToProbability.containsKey(category);
    }
    @Override
    SyntaxTreeNode getEntry(Category category, int hash)
    {
      return keyToProbability.get(category);
    }
  }
  
  private static abstract class ChartCell {
    private double bestValue = IMPOSSIBLE;

    public ChartCell() {}
    /**
     * Possibly adds a @CellEntry to this chart cell. Returns true if the parse was added, and false if the cell was unchanged. 
     */
    public boolean add(SyntaxTreeNode entry)    
    {
      // See if the cell already has enough parses with this category.
      // All existing entries are guaranteed to have a higher probability
      if (isFull(entry.getCategory(), entry.hash)) {
        return false;
      } else {
        addEntry(entry.getCategory(), entry.hash, entry);
        
        if (entry.probability > bestValue) {
          bestValue = entry.probability;
        }
        
        return true;
      }
    }
    
    abstract boolean isFull(Category category, int hash);
    public abstract Collection<SyntaxTreeNode> getEntries();
    abstract void addEntry(Category category, int hash, SyntaxTreeNode newEntry);
    abstract SyntaxTreeNode getEntry(Category category, int hash);

  }
  

  /**
   * Handles filtering rules by CCGBank category combination.
   */
  class SeenRules {
    private Map<Category, Category> simplify = new HashMap<Category, Category>();
    private Category simplify(Category input) {
      Category result = simplify.get(input);
      if (result == null) {
        // Simplify categories for compatibility with the C&C rules file.
        result = Category.valueOf(input.toString().replaceAll("\\[X\\]", "").replaceAll("\\[nb\\]", ""));
        simplify.put(input, result);
      }

      return result;
    }

    private final boolean[][] seen;
    private final int numberOfSeenCategories;
    boolean isSeen(Category left, Category right) {
      if (seen == null) return true;
      left = simplify(left);
      right = simplify(right);
      return left.getID() < numberOfSeenCategories && right.getID() < numberOfSeenCategories && 
             seen[left.getID()][right.getID()];
    }
    
    private SeenRules(File file) throws IOException {   
      if (file == null) {
        seen = null;
        numberOfSeenCategories = 0;
      } else if (!file.exists()) {
        System.err.println("No 'seenRules' file available for model. Allowing all CCG-legal rules.");
        seen = null;
        numberOfSeenCategories = 0;
      } else {
        Table<Category, Category, Boolean> tab = HashBasedTable.create();
        int maxID = 0;
        for (String line : Util.readFile(file)) {
          // Assumes the file has the format:
          // cat1 cat2
          if (!line.startsWith("#") && !line.isEmpty()) {
            String[] fields = line.split(" ");
            Category left = Category.valueOf(fields[0]);
            Category right = Category.valueOf(fields[1]);
            maxID = Math.max(left.getID(), maxID);
            maxID = Math.max(right.getID(), maxID);
            tab.put(simplify(left), simplify(right), true);
          }
        }
        
        seen = new boolean[maxID + 1][maxID + 1];
        for (Cell<Category, Category, Boolean> entry : tab.cellSet()) {
          seen[entry.getRowKey().getID()][entry.getColumnKey().getID()] = true;
        }
        numberOfSeenCategories = seen.length;
      }
    }
  }
} public static class SuperTaggingResults {
  public AtomicInteger parsedSentences = new AtomicInteger();
  public AtomicInteger totalSentences = new AtomicInteger();
    
  public AtomicInteger rightCats = new AtomicInteger();
  public AtomicInteger totalCats = new AtomicInteger();
    
  public AtomicInteger exactMatch = new AtomicInteger();    
} public abstract class SyntaxTreeNode implements Comparable<SyntaxTreeNode> {
  
  private final Category category;
  final double probability;
  final int hash;
  final int totalDependencyLength;
  private final int headIndex;
  
  abstract SyntaxTreeNodeLeaf getHead();
  
  private SyntaxTreeNode(
      Category category, 
      double probability, 
      int hash, 
      int totalDependencyLength,
      int headIndex
      )
  {
    this.category = category;
    this.probability = probability;
    this.hash = hash;
    this.totalDependencyLength = totalDependencyLength;
    this.headIndex = headIndex;
  }
  
  static class SyntaxTreeNodeBinary extends SyntaxTreeNode {
    final RuleType ruleType;
    final boolean headIsLeft;
    final SyntaxTreeNode leftChild;
    final SyntaxTreeNode rightChild;
    private SyntaxTreeNodeBinary(Category category, double probability, int hash, int totalDependencyLength, int headIndex,
        RuleType ruleType, boolean headIsLeft, SyntaxTreeNode leftChild, SyntaxTreeNode rightChild)
    {
      super(category, probability, hash, totalDependencyLength, headIndex);
      this.ruleType = ruleType;
      this.headIsLeft = headIsLeft;
      this.leftChild = leftChild;
      this.rightChild = rightChild;
    }
    @Override
    void accept(SyntaxTreeNodeVisitor v)
    {
      v.visit(this);
    }
    @Override
    public RuleType getRuleType()
    {
      return ruleType;
    }
    @Override
    public List<SyntaxTreeNode> getChildren()
    {
      return Arrays.asList(leftChild, rightChild);
    }
    @Override
    SyntaxTreeNodeLeaf getHead()
    {
      return headIsLeft ? leftChild.getHead() : rightChild.getHead();
    }
    @Override
    int dimension()
    {
      int left = leftChild.dimension();
      int right = rightChild.dimension();
      if (left == right) {
        return 1 + left;
      } else {
        return Math.max(left, right);
      }
      
      
    }
    
  }
  
  public static class SyntaxTreeNodeLeaf extends SyntaxTreeNode {
    private SyntaxTreeNodeLeaf(
        String word, String pos, String ner, 
        Category category, double probability, int hash, int totalDependencyLength, int headIndex
        )
    {
      super(category, probability, hash, totalDependencyLength, headIndex);
      this.pos = pos;
      this.ner = ner;
      this.word = word;
    }
    private final String pos;
    private final String ner;
    private final String word;    
    @Override
    void accept(SyntaxTreeNodeVisitor v)
    {
      v.visit(this);
    }
    @Override
    public RuleType getRuleType()
    {
      return RuleType.LEXICON;
    }
    @Override
    public List<SyntaxTreeNode> getChildren()
    {
      return Collections.emptyList();
    }
    
    @Override
    public boolean isLeaf()
    {
      return true;
    }
    
    @Override
    void getWords(List<SyntaxTreeNodeLeaf> result) {
      result.add(this);
    }
    public String getPos()
    {
      return pos;
    }
    public String getNER()
    {
      return ner;
    }
    public String getWord()
    {
      return word;
    }
    @Override
    SyntaxTreeNodeLeaf getHead()
    {
      return this;
    }
    @Override
    int dimension()
    {
      return 0;
    }
    public int getSentencePosition()
    {
      return getHeadIndex();
    }
  }
  
  static class SyntaxTreeNodeUnary extends SyntaxTreeNode {
    private SyntaxTreeNodeUnary(Category category, double probability, int hash, int totalDependencyLength, int headIndex, SyntaxTreeNode child)
    {
      super(category, probability, hash, totalDependencyLength, headIndex);

      this.child = child;
    }

    final SyntaxTreeNode child;

    @Override
    void accept(SyntaxTreeNodeVisitor v)
    {
      v.visit(this);
    }

    @Override
    public RuleType getRuleType()
    {
      return RuleType.UNARY;
    }

    @Override
    public List<SyntaxTreeNode> getChildren()
    {
      return Arrays.asList(child);
    }

    @Override
    SyntaxTreeNodeLeaf getHead()
    {
      return child.getHead();
    }

    @Override
    int dimension()
    {
      return child.dimension();
    }
  }

  public String toString() {
    return ParsePrinter.CCGBANK_PRINTER.print(this, -1);
  }
  
  abstract int dimension();
  
  public int getHeadIndex() {
    return headIndex;
  }
  
  @Override
  public int compareTo(SyntaxTreeNode o)
  {
    return Double.compare(o.probability, probability); 
  }
  
  /**
   * Factory for SyntaxTreeNode. Using a factory so we can have different hashing/caching behaviour when N-best parsing.
   */
  public static class SyntaxTreeNodeFactory {
    private final int[][] categoryHash;
    private final int[][] dependencyHash;
    private final boolean hashWords;
    
    /**
     * These parameters are needed so that it can pre-compute some hash values. 
     * @param maxSentenceLength
     * @param numberOfLexicalCategories
     */
    public SyntaxTreeNodeFactory(int maxSentenceLength, int numberOfLexicalCategories) {
      
      hashWords = numberOfLexicalCategories > 0;
      categoryHash = makeRandomArray(maxSentenceLength, numberOfLexicalCategories + 1);
      dependencyHash = makeRandomArray(maxSentenceLength, maxSentenceLength);
    }

    private int[][] makeRandomArray(int x, int y) {
      Random random = new Random();
      int[][] result = new int[x][y];  
      for (int i=0; i<x; i++) {
        for (int j=0; j<y; j++) {
          result[i][j] = random.nextInt();
        }
      }
      
      return result;
    }
    
    public SyntaxTreeNodeLeaf makeTerminal(String word, Category category, String pos, String ner, double probability, int sentencePosition) {
      return new SyntaxTreeNodeLeaf(
          word, pos, ner, category, probability, 
          hashWords ? categoryHash[sentencePosition][category.getID()] : 0, 0, sentencePosition);
    }
    
    public SyntaxTreeNode makeUnary(Category category, SyntaxTreeNode child) {
      return new SyntaxTreeNodeUnary(category, child.probability, child.hash, child.totalDependencyLength, child.getHeadIndex(), child);
    }
    
    public SyntaxTreeNode makeBinary(Category category, SyntaxTreeNode left, SyntaxTreeNode right, RuleType ruleType, boolean headIsLeft) {
      
      int totalDependencyLength = (right.getHeadIndex() - left.getHeadIndex())
                                  + left.totalDependencyLength + right.totalDependencyLength;

      int hash;
      if (right.getCategory().isPunctuation()) {
        // Ignore punctuation when calculating the hash, because we don't really care where a full-stop attaches.
        hash = left.hash;
      } else if (left.getCategory().isPunctuation()) {
        // Ignore punctuation when calculating the hash, because we don't really care where a full-stop attaches.
        hash = right.hash;
      } else {
        // Combine the hash codes in a commutive way, so that left and right branching derivations can still be equivalent.
        hash = left.hash ^ right.hash ^ dependencyHash[left.getHeadIndex()][right.getHeadIndex()];
      }
      
      SyntaxTreeNode result = new SyntaxTreeNodeBinary(
          category, 
          left.probability + right.probability, // log probabilities 
          hash,  
          totalDependencyLength,
          headIsLeft ? left.getHeadIndex() : right.getHeadIndex(),
          ruleType, 
          headIsLeft,
          left, 
          right);
      
      
      return result;
    }      
  }

  abstract void accept(SyntaxTreeNodeVisitor v);
  
  public interface SyntaxTreeNodeVisitor {
    void visit(SyntaxTreeNodeBinary node);
    void visit(SyntaxTreeNodeUnary node);
    void visit(SyntaxTreeNodeLeaf node);
  }

  public abstract RuleType getRuleType();

  public abstract List<SyntaxTreeNode> getChildren();

  public boolean isLeaf()
  {
    return false;
  }

  /**
   * Returns all the terminal nodes in the sentence, from left to right. 
   */
  public List<SyntaxTreeNodeLeaf> getWords()
  {
    List<SyntaxTreeNodeLeaf> result = new ArrayList<SyntaxTreeNodeLeaf>();
    getWords(result);
    return result;
  }
  
  void getWords(List<SyntaxTreeNodeLeaf> result) {
    for (SyntaxTreeNode child : getChildren()) {
      child.getWords(result);
    }
  }

  public Category getCategory()
  {
    return category;
  }
} public static class SyntaxTreeNodeFactory {
  private final int[][] categoryHash;
  private final int[][] dependencyHash;
  private final boolean hashWords;
    
  /**
   * These parameters are needed so that it can pre-compute some hash values. 
   * @param maxSentenceLength
   * @param numberOfLexicalCategories
   */
  public SyntaxTreeNodeFactory(int maxSentenceLength, int numberOfLexicalCategories) {
      
    hashWords = numberOfLexicalCategories > 0;
    categoryHash = makeRandomArray(maxSentenceLength, numberOfLexicalCategories + 1);
    dependencyHash = makeRandomArray(maxSentenceLength, maxSentenceLength);
  }

  private int[][] makeRandomArray(int x, int y) {
    Random random = new Random();
    int[][] result = new int[x][y];  
    for (int i=0; i<x; i++) {
      for (int j=0; j<y; j++) {
        result[i][j] = random.nextInt();
      }
    }
      
    return result;
  }
    
  public SyntaxTreeNodeLeaf makeTerminal(String word, Category category, String pos, String ner, double probability, int sentencePosition) {
    return new SyntaxTreeNodeLeaf(
        word, pos, ner, category, probability, 
        hashWords ? categoryHash[sentencePosition][category.getID()] : 0, 0, sentencePosition);
  }
    
  public SyntaxTreeNode makeUnary(Category category, SyntaxTreeNode child) {
    return new SyntaxTreeNodeUnary(category, child.probability, child.hash, child.totalDependencyLength, child.getHeadIndex(), child);
  }
    
  public SyntaxTreeNode makeBinary(Category category, SyntaxTreeNode left, SyntaxTreeNode right, RuleType ruleType, boolean headIsLeft) {
      
    int totalDependencyLength = (right.getHeadIndex() - left.getHeadIndex())
                                + left.totalDependencyLength + right.totalDependencyLength;

    int hash;
    if (right.getCategory().isPunctuation()) {
      // Ignore punctuation when calculating the hash, because we don't really care where a full-stop attaches.
      hash = left.hash;
    } else if (left.getCategory().isPunctuation()) {
      // Ignore punctuation when calculating the hash, because we don't really care where a full-stop attaches.
      hash = right.hash;
    } else {
      // Combine the hash codes in a commutive way, so that left and right branching derivations can still be equivalent.
      hash = left.hash ^ right.hash ^ dependencyHash[left.getHeadIndex()][right.getHeadIndex()];
    }
      
    SyntaxTreeNode result = new SyntaxTreeNodeBinary(
        category, 
        left.probability + right.probability, // log probabilities 
        hash,  
        totalDependencyLength,
        headIsLeft ? left.getHeadIndex() : right.getHeadIndex(),
        ruleType, 
        headIsLeft,
        left, 
        right);
      
      
    return result;
  }      
} public class TagDict
{

  private static final int MIN_OCCURENCES_OF_WORD = 500;
  /**
   * Key used in the tag dictionary for infrequent words
   */
  public static final String OTHER_WORDS = "*other_words*";
  private final static String fileName = "tagdict";
  
  /**
   * Saves a tag dictionary to the model folder
   */
  public static void writeTagDict(Map<String, Collection<Category>> tagDict, File modelFolder) throws FileNotFoundException, UnsupportedEncodingException {
    PrintWriter writer = new PrintWriter(new File(modelFolder, fileName), "UTF-8");
    for (java.util.Map.Entry<String, Collection<Category>> entry : tagDict.entrySet()) {
      writer.print(entry.getKey());
      for (Category c : entry.getValue()) {
        writer.print("\t" + c.toString());
      }
      writer.println();
    }
    
    writer.close();
  }
  
  /**
   * Loads a tag dictionary from the model folder
   */
  public static Map<String, Collection<Category>> readDict(File modelFolder) throws IOException {
    Map<String, Collection<Category>> result = new HashMap<String, Collection<Category>>();
    File file = new File(modelFolder, fileName);
    if (!file.exists()) return null;
    for (String line : Util.readFile(file)) {
      String[] fields = line.split("\t");
      List<Category> cats = new ArrayList<Category>();
      for (int i=1; i<fields.length; i++) {
        cats.add(Category.valueOf(fields[i]));        
      }
      result.put(fields[0], ImmutableSet.copyOf(cats));
    }
    
    return ImmutableMap.copyOf(result);
  }
  
  private final static Comparator<Entry<Category>> comparator = new Comparator<Entry<Category>>()
  {
    @Override
    public int compare(Entry<Category> arg0, Entry<Category> arg1)
    {
      return arg1.getCount() - arg0.getCount();
    }
  };
  
  /**
   * Finds the set of categories used for each word in a corpus
   */
  public static Map<String, Collection<Category>> makeDict(Iterable<InputToParser> input) {
    Multiset<String> wordCounts = HashMultiset.create();
    Map<String, Multiset<Category>> wordToCatToCount = new HashMap<String, Multiset<Category>>();
    
    // First, count how many times each word occurs with each category
    for (InputToParser sentence : input) {
      for (int i=0; i<sentence.getInputWords().size(); i++) {
        String word = sentence.getInputWords().get(i).word;
        Category cat = sentence.getGoldCategories().get(i);
        wordCounts.add(word);
        
        if (!wordToCatToCount.containsKey(word)) {
          Multiset<Category> tmp = HashMultiset.create();
          wordToCatToCount.put(word, tmp);
        }

        wordToCatToCount.get(word).add(cat);
      }
    }
    

    // Now, save off a sorted list of categories
    Multiset<Category> countsForOtherWords = HashMultiset.create();
    
    Map<String, Collection<Category>> result = new HashMap<String, Collection<Category>>();
    for (Entry<String> wordAndCount : wordCounts.entrySet()) {
      Multiset<Category> countForCategory = wordToCatToCount.get(wordAndCount.getElement());
      if (wordAndCount.getCount() > MIN_OCCURENCES_OF_WORD) {
        // Frequent word
        addEntryForWord(countForCategory, result, wordAndCount.getElement());
      } else {
        // Group stats for all rare words together.
        
        for (Entry<Category> catToCount : countForCategory.entrySet()) {
          countsForOtherWords.add(catToCount.getElement(), catToCount.getCount());
        }
      }
    }
    addEntryForWord(countsForOtherWords, result, OTHER_WORDS);


    return ImmutableMap.copyOf(result);
  }

  private static void addEntryForWord(Multiset<Category> countForCategory,
      Map<String, Collection<Category>> result, String word)
  {
    List<Entry<Category>> cats = new ArrayList<Entry<Category>>();
    for (Entry<Category> catToCount : countForCategory.entrySet()) {
      cats.add(catToCount);
    }
    
    Collections.sort(cats, comparator);
    List<Category> cats2 = new ArrayList<Category>();
        
    for (Entry<Category> entry : cats) {
      cats2.add(entry.getElement());
    }
    
    result.put(word, cats2);
  }
} public class TaggerEmbeddings extends Tagger
{
  private final Matrix weightMatrix;
  private final Vector bias;

  private final Map<String, double[]> discreteFeatures;
  private final Map<String, double[]> embeddingsFeatures;

  private final List<Category> lexicalCategories;

  private final int totalFeatures;
  
  /**
   * Number of words forward/backward to use as context (so a value of 3 means the tagger looks at 3+3+1=7 words).
   */
  private final int contextWindow = 3;

  // Special words used in the embeddings tables.
  private final static String leftPad="*left_pad*";
  private final static String rightPad="*right_pad*";
  private final static String unknownLower="*unknown_lower*";
  private final static String unknownUpper="*unknown_upper*";
  private final static String unknownSpecial="*unknown_special*";

  private static final String capsLower = "*lower_case*";
  private static final String capsUpper = "*upper_case*";
  private final static String capitalizedPad="*caps_pad*";
  private final static String suffixPad="*suffix_pad*";
  private final static String unknownSuffix="*unknown_suffix*";

  /**
   * Indices for POS-tags, if using them as features.
   */
  private final Map<String, Integer> posFeatures;

  /**
   * Indices for specific words, if using them as features.
   */
  private final Map<String, Integer> lexicalFeatures;

  private final List<Vector> weightMatrixRows;

  /**
   * Number of supertags to consider for each word. Choosing 50 means it's effectively unpruned,
   * but saves us having to sort the complete list of categories.
   */
  private final int maxTagsPerWord;

  /**
   * Pruning parameter. Supertags whose probability is less than beta times the highest-probability
   * supertag are ignored.
   */
  private final double beta;
  
  private final SyntaxTreeNodeFactory terminalFactory;
  private final Map<String, Collection<Integer>> tagDict;


  public TaggerEmbeddings(File modelFolder, int maxSentenceLength, double beta, int maxTagsPerWord) {
    try {
      FilenameFilter embeddingsFileFilter = new PatternFilenameFilter("embeddings.*");

      // If we're using POS tags or lexical features, load l.
      this.posFeatures = loadSparseFeatures(new File(modelFolder + "/postags"));     
      this.lexicalFeatures = loadSparseFeatures(new File(modelFolder + "/frequentwords"));     
      
      // Load word embeddings.
      embeddingsFeatures = loadEmbeddings(true, modelFolder.listFiles(embeddingsFileFilter));
      
      // Load embeddings for capitalization and suffix features.
      discreteFeatures = new HashMap<String, double[]>();
      discreteFeatures.putAll(loadEmbeddings(false, new File(modelFolder, "capitals")));
      discreteFeatures.putAll(loadEmbeddings(false, new File(modelFolder, "suffix")));
      totalFeatures = 
        (embeddingsFeatures.get(unknownLower).length + 
            discreteFeatures.get(unknownSuffix).length + 
            discreteFeatures.get(capsLower).length +
            posFeatures.size()  + lexicalFeatures.size())       * (2 * contextWindow + 1);
      
      // Load the list of categories used by the model.
      lexicalCategories = loadCategories(new File(modelFolder, "categories"));
      
      // Load the weight matrix used by the classifier.
      weightMatrix = new DenseMatrix(lexicalCategories.size(), totalFeatures);
      loadMatrix(weightMatrix, new File(modelFolder, "classifier"));

      weightMatrixRows = new ArrayList<Vector>(lexicalCategories.size());
      for (int i=0; i<lexicalCategories.size(); i++) {
        Vector row = new DenseVector(totalFeatures);
        for (int j=0; j<totalFeatures; j++) {
          row.set(j, weightMatrix.get(i, j));
        }
        weightMatrixRows.add(row);
      }

      bias = new DenseVector(lexicalCategories.size());
      this.beta = beta;
      this.maxTagsPerWord = maxTagsPerWord;

      int maxCategoryID = 0;
      for (Category c : lexicalCategories) {
        maxCategoryID = Math.max(maxCategoryID, c.getID());
      }
      
      this.tagDict = ImmutableMap.copyOf(loadTagDictionary(modelFolder));
      
      terminalFactory = new SyntaxTreeNodeFactory(maxSentenceLength, maxCategoryID);
      loadVector(bias, new File(modelFolder, "bias"));

    }
    catch (Exception e) {
      throw new RuntimeException(e);
    }
  }

  public Map<String, Collection<Integer>> loadTagDictionary(File modelFolder) throws IOException
  {
    Map<Category, Integer> catToIndex = new HashMap<Category, Integer>();

    int index = 0;
    for (Category c : lexicalCategories) {
      catToIndex.put(c, index);
      index++;
    }
    
    // Load a tag dictionary
    Map<String, Collection<Category>> dict = TagDict.readDict(modelFolder);
    Map<String, Collection<Integer>> tagDict = new HashMap<String, Collection<Integer>>();
    if (dict == null) {
      dict = new HashMap<String, Collection<Category>>();
      dict.put(TagDict.OTHER_WORDS, lexicalCategories);
    }
    for (Entry<String, Collection<Category>> entry : dict.entrySet()) {
      List<Integer> catIndices = new ArrayList<Integer>(entry.getValue().size());
      for (Category cat : entry.getValue()) {
        catIndices.add(catToIndex.get(cat));
      }
      tagDict.put(entry.getKey(), ImmutableList.copyOf(catIndices));
    }
    return tagDict;
  }

  public Map<String, Integer> loadSparseFeatures(File posTagFeaturesFile) throws IOException
  {
    Map<String, Integer> posFeatures;
    if (posTagFeaturesFile.exists()) {
      posFeatures = new HashMap<String, Integer>();
      for (String line : Util.readFile(posTagFeaturesFile)) {
        posFeatures.put(line, posFeatures.size());
      }
      posFeatures = ImmutableMap.copyOf(posFeatures);
    } else {
      posFeatures = Collections.emptyMap();
    }
          
    return posFeatures;
  }

  /**
   * Loads the neural network weight matrix.
   */
  private void loadMatrix(Matrix matrix, File file) throws IOException
  {
    Iterator<String> lines = Util.readFileLineByLine(file);
    int row=0;
    while (lines.hasNext()) {
      String line = lines.next();
      String[] fields = line.split(" ");
      for (int i = 0 ; i < fields.length; i++) {
        matrix.set(row, i, Double.valueOf(fields[i]));
      }

      row++;
    }
  }

  private void loadVector(Vector vector, File file) throws IOException
  {
    Iterator<String> lines = Util.readFileLineByLine(file);
    int row=0;
    while (lines.hasNext()) {

      String data = lines.next();
      vector.set(row, Double.valueOf(data));
      row++;
    }
  }

  private List<Category> loadCategories(File catFile) throws IOException
  {
    List<Category> categories = new ArrayList<Category>();
    Iterator<String> lines = Util.readFileLineByLine(catFile);
    while (lines.hasNext()) {
      categories.add(Category.valueOf(lines.next()));
    }

    return categories;
  }

  /* (non-Javadoc)
   * @see uk.ac.ed.easyccg.syntax.Tagger#tag(java.util.List)
   */
  @Override
  public List<List<SyntaxTreeNodeLeaf>> tag(List<InputWord> words) {
    final List<List<SyntaxTreeNodeLeaf>> result = new ArrayList<List<SyntaxTreeNodeLeaf>>(words.size());
    final double[] vector = new double[totalFeatures];
    
    for (int wordIndex = 0; wordIndex < words.size(); wordIndex++) {
      if (posFeatures.size() > 0 || lexicalFeatures.size() > 0) {
        // If we're not using sparse features, all the old values will be over written anyway.
        Arrays.fill(vector, 0.0);
      }
      
      int vectorIndex = 0;
      for (int sentencePosition = wordIndex - contextWindow; sentencePosition<= wordIndex+contextWindow; sentencePosition++) {
        vectorIndex = addToFeatureVector(vectorIndex, vector, sentencePosition, words);
        
        // If using lexical features, update the vector.
        if (lexicalFeatures.size() > 0) {
            if (sentencePosition >= 0 && sentencePosition < words.size())  {
              Integer index = lexicalFeatures.get(words.get(sentencePosition).word);
              if (index != null) {
                vector[vectorIndex + index] = 1; 
              }
            }
            vectorIndex = vectorIndex + lexicalFeatures.size();
        }

        // If using POS-tag features, update the vector.
        if (posFeatures.size() > 0) {
            if (sentencePosition >= 0 && sentencePosition < words.size())  {
              vector[vectorIndex + posFeatures.get(words.get(sentencePosition).pos)] = 1; 
            }

            vectorIndex = vectorIndex + posFeatures.size();
        }

      }

      result.add(getTagsForWord(new DenseVector(vector), words.get(wordIndex), wordIndex));
    }

    return result;
  }
  
  /**
   * Adds the features for the word in the specified position to the vector, and returns the next empty index in the vector.
   */
  private int addToFeatureVector(int vectorIndex, double[] vector, int sentencePosition, List<InputWord> words)
  {
    double[] embedding = getEmbedding(words, sentencePosition);
    vectorIndex = addToVector(vectorIndex, vector, embedding);
    double[] suffix = getSuffix(words, sentencePosition);
    vectorIndex = addToVector(vectorIndex, vector, suffix);
    double[] caps = getCapitalization(words, sentencePosition);
    vectorIndex = addToVector(vectorIndex, vector, caps);
    
    return vectorIndex;
  }

  private int addToVector(int index, double[] vector, double[] embedding)
  {
    System.arraycopy(embedding, 0, vector, index, embedding.length);
    index = index + embedding.length;
    return index;
  }

  /**
   * 
   * @param normalize If true, words are lower-cased with numbers replaced
   * @param embeddingsFiles
   * @return
   * @throws IOException
   */
  private Map<String, double[]> loadEmbeddings(boolean normalize, File... embeddingsFiles) throws IOException {
    Map<String, double[]> embeddingsMap = new HashMap<String, double[]>();
    // Allow sharded input, by allowing the embeddings to be split across multiple files.
    for (File embeddingsFile : embeddingsFiles) {
      Iterator<String> lines = Util.readFileLineByLine(embeddingsFile);
      while (lines.hasNext()) {
        String line = lines.next();
        // Lines have the format: word dim1 dim2 dim3 ...
        String word = line.substring(0, line.indexOf(" "));
        if (normalize) {
          word = normalize(word);
        }

        if (!embeddingsMap.containsKey(word)) {
          String[] fields = line.split(" ");
          double[] embeddings = new double[fields.length - 1];
          for (int i = 1 ; i < fields.length; i++) {
            embeddings[i - 1] = Double.valueOf(fields[i]);
          }
          embeddingsMap.put(word, embeddings);
        }
      }
    }

    return embeddingsMap;
  }

  /**
   * Normalizes words by lower-casing and replacing numbers with '#'/
   */
  private final static Pattern numbers = Pattern.compile("[0-9]");
  private String normalize(String word) {
    word = numbers.matcher(word.toLowerCase()).replaceAll("#");
    return word;
  }

  /**
   * Loads the embedding for the word at the specified index in the sentence.
   * The index is allowed to be outside the sentence range, in which case
   * the appropriate 'padding' embedding is returned. 
   */
  private double[] getEmbedding(List<InputWord> words, int index)
  {
    if (index < 0) return embeddingsFeatures.get(leftPad);
    if (index >= words.size()) return embeddingsFeatures.get(rightPad);
    String word = words.get(index).word;

    word = translateBrackets(word);
    
    double[] result = embeddingsFeatures.get(normalize(word));
    if (result == null) {
      char firstCharacter = word.charAt(0);
      boolean isLower = 'a' <= firstCharacter && firstCharacter <= 'z';
      boolean isUpper = 'A' <= firstCharacter && firstCharacter <= 'Z';
      if (isLower) {
        return embeddingsFeatures.get(unknownLower);
      } else if (isUpper) {
        return embeddingsFeatures.get(unknownUpper);
      } else {
        return embeddingsFeatures.get(unknownSpecial);
      }
    }
    return result;
  }

  private String translateBrackets(String word)
  {
    if (word.equalsIgnoreCase("-LRB-")) word = "(";
    if (word.equalsIgnoreCase("-RRB-")) word = ")";
    return word;
  }

  /**
   * Loads the embedding for a word's 2-character suffix.
   * The index is allowed to be outside the sentence range, in which case
   * the appropriate 'padding' embedding is returned. 
   */
  private double[] getSuffix(List<InputWord> words, int index)
  {
    String suffix = null;
    if (index < 0 || index >= words.size()) {
      suffix = suffixPad;
    } else {
      String word = words.get(index).word;
      
      word = translateBrackets(word);

      if (word.length() > 1) { 
        suffix = (word.substring(word.length() - 2, word.length()));
      } else {
        // Padding for words of length 1.
        suffix = ("_" + word.substring(0, 1));
      }
    }

    double[] result = discreteFeatures.get(suffix.toLowerCase());
    if (result == null) {
      result = discreteFeatures.get(unknownSuffix);
    }
    return result;
  }

  /**
   * Loads the embedding for a word's capitalization.
   * The index is allowed to be outside the sentence range, in which case
   * the appropriate 'padding' embedding is returned. 
   */
  private double[] getCapitalization(List<InputWord> words, int index)
  {
    String key;
    if (index < 0 || index >= words.size()) {
      key = capitalizedPad;
    } else {
      String word = words.get(index).word;

      char c = word.charAt(0);
      if ('A' <= c && c <= 'Z') {
        key = capsUpper;
      } else {
        key = capsLower;
      }   
    }

    return discreteFeatures.get(key);
  }

  private static class ScoredCategory implements Comparable<ScoredCategory> {
    private final int id;
    private final double score;
    private ScoredCategory(int id, double score)
    {
      this.id = id;
      this.score = score;
    }
    @Override
    public int compareTo(ScoredCategory o)
    {
      return Doubles.compare(o.score, score);
    }
  }

  /**
   * Returns a list of @SyntaxTreeNode for this word, sorted by their probability. 
   * @param vector A vector
   * @param word The word itself.
   * @param wordIndex The position of the word in the sentence.
   * @return
   */
  private List<SyntaxTreeNodeLeaf> getTagsForWord(final Vector vector, final InputWord word, final int wordIndex)
  {
    double total = 0.0;

    // If we're using a tag dictionary, consider those tags --- otherwise, try all tags.
    Collection<Integer> possibleCategories = tagDict.get(word.word);
    if (possibleCategories == null) {
      possibleCategories = tagDict.get(TagDict.OTHER_WORDS);
    }
    
    double threshold = 0.0;

    final int size = Math.min(maxTagsPerWord, possibleCategories.size());
    // Fixed length priority queue, used to sort candidate tags.
    MinMaxPriorityQueue<ScoredCategory> queue = MinMaxPriorityQueue.maximumSize(size).create();

    double bestScore = 0.0;

    for (Integer cat : possibleCategories) {
      double score = Math.exp(weightMatrixRows.get(cat).dot(vector) + bias.get(cat));
      if (score >= threshold) {
        queue.add(new ScoredCategory(cat, score));
        
        if (score > bestScore) {
          bestScore = score;
          threshold = beta * bestScore;
          
          // Prune the queue of any categories whose score it too low.
          while (queue.peekLast().score < threshold) {
            queue.pollLast();
          }
        }
      }
      total += score;
    }
    
    // Convert the queue into a sorted list of SyntaxTreeNode terminals.
    List<SyntaxTreeNodeLeaf> result = new ArrayList<SyntaxTreeNodeLeaf>(queue.size());
    while (queue.size() > 0) {
      ScoredCategory cat = queue.poll();
      double probability = cat.score / total;
      result.add(terminalFactory.makeTerminal(
          word.word,           
          lexicalCategories.get(cat.id),
          word.pos,
          word.ner,
          Math.log(probability), 
          wordIndex)); 
    }
    
    return result;
  }
} public class Util
{
  public static int indexOfAny(String haystack, String needles) {
    for (int i=0; i<haystack.length(); i++) {
      for (int j=0; j<needles.length(); j++) {
        if (haystack.charAt(i) == needles.charAt(j)) {
          return i;
        }
      }  
    }
    
    return -1;
  }

  public static Iterable<String> readFile(final File filePath)
  throws java.io.IOException
  {
    return new Iterable<String>()    
    {

      public Iterator<String> iterator() {
        
      try
      {
        return readFileLineByLine(filePath);
      }
      catch (IOException e)
      {
        throw new RuntimeException(e);
      }
    }
    };
      
  }
  
  public static String executeCommand(String command) throws IOException
  {
      Process process = Runtime.getRuntime().exec(new String[] { "/bin/sh", "-c", command });
      
      BufferedReader input =
        new BufferedReader
          (new InputStreamReader(process.getInputStream()));

      StringBuilder output = new StringBuilder();
      String line;
      while ((line = input.readLine()) != null) {
        output.append(line);
        output.append("\n");
      }
      input.close();
      
      return output.toString();      
    
  }
  
  public static void writeStringToFile(String text, File filePath)
  throws java.io.IOException{
      BufferedWriter out = new BufferedWriter(new FileWriter(filePath));
      out.write(text);
      out.close();
  }

  public static Iterator<String> readFileLineByLine(final File filePath)
  throws java.io.IOException
  {
    return new Iterator<String>()
    {

      // Open the file that is the first 
      // command line parameter
      InputStream fstream = new FileInputStream(filePath);
      {
        if (filePath.getName().endsWith(".gz")) {
          // Automatically unzip zipped files.
          fstream = new GZIPInputStream(fstream);
        }
      }
      
      // Get the object of DataInputStream
      DataInputStream in = new DataInputStream(fstream);
      BufferedReader br = new BufferedReader(new InputStreamReader(in));

      String next = br.readLine();

      @Override
      public boolean hasNext()
      {
        
        boolean result = (next != null);
        if(!result) {
          try
          {
            br.close();
          }
          catch (IOException e)
          {
            throw new RuntimeException(e);         
          }
        }
        
        return result;
      }

      @Override
      public String next()
      {
        String result = next;
        try
        {
          next = br.readLine();
        }
        catch (IOException e)
        {
          throw new RuntimeException(e);
        }
        return result;
      }

      @Override
      public void remove()
      {
        throw new UnsupportedOperationException();
      }
    };
  }

  static String dropBrackets(String cat) {
    if (cat.startsWith("(") && cat.endsWith(")") && findClosingBracket(cat) == cat.length() - 1) {
      return cat.substring(1, cat.length() - 1);
    } else {
      return cat; 
    }      
  }

  public static int findClosingBracket(String source)
  {
    return findClosingBracket(source, 0);
  }

  public static int findClosingBracket(String source, int startIndex)
  {
    int openBrackets = 0;
    for (int i = startIndex; i < source.length(); i++)
    {
      if (source.charAt(i) == '(')
      {
        openBrackets++;
      }
      else if (source.charAt(i) == ')')
      {
        openBrackets--;
      }
  
      if (openBrackets==0)
      {
        return i;
      }
    }
    
    throw new Error("Mismatched brackets in string: " + source);
  }

  /**
   * Finds the first index of a needle character in the haystack, that is not nested in brackets.
   */
  public static int findNonNestedChar(String haystack, String needles)
  {
    int openBrackets = 0;

    for (int i=0; i<haystack.length(); i++) {
      if (haystack.charAt(i) == '(')
      {
        openBrackets++;
      }
      else if (haystack.charAt(i) == ')')
      {
        openBrackets--;
      } else if (openBrackets == 0) {
        for (int j=0; j<needles.length(); j++) {
          if (haystack.charAt(i) == needles.charAt(j)) {
            return i;
          }
        }  
      }
    }
     
    return -1;
  }
  
  public static List<File> findAllFiles(File folder, final String regex) {
    return Util.findAllFiles(folder,
        new FilenameFilter() {
          @Override
          public boolean accept(File dir, String name) {
              return name.matches(regex);
          }
      });    
  }
  
  public static List<File> findAllFiles(File folder, FilenameFilter filter) {
    List<File> result = new ArrayList<File>();
    
    findAllFiles(folder, filter, result);
    return result;
  }

  private static void findAllFiles(File folder, FilenameFilter filter, List<File> result) {
    for (File file : folder.listFiles()) {
      if (file.isDirectory()) {
        findAllFiles(file, filter, result);
      } else if (filter.accept(file, file.getName())) {
        result.add(file.getAbsoluteFile());
      }
    }
  }
} public class CCGBankDependencies
{
  private final static File candcFolder = new File("/disk/data2/s1049478/my_parser/candc"); //TODO
  private final static ParsePrinter autoPrinter = ParsePrinter.CCGBANK_PRINTER;
    
  /**
   * Runs the C&C generate program on a list of parses for a sentence, and returns the output.
   */
  public static String getDependenciesAsString(List<SyntaxTreeNode> parses, int id) {

    try {
      File candcScripts = new File(candcFolder,  "/src/scripts/ccg");

      File catsFolder = new File(candcFolder,  "/src/data/ccg/cats/");
      File markedUpCategories = new File(catsFolder,  "/markedup");

      File autoFile = File.createTempFile("parse", ".auto");
      File convertedFile = File.createTempFile("parse", ".auto2");

      String autoString = autoPrinter.print(parses, id);
      Util.writeStringToFile(autoString, autoFile);
      String command = "cat \"" + autoFile + "\" | "  +candcScripts + "/convert_auto " + autoFile + " | sed -f " + candcScripts + "/convert_brackets > " + convertedFile;
      String command2 = candcFolder + "/bin/generate -j  " + catsFolder + " " + markedUpCategories + " " + convertedFile;
      Util.executeCommand(command);
      String deps = Util.executeCommand(command2);
      
      autoFile.delete();
      convertedFile.delete();
      
      return deps;
    } catch (IOException e) {
      throw new RuntimeException(e);
    }
  }

  /**
   * Runs the C&C generate program on a list of parses for a sentence, and returns the output.
   * 
   * Failed parses are represented as 'null'.
   */
  public static List<DependencyParse> getDependencies(List<SyntaxTreeNode> parses, int id) {
    
    String output = getDependenciesAsString(parses, id);
    List<String> lines = Arrays.asList(output.split("\n", -1));
    if (lines.size() == 2) {
      return Arrays.asList((CCGBankDependencies.DependencyParse) null);
    }
    
    List<DependencyParse> result = new ArrayList<DependencyParse>();
    // Skip the C&C header.
    Iterator<String> linesIt = lines.subList(3, lines.size()).iterator();
    Iterator<SyntaxTreeNode> parseIt = parses.iterator();

    while (linesIt.hasNext() && parseIt.hasNext()) {
      if (!parseIt.hasNext()) {
        throw new RuntimeException("More dependency parses than input");
      }
      result.add(getDependencyParseCandC(linesIt, parseIt.next().getWords()));
    }

    if (result.size() != parses.size()) {
      throw new RuntimeException("Error in oracle parses");
    }
    return result;
  }

  /**
   * Represents a CCGBank dependency.
   */
  public static class Dependency {

    private final SyntaxTreeNodeLeaf parent;
    private final SyntaxTreeNodeLeaf child;
    private final int argumentNumber;
    private final int sentencePositionOfPredicate;

    public int getSentencePositionOfPredicate()
    {
      return sentencePositionOfPredicate;
    }
    public int getSentencePositionOfArgument()
    {
      return sentencePositionOfArgument;
    }
    private final int sentencePositionOfArgument;
    private Dependency(SyntaxTreeNodeLeaf parent, SyntaxTreeNodeLeaf child, int index, int sentencePositionOfPredicate, int sentencePositionOfArgument)
    {
      this.parent = parent;
      this.child = child;
      this.argumentNumber = index;
      this.sentencePositionOfPredicate = sentencePositionOfPredicate;
      this.sentencePositionOfArgument = sentencePositionOfArgument;
    }
    public SyntaxTreeNodeLeaf getParent()
    {
      return parent;
    }
    public SyntaxTreeNodeLeaf getChild()
    {
      return child;
    }
    public int getArgNumber()
    {
      return argumentNumber;
    }

  }

  /**
   * Represents a complete dependency parse of a sentence.
   */
  public static class DependencyParse {
    private final Table<SyntaxTreeNodeLeaf, Integer, Collection<Dependency>> arguments = HashBasedTable.create();
    private final Multimap<SyntaxTreeNodeLeaf, Dependency> predicates = HashMultimap.create();
    private final Collection<Dependency> allDependencies = new HashSet<Dependency>();

    void addDependency(Dependency dep) {
      Collection<Dependency> args = arguments.get(dep.parent, dep.getArgNumber());
      if (args == null) {
        args = new ArrayList<Dependency>();
        arguments.put(dep.parent, dep.getArgNumber(), args);
      }

      args.add(dep);

      predicates.put(dep.getChild(), dep);
      allDependencies.add(dep);
    }

    public Collection<Dependency> getDependencies() {
      return allDependencies;
    }

    public Collection<Dependency> getArguments(SyntaxTreeNodeLeaf node, int argumentIndex)
    {
      Collection<Dependency> result = arguments.get(node, argumentIndex);
      if (result == null) return Collections.emptyList();
      return result;
    }

    public Collection<Dependency> getPredicates(SyntaxTreeNodeLeaf argument)
    {
      return predicates.get(argument);
    }
  }

  /**
   * Builds a DependencyParse, from C&C 'deps' output. 
   * 
   * 'lines' is an iterator over input lines. The function reads one parse from this iterator.
   */
  public static DependencyParse getDependencyParseCandC(Iterator<String> lines, List<SyntaxTreeNodeLeaf> goldSupertags) {
    // Pierre_1 N/N 1 Vinken_2
    DependencyParse result = new DependencyParse();
    
    while (lines.hasNext()) {
      String line = lines.next();

      if (line.isEmpty()) {
        if (result.getDependencies().size() == 0) {
          return null;
        }
        break ;
      }

      String[] fields = line.split(" ");
      int predicate = Integer.valueOf(fields[0].substring(fields[0].indexOf('_') + 1));
      int argIndex = Integer.valueOf(fields[2].trim());
      int argument = Integer.valueOf(fields[3].substring(fields[3].indexOf('_') + 1));
      result.addDependency(new Dependency(goldSupertags.get(predicate - 1), goldSupertags.get(argument - 1), argIndex, predicate, argument));
    }

    return result;
  }

  /**
   * Builds a DependencyParse, from CCGBank PARG format.
   * 
   * 'lines' is an iterator over input lines. The function reads one parse from this iterator.
   */
  public static DependencyParse getDependencyParseCCGBank(Iterator<String> lines, List<SyntaxTreeNodeLeaf> words) {
    /*    
    <s id="wsj_0001.1"> 17
    1        0       N/N     1       Vinken Pierre
    1        5       (S[adj]\NP)\NP          1       Vinken old <XB>
    1        7       (S[dcl]\NP)/(S[b]\NP)   1       Vinken will
    1        8       (S[b]\NP)/NP    1       Vinken join <XB>
    10       8       (S[b]\NP)/NP    2       board join
    10       9       NP/N    1       board the
    14       11      ((S\NP)\(S\NP))/NP      3       director as
    14       12      NP/N    1       director a
    14       13      N/N     1       director nonexecutive
    16       15      ((S\NP)\(S\NP))/N[num]          3       29 Nov.
    4        3       N/N     1       years 61
    4        5       (S[adj]\NP)\NP          2       years old
    8        11      ((S\NP)\(S\NP))/NP      2       join as
    8        15      ((S\NP)\(S\NP))/N[num]          2       join Nov.
    8        7       (S[dcl]\NP)/(S[b]\NP)   2       join will
    <\s>
     */
    DependencyParse result = new DependencyParse();

    // Header line
    String line = lines.next();
    while (lines.hasNext()) {
      line = lines.next();

      if (line.startsWith("<\\s>")) {
        break ;
      }

      String[] fields = line.split("\t");
      int argument = Integer.valueOf(fields[0].trim());
      int predicate = Integer.valueOf(fields[1].trim());
      int argIndex = Integer.valueOf(fields[3].trim());
      result.addDependency(new Dependency(words.get(predicate), words.get(argument), argIndex, predicate, argument));
    }

    return result;
  }
} public static class DependencyParse {
  private final Table<SyntaxTreeNodeLeaf, Integer, Collection<Dependency>> arguments = HashBasedTable.create();
  private final Multimap<SyntaxTreeNodeLeaf, Dependency> predicates = HashMultimap.create();
  private final Collection<Dependency> allDependencies = new HashSet<Dependency>();

  void addDependency(Dependency dep) {
    Collection<Dependency> args = arguments.get(dep.parent, dep.getArgNumber());
    if (args == null) {
      args = new ArrayList<Dependency>();
      arguments.put(dep.parent, dep.getArgNumber(), args);
    }

    args.add(dep);

    predicates.put(dep.getChild(), dep);
    allDependencies.add(dep);
  }

  public Collection<Dependency> getDependencies() {
    return allDependencies;
  }

  public Collection<Dependency> getArguments(SyntaxTreeNodeLeaf node, int argumentIndex)
  {
    Collection<Dependency> result = arguments.get(node, argumentIndex);
    if (result == null) return Collections.emptyList();
    return result;
  }

  public Collection<Dependency> getPredicates(SyntaxTreeNodeLeaf argument)
  {
    return predicates.get(argument);
  }
} public class Evaluate
{

  public static class Results {
    public static Results EMPTY = new Results(0, 0, 0);
    private final AtomicInteger parseDependencies;
    private final AtomicInteger correctDependencies;
    private final AtomicInteger goldDependencies;
    private Results(int parseDependencies, int correctDependencies, int goldDependencies)
    {
      this.parseDependencies = new AtomicInteger(parseDependencies);
      this.correctDependencies = new AtomicInteger(correctDependencies);
      this.goldDependencies = new AtomicInteger(goldDependencies);
    }
    public Results()
    {
      this (0, 0, 0);
    }
    public void add(Results other)
    {
      parseDependencies.addAndGet(other.parseDependencies.get());
      correctDependencies.addAndGet(other.correctDependencies.get());
      goldDependencies.addAndGet(other.goldDependencies.get());
    }
    public double getRecall()
    {
      return (double) correctDependencies.get() / goldDependencies.get();
    }
    
    public double getPrecision()
    {
      return (double) correctDependencies.get() / parseDependencies.get();
    }
    
    public double getF1()
    {
      return 2 * (getPrecision() * getRecall()) / (getPrecision() + getRecall());
    }
    public boolean isEmpty()
    {
      return goldDependencies.get() == 0;
    }
  }

  /**
   * Evaluates a parse against a gold standard parse.
   */
  public static Results evaluate(DependencyParse parse, DependencyParse gold) {
    //Conversion script errors
    if (parse == null) return new Results();
    
    Set<String> parseDeps = convertDependencies(parse);
    Set<String> goldDeps = convertDependencies(gold);
    
    Set<String> right = Sets.intersection(parseDeps, goldDeps);

    return new Results(parseDeps.size(), right.size(), goldDeps.size());
  }
  
  /**
   * Converts a DependencyParse into a set of string objects, to make it easier to compare with others.
   */
  private static Set<String> convertDependencies(DependencyParse parse) {
    Set<String> result = new HashSet<String>();
    for (Dependency dep : parse.getDependencies()) {
      result.add(dep.getParent().getCategory() + "_" + dep.getArgNumber() + "_" + dep.getSentencePositionOfPredicate() + "_" + dep.getSentencePositionOfArgument());
    }
    
    return result;
  }
  
  /**
   * Given a list of parses, and a gold dependencies file, it returns the parse which maximizes recall.
   */
  public static SyntaxTreeNode getOracle(List<SyntaxTreeNode> parses, DependencyParse gold) {
    Results best = null;
    SyntaxTreeNode bestParse = null;
    List<DependencyParse> dependencyParses = CCGBankDependencies.getDependencies(parses, -1);
    
    
    for (int i=0; i<dependencyParses.size(); i++) {
      SyntaxTreeNode parse = parses.get(i);
      DependencyParse dependencyParse = dependencyParses.get(i);
      if (dependencyParse == null) continue;

      Results results = evaluate(dependencyParse, gold);
      if (best == null || results.getRecall() > best.getRecall()) {
        best = results;
        bestParse = parse;
      }
    }
    
    return bestParse;
  }
} public static class Results {
  public static Results EMPTY = new Results(0, 0, 0);
  private final AtomicInteger parseDependencies;
  private final AtomicInteger correctDependencies;
  private final AtomicInteger goldDependencies;
  private Results(int parseDependencies, int correctDependencies, int goldDependencies)
  {
    this.parseDependencies = new AtomicInteger(parseDependencies);
    this.correctDependencies = new AtomicInteger(correctDependencies);
    this.goldDependencies = new AtomicInteger(goldDependencies);
  }
  public Results()
  {
    this (0, 0, 0);
  }
  public void add(Results other)
  {
    parseDependencies.addAndGet(other.parseDependencies.get());
    correctDependencies.addAndGet(other.correctDependencies.get());
    goldDependencies.addAndGet(other.goldDependencies.get());
  }
  public double getRecall()
  {
    return (double) correctDependencies.get() / goldDependencies.get();
  }
    
  public double getPrecision()
  {
    return (double) correctDependencies.get() / parseDependencies.get();
  }
    
  public double getF1()
  {
    return 2 * (getPrecision() * getRecall()) / (getPrecision() + getRecall());
  }
  public boolean isEmpty()
  {
    return goldDependencies.get() == 0;
  }
}
import java.io.BufferedWriter;
import java.io.File;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.text.DecimalFormat;
import java.util.Collection;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import uk.ac.ed.easyccg.syntax.Category;
import uk.ac.ed.easyccg.syntax.InputReader;
import uk.ac.ed.easyccg.syntax.InputReader.InputToParser;
import uk.ac.ed.easyccg.syntax.ParsePrinter;
import uk.ac.ed.easyccg.syntax.Parser;
import uk.ac.ed.easyccg.syntax.ParserAStar;
import uk.ac.ed.easyccg.syntax.ParserAStar.SuperTaggingResults;
import uk.ac.ed.easyccg.syntax.SyntaxTreeNode;
import uk.ac.ed.easyccg.syntax.SyntaxTreeNode.SyntaxTreeNodeFactory;
import uk.ac.ed.easyccg.syntax.TagDict;
import uk.ac.ed.easyccg.syntax.TaggerEmbeddings;
import uk.ac.ed.easyccg.syntax.Util;
import uk.ac.ed.easyccg.syntax.evaluation.CCGBankDependencies;
import uk.ac.ed.easyccg.syntax.evaluation.CCGBankDependencies.DependencyParse;
import uk.ac.ed.easyccg.syntax.evaluation.Evaluate;
import uk.ac.ed.easyccg.syntax.evaluation.Evaluate.Results;
import uk.co.flamingpenguin.jewel.cli.ArgumentValidationException;
import uk.co.flamingpenguin.jewel.cli.CliFactory;
import uk.co.flamingpenguin.jewel.cli.Option;
import com.google.common.base.Stopwatch;
import com.google.common.collect.Multimap;
package uk.ac.ed.easyccg.main;




public class EasyCCG
{

  /**
   * Command Line Interface
   */
  public interface CommandLineArguments  
  {
    @Option(shortName="m", description = "Path to the parser model")
    File getModel();

    @Option(shortName="f", defaultValue="", description = "(Optional) Path to the input text file. Otherwise, the parser will read from stdin.")
    File getInputFile();

    @Option(shortName="i", defaultValue="tokenized", description = "(Optional) Input Format: one of \"tokenized\", \"POStagged\", \"POSandNERtagged\", \"gold\", \"deps\" or \"supertagged\"")
    String getInputFormat();

    @Option(shortName="o", description = "Output Format: one of \"ccgbank\", \"html\", or \"prolog\"", defaultValue="ccgbank")
    String getOutputFormat();

    @Option(shortName="l", defaultValue="70", description = "(Optional) Maximum length of sentences in words. Defaults to 70.")
    int getMaxLength();

    @Option(shortName="n", defaultValue="1", description = "(Optional) Number of parses to return per sentence. Defaults to 1.")
    int getNbest();

    @Option(shortName="r", defaultValue={"S[dcl]", "S[wq]", "S[q]", "S[qem]", "NP"}, description = "(Optional) List of valid categories for the root node of the parse. Defaults to: S[dcl] S[wq] S[q] NP")
    List<String> getRootCategories();

    @Option(shortName="s", description = "(Optional) Allow rules not involving category combinations seen in CCGBank. Slows things down by around 20%.")
    boolean getUnrestrictedRules();

    @Option(description = "(Optional) If true, print detailed timing information.")
    boolean getTiming();
    
    @Option(defaultValue="0.0001", description = "(Optional) Prunes lexical categories whose probability is less than this ratio of the best category. Defaults to 0.0001.")
    double getSupertaggerbeam();

    @Option(defaultValue="50", description = "(Optional) Maximum number of categores per word output by the supertagger. Defaults to 50.")
    int getMaxTagsPerWord();
    
    @Option(defaultValue="0.0", description = "(Optional) If using N-best parsing, filter parses whose probability is lower than this fraction of the probability of the best parse. Defaults to 0.0")
    double getNbestbeam();

    @Option(defaultValue="1", description = "(Optional) Number of threads to use. If greater than 1, the output order may differ from the input.")
    int getThreads();

    @Option(defaultValue="", description = "(Optional) Gold dependencies file, for use in oracle experiments")
    File getGoldDependenciesFile();

    @Option(helpRequest = true, description = "Display this message", shortName = "h")
    boolean getHelp();

    @Option(description = "(Optional) Make a tag dictionary")
    boolean getMakeTagDict();

  }

  // Set of supported InputFormats
  public enum InputFormat {
    TOKENIZED, GOLD, SUPERTAGGED, POSTAGGED, POSANDNERTAGGED
  }

  // Set of supported OutputFormats
  public enum OutputFormat {
    CCGBANK(ParsePrinter.CCGBANK_PRINTER), 