class FilterLineReachabilityAnswerer extends Answerer {

  @VisibleForTesting
  static BlockingProperties findBlockingPropsForLine(
      int blockedLineNum, List<PermitAndDenyBdds> bdds) {
    PermitAndDenyBdds blockedLine = bdds.get(blockedLineNum);

    ImmutableSortedSet.Builder<LineAndWeight> linesByWeight =
        ImmutableSortedSet.orderedBy(LineAndWeight.COMPARATOR);

    // First, we find all lines before blockedLine that actually terminate any packets
    // blockedLine intends to. These, collectively, are the (partially-)blocking lines.
    //
    // In this same loop, we also compute the overlap of each such line with the blocked line
    // and weight each blocking line by that overlap.
    //
    // Finally, we record whether any of these lines has a different action than the blocked line.
    PermitAndDenyBdds restOfLine = blockedLine;
    boolean diffAction = false; // true if some partially-blocking line has a different action.
    for (int prevLineNum = 0; prevLineNum < blockedLineNum && !restOfLine.isZero(); prevLineNum++) {
      PermitAndDenyBdds prevLine = bdds.get(prevLineNum);

      if (!prevLine.getMatchBdd().andSat(restOfLine.getMatchBdd())) {
        continue;
      }

      BDD blockedLineOverlap = prevLine.getMatchBdd().and(blockedLine.getMatchBdd());
      linesByWeight.add(new LineAndWeight(prevLineNum, blockedLineOverlap.satCount()));
      diffAction = diffAction || takeDifferentActions(prevLine, restOfLine);
      restOfLine = restOfLine.diff(prevLine.getMatchBdd());
    }

    // In this second loop, we compute the answer:
    // * include partially-blocking lines in weight order until the blocked line is fully blocked by
    //   this subset.
    // * also include the largest blocking line with a different action than the blocked line, if
    //   not already in the above subset.
    ImmutableSortedSet.Builder<Integer> answerLines = ImmutableSortedSet.naturalOrder();
    restOfLine = blockedLine;
    boolean needDiffAction = diffAction;
    for (LineAndWeight line : linesByWeight.build()) {
      int curLineNum = line.getLine();
      PermitAndDenyBdds curLine = bdds.get(curLineNum);
      boolean curDiff = takeDifferentActions(curLine, blockedLine);

      // The original line is still not blocked, or this is the first line with a different action.
      if (!restOfLine.isZero() || needDiffAction && curDiff) {
        restOfLine = restOfLine.diff(curLine.getMatchBdd());
        answerLines.add(curLineNum);
        needDiffAction = needDiffAction && !curDiff;
      }

      // The original line is blocked and we have a line with a different action (if such exists).
      if (restOfLine.isZero() && !needDiffAction) {
        break;
      }
    }

    return new BlockingProperties(answerLines.build(), diffAction);
  }

  public  FilterLineReachabilityAnswerer(Question question, IBatfish batfish);

}