static class BlockDiff {

  public CopyBlock asCopyBlock() { return null; }

  public NewBlock  asNewBlock () { return null; }

}

static class CopyBlock extends BlockDiff {

  int firstLine, lines;

  CopyBlock(int firstLine, int lines) {

    this.firstLine = firstLine;

    this.lines = lines;

  }

  public CopyBlock asCopyBlock() { return this; }

  public int getFirstLine() { return firstLine; }

  public int getLines() { return lines; }

}

static class NewBlock extends BlockDiff {

  int originalStart;

  List<String> contents;

  NewBlock(int originalStart, List<String> contents) {

    this.originalStart = originalStart;

    this.contents = contents;

  }

  public NewBlock  asNewBlock () { return this; }

  public int getOriginalStart() {

    return originalStart;

  }

  public List<String> getContents() {

    return contents;

  }

}

static class ExplodedLine {

  int type;

  String left, right;

  int leftIndex, rightIndex;

  ExplodedLine(int type, String left, String right, int leftIndex, int rightIndex) {

    this.type = type;

    this.left = left;

    this.right = right;

    this.leftIndex = leftIndex;

    this.rightIndex = rightIndex;

  }

  public int getType() {

    return type;

  }

  public String getLeft() {

    return left;

  }

  public String getRight() {

    return right;

  }

  public int getLeftIndex() {

    return leftIndex;

  }

  public int getRightIndex() {

    return rightIndex;

  }

}

static class BlockDiffer {

  public static final int IDENTICAL = 0;

  public static final int DIFFERENT = 1;

  public static final int LEFT_ONLY = 2;

  public static final int RIGHT_ONLY = 3;

  private static void printChange(EGDiff.change change) {

    if (change != null) {

      System.out.println("line0="+change.line0+", line1="+change.line1

        +", inserted="+change.inserted+", deleted="+change.deleted);

      printChange(change.link);

    }

  }

  /** Generates the text content of a Unified-format context diff between 2 files

   *  (NB the 'files-changed' header must be added separately).

   */

  public static List<String> generateUniDiff(List<String> fileA, List<String> fileB, int contextSize) {

    EGDiff diff = new EGDiff(fileA.toArray(), fileB.toArray());

    EGDiff.change change = diff.diff_2(false);

    if (change != null) {

      int inserted, deleted;

      List<String> hunkLines = new ArrayList<String>();

      int cumulExtraLinesBwrtA = 0;

      // Each hunk is generated with a header

      do {

        int line0 = change.line0, line1 = change.line1;

        int changeStart = ((line1 < line0) ? line1 : line0);

        int contextStart = ((changeStart > contextSize) ? changeStart - contextSize : 0);

        int headerPosn = hunkLines.size();

        // Provide the first lines of context

        for (int i = contextStart; i < changeStart; i++)

          //System.out.println(" " + fileA.get(i));

          hunkLines.add(" " + fileA.get(i));

        boolean hunkFinish = false;

        // Step through each change giving the change lines and following context

        do {

          inserted = change.inserted;

          deleted = change.deleted;

          line0 = change.line0;

          line1 = change.line1;

          if (line1 < line0) // An insert comes earlier

            while (inserted-- > 0)

              hunkLines.add("+" + fileB.get(line1++));

          while (deleted-- > 0)

            hunkLines.add("-" + fileA.get(line0++));

          while (inserted-- > 0)

            hunkLines.add("+" + fileB.get(line1++));

          // Lines following are trailing context, identical in fileA and fileB

          // The next change may overlap the context, so check and if so, form one hunk

          EGDiff.change nextChange = change.link;

          int nextChangeStart = fileA.size();

          if (nextChange != null)

            nextChangeStart = ((nextChange.line1 < nextChange.line0) ? nextChange.line1 : nextChange.line0);

          if (nextChangeStart - line0 > contextSize * 2) { // A separate hunk

            nextChangeStart = line0 + contextSize;

            hunkFinish = true;

          }

          if (nextChangeStart > fileA.size())

            nextChangeStart = fileA.size(); // Limit to file size

          while (line0 < nextChangeStart) {

            hunkLines.add(" " + fileA.get(line0++));

            line1++; // Keep in sync with trailing context

          }

          change = change.link;

        } while (!hunkFinish && change != null);

        int hunkStartB = contextStart + cumulExtraLinesBwrtA;

        int hunkTotA = line0 - contextStart;

        int hunkTotB = line1 - hunkStartB;

        hunkLines.add(headerPosn, "@@ -" + (contextStart + 1) + ',' + hunkTotA +

                        " +" + (hunkStartB + 1) + ',' + hunkTotB + " @@");

        cumulExtraLinesBwrtA += hunkTotB - hunkTotA;

      } while (change != null);

      return hunkLines;

    }

    return null;

  }

/* For testing:

  private static void printUniDiff(List<String> fileA, List<String> fileB, int contextSize) {

    List<String> uniDiff = generateUniDiff(fileA, fileB, contextSize);

    if (uniDiff != null)

      for (int j = 0; j < uniDiff.size(); j++)

        System.out.println(uniDiff.get(j));

  }

 */

  public static List<BlockDiff> diffLines(List<String> lines, List<String> reference) {

    List<BlockDiff> diffs = new ArrayList<BlockDiff>();

    EGDiff diff = new EGDiff(reference.toArray(), lines.toArray());

    EGDiff.change change = diff.diff_2(false);

    //printChange(change);

    //printUniDiff(reference, lines, 3);

    int l0 = 0, l1 = 0;

    while (change != null) {

      if (change.line0 > l0 && change.line1 > l1)

        diffs.add(new CopyBlock(l0, change.line0-l0));

      if (change.inserted != 0)

        diffs.add(new NewBlock(change.line1, lines.subList(change.line1, change.line1+change.inserted)));

      l0 = change.line0 + change.deleted;

      l1 = change.line1 + change.inserted;

      change = change.link;

    }

    if (l0 < reference.size())

      diffs.add(new CopyBlock(l0, reference.size()-l0));

    return diffs;

  }

  /** fills files with empty lines to align matching blocks

   *

   * @param file1 first file

   * @param file2 second file

   * @return an array with two lists

   */

  public static List<ExplodedLine> explode(List<String> file1, List<String> file2) {

    List<ExplodedLine> lines = new ArrayList<ExplodedLine>();

    List<BlockDiff> diffs = BlockDiffer.diffLines(file2, file1);

    int lastLineCopied = 0, rightOnlyStart = -1, rightPosition = 0;

    for (int i = 0; i < diffs.size(); i++) {

      BlockDiff diff = diffs.get(i);

      if (diff instanceof CopyBlock) {

        CopyBlock copyBlock = (CopyBlock) diff;

        if (lastLineCopied < copyBlock.getFirstLine()) {

          if (rightOnlyStart >= 0) {

            int overlap = Math.min(lines.size()-rightOnlyStart, copyBlock.getFirstLine()-lastLineCopied);

            //lines.subList(rightOnlyStart, rightOnlyStart+overlap).clear();

            convertRightOnlyToDifferent(lines, rightOnlyStart, overlap, file1, lastLineCopied);

            lastLineCopied += overlap;

          }

          addBlock(lines, LEFT_ONLY, file1, lastLineCopied, copyBlock.getFirstLine(), lastLineCopied, -1);

        }

        addBlock(lines, IDENTICAL, file1, copyBlock.getFirstLine(), copyBlock.getFirstLine()+copyBlock.getLines(),

          copyBlock.getFirstLine(), rightPosition);

        rightPosition += copyBlock.getLines();

        lastLineCopied = copyBlock.getFirstLine()+copyBlock.getLines();

        rightOnlyStart = -1;

      } else if (diff instanceof NewBlock) {

        NewBlock newBlock = (NewBlock) diff;

        /*if (nextDiff instanceof BlockDiffer.CopyBlock) {

          BlockDiffer.CopyBlock copyBlock = (BlockDiffer.CopyBlock) nextDiff;

          copyBlock.getFirstLine()-lastLineCopied*/

        rightOnlyStart = lines.size();

        addBlock(lines, RIGHT_ONLY, newBlock.getContents(), 0, newBlock.getContents().size(), -1, rightPosition);

        rightPosition += newBlock.getContents().size();

      }

    }

    if (rightOnlyStart >= 0) {

      int overlap = Math.min(lines.size()-rightOnlyStart, file1.size()-lastLineCopied);

      //lines.subList(rightOnlyStart, rightOnlyStart+overlap).clear();

      convertRightOnlyToDifferent(lines, rightOnlyStart, overlap, file1, lastLineCopied);

      lastLineCopied += overlap;

    }

    addBlock(lines, LEFT_ONLY, file1, lastLineCopied, file1.size(), lastLineCopied, -1);

    return lines;

  }

  private static void convertRightOnlyToDifferent(List<ExplodedLine> lines, int start, int numLines,

                                                  List<String> leftLines, int leftStart) {

    for (int i = 0; i < numLines; i++) {

      ExplodedLine line = lines.get(start+i);

      lines.set(start+i,

        new ExplodedLine(DIFFERENT, leftLines.get(i+leftStart), line.getRight(), i+leftStart, line.getRightIndex()));

    }

  }

  private static void addBlock(List<ExplodedLine> lines, int type, List<String> srcLines, int start, int end,

                               int leftStart, int rightStart) {

    for (int i = start; i < end; i++)

      lines.add(new ExplodedLine(type, type == RIGHT_ONLY ? "" : srcLines.get(i),

                                       type == LEFT_ONLY ? "" : srcLines.get(i),

                                       type == RIGHT_ONLY ? -1 : i - start + leftStart,

                                       type == LEFT_ONLY ? -1 : i - start + rightStart));

  }

  public static List<ExplodedLine> condense(List<ExplodedLine> lines) {

    List<ExplodedLine> result = new ArrayList<ExplodedLine>();

    for (Iterator<ExplodedLine> i = lines.iterator(); i.hasNext();) {

      ExplodedLine line = i.next();

      if (line.getType() == IDENTICAL) {

        if (result.isEmpty() || result.get(result.size()-1).getType() != IDENTICAL)

          result.add(new ExplodedLine(IDENTICAL, "[...]", "[...]", -1, -1));

      } else

        result.add(line);

    }

    return result;

  }

}