gt:       while (true) {
context: package edu.stanford.nlp.mt.train;
  
  import edu.stanford.nlp.mt.tm.DTUTable;
  import edu.stanford.nlp.mt.util.CoverageSet;
  import edu.stanford.nlp.mt.util.IString;
  import edu.stanford.nlp.mt.util.Sequence;
  import edu.stanford.nlp.mt.util.TrieIntegerArrayIndex;
  import edu.stanford.nlp.util.Triple;
  
  import java.util.*;
  
  /**
   * @author Michel Galley
   */
  public class DTUPhraseExtractor extends AbstractPhraseExtractor {
  
    static public final String MAX_SPAN_OPT = "maxDTUSpan";
    static public final String MAX_SPAN_E_OPT = "maxDTUSpanE";
    static public final String MAX_SPAN_F_OPT = "maxDTUSpanF";
  
    static public final String MAX_SIZE_OPT = "maxDTUSize";
    static public final String MAX_SIZE_E_OPT = "maxDTUSizeE";
    static public final String MAX_SIZE_F_OPT = "maxDTUSizeF";
  
    static public final String NO_TARGET_GAPS_OPT = "noTargetGaps";
    static public final String GAPS_BOTH_SIDES_OPT = "gapsBothSides";
    static public final String ALLOW_UNALIGNED_GAPS_OPT = "allowUnalignedGaps"; // extract
                                                                                // "w X w"
                                                                                // if
                                                                                // X
                                                                                // is
                                                                                // unaligned
    static public final String ALLOW_LOOSE_GAPS_OPT = "allowLooseGaps";
    static public final String ALLOW_LOOSE_GAPS_E_OPT = "allowLooseGapsE";
    static public final String ALLOW_LOOSE_GAPS_F_OPT = "allowLooseGapsF";
    static public final String NO_UNALIGNED_SUBPHRASE_OPT = "noUnalignedSubphrase";
  
    static public final int DEFAULT_MAX_SIZE = 5;
    static public final int DEFAULT_MAX_SPAN = 12;
  
    static int maxSize = DEFAULT_MAX_SIZE;
    static int maxSizeF = maxSize, maxSizeE = maxSize;
  
    static int maxSpan = DEFAULT_MAX_SPAN;
    public static int maxSpanF = maxSpan, maxSpanE = maxSpan;
  
    static final int QUEUE_SZ = 1024;
  
    static final boolean DEBUG = System.getProperty("DebugDTU") != null;
  
    static boolean looseDTU = true, looseOutsideDTU = true, growSource = false;
    static boolean withGaps, gapsBothSides, noTargetGaps, noUnalignedSubphrase,
        allowLooseGapsE, allowLooseGapsF, allowUnalignedGaps;
  
    Set<DTUPhrase> seen = new HashSet<DTUPhrase>(QUEUE_SZ);
  
    FlatPhraseExtractor substringExtractor;
  
    public DTUPhraseExtractor(Properties prop, AlignmentTemplates alTemps,
        List<AbstractFeatureExtractor> extractors) {
      super(prop, alTemps, extractors);
      substringExtractor = new FlatPhraseExtractor(prop, alTemps, extractors);
      substringExtractor.alGrid = alGrid;
      System.err.println("Using DTU phrase extractor.");
    }
  
    @Override
    public Object clone() throws CloneNotSupportedException {
      DTUPhraseExtractor c = (DTUPhraseExtractor) super.clone();
      c.substringExtractor = (FlatPhraseExtractor) substringExtractor.clone();
      c.substringExtractor.alGrid = c.alGrid;
      c.seen = new HashSet<DTUPhrase>(QUEUE_SZ);
      return c;
    }
  
    static String stringWithGaps(Sequence<IString> f, CoverageSet bitset) {
      StringBuilder sb = new StringBuilder();
      int oldI = -1;
      for (int i : bitset) {
        if (oldI != -1) {
          if (i > oldI + 1) {
            sb.append(" ").append(DTUTable.GAP_STR).append(" ");
          } else {
            sb.append(" ");
          }
        }
        sb.append(f.get(i));
        oldI = i;
      }
      return sb.toString();
    }
  
    static public void setDTUExtractionProperties(Properties prop) {
  
      String optStr;
      withGaps = true; // withGaps normally set to true. (withGaps = false only
                       // useful for debugging)
  
      // No gaps on the target:
      optStr = prop.getProperty(NO_TARGET_GAPS_OPT);
      noTargetGaps = optStr != null && !optStr.equals("false");
  
      // Don't ignore DTU if a gap only covers unaligned words:
      optStr = prop.getProperty(ALLOW_UNALIGNED_GAPS_OPT);
      allowUnalignedGaps = optStr != null && !optStr.equals("false");
  
      // Don't Ignore DTU if first or last word of X is unaligned:
      optStr = prop.getProperty(ALLOW_LOOSE_GAPS_OPT);
      boolean allowLooseGaps = optStr == null || optStr.equals("true"); // on by
                                                                        // default
      if (allowLooseGaps) {
        allowLooseGapsE = allowLooseGapsF = true;
      } else {
        optStr = prop.getProperty(ALLOW_LOOSE_GAPS_E_OPT);
        allowLooseGapsE = optStr != null && !optStr.equals("false");
        optStr = prop.getProperty(ALLOW_LOOSE_GAPS_F_OPT);
        allowLooseGapsF = optStr != null && !optStr.equals("false");
      }
  
      // Each wi in w1 X w2 X ... X wN must be licensed by at least one alignment:
      optStr = prop.getProperty(NO_UNALIGNED_SUBPHRASE_OPT);
      noUnalignedSubphrase = optStr != null && !optStr.equals("false");
  
      // Enable phrases with gaps on both sides:
      // (note: this creates a lot of phrases)
      optStr = prop.getProperty(GAPS_BOTH_SIDES_OPT);
      gapsBothSides = optStr != null && !optStr.equals("false");
  
      String s;
      if ((s = prop.getProperty(MAX_SPAN_F_OPT)) != null) {
        maxSpanF = Integer.parseInt(s);
      } else if ((s = prop.getProperty(MAX_SPAN_OPT)) != null) {
        maxSpanF = Integer.parseInt(s);
      }
  
      if ((s = prop.getProperty(MAX_SPAN_E_OPT)) != null) {
        maxSpanE = Integer.parseInt(s);
      } else if ((s = prop.getProperty(MAX_SPAN_OPT)) != null) {
        maxSpanE = Integer.parseInt(s);
      }
      maxSpan = Math.max(maxSpanF, maxSpanE);
  
      if ((s = prop.getProperty(MAX_SIZE_F_OPT)) != null) {
        maxSizeF = Integer.parseInt(s);
      } else if ((s = prop.getProperty(MAX_SIZE_OPT)) != null) {
        maxSizeF = Integer.parseInt(s);
      }
  
      if ((s = prop.getProperty(MAX_SIZE_E_OPT)) != null) {
        maxSizeE = Integer.parseInt(s);
      } else if ((s = prop.getProperty(MAX_SIZE_OPT)) != null) {
        maxSizeE = Integer.parseInt(s);
      }
      maxSize = Math.max(maxSizeF, maxSizeE);
      System.err.printf("Discontinuous phrase constraints:\n"
          + "Size: max=%d,maxE=%d,maxF=%d\nSpan: max=%d,maxE=%d,maxF=%d\n",
          maxSize, maxSizeE, maxSizeF, maxSpan, maxSpanE, maxSpanF);
  
      if (DEBUG)
        AlignmentTemplateInstance.lazy = false;
    }
  
    class DTUPhrase {
  
      WordAlignment sent;
  
      CoverageSet consistencizedF, consistencizedE;
  
      final CoverageSet f, e;
  
      boolean isContiguous(BitSet bitset) {
        int i = bitset.nextSetBit(0);
        int j = bitset.nextClearBit(i + 1);
        return (bitset.nextSetBit(j + 1) == -1);
      }
  
      CoverageSet e() {
        return e;
      }
  
      CoverageSet f() {
        return f;
      }
  
      boolean fContiguous() {
        return isContiguous(f);
      }
  
      boolean eContiguous() {
        return isContiguous(e);
      }
  
      DTUPhrase expandF(int fi) {
        f.set(fi);
        return consistencize(fi, true) ? this : null;
      }
  
      DTUPhrase expandE(int ei) {
        e.set(ei);
        return consistencize(ei, false) ? this : null;
      }
  
      boolean sane() {
        return f.equals(consistencizedF) && e.equals(consistencizedE);
      }
  
      int sizeE() {
        return e.cardinality();
      }
  
      int sizeF() {
        return f.cardinality();
      }
  
      int spanE() {
        return e.length() - e.nextSetBit(0);
      }
  
      int spanF() {
        return f.length() - f.nextSetBit(0);
      }
  
      void addE(int ei) {
        e.set(ei);
      }
  
      void addF(int fi) {
        f.set(fi);
      }
  
      CoverageSet toConsistencizeInF() {
        CoverageSet newF = f.clone();
        newF.xor(consistencizedF);
        return newF;
      }
  
      CoverageSet toConsistencizeInE() {
        CoverageSet newE = e.clone();
        newE.xor(consistencizedE);
        return newE;
      }
  
      @Override
      public String toString() {
        return toString(true);
      }
  
      String toString(boolean sanityCheck) {
        if (sanityCheck && !sane()) {
          System.err.println("f: " + f);
          System.err.println("cf: " + consistencizedF);
          System.err.println("e: " + e);
          System.err.println("ce: " + consistencizedE);
        }
        String fp = stringWithGaps(sent.f(), f);
        String ep = stringWithGaps(sent.e(), e);
        return String.format("f={{{%s}}} e={{{%s}}}", fp, ep);
      }
  
      @Override
      public int hashCode() {
        // Same implementation as in Arrays.hashCode():
        return 31 * f.hashCode() + e.hashCode();
      }
  
      @Override
      public boolean equals(Object o) {
        if (!(o instanceof DTUPhrase))
          return false;
        DTUPhrase dtu = (DTUPhrase) o;
        return f.equals(dtu.f) && e.equals(dtu.e);
      }
  
      DTUPhrase(DTUPhrase dtu) {
        sent = dtu.sent;
        f = dtu.f.clone();
        e = dtu.e.clone();
        consistencizedF = dtu.consistencizedF.clone();
        consistencizedE = dtu.consistencizedE.clone();
      }
  
      DTUPhrase(WordAlignment sent, int fi, int ei) {
        super();
        this.sent = sent;
        f = new CoverageSet();
        e = new CoverageSet();
        f.set(fi);
        e.set(ei);
        consistencizedF = new CoverageSet();
        consistencizedE = new CoverageSet();
      }
  
      DTUPhrase(WordAlignment sent, CoverageSet f, CoverageSet e) {
        super();
        this.sent = sent;
        this.f = f;
        this.e = e;
        consistencizedF = new CoverageSet();
        consistencizedE = new CoverageSet();
      }
  
      boolean isConsistencizedE(int ei) {
        return consistencizedE.get(ei);
      }
  
      boolean isConsistencizedF(int fi) {
        return consistencizedF.get(fi);
      }
  
      void setConsistencizedE(int ei) {
        consistencizedE.set(ei);
      }
  
      void setConsistencizedF(int fi) {
        consistencizedF.set(fi);
      }
  
      boolean consistencize(int i, boolean source) {
        if (!consistencize(i, source, true))
          return false;
  
        // Drop phrase if too large:
        if (sizeF() > maxSize)
          return false;
        if (sizeE() > maxSize)
          return false;
        if (!fContiguous() || !eContiguous()) {
          if (sizeF() > maxSize)
            return false;
          if (sizeE() > maxSize)
            return false;
          if (spanF() > maxSpan)
            return false;
          if (spanE() > maxSpan)
            return false;
        }
        return true;
      }
  
      boolean consistencize(int i, boolean source, boolean topLevel) {
        if (sizeF() > maxSize)
          return false;
        if (sizeE() > maxSize)
          return false;
  
        if (source) {
          setConsistencizedF(i);
          for (int ei : sent.f2e(i)) {
            if (!isConsistencizedE(ei)) {
              addE(ei);
              if (!consistencize(ei, false, false))
                return false;
            }
          }
        } else {
          setConsistencizedE(i);
          for (int fi : sent.e2f(i)) {
            if (!isConsistencizedF(fi)) {
              addF(fi);
              if (!consistencize(fi, true, false))
                return false;
            }
          }
        }
  
        // Consistencize words that have been added, but that may not be
        // consistent:
        if (topLevel) {
          for (int fi : toConsistencizeInF()) {
            if (!consistencize(fi, true, true))
              return false;
          }
          for (int ei : toConsistencizeInE()) {
            if (!consistencize(ei, false, true))
              return false;
          }
        }
        return true;
      }
  
      boolean hasUnalignedGap() {
        boolean unalignedGap = hasUnalignedGap(sent, f, true)
            || hasUnalignedGap(sent, e, false);
        if (DEBUG) {
          System.err.println("f: " + sent.f());
          System.err.println("e: " + sent.e());
          System.err.println("fs: " + f);
          System.err.println("es: " + e);
          System.err.println("gap: " + hasUnalignedGap(sent, f, true));
          System.err.println("gap: " + hasUnalignedGap(sent, e, false));
        }
        return unalignedGap;
      }
  
      boolean hasUnalignedGap(WordAlignment sent, BitSet fs, boolean source) {
        if (fs.isEmpty())
          return false;
        int startIdx, endIdx = 0;
        while (true) {
          startIdx = fs.nextClearBit(fs.nextSetBit(endIdx));
          endIdx = fs.nextSetBit(startIdx) - 1;
          if (startIdx > endIdx)
            break;
          boolean unalignedGap = true;
          for (int i = startIdx; i <= endIdx; ++i) {
            assert (!fs.get(i));
            if (source) {
              if (!sent.f2e(i).isEmpty()) {
                unalignedGap = false;
                break;
              }
            } else {
              if (!sent.e2f(i).isEmpty()) {
                unalignedGap = false;
                break;
              }
            }
          }
          if (unalignedGap)
            return true;
        }
        return false;
      }
  
      boolean hasUnalignedSubphrase() {
        return hasUnalignedSubphrase(sent, f, true)
            || hasUnalignedSubphrase(sent, e, false);
      }
  
      boolean hasUnalignedSubphrase(WordAlignment sent, BitSet fs, boolean source) {
        int startIdx, endIdx = 0;
        while (true) {
          startIdx = fs.nextSetBit(endIdx);
          if (startIdx < 0)
            break;
          endIdx = fs.nextClearBit(startIdx) - 1;
          boolean unalignedSP = true;
          for (int i = startIdx; i <= endIdx; ++i) {
            if (source) {
              if (!sent.f2e(i).isEmpty()) {
                unalignedSP = false;
                break;
              }
            } else {
              if (!sent.e2f(i).isEmpty()) {
                unalignedSP = false;
                break;
              }
            }
          }
          ++endIdx;
          if (unalignedSP)
            return true;
        }
        return false;
      }
  
      // boolean hasLooseGaps() { return hasLooseGap(sent, f, true) ||
      // hasLooseGap(sent, e, false); }
      boolean hasLooseGapsE() {
        return hasLooseGap(sent, e, false);
      }
  
      boolean hasLooseGapsF() {
        return hasLooseGap(sent, f, true);
      }
  
      boolean hasLooseGap(WordAlignment sent, BitSet fs, boolean source) {
        if (fs.isEmpty())
          return false;
        int startIdx, endIdx = 0;
        while (true) {
          // Position of the gap:
          startIdx = fs.nextClearBit(fs.nextSetBit(endIdx));
          endIdx = fs.nextSetBit(startIdx) - 1;
          if (startIdx > endIdx)
            break;
          if (source) {
            // if (sent.f2e(startIdx).isEmpty() || sent.f2e(startIdx).isEmpty()) {
            if (sent.f2e(startIdx).isEmpty() || sent.f2e(endIdx).isEmpty()) {
              return true;
            }
          } else {
            // if (sent.e2f(endIdx).isEmpty() || sent.e2f(endIdx).isEmpty()) {
            if (sent.e2f(startIdx).isEmpty() || sent.e2f(endIdx).isEmpty()) {
              return true;
            }
          }
        }
        return false;
      }
  
      boolean consistencize() {
        boolean done = false;
        while (!done) {
          boolean doneF = false, doneE = false;
          if (f.equals(consistencizedF)) {
            doneF = true;
          } else {
            for (int fi : f)
              if (!consistencizedF.get(fi))
                if (!consistencize(fi, true))
                  return false;
            if (e.isEmpty())
              return false;
          }
          if (e.equals(consistencizedE)) {
            doneE = true;
          } else {
            for (int ei : e)
              if (!consistencizedE.get(ei))
                if (!consistencize(ei, false))
                  return false;
            if (f.isEmpty())
              return false;
          }
          done = doneF && doneE;
        }
        return true;
      }
  
      BitSet adjacentWords(BitSet bitset, boolean growOutside) {
        BitSet adjWords = new BitSet();
        int firstI = bitset.nextSetBit(0);
        int lastI = bitset.length() - 1;
        int si = 0;
  