public class Alpha {
  
  private final Map<String, Integer> stoi = new HashMap<String, Integer>(50000);
  private final List<String> itos = new ArrayList<String>();
  
  public int getCode(String term) {
    if (stoi.containsKey(term))
      return stoi.get(term);
    
    assert term.length() != 0;
    
    int code = itos.size();
    stoi.put(term, code);
    itos.add(term);
    return code;
  }
  
  public String getString(int code) {
    return itos.get(code);
  }

  public int size() {
    return itos.size();
  }
} public class ChunkedCorpus {
  
  private int[][][] corpus;
  final Alpha alpha;

  private ChunkedCorpus(final int[][][] _corpus, final Alpha _alpha) {
    corpus = _corpus;
    alpha = _alpha;
  }
  
  public int[][][] getArrays() {
    return corpus;
  }
  
  public void writeTo(BufferedWriter bw, String[][] outputText) 
  throws IOException {        
    int i, j, k;
    final GetString getString = 
      GetString.altGetString(outputText, corpus, alpha);
    
    for (i = 0; i < corpus.length; i++) {
      for (j = 0; j < corpus[i].length; j++) {
        if (corpus[i][j].length == 1) 
          bw.write(getString.getString(i, j, 0));
        
        else {
          bw.write("(");
          for (k = 0; k < corpus[i][j].length; k++) {
            bw.write(getString.getString(i, j, k)); 
            if (k < corpus[i][j].length - 1) bw.write(" ");
          }
          bw.write(")");
        }
        
        if (j != corpus[i].length - 1) bw.write(" ");
      }
      bw.write("\n");
    }
    
    bw.close();
  }
  

  public void writeToUnderscore(BufferedWriter bw, String[][] outputText) 
  throws IOException {
    GetString getString = GetString.altGetString(outputText, corpus, alpha);
    int i, j, k;
    for (i = 0; i < corpus.length; i++) {
      for (j = 0; j < corpus[i].length; j++) {
        if (corpus[i][j].length == 1) 
          bw.write(getString.getString(i, j, 0));
        
        else {
          for (k = 0; k < corpus[i][j].length; k++) {
            bw.write(getString.getString(i, j, k));
            if (k < corpus[i][j].length - 1) bw.write("_");
          }
        }
        
        if (j != corpus[i].length - 1) bw.write(" ");
      }
      bw.write("\n");
    }
    
    bw.close();
  }

        
  public static ChunkedCorpus fromChunkedSegmentedCorpus(
      ChunkedSegmentedCorpus c) {
    int[][][][] csArr = c.getArrays();
    int[][][] arr = new int[csArr.length][][];
    
    int numClumps, i, j;
    for (i = 0; i < arr.length; i++) {
      numClumps = 0;
      for (int[][] seg: csArr[i]) 
        numClumps += seg.length;
      
      arr[i] = new int[numClumps][];
      
      j = 0;
      for (int[][] seg: csArr[i])
        for (int[] clump: seg)
          arr[i][j++] = clump;
    }
    
    return new ChunkedCorpus(arr, c.alpha);
  }

  public static ChunkedCorpus fromFile(String filename, Alpha alpha) 
  throws IOException {
    int numS = 0;
    BufferedReader br = new BufferedReader(new FileReader(filename));
    while (br.readLine() != null) numS++;
    br.close();
    
    int[][][] corpus = new int[numS][][];
    
    br = new BufferedReader(new FileReader(filename));
    String s;
    String[] pieces;
    int i = 0, j, k, nClump, cStart, cLen;
    boolean inClump;
    int[][] clumpS;
    
    while ((s = br.readLine()) != null) {
      pieces = s.replace("(", "( ").replace(")", " )").split("  *");
      if (pieces.length == 1 && pieces[0].length() == 0) {
        pieces = new String[0];
      }
      inClump = false;
      nClump = 0;
      for (String piece: pieces) { 
        if (piece.equals("(")) {
          assert !inClump;
          inClump = true;
          nClump++;
        }
        
        else if (piece.equals(")")) {
          assert inClump;
          inClump = false;
        }
        
        else {
          if (!inClump) 
            nClump++;
        }
      }
      
      assert !inClump;
      
      clumpS = new int[nClump][]; 
      j = 0;
      k = 0;
      while (k < pieces.length) {
        if (pieces[k].equals("(")) {
          cStart = k + 1;
          cLen = 0;
          while (!pieces[cStart+cLen].equals(")")) cLen++;
          clumpS[j]= new int[cLen];
          
          for (k = cStart; k < cStart+cLen; k++)
            clumpS[j][k-cStart] = alpha.getCode(pieces[k]);
          
          assert pieces[k].equals(")"): 
            String.format("%d %s", k, pieces[k]);
          k++;
          j++;
        } else {
          clumpS[j++] = new int[] { alpha.getCode(pieces[k++]) };
        }
      }
      
      corpus[i++] = clumpS;
    }
    return new ChunkedCorpus(corpus, alpha);
  }

  public ChunkedCorpus filterBySentenceLength(int n) {
    List<Integer> sentences = new ArrayList<Integer>();
    for (int i = 0; i < corpus.length; i++)
      if (sentenceLen(corpus[i]) <= n)
        sentences.add(i);

    final int[][][] newCorpus = new int[sentences.size()][][];
    int i = 0;
    for (Integer j: sentences)
      newCorpus[i++] = corpus[j];
    
    return new ChunkedCorpus(newCorpus, alpha);
  }
  
  private static int sentenceLen(final int[][] sentence) {
    int len = 0;
    for (int[] chunk: sentence)
      len += chunk.length;
    return len;
  }

  public String getString(int i) {
    return alpha.getString(i);
  }

  public static ChunkedCorpus fromArrays(int[][][] arrays, Alpha alpha) {
    return new ChunkedCorpus(arrays, alpha);
  }
  public UnlabeledBracketSet[] toUnlabeledBracketSets() {
    UnlabeledBracketSet[] outputUB = 
      new UnlabeledBracketSet[corpus.length];
    
    for (int i = 0; i < corpus.length; i++) 
      outputUB[i] = new UnlabeledBracketSet(tokens(i), conv(i), alpha, false);
    
    return outputUB;
  }

  private Collection<UnlabeledBracket> conv(int i) {
    final int[][] chunks = corpus[i];
    List<UnlabeledBracket> b = new ArrayList<UnlabeledBracket>();
    int m = 0;
    for (int[] chunk: chunks) {
      int chunklen = chunk.length;
      m += chunklen;
      if (chunklen > 1)
        b.add(new UnlabeledBracket(m - chunklen, m));
    }
    return b;
  }

  private int[] tokens(int i) {
    final int[][] chunks = corpus[i];
    int n = 0;
    for (int[] a: chunks) n += a.length;
    int[] tokens = new int[n];
    int j = 0;
    for (int[] a: chunks) for (int c: a) tokens[j++] = c;
    return tokens;
  }


  public UnlabeledBracketSetCorpus toUnlabeledBracketSetCorpus() {
    return UnlabeledBracketSetCorpus.fromArrays(toUnlabeledBracketSets());
  }

  /** Reverse sequence of tokens and sentences */
  public void reverse() {
    corpus = Util.reverse(corpus);
  }

  public ChunkedSegmentedCorpus toSimpleChunkedSegmentedCorpus() {
    int[][][][] newCorpus = new int[corpus.length][1][][];
    for (int i = 0; i < corpus.length; i++)
      newCorpus[i][0] = corpus[i];
    return ChunkedSegmentedCorpus.fromArrays(newCorpus, alpha);
  }
} public class ChunkedSegmentedCorpus implements Corpus {

  /** Utilities to convert ChunkedSegmentedCorpus into a set of unlabeled 
   * bracket sets */
  public interface BracketConv {
    Collection<UnlabeledBracket> conv(int[][][] s);
  }
  
  private int[][][][] corpus;
  final Alpha alpha;
  
  private ChunkedSegmentedCorpus(final int[][][][] _corpus, final Alpha _alpha) {
    corpus = _corpus;
    alpha = _alpha;
  }

  public int[][][][] getArrays() {
    return corpus;
  }

  /** Utility to convert this corpus into sets of just the chunks */
  private static BracketConv CHUNKCONV = new BracketConv() {
    @Override
    public Collection<UnlabeledBracket> conv(int[][][] s) {
      List<UnlabeledBracket> b = new ArrayList<UnlabeledBracket>();
      int m = 0;
      for (int[][] seg: s)
        for (int[] chunk: seg) {
          if (chunk.length > 1)
            b.add(new UnlabeledBracket(m, m + chunk.length));
          m += chunk.length;
        }
      
      return b;
    }
  };

  public UnlabeledBracketSet[] asChunked() {
    return conv(CHUNKCONV, false);
  }

  /** Utility to convert this corpus into a right-branching baseline */ 
  private static BracketConv RBCONV = new BracketConv() {
    @Override
    public Collection<UnlabeledBracket> conv(int[][][] s) {
      List<UnlabeledBracket> b = new ArrayList<UnlabeledBracket>();
      int m = 0;
      for (int[][] seg: s) { 
        for (int i = 0; i < seg.length; i++) {
          if (i < seg.length - 1) {
            final int len = segLen(Arrays.copyOfRange(seg, i, seg.length)); 
            if (len > 1) 
              b.add(new UnlabeledBracket(m, m + len));
          }
          if (seg[i].length > 1)
            b.add(new UnlabeledBracket(m, m + seg[i].length));
          m += seg[i].length;
        }
      }
      
      final UnlabeledBracket fullSpan = new UnlabeledBracket(0, m);
      if (!b.contains(fullSpan)) b.add(fullSpan);
      
      return b;
    }
  };
  
  public UnlabeledBracketSet[] asRB() {
    return conv(RBCONV);
  }
  
  private static BracketConv FLATCONV = new BracketConv() {
    @Override
    public Collection<UnlabeledBracket> conv(int[][][] s) {
      List<UnlabeledBracket> b = new ArrayList<UnlabeledBracket>();
      int m = 0;
      for (int[][] seg: s) {
        final int seglen = segLen(seg);
        if (seglen > 1) {
          b.add(new UnlabeledBracket(m, m + seglen));
          if (seg.length > 1) {
            for (int[] chunk: seg) {
              if (chunk.length > 1)
                b.add(new UnlabeledBracket(m, m + chunk.length));
              m += chunk.length;
            }
          }
        }
      }
      return b;
    }
  };

  public UnlabeledBracketSet[] asFlat() {
    return conv(FLATCONV);
  }
  
  
  private UnlabeledBracketSet[] conv(BracketConv b, boolean countRoot) {
    UnlabeledBracketSet[] outputUB = 
      new UnlabeledBracketSet[nSentences()];
    
    for (int i = 0; i < nSentences(); i++) {
      final Collection<UnlabeledBracket> brackets = b.conv(corpus[i]);
      outputUB[i] = new UnlabeledBracketSet(tokens(i), brackets, alpha, countRoot);
    }
    
    return outputUB;
  }

  
  private UnlabeledBracketSet[] conv(BracketConv b) {
    return conv(b, true);
  }

  /**
   * Iterate over the sentences of the original training corpus, returning
   * strings representing clumped sentences
   */
  public Iterable<String> strIter() {
    return new Iterable<String>() {
      
      @Override
      public Iterator<String> iterator() {
        
        return new Iterator<String>() {
          
          int i = 0;
          
          @Override
          public void remove() {
            throw new UnsupportedOperationException();
          }
          
          @Override
          public String next() {
            return clumps2str(corpus[i++]);
          }
          
          @Override
          public boolean hasNext() {
            return i < corpus.length;
          }
        };
      }
    };
  }
  
  /** Returns string representation of clumped sentence */
  public String clumps2str(int[][][] clumps) {
    StringBuffer sb = new StringBuffer();
    
    int lasti = clumps.length-1, lastj, lastk;
    for (int i = 0; i < clumps.length; i++) {
      lastj = clumps[i].length - 1;
      for (int j = 0; j <= lastj; j++) {
        lastk = clumps[i][j].length - 1;
        
        if (lastk == 0)
          sb.append(alpha.getString(clumps[i][j][0]));
        
        else {
          sb.append("(");

          for (int k = 0; k <= lastk; k++) {
            sb.append(alpha.getString(clumps[i][j][k]));
            if (k != lastk)
              sb.append(" ");
          }
          
          sb.append(")");
        }
        
        if (j != lastj)
          sb.append(" ");
      }
      
      if (i != lasti)
        sb.append(" ");
    }
    
    return sb.toString();
  }

  public void writeTo(BufferedWriter output, String[][] outputText) throws IOException {
    ChunkedCorpus.fromChunkedSegmentedCorpus(this).writeTo(output, outputText);
  }
  

  private void writeToUnderscore(BufferedWriter output, String[][] outputText) 
  throws IOException {
    ChunkedCorpus
      .fromChunkedSegmentedCorpus(this).writeToUnderscore(output, outputText);
  }
  
  private void writeToUnderscoreCCL(BufferedWriter bw, String[][] outputText) 
  throws IOException {
    GetString getString = 
      GetString.altGetString(outputText, toChunkedCorpus().getArrays(), alpha);

    for (int sent = 0; sent < corpus.length; sent++) {
      int chunkI = 0;
      for (int[][] seg: corpus[sent]) {
        for (int[] chunk: seg) {
          for (int wrd = 0; wrd < chunk.length; wrd++) {
            bw.write(getString.getString(sent, chunkI, wrd));
            if (wrd == chunk.length - 1)
              bw.write(' ');
            else
              bw.write('_');
          }
          chunkI++;
        }
        bw.write(" ; ");
      }
      bw.write("\n");
    }
    bw.close();
  }
  

  private void writeToWithPunc(BufferedWriter bw, String[][] textOutput) 
  throws IOException {
    GetString getString = GetString.altGetString(
        textOutput, toChunkedCorpus().getArrays(), alpha);
    
    for (int sent = 0; sent < corpus.length; sent++) {
      int chunkI = 0;
      for (int seg = 0; seg < corpus[sent].length; seg++) {
        for (int[] chunk: corpus[sent][seg]) {
          if (chunk.length > 1) 
            bw.write("(");
          for (int wrd = 0; wrd < chunk.length; wrd++) {
            bw.write(getString.getString(sent, chunkI, wrd));
            if (wrd < chunk.length - 1)
              bw.write(' ');
          }
          bw.write(chunk.length > 1 ? ") " : " ");
          chunkI++;
        }
        bw.write(" ; ");
      }
      bw.write('\n');
    }
    bw.close();
  }


  public static ChunkedSegmentedCorpus fromArrays(
      int[][][][] clumpedCorpus, Alpha alpha) {
    return new ChunkedSegmentedCorpus(clumpedCorpus, alpha);
  }

  public ChunkedCorpus toChunkedCorpus() {
    return ChunkedCorpus.fromChunkedSegmentedCorpus(this);
  }

  @Override
  public int nSentences() {
    return corpus.length;
  }

  public int[] tokens(int i) {
    int n = 0;
    for (int[][] seg: corpus[i]) n += segLen(seg);
    
    final int[] tokens = new int[n];
    int j = 0;
    for (int[][] seg: corpus[i])
      for (int[] chunk: seg)
        for (int w: chunk)
          tokens[j++] = w;
    
    return tokens;
  }

  public Collection<UnlabeledBracket> chunkBrackets(int i) {
    final List<UnlabeledBracket> b = new ArrayList<UnlabeledBracket>();
    int curr = 0;
    for (int[][] seg: corpus[i]) {
      b.add(new UnlabeledBracket(curr, curr + segLen(seg)));
      for (int[] chunk: seg) {
        final int next = curr + chunk.length;
        b.add(new UnlabeledBracket(curr, next));
        curr = next;
      }
    }
    return b;
  }

  private static int segLen(int[][] seg) {
    int n = 0;
    for (int[] chunk: seg) n += chunk.length;
    return n;
  }


  public void writeTo(
      BufferedWriter output, OutputType outputType, String[][] outputText) 
  throws IOException, CorpusError {
    switch (outputType) {
      case CLUMP:
      case NPS:
      case PPS:
        writeTo(output, outputText);
        break;
        
      case PUNC:
        writeToWithPunc(output, outputText);
        break;
       
      case UNDERSCORE:
        writeToUnderscore(output, outputText);
        break;
        
      case UNDERSCORE4CCL:
        writeToUnderscoreCCL(output, outputText);
        break;
        
      case TREEBANKRB:
        UnlabeledBracketSetCorpus.fromArrays(asRB()).writeTo(output, outputText);
        break;
        
      case TREEBANKPREC:
        UnlabeledBracketSetCorpus
          .fromArrays(asChunked()).writeTo(output, outputText);
        break;
        
      case TREEBANKFLAT:
        UnlabeledBracketSetCorpus.fromArrays(asFlat())
          .writeTo(output, outputText);
        break;
        
      default:
        throw new CorpusError("Unexpected output type: " + outputType);
    }
  }

  public void writeTo(
      String output, OutputType outputType, String[][] outputText) 
  throws IOException, CorpusError {
    BufferedWriter bw = Util.bufferedWriter(output);
    writeTo(bw, outputType, outputText);
  }

  public ChunkedSegmentedCorpus filter(int filterLen) {
    List<int[][][]> newCorpusConstr = new ArrayList<int[][][]>();
    for (int i = 0; i < corpus.length; i++)
      if (tokens(i).length <= filterLen)
        newCorpusConstr.add(corpus[i]);
    int[][][][] newCorpus = newCorpusConstr.toArray(new int[0][][][]);
    return new ChunkedSegmentedCorpus(newCorpus, alpha);
  }

  public void reverse() {
    corpus = Util.reverse(corpus);
  }
} public class CorpusError extends Exception {
  private static final long serialVersionUID = -4442353664126538807L;

  public CorpusError(String msg) {
    super(msg);
  }
} public enum CorpusType {
  WSJ, NEGRA, CTB, SPL, WPL;
} public class CorpusUtil {

  private CorpusUtil() {
  }

  public static StopSegmentCorpus wsjStopSegmentCorpus(final Alpha alpha,
      final String[] corpusFiles, final int numSent, final boolean noSeg) {
    final Iterable<LabeledBracketSet> treeiter = WSJCorpusTreeIter.fromFiles(
        corpusFiles, alpha);
    return treeIterStopSegmentCorpus(alpha, treeiter, KeepStop.wsjKeepStop,
        numSent, noSeg);
  }

  public static StopSegmentCorpus negraStopSegmentCorpus(final Alpha alpha,
      final String[] corpusFiles, final int numSent, final boolean noSeg) {
    final Iterable<LabeledBracketSet> treeiter = NegraCorpusTreeIter.fromFiles(
        corpusFiles, alpha);
    return treeIterStopSegmentCorpus(alpha, treeiter, KeepStop.negraKeepStop,
        numSent, noSeg);
  }

  public static StopSegmentCorpus ctbStopSegmentCorpus(final Alpha alpha,
      final String[] corpusFiles, final int numSent, final boolean noSeg) {
    final Iterable<LabeledBracketSet> treeiter = CTBCorpusTreeIter.fromFiles(
        corpusFiles, alpha);
    return treeIterStopSegmentCorpus(alpha, treeiter, KeepStop.ctbKeepStop,
        numSent, noSeg);
  }

  private static int[] list2array(final List<Integer> segment) {
    final int[] segArray = new int[segment.size()];
    for (int i = 0; i < segArray.length; i++)
      segArray[i] = segment.get(i);
    return segArray;
  }

  private static int[][] lists2array(List<int[]> segments) {
    final int[][] array = new int[segments.size()][];
    for (int i = 0; i < segments.size(); i++)
      array[i] = segments.get(i);
    return array;
  }

  public static StopSegmentCorpus splStopSegmentCorpus(final Alpha alpha,
      final String[] corpusStr, final int numSent, final boolean noSeg)
  throws CorpusError {

    // count the number of sentences:
    int s = 0;
    for (final String file : corpusStr) {

      BufferedReader br;
      try {
        br = new BufferedReader(
            new InputStreamReader(new FileInputStream(file), "UTF8"));
        try {
          while (br.readLine() != null)
            s++;
        } catch (final IOException e) {
          throw new CorpusError(e.getMessage());
        } finally {
          br.close();
        }
      } catch (final IOException e1) {
        throw new CorpusError(e1.getMessage());
      }
    }
    final int[][][] corpus = new int[s][][];

    s = 0;
    for (final String file : corpusStr) {
      BufferedReader br;
      try {
        br = new BufferedReader(
            new InputStreamReader(new FileInputStream(file), "UTF8"));
        String line;
        try {
          while ((line = br.readLine()) != null) {
            if (line.trim().equals("")) {
              corpus[s++] = new int[0][];
            } else {
              final List<int[]> segments = new ArrayList<int[]>();
              List<Integer> segment = new ArrayList<Integer>();
              for (final String word : line.split(" ")) {
                if (KeepStop.isStoppingPunc(word) && !noSeg
                    && !segment.isEmpty()) {
                  segments.add(list2array(segment));
                  segment = new ArrayList<Integer>();
                } else {
                  segment.add(alpha.getCode(word));
                }
              }
              if (!segment.isEmpty())
                segments.add(list2array(segment));

              corpus[s++] = lists2array(segments);
            }
          }
        } catch (final IOException e) {
          throw new CorpusError(e.getMessage());
        } finally {
          br.close();
        }
      } catch (final IOException e1) {
        throw new CorpusError(e1.getMessage());
      }

    }
    return StopSegmentCorpus.fromArrays(alpha, corpus);
  }

  public static StopSegmentCorpus wplStopSegmentCorpus(final Alpha alpha,
      final String[] corpusStr, final int numSent) {
    // TODO Auto-generated method stub
    return null;
  }

  public static StopSegmentCorpus treeIterStopSegmentCorpus(final Alpha alpha,
      final Iterable<LabeledBracketSet> treeiter, final CorpusConstraints cc,
      final int numS, final boolean noSeg) {
    final LabeledBracketSet[] lbs = lbsArrayFromIter(treeiter);
    final int len;
    if (numS == -1 || numS > lbs.length)
      len = lbs.length;
    else
      len = numS;
    final int[][][] corpus = new int[len][][];
    int i = 0;

    if (len > 0) {
      for (final LabeledBracketSet s : lbs) {
        final String str = s.tokenString(cc);
        final String[] segments = str.split(KeepStop.STOP);
        int m = 0;
        for (final String seg : segments)
          if (seg.trim().length() > 0)
            m++;
        corpus[i] = new int[m][];
        int j = 0;
        for (final String seg : segments) {
          if (seg.trim().length() > 0) {
            final String[] tokens = seg.trim().split(" +");
            corpus[i][j] = new int[tokens.length];
            for (int k = 0; k < tokens.length; k++)
              corpus[i][j][k] = alpha.getCode(tokens[k]);
            j++;
          }
        }

        if (noSeg) {
          final int l = sentLen(corpus[i]);
          final int[][] newsent = new int[1][l];
          int x = 0;
          for (final int[] seg : corpus[i])
            for (final int w : seg)
              newsent[0][x++] = w;
          corpus[i] = newsent;
        }

        i++;
        if (i >= len)
          break;
      }
    }

    return StopSegmentCorpus.fromArrays(alpha, corpus);
  }

  private static int sentLen(final int[][] sent) {
    int s = 0;
    for (final int[] sg : sent)
      s += sg.length;
    return s;
  }

  public static UnlabeledBracketSetCorpus wsjUnlabeledBracketSetCorpus(
      final Alpha alpha, final String[] corpusFiles) {
    return UnlabeledBracketSetCorpus.fromTreeIter(WSJCorpusTreeIter.fromFiles(
        corpusFiles, alpha).toUnlabeledIter(WSJCorpusStandard.instance));
  }

  public static UnlabeledBracketSetCorpus negraUnlabeledBrackSetCorpus(
      final Alpha alpha, final String[] corpusFiles) {
    return UnlabeledBracketSetCorpus.fromTreeIter(NegraCorpusTreeIter
        .fromFiles(corpusFiles, alpha).toUnlabeledIter(
            NegraCorpusStandard.instance));
  }

  public static UnlabeledBracketSetCorpus ctbUnlabeledBracketSetCorpus(
      final Alpha alpha, final String[] corpusFiles) {
    return UnlabeledBracketSetCorpus.fromTreeIter(CTBCorpusTreeIter.fromFiles(
        corpusFiles, alpha).toUnlabeledIter(CTBCorpusStandard.instance));
  }

  public static UnlabeledBracketSetCorpus cclpUnlabeledBracketSetCorpus(
      final Alpha alpha, final String[] files) {
    return UnlabeledBracketSetCorpus.fromTreeIter(CCLParserCorpusTreeIter
        .fromFiles(files, alpha));
  }

  public static ChunkedCorpus getChunkedCorpusClumps(final Alpha alpha,
      final Iterable<UnlabeledBracketSet> iter) {
    final UnlabeledBracketSet[] uBraks = ubsArrayFromIter(iter);
    final int[][][] arrays = new int[uBraks.length][][];
    int[][] clumpArrays;
    int i = 0;
    int clumpsTotal = 0, numClumps = 0;
    int wrdsUnderClumps = 0, totalWrds = 0; 
    for (final UnlabeledBracketSet u : uBraks) {
      clumpArrays = u.clumps();
      arrays[i++] = clumpArrays;
      clumpsTotal += u.getBrackets().size();
      numClumps += numClumps(clumpArrays);
      wrdsUnderClumps += wordsInClumps(clumpArrays);
      totalWrds += allWords(clumpArrays);
    }
    return ChunkedCorpus.fromArrays(arrays, alpha);
  }
  
  private static int allWords(final int[][] clumps) {
    int total = 0;
    for (int[] clump: clumps) 
      total += clump.length;
    return total;
  }
  
  private static int wordsInClumps(final int[][] clumps) {
    int total = 0;
    for (int[] clump: clumps)
      if (clump.length > 1)
        total += clump.length;
    return total;
  }
  
  private static int numClumps(final int[][] clumps) {
    int total = 0;
    for (int[] clump: clumps) 
      if (clump.length > 1)
        total++;
    return total;
  }

  private static UnlabeledBracketSet[] ubsArrayFromIter(
      final Iterable<UnlabeledBracketSet> iter) {
    final List<UnlabeledBracketSet> l = new ArrayList<UnlabeledBracketSet>();
    for (final UnlabeledBracketSet s : iter)
      l.add(s);
    return l.toArray(new UnlabeledBracketSet[0]);
  }

  public static ChunkedCorpus wsjClumpGoldStandard(final Alpha alpha,
      final String[] corpusFiles) {
    return getChunkedCorpusClumps(
        alpha,
        WSJCorpusTreeIter.fromFiles(corpusFiles, alpha).toUnlabeledIter(
            WSJCorpusStandard.instance));
  }

  public static ChunkedCorpus negraClumpGoldStandard(final Alpha alpha,
      final String[] corpusFiles) {
    return getChunkedCorpusClumps(
        alpha,
        NegraCorpusTreeIter.fromFiles(corpusFiles, alpha).toUnlabeledIter(
            NegraCorpusStandard.instance));
  }

  public static ChunkedCorpus ctbClumpGoldStandard(final Alpha alpha,
      final String[] corpusFiles) {
    return getChunkedCorpusClumps(
        alpha,
        CTBCorpusTreeIter.fromFiles(corpusFiles, alpha).toUnlabeledIter(
            CTBCorpusStandard.instance));
  }

  private static ChunkedCorpus getChunkedCorpusNPs(final Alpha alpha,
      final Iterable<LabeledBracketSet> iter, final String cat,
      final CorpusConstraints cc) {
    final LabeledBracketSet[] lBraks = lbsArrayFromIter(iter);
    final int[][][] arrays = new int[lBraks.length][][];
    int i = 0;
    int numConst = 0, numWords = 0, totalWords = 0;
    int[][] constituents;
    for (final LabeledBracketSet l : lBraks) {
      constituents = l.lowestChunksOfType(cat, alpha, cc);
      arrays[i++] = constituents;
      numConst += numClumps(constituents);
      numWords += wordsInClumps(constituents);
      totalWords += allWords(constituents);
    }
    return ChunkedCorpus.fromArrays(arrays, alpha);
  }

  private static LabeledBracketSet[] lbsArrayFromIter(
      final Iterable<LabeledBracketSet> unlabeledIter) {
    final List<LabeledBracketSet> l = new ArrayList<LabeledBracketSet>();
    for (final LabeledBracketSet u : unlabeledIter)
      l.add(u);
    return l.toArray(new LabeledBracketSet[0]);
  }

  public static ChunkedCorpus wsjNPsGoldStandard(final Alpha alpha,
      final String[] corpusFiles) {
    return getChunkedCorpusNPs(alpha,
        WSJCorpusTreeIter.fromFiles(corpusFiles, alpha), 
        "NP",
        WSJCorpusStandard.instance); 
  }

  public static ChunkedCorpus negraNPsGoldStandard(final Alpha alpha,
      final String[] corpusFiles) {
    return getChunkedCorpusNPs(alpha,
        NegraCorpusTreeIter.fromFiles(corpusFiles, alpha), "NP",
        NegraCorpusStandard.instance);
  }

  public static ChunkedCorpus ctbNPsGoldStandard(final Alpha alpha,
      final String[] corpusFiles) {
    return getChunkedCorpusNPs(alpha,
        CTBCorpusTreeIter.fromFiles(corpusFiles, alpha), "NP",
        CTBCorpusStandard.instance);
  }

  public static ChunkedCorpus wsjPPsGoldStandard(final Alpha alpha,
      final String[] corpusFiles) {
    return getChunkedCorpusNPs(alpha,
        WSJCorpusTreeIter.fromFiles(corpusFiles, alpha), "PP",
        WSJCorpusStandard.instance);
  }

  public static ChunkedCorpus negraPPsGoldStandard(final Alpha alpha,
      final String[] corpusFiles) {
    return getChunkedCorpusNPs(alpha,
        NegraCorpusTreeIter.fromFiles(corpusFiles, alpha), "PP",
        NegraCorpusStandard.instance);
  }

  public static ChunkedCorpus ctbPPsGoldStandard(final Alpha alpha,
      final String[] corpusFiles) {
    return getChunkedCorpusNPs(alpha,
        CTBCorpusTreeIter.fromFiles(corpusFiles, alpha), "PP",
        CTBCorpusStandard.instance);
  }

  /**
   * @param corpusStr
   * @param fileType
   * @param numSent
   * @param filterByLength
   * @param noSeg
   * @param reverse
   * @return
   * @throws IOException
   */
  public static StopSegmentCorpus stopSegmentCorpus(final Alpha alpha,
      final String[] corpusStr, final CorpusType fileType, final int numSent,
      final int filterByLength, final boolean noSeg,
      boolean reverse) throws CorpusError {
    StopSegmentCorpus corpus;
    switch (fileType) {
      case WSJ:
        corpus = CorpusUtil.wsjStopSegmentCorpus(alpha, corpusStr, numSent,
            noSeg);
        break;

      case NEGRA:
        corpus = CorpusUtil.negraStopSegmentCorpus(alpha, corpusStr, numSent,
            noSeg);
        break;

      case CTB:
        corpus = CorpusUtil.ctbStopSegmentCorpus(alpha, corpusStr, numSent,
            noSeg);
        break;

      case SPL:
        corpus = CorpusUtil.splStopSegmentCorpus(alpha, corpusStr, numSent,
            noSeg);
        break;

      case WPL:
        corpus = CorpusUtil.wplStopSegmentCorpus(alpha, corpusStr, numSent);
        break;

      default:
        throw new CorpusError("Unexpected file-type: " + fileType);
    }

    if (filterByLength > 0)
      corpus = corpus.filterLen(filterByLength);
    
    if (reverse)
      corpus.reverse();

    return corpus;
  }

  public static ChunkedCorpus npsGoldStandard(final CorpusType testFileType,
      final Alpha alpha, final String[] corpusFiles, final int filterLength) 
      throws CorpusError {
    ChunkedCorpus corpus;
    switch (testFileType) {
      case WSJ:
        corpus = CorpusUtil.wsjNPsGoldStandard(alpha, corpusFiles);
        break;

      case NEGRA:
        corpus = CorpusUtil.negraNPsGoldStandard(alpha, corpusFiles);
        break;

      case CTB:
        corpus = CorpusUtil.ctbNPsGoldStandard(alpha, corpusFiles);
        break;

      default:
        throw new CorpusError("Unexpected file type for NPs gold standard: "
            + testFileType);
    }

    if (filterLength > 0)
      corpus = corpus.filterBySentenceLength(filterLength);
    
    return corpus;
  }

  public static ChunkedCorpus ppsGoldStandard(final CorpusType testFileType,
      final Alpha alpha, final String[] corpusFiles, final int filterLength)
      throws CorpusError {
    ChunkedCorpus corpus;
    switch (testFileType) {
      case WSJ:
        corpus = CorpusUtil.wsjPPsGoldStandard(alpha, corpusFiles);
        break;

      case NEGRA:
        corpus = CorpusUtil.negraPPsGoldStandard(alpha, corpusFiles);
        break;

      case CTB:
        corpus = CorpusUtil.ctbPPsGoldStandard(alpha, corpusFiles);
        break;

      default:
        throw new CorpusError("Unexpected file type for PPs gold standard: "
            + testFileType);
    }

    if (filterLength > 0)
      corpus = corpus.filterBySentenceLength(filterLength);
    
    return corpus;
  }

  public static UnlabeledBracketSetCorpus goldUnlabeledBracketSets(
      final CorpusType testFileType, final Alpha alpha,
      final String[] corpusFiles, final int filterLength, boolean reverse)
      throws CorpusError {

    final UnlabeledBracketSetCorpus corpus;
    switch (testFileType) {
      case WSJ:
        corpus = CorpusUtil.wsjUnlabeledBracketSetCorpus(alpha, corpusFiles);
        break;

      case NEGRA:
        corpus = CorpusUtil.negraUnlabeledBrackSetCorpus(alpha, corpusFiles);
        break;

      case CTB:
        corpus = CorpusUtil.ctbUnlabeledBracketSetCorpus(alpha, corpusFiles);
        break;

      default:
        throw new CorpusError(
            "Unexpected file type for unlabeled bracket sets: " + testFileType);
    }

    return filterLength > 0 ? corpus.filterBySentenceLength(filterLength)
        : corpus;
  }
} public class EncoderError extends Exception {
  private static final long serialVersionUID = 1L;

  public EncoderError(String e) {
    super(e);
  }
} public class KeepStop implements CorpusConstraints {

  private final CorpusConstraints standard;

  private KeepStop(CorpusConstraints _standard) {
    standard = _standard;
  }

  public static final KeepStop wsjKeepStop = new KeepStop(
      WSJCorpusStandard.instance);

  public static final KeepStop negraKeepStop = new KeepStop(
      NegraCorpusStandard.instance);

  public static final KeepStop ctbKeepStop = new KeepStop(
      CTBCorpusStandard.instance);

  static String[] STOPPING_PUNC = new String[] { ".", "?", "!", ";", ",", "--",
      "\u3002", "\u3001", "\uFF0C" }; // Chinese ideographic stop, ideographic
                                      // comma, fullwidth comma

  public static final String STOP = "__stop__";

  public static boolean isStoppingPunc(final String w) {
    for (String p : STOPPING_PUNC)
      if (p.equals(w))
        return true;
    return false;
  }

  @Override
  public String wrap(final String s) {
    StringBuffer sb = new StringBuffer();
    if (!s.startsWith(STOP)) {
      sb.append(STOP);
      sb.append(" ");
    }
    sb.append(s);
    if (!s.endsWith(STOP)) {
      if (!s.endsWith(" "))
        sb.append(" ");
      sb.append(STOP);
    }

    return sb.toString();
  }

  @Override
  public String getToken(String token, String pos) {
    if (isStoppingPunc(token))
      return STOP;
    else
      return standard.getToken(token, pos);
  }
} public enum OutputType {
  CLUMP, NPS, TREEBANKRB, TREEBANKPREC, TREEBANKFLAT, UNDERSCORE, NONE, 
  UNDERSCORE4CCL, PUNC, PPS;

  public static String outputTypesHelp() {
    return 
    "Evaluation types:\n" +
    "  CLUMP\n" + 
    "  NPS\n"+
    "  TREEBANKPREC\n"+
    "  TREEBANKFLAT\n"+
    "  TREEBANKRB\n"+
    "  UNDERSCORE\n" +
    "  NONE";
  }
} public class StopSegmentCorpus {

  int[][][] corpus;
  private final Alpha alpha;

  private StopSegmentCorpus(final Alpha _alpha, final int[][][] _corpus) {
    alpha = _alpha;
    corpus = _corpus;
  }

  public static StopSegmentCorpus fromArrays(final Alpha alpha,
      final int[][][] corpus) {
    return new StopSegmentCorpus(alpha, corpus);
  }

  public ChunkedSegmentedCorpus toBaseChunkedSegmentedCorpus(Alpha alpha) {
    int[][][][] arrays = new int[corpus.length][][][];
    for (int i = 0; i < corpus.length; i++) {
      arrays[i] = new int[corpus[i].length][][];
      for (int j = 0; j < corpus[i].length; j++) {
        arrays[i][j] = new int[corpus[i][j].length][];
        for (int k = 0; k < corpus[i][j].length; k++) {
          arrays[i][j][k] = new int[] { corpus[i][j][k] };
        }
      }
    }

    return ChunkedSegmentedCorpus.fromArrays(arrays, alpha);
  }

  /** Create a sub-corpus of setences whose length is lte to num */
  public StopSegmentCorpus filterLen(final int num) {
    boolean[] filt = new boolean[corpus.length];
    int i = 0;
    int n = 0;
    for (int[][] s : corpus) {
      int len = 0;
      for (int[] seg : s)
        len += seg.length;
      if (len <= num) {
        n++;
        filt[i] = true;
      }
      i++;
    }

    int[][][] _corpus = new int[n][][];
    i = 0;
    for (int j = 0; j < corpus.length; j++)
      if (filt[j])
        _corpus[i++] = corpus[j];

    return fromArrays(getAlpha(), _corpus);
  }

  public Iterable<int[][]> arrayIter() {
    return new Iterable<int[][]>() {

      @Override
      public Iterator<int[][]> iterator() {
        return new Iterator<int[][]>() {
          int i = 0;

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

          @Override
          public int[][] next() {
            return corpus[i++];
          }

          @Override
          public boolean hasNext() {
            return i < corpus.length;
          }
        };
      }
    };
  }

  public int[][][] getArrays() {
    return corpus;
  }

  public void writeTo(String output) throws IOException {
    BufferedWriter bw = new BufferedWriter(new FileWriter(output));
    for (int[][] sent : corpus) {
      bw.write("__stop__");
      for (int[] seg : sent) {
        for (int w : seg) {
          bw.write(" ");
          bw.write(getAlpha().getString(w));
        }
        bw.write(" __stop__");
      }
      bw.write("\n");
    }
    bw.close();
  }

  public Alpha getAlpha() {
    return alpha;
  }

  public int size() {
    return corpus.length;
  }

  /** Reverse sequence of words in corpus */
  public void reverse() {
    corpus = Util.reverse(corpus);
  }

  public void writeTokenizedPlaintextTo(String output) throws IOException {
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(output), "UTF8"));
    for (int[][] sent : corpus) {
      final int n = sent.length;
      for (int i = 0; i < n; i++) {
        final int[] seg = sent[i];
        for (int w : seg) {
          bw.write(getAlpha().getString(w));
          bw.write(" ");
        }
        if (i != n - 1)
          bw.write(", ");
      }
      bw.write(".\n");
    }
    bw.close();
  }
} public abstract class TagEncoder {

  public static String encoderTypeHelp() {
    return 
    "  BIO            Basic BIO encoding\n"
    + "  BILO           Basic BILO encoding\n"
    + "  BIO_GP         BIO encoding with 2nd order tagset\n"
    + "  BIO_GP_NOSTOP  BIO encoding with 2nd order tagset (except on STOP)\n"
    + "  BEO            Two-tag two-word chunks only\n"
    + "  BIO_n          BIO encoding with n groups of clumping types\n"
    + "  BILO_n         BILO encoding with n groups of clumping types";
  }

  private static final String EOS = "__eos__";

  private final int stopv;
  private final int eosv;
  final Alpha alpha;

  public TagEncoder(String stop, Alpha alpha) {
    this.alpha = alpha;
    stopv = alpha.getCode(stop);
    eosv = alpha.getCode(EOS);
  }

  protected boolean isStop(int w) {
    return w == stopv;
  }

  protected boolean isEos(int w) {
    return w == eosv;
  }

  protected boolean isStopOrEos(int w) {
    return isStop(w) || isEos(w);
  }

  protected int getEos() {
    return eosv;
  }

  public static TagEncoder getBIOEncoder(final String type,
      final String stop, final Alpha alpha) throws EncoderError {
    if (type.equals("BIO_GP_NOSTOP"))
      return new GrandparentWithStopBIOEncoder(stop, alpha);
    
    else if (type.equals("BIO_GP"))
      return new GrandparentBIOEncoder(stop, alpha);
    
    else if (type.equals("BIO")) 
      return new SimpleBIOEncoder(stop, alpha);
    
    else if (type.equals("BILO"))
      return new SimpleBILOEncoder(stop, alpha);
    
    else if (type.equals("BEO"))
      return new SimpleBEOEncoder(stop, alpha);
    
    else {
      Pattern patt = Pattern.compile("BIO_(\\d+)");
      Matcher m = patt.matcher(type);
      if (m != null && m.matches()) 
        return new BnInOEncoder(stop, alpha, Integer.parseInt(m.group(1)));
      
      patt = Pattern.compile("BILO_(\\d+)");
      m = patt.matcher(type);
      if (m != null && m.matches())
        return new BnInLnOEncoder(stop, alpha, Integer.parseInt(m.group(1)));
      
      else
        throw new EncoderError("Unexpected GP option " + type);
    }
  }

  public final int[] tokensFromClumpedCorpus(final ChunkedSegmentedCorpus corpus) {

    int[][][][] clumpedCorpus = corpus.getArrays();

    // count tokens
    int n = 1; // for start token
    for (int[][][] s : clumpedCorpus) {
      if (s.length != 0) {
        for (int[][] seg : s) {
          for (int[] clump : seg) {
            n += clump.length;
          }
          n++;
        }
      } else
        n++;
    }

    int[] tokens = new int[n];
    int i = 0, eosv = alpha.getCode(EOS);
    tokens[i++] = eosv;

    for (int[][][] s : clumpedCorpus) {
      if (s.length != 0) {
        for (int[][] seg : s) {
          for (int[] clump : seg) {
            System.arraycopy(clump, 0, tokens, i, clump.length);
            i += clump.length;
          }
          tokens[i++] = stopv;
        }
        tokens[i - 1] = eosv;
      } else
        tokens[i++] = eosv;
    }

    return tokens;
  }

  /**
   * Creating BIO encoded training material for HMM
   * 
   * @param n
   *          number of tokens in clumpedCorpus
   */
  public abstract int[] bioTrain(ChunkedSegmentedCorpus corpus, int n)
      throws EncoderError;

  /** Return a clumped corpus from BIO encoded HMM output */
  public abstract ChunkedSegmentedCorpus clumpedCorpusFromBIOOutput(
      int[] tokens, int[] output) throws EncoderError;

  /** Predicate for whether a tag is a stop tag */
  public abstract Ipredicate isStopPred();

  /** Create soft training for sequence models */
  public abstract double[][] softTrain(final int[] train);

  /** @return the number of tags used */
  public abstract int numTags();

  /**
   * @return constraints on tag-pairs
   */
  public abstract boolean[][] constraints();

  public abstract double[] getInitTagProb();

  public double[][][] softCounts(final StopSegmentCorpus corpus) {
    return softCounts(tokensFromStopSegmentCorpus(corpus));
  }

  public int[] tokensFromStopSegmentCorpus(final StopSegmentCorpus corpus) {
    int[][][] clumpedCorpus = corpus.corpus;

    // count tokens
    int n = 1; // for start token
    for (int[][] s : clumpedCorpus) {
      if (s.length != 0) {
        for (int[] seg : s) {
          n += seg.length + 1;
        }
      } else
        n++;
    }

    int[] tokens = new int[n];
    int i = 0, eosv = alpha.getCode(EOS);
    tokens[i++] = eosv;

    for (int[][] s : clumpedCorpus) {
      if (s.length != 0) {
        for (int[] seg : s) {
          System.arraycopy(seg, 0, tokens, i, seg.length);
          i += seg.length;
          tokens[i++] = stopv;
        }
        tokens[i - 1] = eosv;
      } else
        tokens[i++] = eosv;
    }

    return tokens;
  }

  public double[][][] softCounts(final int[] train) {
    final boolean[][] constraints = constraints();
    final double[][] tags = softTrain(train);
    final int nVocab = MaxVals.arrayMax(train) + 1;
    final int nTag = numTags();
    final double[][][] counts = new double[nTag][nVocab][nTag];

    for (int i = 0; i < train.length - 1; i++) {
      double numOK = 0, numTotal = 0;
      for (int t = 0; t < nTag; t++)
        for (int _t = 0; _t < nTag; _t++)
          if (tags[i][t] != 0 && tags[i + 1][_t] != 0) {
            numTotal += 1.0;
            if (!constraints[t][_t])
              numOK += 1.0;
          }

      final double ratio = numTotal / numOK;

      for (int t = 0; t < nTag; t++) {
        for (int _t = 0; _t < nTag; _t++) {
          if (!constraints[t][_t])
            counts[t][train[i]][_t] += ratio * tags[i][t] * tags[i + 1][_t];
        }
      }

    }
    return counts;
  }

  public double[][][] hardCounts(final ChunkedSegmentedCorpus corpus)
      throws EncoderError {
    final int[] tokens = tokensFromClumpedCorpus(corpus), tags = bioTrain(
        corpus, tokens.length);

    final int nTerm = MaxVals.arrayMax(tokens) + 1, nTag = numTags();

    final int[][][] counts = new int[nTag][nTerm][nTag];
    for (int t = 0; t < tokens.length - 1; t++)
      counts[tags[t]][tokens[t]][tags[t + 1]]++;

    final double[][][] countsD = new double[nTag][nTerm][nTag];
    for (int t = 0; t < nTag; t++)
      for (int w = 0; w < nTerm; w++)
        for (int _t = 0; _t < nTag; _t++)
          countsD[t][w][_t] = (double) counts[t][w][_t];

    return countsD;
  }

  public abstract int[] allNonStopTags();

  public abstract int[] allStopTags();

  /**
   * Create uniform emissions probabilities subject to the constraints imposed
   * by this encoding scheme
   * 
   * @param smoothParam
   * @return A sort-of uniform set of emissions probabilities
   */
  public EmissionProbs altUniformEmiss(final int numVocab,
      final double smoothParam) {
    final double[][] prob = altUniformEmissP(numVocab);
    return EmissionProbs.directFromProbs(prob, isStopPred(), smoothParam);
  }
  
  private double[][] altUniformEmissP(final int numVocab) {
    double[][] prob = new double[numTags()][numVocab];
    final int[] stopTags = allStopTags(), nonStopTags = allNonStopTags();
    final double stopP = Math.log(1 / 2.);
    final double nonStopP = Math.log(1 / ((double) numVocab - 2));

    for (int v = 0; v < numVocab; v++) {
      if (isStopOrEos(v)) {
        for (int t : stopTags)
          prob[t][v] = stopP;
        for (int t : nonStopTags)
          prob[t][v] = Double.NEGATIVE_INFINITY;
      } else {
        for (int t : nonStopTags)
          prob[t][v] = nonStopP;
        for (int t : stopTags)
          prob[t][v] = Double.NEGATIVE_INFINITY;
      }
    }
    return prob;
  }
  
  private double[][] randomEmiss(int size) {
    final double[][] prob = altUniformEmissP(size);
    int ntag = prob.length;
    
    // create array of random probs
    final double[][] randProb = new double[ntag][size];
    Random r = new Random();
    
    // set all non-zero probs to randoms
    for (int t = 0; t < ntag; t++) { 
      for (int v = 0; v < size; v++) {
        if (prob[t][v] != Double.NEGATIVE_INFINITY)
          randProb[t][v] = r.nextDouble();
        else
          randProb[t][v] = 0;
      }

      // normalize and log
      double sum = Util.sum(randProb[t]);
      for (int v = 0; v < size; v++)
        randProb[t][v] = Math.log(randProb[t][v] / sum);
    }
    return randProb;
  }


  public EmissionProbs randomEmiss(int size, double smoothParam) {
    final double[][] randProb = randomEmiss(size);
    return EmissionProbs.directFromProbs(randProb, isStopPred(), smoothParam);
  }
  
  private double[][][] combineForJoint(final double[][] emiss, final double[][] trans) {
    final int ntag = numTags();
    final int numVocab = emiss[0].length;
    final double[][][] pr = new double[ntag][ntag][numVocab];
    for (int q = 0; q < ntag; q++)
      for (int r = 0; r < ntag; r++)
        for (int v = 0; v < numVocab; v++)
          pr[q][r][v] = emiss[q][v] + trans[q][r];
    return pr;
  }

  public double[][][] altUniformJoint(final int numVocab) {
    final double[][] emiss = altUniformEmissP(numVocab);
    final double[][] trans = altUniformTrans();
    return combineForJoint(emiss, trans);
  }

  public double[][][] randomJoint(final int size) {
    final double[][] emiss = randomEmiss(size);
    final double[][] trans = randomTrans();
    return combineForJoint(emiss, trans);
  }
  
  /**
   * Create uniform transition probabilities subject to the constraints imposed
   * by this encoding scheme
   * 
   * @return A sort-of uniform set of transition probabilities
   */
  public double[][] altUniformTrans() {
    int ntag = numTags();
    double[][] probs = new double[ntag][ntag];
    boolean[][] constraints = constraints();
    for (int q = 0; q < ntag; q++) {
      for (int r = 0; r < ntag; r++)
        probs[q][r] = constraints[q][r] ? 0 : 1;

      double sum = Util.sum(probs[q]);
      for (int r = 0; r < ntag; r++)
        probs[q][r] = Math.log(probs[q][r] / sum);
    }
    return probs;
  }

  public double[][] randomTrans() {
    int ntag = numTags();
    double[][] probs = altUniformTrans();
    double[][] rprobs = new double[ntag][ntag];
    Random rand = new Random();
    for (int q = 0; q < ntag; q++) {
      for (int r = 0; r < ntag; r++) 
        if (probs[q][r] != Double.NEGATIVE_INFINITY) 
          rprobs[q][r] = rand.nextDouble();
        else
          rprobs[q][r] = 0;
      
      double sum = Util.sum(rprobs[q]);
      for (int r = 0; r < ntag; r++)
        rprobs[q][r] = Math.log(rprobs[q][r] / sum);
    }
    
    return rprobs;
  }
} public class UnlabeledBracketSetCorpus 
implements Iterable<UnlabeledBracketSet> { 
  
  private final UnlabeledBracketSet[] trees;

  private UnlabeledBracketSetCorpus(UnlabeledBracketSet[] _trees) {
    trees = _trees;
  }
  
  public UnlabeledBracketSet[] getTrees() { return trees; }

  public UnlabeledBracketSetCorpus filterBySentenceLength(int n) {
    List<Integer> indices = new ArrayList<Integer>();
    for (int i = 0; i < trees.length; i++) 
      if (trees[i].getTokens().length <= n)
        indices.add(i);

    UnlabeledBracketSet[] newTrees = new UnlabeledBracketSet[indices.size()];
    int i = 0;
    for (Integer j: indices)
      newTrees[i++] = trees[j];
    
    return new UnlabeledBracketSetCorpus(newTrees);
  }

  public static UnlabeledBracketSetCorpus fromTreeIter(Iterable<UnlabeledBracketSet> iter) {
    List<UnlabeledBracketSet> trees = new ArrayList<UnlabeledBracketSet>();
    for (UnlabeledBracketSet tree: iter)
      trees.add(tree);
    return new UnlabeledBracketSetCorpus(
        trees.toArray(new UnlabeledBracketSet[0]));
  }
  
  public int size() {
    return trees.length;
  }
  
  public UnlabeledBracketSet get(int i) {
    return trees[i];
  }

  public static UnlabeledBracketSetCorpus fromArrays(
      final UnlabeledBracketSet[] a) {
    return new UnlabeledBracketSetCorpus(a);
  }

  public void writeTo(BufferedWriter writer, String[][] outputText) throws IOException {
    for (int i = 0; i < trees.length; i++) {
      writer.write(trees[i].toString());
      writer.write('\n');
    }
    writer.close();
  }

  @Override
  public Iterator<UnlabeledBracketSet> iterator() {
    return new Iterator<UnlabeledBracketSet>() {
      
      int i = 0;
      
      @Override
      public void remove() { throw new UnsupportedOperationException(); }
      
      @Override
      public UnlabeledBracketSet next() { return trees[i++]; }
      
      @Override
      public boolean hasNext() { return i < trees.length; }
    };
  }
} public abstract class Eval {
  
  private final List<UnlabeledExperimentEval> experiments = 
    new ArrayList<UnlabeledExperimentEval>();

  private final String evalName;
  
  protected Eval(final String _evalName) {
    evalName = _evalName;
  }
  
  public String getEvalName() {
    return evalName;
  }
  
  protected void addExperiment(UnlabeledExperimentEval exp) {
    experiments.add(exp);
  }
  
  protected UnlabeledExperimentEval lastExperment() {
    return experiments.get(experiments.size()-1);
  }

  public abstract void eval(String string, ChunkedSegmentedCorpus output) 
  throws EvalError;

  public String getName() {
    return evalName;
  }

  public void writeSummary(
      final EvalReportType evalType, final PrintStream out, final boolean onlyLast) 
  throws EvalError {
    if (onlyLast) {
       writeSummary(lastExperment(), evalType, out);
    } else {
      for (UnlabeledExperimentEval experiment: experiments) {
        writeSummary(experiment, evalType, out);
      }
    }
  }

  private void writeSummary(
      UnlabeledExperimentEval experiment, EvalReportType evalType, PrintStream out) 
  throws EvalError {
    switch (evalType) {
      case PR:
        experiment.writeSummary(out);
        break;
        
      case PRLcsv: 
        experiment.writeSummaryWithLenCSV(out);
        break;
        
      case nPRLcsv: 
        experiment.writeSummaryWithLenAndNameCSV(out);
        break;
        
      case PRL:
        experiment.writeSummaryWithLen(out);
        break;
        
      case PRC:
        experiment.writeSummaryWithCounts(out);
        break;
        
      case PRCL:
        experiment.writeSummaryWithCountsAndLen(out);
        break;
        
      default:
        throw new EvalError("Unknown eval type:: " + evalType);
    }
  }


  public static String evalReportHelp() {
    return
    "Evaluation reports:\n" +
    "  PR      : Precision / recall / F-score\n" +
    "  PRL     : Prec / rec / F plus chunk length info\n" +
    "  PRC     : Prec / rec/ F plus raw counts for tp, fp and fn\n" +
    "  PRCL    : PRL output with raw counts\n" +
    "  PRLcsv  : PRL output in CSV format\n" +
    "  nPRLcsv : PRLcsv with experiment name column";
  }
} public class EvalError extends Exception {
  private static final long serialVersionUID = 1L;

  public EvalError(String errorStr) {
    super(errorStr);
  }
} public class EvalManager {

  Alpha alpha;

  public EvalManager(final Alpha a) {
    alpha = a;
  }
  
  private EvalReportType evalReportType = EvalReportType.PR;
  private final List<Eval> evals = new ArrayList<Eval>();
  private final List<OutputType> evalTypes = new ArrayList<OutputType>();
  private String[] corpusFiles = null;
  private int filterLength = -1;
  private CorpusType testFileType = CorpusType.WSJ;
  private ChunkedCorpus npsGoldStandard;
  private ChunkedCorpus clumpGoldStandard = null;
  private UnlabeledBracketSetCorpus goldUnlabeledBracketSet = null;
  private StopSegmentCorpus testStopSegmentCorpus = null;
  private final int numSent = -1;
  private final boolean onlyLast = false;
  private TreebankEval treebankEval;
  private ChunkingEval npsEval;
  private ChunkingEval clumpsEval;
  private TreebankEval ubsFromClumpsEval;
  private TreebankEval ubsFromNPsEval;
  private boolean noSeg = false;
  private ChunkedCorpus ppsGoldStandard;
  private TreebankEval ubsFromPPsEval;
  private boolean reverse = false;
  private String[][] outputText = null;
  
  public String[][] getTestPos() {
    return getTestPos(null);
  }
  
  public String[][] getTestPos(String puncSymbol) {
    return GetPOS.getPos(alpha, corpusFiles, testFileType, puncSymbol, filterLength);
  }

  public void setNoSeg(final boolean b) {
    noSeg = b;
  }

  public void writeMetadata(final PrintStream s) {
    s.print("  Evaluation type: ");
    for (final Eval e : evals)
      s.print(e.getEvalName() + " ");
    s.println();
    s.println("  Test files:");
    for (final String f : corpusFiles)
      s.println("    " + f);
    if (filterLength > 0)
      s.println("  Filter test files by len: " + filterLength);
//    if (numSent > 0)
//      s.println("  Num test sentences: " + numSent);
    s.println("  Test file type: " + testFileType);
  }

  public void setTestFileType(final CorpusType t) {
    testFileType = t;
  }

  public void setEvalReportType(final EvalReportType type) {
    evalReportType = type;
  }

  public void setParserEvaluationTypes(final String string) throws EvalError,
      CorpusError {
    if (string.equals("")) {
      evalTypes.add(OutputType.CLUMP);
      evalTypes.add(OutputType.NPS);
    } else
      for (final String s : string.split(","))
        evalTypes.add(OutputType.valueOf(s));
  }

  private void initParseEvaluationTypes() throws EvalError, CorpusError {
    for (final OutputType t : evalTypes) {
      switch (t) {
        case CLUMP:
          evals.add(ChunkingEval.fromChunkedCorpus(t, getClumpGoldStandard()));
          break;

        case NPS:
          evals.add(ChunkingEval.fromChunkedCorpus(t, getNPsGoldStandard()));
          break;
          
        case PPS:
          evals.add(ChunkingEval.fromChunkedCorpus(t, getPPsGoldStandard()));
          break;

        case TREEBANKPREC:
          evals.add(TreebankPrecisionEval.fromUnlabeledBracketSets(t,
              getGoldUnlabeledBracketSets()));
          break;

        case TREEBANKFLAT:
          evals.add(TreebankFlatEval.fromUnlabeledBracketSets(t,
              getGoldUnlabeledBracketSets()));
          break;

        case TREEBANKRB:
          evals.add(TreebankRBEval.fromUnlabeledBracketSets(t,
              getGoldUnlabeledBracketSets()));
          break;

        case NONE:
          evals.add(NullEval.instance());
          break;

        default:
          throw new EvalError("Unexpected evaluation type: " + t);
      }
    }
  }

  public void setTestCorpusString(final String[] filenames) {
    corpusFiles = filenames;
  }

  private UnlabeledBracketSetCorpus getGoldUnlabeledBracketSets()
      throws EvalError, CorpusError {
    checkGoldUnlabeledBracketSet();
    return goldUnlabeledBracketSet;
  }

  private void checkGoldUnlabeledBracketSet() throws CorpusError {
    if (goldUnlabeledBracketSet == null)
      goldUnlabeledBracketSet = CorpusUtil.goldUnlabeledBracketSets(
          testFileType, alpha, corpusFiles, filterLength, reverse);
    assert goldUnlabeledBracketSet != null;
  }

  private void checkNPsGoldStandard() throws CorpusError {
    if (npsGoldStandard == null)
      npsGoldStandard = CorpusUtil.npsGoldStandard(testFileType, alpha,
          corpusFiles, filterLength);
    assert npsGoldStandard != null;
  }

  /**
   * Please don't use this method, except to dump gold-standard clumps to 
   * file
   * @return the clumping gold-standard
   */
  public ChunkedCorpus getNPsGoldStandard() throws CorpusError {
    checkNPsGoldStandard();
    return npsGoldStandard;
  }

  private void checkPPsGoldStandard() throws CorpusError {
    if (ppsGoldStandard == null)
      ppsGoldStandard = CorpusUtil.ppsGoldStandard(testFileType, alpha,
          corpusFiles, filterLength);
    assert ppsGoldStandard != null;
  }

  private ChunkedCorpus getPPsGoldStandard() throws CorpusError {
    checkPPsGoldStandard();
    return ppsGoldStandard;
  }

  private void makeClumpGoldStandard() throws EvalError {
    switch (testFileType) {
      case WSJ:
        clumpGoldStandard = 
          CorpusUtil.wsjClumpGoldStandard(alpha, corpusFiles);
        break;

      case NEGRA:
        clumpGoldStandard = 
          CorpusUtil.negraClumpGoldStandard(alpha, corpusFiles);
        break;

      case CTB:
        clumpGoldStandard = 
          CorpusUtil.ctbClumpGoldStandard(alpha, corpusFiles);
        break;
        
      case SPL:
        evalTypes.clear();
        evalTypes.add(OutputType.NONE);
        evals.clear();
        evals.add(NullEval.instance());
        break;

      default:
        throw new EvalError("Unexpected file type for clumping gold standard: "
            + corpusFiles);
    }

    if (filterLength > 0)
      clumpGoldStandard = clumpGoldStandard
          .filterBySentenceLength(filterLength);
  }

  private void checkClumpGoldStandard() throws EvalError {
    if (clumpGoldStandard == null)
      makeClumpGoldStandard();
  }

  /**
   * Please don't use this method, except to dump gold-standard clumps to 
   * file
   * @return the clumping gold-standard
   */
  public ChunkedCorpus getClumpGoldStandard() throws EvalError {
    checkClumpGoldStandard();
    return clumpGoldStandard;
  }

  public void setFilterLen(final int len) {
    filterLength = len;
  }

  public StopSegmentCorpus getEvalStopSegmentCorpus() throws CorpusError,
      EvalError {
    if (evals.size() == 0 && testFileType != CorpusType.SPL) 
      initParseEvaluationTypes();
    if (testStopSegmentCorpus == null)
      makeEvalStopSegmentCorpus();
    return testStopSegmentCorpus;
  }

  private void makeEvalStopSegmentCorpus() throws CorpusError {
    testStopSegmentCorpus = CorpusUtil.stopSegmentCorpus(alpha, corpusFiles,
        testFileType, numSent, filterLength, noSeg, reverse);
  }

  public boolean isNull() throws EvalError, CorpusError {
    return corpusFiles.length == 0 || evalReportType == null || noEvals();
  }

  private boolean noEvals() throws EvalError, CorpusError {
    if (evals.size() == 0)
      initParseEvaluationTypes();
    return evals.size() == 0 || (evals.size() == 1 && evals.get(0) == null);
  }

  public void addChunkerOutput(final String comment,
      final ChunkedSegmentedCorpus output) throws EvalError, CorpusError {
    if (evals.size() == 0)
      initParseEvaluationTypes();
    for (final Eval eval : evals)
      eval.eval(comment, output);
  }

  public void writeEval(final PrintStream out) throws EvalError {
    for (final Eval eval : evals) {
      eval.writeSummary(evalReportType, out, onlyLast);
      out.println();
    }
  }

  public void initializeCCLParserEval() throws EvalError, CorpusError {
    checkNPsGoldStandard();
    checkPPsGoldStandard();
    checkClumpGoldStandard();
    treebankEval = new TreebankEval("asTrees", getGoldUnlabeledBracketSets());
    npsEval = ChunkingEval.fromChunkedCorpus(OutputType.NPS, npsGoldStandard);
    clumpsEval = ChunkingEval.fromChunkedCorpus(OutputType.CLUMP,
        clumpGoldStandard);
    ubsFromClumpsEval = new TreebankEval("clumps Recall",
        clumpGoldStandard.toUnlabeledBracketSetCorpus());
    ubsFromNPsEval = new TreebankEval("NPs Recall",
        npsGoldStandard.toUnlabeledBracketSetCorpus());
    ubsFromPPsEval = new TreebankEval("PPs Recall", 
        ppsGoldStandard.toUnlabeledBracketSetCorpus());
  }

  public void evalParserOutput(final UnlabeledBracketSetCorpus output,
      final OutputManager man) throws CorpusError, EvalError, IOException {
    final ChunkedCorpus chunked = CorpusUtil.getChunkedCorpusClumps(alpha,
        output);
    treebankEval.getExperiment("asTrees", output.getTrees()).writeSummary(
        man.getResultsStream());

    clumpsEval.addExperiment(clumpsEval
        .newChunkingExperiment("clumps", chunked));
    clumpsEval.writeSummary(evalReportType, man.getResultsStream(), false);

    ubsFromClumpsEval.getExperiment("", output.getTrees()).writeSummary(
        man.getResultsStream());

    npsEval.addExperiment(npsEval.newChunkingExperiment("NPs", chunked));
    npsEval.writeSummary(evalReportType, man.getResultsStream(), false);
    
    ubsFromNPsEval.getExperiment("", output.getTrees()).writeSummary(
        man.getResultsStream());

    ubsFromPPsEval.getExperiment("", output.getTrees()).writeSummary(
        man.getResultsStream());

    if (!man.isNull()) {
      BufferedWriter bw = Util.bufferedWriter(man.treeOutputFilename()); 
      output.writeTo(bw, outputText);
      bw = Util.bufferedWriter(man.clumpsOutputFilename());
      chunked.writeTo(bw, outputText);
    }
  }
  
  
  
  public int getFilterLen() { 
    return filterLength;
  }

  public boolean doEval() { 
    return testFileType != CorpusType.SPL;
  }

  public void setReverseEval(final boolean r) {
    reverse = r;
  }

  public void useOutputText(String[][] testPos) {
    outputText = testPos;
  }
} public enum EvalReportType { PR, PRLcsv, nPRLcsv, PRC, PRL, PRCL; } public interface Chunker {

  ChunkedSegmentedCorpus getChunkedCorpus(StopSegmentCorpus c) throws ChunkerError;
} public class ChunkerError extends Exception {
  private static final long serialVersionUID = 4008234820976511784L;

  public ChunkerError(Exception e) {
    super(e);
  }
} public abstract class SequenceModel {

  private final int[] orig;
  private final TagEncoder encoder;
  private double perplex = -1;
  private int[][] tagdict;

  public SequenceModel(final TagEncoder _encoder, final int[] _orig,
      final int[][] _tagdict) {
    encoder = _encoder;
    orig = _orig;
    tagdict = _tagdict;
  }

  /** Tag the corpus, return structured corpus */
  public final ChunkedSegmentedCorpus tagCC(int[] testCorpus)
      throws SequenceModelError, EncoderError {
    int[] output = tag(testCorpus);
    return getEncoder().clumpedCorpusFromBIOOutput(testCorpus, output);
  }

  public final int[] getOrig() {
    return orig;
  }

  public final TagEncoder getEncoder() {
    return encoder;
  }

  /** Update model using (new) data */
  public final void emUpdateFrom(final int[] data) {
    int ndata = data.length, last = ndata - 1, ntag = numTags(), nvocab = numTerms();

    final double neginf = Double.NEGATIVE_INFINITY;

    // Forward-backward algorithm applied to RRGs

    double[][] forward = new double[ndata][ntag], backward = new double[ndata][ntag];

    for (int d = 0; d < ndata; d++) {
      for (int t = 0; t < ntag; t++) {
        forward[d][t] = neginf;
        backward[d][t] = neginf;
      }
    }

    // Forward probabilities
    // Time n = 0
    for (int j = 0; j < ntag; j++)
      forward[0][j] = initTagProb(j);

    // Times n+1 to N
    for (int n = 1; n < ndata; n++) {
      for (int j : getTagdict(data[n - 1])) {
        for (int k : getTagdict(data[n])) {
          final double forwUpd = forward[n - 1][j] + arcprob(j, data[n - 1], k);
          forward[n][k] = Util.logadd(forward[n][k], forwUpd);
        }
      }
    }

    // Finally update forward probabilities with last token probs
    for (int j : getTagdict(data[last - 1])) {
      for (int k : getTagdict(data[last])) {
        final double forwUpd = forward[last - 1][j] + termProb(k, data[last]);
        forward[last][j] = Util.logadd(forward[last][j], forwUpd);
      }
    }

    double forwTotal = neginf;

    for (int t : getTagdict(data[last])) {
      forwTotal = Util.logadd(forwTotal, forward[last][t]);
      backward[last][t] = 0;
    }

    // Backward probabilities. Also collecting new training counts as we go
    final double[][][] counts = new double[ntag][nvocab][ntag];

    for (int n = last; n > 0; n--) {
      for (int k : getTagdict(data[n])) {
        for (int j : getTagdict(data[n - 1])) {
          final double fwd = forward[n - 1][j], bwd = backward[n][k], aprob = arcprob(
              j, data[n - 1], k), backUpd = aprob + bwd;

          backward[n - 1][j] = Util.logadd(backward[n - 1][j], backUpd);

          // TODO shouldn't need to check for neginfs
          if (aprob != neginf && fwd != neginf && bwd != neginf) {
            final double logupd = fwd + bwd + aprob - forwTotal, upd = exp(logupd);
            final int w = data[n - 1];
            counts[j][w][k] += upd;
          }
        }
      }
    }

    update(counts);

    updateTagDict();
    checkSanity();

    // Get perplexity
    setPerplex(exp(-forwTotal / ndata));
  }

  public void updateTagDict() {
    int[] temp;
    final Double neginf = Double.NEGATIVE_INFINITY;

    for (int w = 0; w < numTerms(); w++) {
      temp = new int[numTags()];
      int ntag = 0;
      for (int t = 0; t < numTags(); t++)
        if (termProb(t, w) != neginf)
          temp[ntag++] = t;

      tagdict[w] = copyOf(temp, ntag);
    }
  }

  private final void setPerplex(final double p) {
    perplex = p;
  }

  /** Update model using expectation maximization on original training data */
  public final void emUpdateFromTrain() {
    emUpdateFrom(orig);
  }

  public final int[] getTagdict(int term) {
    if (term >= tagdict.length)
      return encoder.allNonStopTags();
    else
      return tagdict[term];
  }

  /** Viterbi tagger for right-regular grammars */
  public final int[] tag(int[] tokens) {
    int ndata = tokens.length;

    final double[][] viterbi = new double[ndata][];
    final int[][] backpointer = new int[ndata][];
    int[] tags, _tags = getTagdict(tokens[0]);

    double[] v;
    MaxVals mv;

    viterbi[0] = new double[_tags.length];
    for (int j = 0; j < _tags.length; j++)
      viterbi[0][j] = initTagProb(_tags[j]);

    for (int t = 1; t < ndata; t++) {
      tags = getTagdict(tokens[t]);
      viterbi[t] = new double[tags.length];
      backpointer[t] = new int[tags.length];
      final double[][] arcprobs = new double[_tags.length][tags.length];
      final int token = tokens[t - 1];
      for (int j = 0; j < _tags.length; j++)
        for (int k = 0; k < tags.length; k++)
          arcprobs[j][k] = arcprob(_tags[j], token, tags[k]);

      for (int k = 0; k < tags.length; k++) {
        v = new double[_tags.length];
        for (int j = 0; j < _tags.length; j++)
          v[j] = viterbi[t - 1][j] + arcprobs[j][k];

        mv = new MaxVals(v);
        viterbi[t][k] = mv.max;
        backpointer[t][k] = mv.argmax;
      }

      mv = new MaxVals(viterbi[t]);
      assert mv.argmax != -1;

      _tags = tags;
    }

    final int last = ndata - 1;
    final int[] lastTags = getTagdict(tokens[last]);
    for (int t = 0; t < lastTags.length; t++)
      viterbi[last][t] += termProb(lastTags[t], tokens[last]);

    mv = new MaxVals(viterbi[last]);
    assert mv.argmax != -1;

    // first past gets the indices for the tags in the tagdict
    final int[] output = new int[ndata];
    int curr, next;
    output[last] = mv.argmax;
    for (int i = last; i > 0; i--) {
      curr = output[i];
      next = backpointer[i][curr];
      output[i - 1] = next;
    }

    // second pass fills in the actual tags from the tagdict
    for (int i = 0; i < ndata; i++)
      output[i] = getTagdict(tokens[i])[output[i]];

    return output;
  }

  /** @return perplexity of current EM step */
  public final double currPerplex() {
    return perplex;
  }

  /** Check that the probability distributions are not degenerate */
  public void checkSanity() {
    for (int t = 0; t < numTags(); t++) {
      double sum = 0;
      for (int w = 0; w < numTerms(); w++)
        for (int _t = 0; _t < numTags(); _t++)
          sum += exp(arcprob(t, w, _t));

      assert abs(sum - 1.) < 1e-5;
    }
  }

  /**
   * @param j
   *          Previous tag
   * @param w
   *          Previous token
   * @param k
   *          Current tag
   * @return The arc probability p(tag_k, word_w | tag_j)
   */
  public abstract double arcprob(int j, int w, int k);

  /**
   * Update the model with combined emission/transition counts
   * 
   * @param counts
   */
  public abstract void update(double[][][] counts);

  public abstract int numTags();

  public abstract int numTerms();

  public abstract double initTagProb(int tag);

  public abstract double termProb(int tag, int term);

  public static SequenceModel mleEstimate(
      final SequenceModelType sequenceModelType,
      final ChunkedSegmentedCorpus corpus, final TagEncoder encoder,
      final double smoothParam) throws EncoderError, SequenceModelError {
    switch (sequenceModelType) {
      case HMM:
        return HMM.mleEstimate(corpus, encoder, smoothParam);
      case PRLG:
        return RRG.mleEstimate(corpus, encoder, smoothParam);
      default:
        throw new SequenceModelError("Unexpected sequence model type: "
            + sequenceModelType);
    }
  }

  public static SequenceModel uniformEstimate(
      final SequenceModelType sequenceModelType,
      final StopSegmentCorpus corpus, final TagEncoder encoder,
      final double smoothParam) throws SequenceModelError {
    switch (sequenceModelType) {
      case HMM:
        return HMM.uniformEstimate(corpus, encoder, smoothParam);
      case PRLG:
        return RRG.uniformEstimate(corpus, encoder, smoothParam);
      default:
        throw new SequenceModelError("Unexpected sequence model type: "
            + sequenceModelType);
    }
  }

  public static SequenceModel softEstimate(
      final SequenceModelType sequenceModelType,
      final StopSegmentCorpus corpus, final TagEncoder encoder,
      final double smoothParam) throws SequenceModelError {
    switch (sequenceModelType) {
      case HMM:
        return HMM.softCountEstimate(corpus, encoder, smoothParam);
      case PRLG:
        return RRG.softCountEstimate(corpus, encoder, smoothParam);
      default:
        throw new SequenceModelError("Unexpected sequence model type: "
            + sequenceModelType);
    }
  }

  public static SequenceModel randomEstimate(SequenceModelType chunkerType,
      StopSegmentCorpus train, TagEncoder encoder, double smooth)
      throws SequenceModelError {
    switch (chunkerType) {
      case HMM:
        return HMM.randomEstimate(train, encoder, smooth);

      case PRLG:
        return RRG.randomEstimate(train, encoder, smooth);

      default:
        throw new SequenceModelError("Unexpected sequence model type: "
            + chunkerType);
    }
  }
} public class SequenceModelChunker {

  private double lastPerplex = -1;
  private int currIter = 0;
  private final SequenceModel model;
  private final double emdelta;
  public final int totalIter;
  
  public SequenceModelChunker(
      final SequenceModel _model, final double _emdelta) {
    this(_model, _emdelta, -1);
  }
  
  public SequenceModelChunker(
      final SequenceModel _model, final double _emdelta, final int _iter) {
    model = _model;
    emdelta = _emdelta;
    totalIter = _iter;
  }
  
  public Chunker getCurrentChunker() {
    return new Chunker() {
      
      @Override
      public ChunkedSegmentedCorpus getChunkedCorpus(StopSegmentCorpus c) 
      throws ChunkerError{
        try {
          return model.tagCC(model.getEncoder().tokensFromStopSegmentCorpus(c));
        } catch (SequenceModelError e) {
          throw new ChunkerError(e);
        } catch (EncoderError e) {
          throw new ChunkerError(e);
        }
      }
    };
  }
  
  private double currDelta() {
    if (lastPerplex < 0)
      return model.currPerplex();
    
    final double 
    curr = model.currPerplex(),
    less = lastPerplex - curr,
    delta = less / curr;
    return delta;
  }
  
  public boolean anotherIteration() {
    if (totalIter == 0) 
      return false;
    if (totalIter > 0)
      return currIter < totalIter;
    else
      return lastPerplex < 0 || emdelta < currDelta();
  }
  
  public void updateWithEM(PrintStream verboseOut) {
    currIter++;
    lastPerplex = model.currPerplex();
    model.emUpdateFromTrain();
    if (verboseOut != null)
      verboseOut.println(
          String.format(
              "Current iter = %d , perplex = %f, delta = %f", 
              currIter, model.currPerplex(), currDelta()));
    
  }

  public int getCurrentIter() {
    return currIter;
  }
} public class SequenceModelError extends Exception {
  private static final long serialVersionUID = 1L;
  
  public SequenceModelError(String e) {
    super(e);
  }
} public enum SequenceModelType { HMM, PRLG; } public class SimpleChunker implements Chunker {

  public static final String STOP = "__stop__";
  final Alpha alpha;
  private final NgramCounts bigramCounts;
  private final int stopv;
  private final double[] factor;

  public static SimpleChunker fromStopSegmentCorpus(final Alpha alpha,
      final StopSegmentCorpus corpus, final double[] factor) {
    final NgramCounts bigramCounts = new NgramCounts();
    final int stopv = alpha.getCode(STOP);
    for (int[][] s : corpus.arrayIter()) {
      for (int[] seg : s) {
        if (seg.length > 0) {
          final int last = seg.length - 1;
          bigramCounts.incr(stopv, seg[0]);
          bigramCounts.incr(seg[last], stopv);
          for (int j = 0; j < last; j++) {
            bigramCounts.incr(seg[j], seg[j + 1]);
          }
        }
      }
    }

    return new SimpleChunker(alpha, bigramCounts, stopv, factor);
  }

  private SimpleChunker(final Alpha _alpha, final NgramCounts _bigramCounts,
      final int _stopv, final double[] _factor) {
    alpha = _alpha;
    bigramCounts = _bigramCounts;
    stopv = _stopv;
    factor = _factor;
  }

  @Override
  public ChunkedSegmentedCorpus getChunkedCorpus(StopSegmentCorpus c) {
    int[][][] _corpus = c.getArrays();
    int[][] _segments;
    int[] _terms;

    double[][] pyr;

    int[][][][] clumpedCorpus = new int[_corpus.length][][][];

    int[][] clumpsTmp;

    int i, j, k, m, n, pyrI, pyrJ, numClump, index1, index2, t1, t2;

    double count, doClump, dontClumpL, dontClumpR, sumP;

    boolean[] toclump;

    for (i = 0; i < _corpus.length; i++) {
      _segments = _corpus[i];

      clumpedCorpus[i] = new int[_segments.length][][];

      for (j = 0; j < _segments.length; j++) {

        _terms = _segments[j];
        clumpsTmp = new int[_terms.length][];
        numClump = 0;

        n = _terms.length;
        m = Math.min(_terms.length - 1, factor.length);
        m = Math.max(m, 0);
        pyr = new double[m][];

        for (pyrI = 0; pyrI < m; pyrI++)
          pyr[pyrI] = new double[n - pyrI - 1];

        for (pyrI = m - 1; pyrI >= 0; pyrI--) {
          for (pyrJ = 0; pyrJ < n - pyrI - 1; pyrJ++) {
            count = bigramCounts.get(_terms[pyrJ], _terms[pyrI + pyrJ + 1]);
            sumP = sumParents(pyr, pyrI, pyrJ, m, n);
            pyr[pyrI][pyrJ] = factor[pyrI] * count + sumP;
          }
        }

        toclump = new boolean[Math.max(_terms.length - 1, 0)];
        for (k = 0; k < _terms.length - 1; k++) {
          doClump = pyr[0][k];
          t1 = _terms[k];
          t2 = _terms[k + 1];
          dontClumpR = bigramCounts.get(t1, stopv);
          dontClumpL = bigramCounts.get(stopv, t2);
          toclump[k] = doClump >= dontClumpL + dontClumpR;
        }

        index1 = index2 = 0;
        if (toclump.length > 0) {
          while (index2 <= toclump.length) {
            while (index2 < toclump.length && toclump[index2])
              index2++;

            index2++;
            clumpsTmp[numClump++] = Arrays.copyOfRange(_terms, index1, index2);
            index1 = index2;
          }
        }

        clumpedCorpus[i][j] = Arrays.copyOf(clumpsTmp, numClump);
      }
    }

    return ChunkedSegmentedCorpus.fromArrays(clumpedCorpus, alpha);
  }

  private static double sumParents(double[][] pyr, int i, int j, int m, int n) {
    assert 0 <= i;
    assert i < m;
    assert 0 <= j;
    assert j < n - i - 1;

    if (i == m - 1)
      return 0.;
    else if (j == 0)
      return pyr[i + 1][0];
    else if (j == n - i - 2)
      return pyr[i + 1][j - 1];
    else
      return pyr[i + 1][j - 1] + pyr[i + 1][j];
  }
} public class Util {

  public static double sum(final double[] ds) {
    double s = 0;
    for (double d: ds)
      s += d;
    return s;
  }

  public static double logadd(final double x, final double y) {
    assert !Double.isNaN(y);
    assert !Double.isNaN(x);
    if (x <= Util.LOGEPS) 
      return y;
    else if (y <= Util.LOGEPS) 
      return x;
    else if (y <= x) 
      return x + log(1 + exp(y-x)); 
    else 
      return y + log(1 + exp(x-y));
  }

  static final double LOGEPS = -1e+16;

  public static double sum(double[][] ds) {
    double s = 0;
    for (double[] a: ds)
      for (double b: a)
        s += b;
    return s;
  }

  public static double countNonzero(double[] ds) {
    int c = 0;
    for (double d: ds) if (d != 0) c++;
    return (double) c;
  }

  public static int[][][] reverse(int[][][] corpus) {
    int n = corpus.length;
    int[][][] newCorpus = new int[n][][];
    for (int i = 0; i < n; i++)
      newCorpus[i] = reverse(corpus[n - i - 1]);
    return newCorpus;
  }

  private static int[][] reverse(int[][] sent) {
    int n = sent.length;
    int[][] newSent = new int[n][];
    for (int i = 0; i < n; i++)
      newSent[i] = reverse(sent[n - i - 1]);
    return newSent;
  }

  private static int[] reverse(int[] seg) {
    int n = seg.length;
    int[] newSeg = new int[n];
    for (int i = 0; i < n; i++)
      newSeg[i] = seg[n - i - 1];
    return newSeg;
  }

  public static int[][][][] reverse(int[][][][] corpus) {
    int n = corpus.length;
    int[][][][] newCorpus = new int[n][][][];
    for (int i = 0; i < n; i++)
      newCorpus[i] = reverse(corpus[n-i-1]);
    return newCorpus;
  }

  public static BufferedWriter bufferedWriter(String filename) 
  throws IOException {
    return new BufferedWriter(new OutputStreamWriter(
        new FileOutputStream(new File(filename)), "UTF-8"));
  }
}
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;
import java.util.List;
import upparse.corpus.Alpha;
import upparse.corpus.ChunkedCorpus;
import upparse.corpus.ChunkedSegmentedCorpus;
import upparse.corpus.CorpusError;
import upparse.corpus.CorpusType;
import upparse.corpus.CorpusUtil;
import upparse.corpus.EncoderError;
import upparse.corpus.KeepStop;
import upparse.corpus.OutputType;
import upparse.corpus.StopSegmentCorpus;
import upparse.corpus.TagEncoder;
import upparse.corpus.UnlabeledBracketSetCorpus;
import upparse.eval.Eval;
import upparse.eval.EvalError;
import upparse.eval.EvalManager;
import upparse.eval.EvalReportType;
import upparse.model.Chunker;
import upparse.model.ChunkerError;
import upparse.model.SequenceModel;
import upparse.model.SequenceModelChunker;
import upparse.model.SequenceModelError;
import upparse.model.SequenceModelType;
import upparse.model.SimpleChunker;
import upparse.util.Util;
package upparse.cli;



/**
 * Main class manages command-line interface to UPP
 * @author eponvert@utexas.edu (Elias Ponvert)
 */
public class Main {

  private static enum ChunkingStrategy {
    TWOSTAGE, SOFT, UNIFORM, RANDOM, SUPERVISED_CLUMP, SUPERVISED_NPS;
  }

  private static final String CCLPARSER_EVAL_ACTION = "cclp-eval";
  private static final String CHUNK_ACTION = "chunk";
  private static final String DUMP_TEXT_ACTION = "dump-text";
  private static final Object DUMP_CLUMPS_ACTION = "dump-clumps";
  private static final Object DUMP_NPS_ACTION = "dump-nps";

  private final Alpha alpha = new Alpha();
  private OutputManager outputManager = OutputManager.nullOutputManager();
  private final EvalManager evalManager = new EvalManager(alpha);
  private String factor = "2,1,1";
  private int iter = -1;
  private double emdelta = .001;
  private String[] args = new String[0];
  private TagEncoder encoder = 
    TagEncoder.getBIOEncoder("BIO", KeepStop.STOP, alpha);
  private String[] trainCorpusString = null;
  private CorpusType trainFileType = CorpusType.WSJ;
  private int trainSents = -1;
  private StopSegmentCorpus trainStopSegmentCorpus;