merge two conflicted diff file `ver1` and `ver2` on the basis of `origin` file. Switched to C++ version.

merge-conflict.cpp

/* http://ideone.com/wcrspw

input: <ORIGIN...>
       =====
       <VERSION 1...>
       =====
       <VERSION 2...>
       =====

example:
ab
cd
ef
=====
ab
fg
=====
ab
cd
=====

*/

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <tuple>

using namespace std;

enum class LCSDir {
  InsertVerX, /* go left */
  DeleteOrigin, /* go up */
  Retains /* up-left */
};

enum class DiffStatus { Matched, Conflicted };

struct diff_t {
  struct origin_diff_t {
    DiffStatus status;
    LCSDir dir[2];
  } origin;
  struct inserted_after_diff_t {
    DiffStatus status;
    struct { int start, length; } pos[2];
  } ins_after;
};

vector<string> get_input() {
  string str;
  vector<string> res {"{-# DUMMY #-}"};
  while (cin >> str) {
    if (str == "=====")
      break;
    res.push_back(str);
  }
  return move(res);
}

vector<vector<LCSDir>> compute_lcs(const vector<string>& xs,
                                   const vector<string>& ys) {
  vector<vector<int>> lcs(xs.size(), vector<int>(ys.size()));
  vector<vector<LCSDir>> res(xs.size(), vector<LCSDir>(ys.size()));
  /* initialize base cases of LCS */
  for (size_t i = 1; i < xs.size(); i++) {
    lcs[i][0] = 0;
    res[i][0] = LCSDir::DeleteOrigin;
  }
  for (size_t j = 1; j < ys.size(); j++) {
    lcs[0][j] = 0;
    res[0][j] = LCSDir::InsertVerX;
  }
  lcs[0][0] = 0;
  res[0][0] = LCSDir::DeleteOrigin;
  /* lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1], ?? lcs[i-1][j-1]+1 ) */
  for (size_t i = 1; i < xs.size(); i++) {
    for (size_t j = 1; j < ys.size(); j++) {
      if (xs[i] == ys[j]) {
        lcs[i][j] = lcs[i-1][j-1] + 1;
        res[i][j] = LCSDir::Retains;
      } else {
        if (lcs[i-1][j] >= lcs[i][j-1]) {
          lcs[i][j] = lcs[i-1][j];
          res[i][j] = LCSDir::DeleteOrigin;
        } else {
          lcs[i][j] = lcs[i][j-1];
          res[i][j] = LCSDir::InsertVerX;
        }
      }
    }
  }
  return move(res);
}

tuple<int,int> calculate_inserted_length(const vector<LCSDir>& lcs_line, int idx) {
  int len = 0;
  while (lcs_line[idx] == LCSDir::InsertVerX) {
    len++;
    idx--;
  }
  return tuple<int, int>(idx, len);
}

vector<diff_t> merge_diff(
  const vector<string>& origin,
  const vector<string>& ver1, const vector<vector<LCSDir>>& lcs1,
  const vector<string>& ver2, const vector<vector<LCSDir>>& lcs2)
{
  int i = ver1.size() - 1, j = ver2.size() - 1;
  vector<diff_t> diff(origin.size());
  for (int line = origin.size()-1; line>=0; line--) {
    int ins1_len, ins2_len;
    tie(i, ins1_len) = calculate_inserted_length(lcs1[line], i);
    tie(j, ins2_len) = calculate_inserted_length(lcs2[line], j);

    if (lcs1[line][i] == lcs2[line][j])
      diff[line].origin.status = DiffStatus::Matched;
    else
      diff[line].origin.status = DiffStatus::Conflicted;
    diff[line].origin.dir[0] = lcs1[line][i];
    diff[line].origin.dir[1] = lcs2[line][j];

    if (ins1_len==ins2_len && equal(ver1.begin()+i+1, ver1.begin()+i+1+ins1_len,
                                    ver2.begin()+j+1))
      diff[line].ins_after.status = DiffStatus::Matched;
    else
      diff[line].ins_after.status = DiffStatus::Conflicted;
    diff[line].ins_after.pos[0].start = i + 1;
    diff[line].ins_after.pos[0].length = ins1_len;
    diff[line].ins_after.pos[1].start = j + 1;
    diff[line].ins_after.pos[1].length = ins2_len;

    if (lcs1[line][i] == LCSDir::Retains) i--;
    if (lcs2[line][j] == LCSDir::Retains) j--;
  }
  return move(diff);
}

void print_conflict(const vector<diff_t>& diff,
                    const vector<string>& origin,
                    const vector<string>& ver,
                    int which, int begin, int end) {
  for (int i = begin; i != end; i++) {
    if (i!=begin || diff[i].origin.status==DiffStatus::Conflicted)
      if (diff[i].origin.dir[which] == LCSDir::Retains)
        cout << origin[i] << endl;
    for (int j = 0; j != diff[i].ins_after.pos[which].length; j++)
      cout << ver[diff[i].ins_after.pos[which].start + j] << endl;
  }
}

void print_diff(const vector<diff_t>& diff,
                const vector<string>& origin,
                const vector<string>& ver1,
                const vector<string>& ver2) {
  using D = DiffStatus;
  cout << "@@@ origin,ver1,ver2 diff" << endl;
  for (size_t begin = 0,end; begin < origin.size(); begin = end) {
    /* initial interval is [begin, begin+1); i.e. end = begin+1 */
    end = begin + 1;
    if (diff[begin].origin.status==D::Matched
     && diff[begin].origin.dir[0]==LCSDir::Retains)
      cout << origin[begin] << endl;
    if (diff[begin].origin.status==D::Matched /* no conflict for this line */
     && diff[begin].ins_after.status==D::Matched)
      continue;
    /* search for end; margin 3 lines: at least 3 conflict-free lines */
    for (size_t i = end; i<end+3 && i<origin.size(); i++)
      if (diff[i].origin.status==D::Conflicted || diff[i].ins_after.status==D::Conflicted)
        end = i + 1;
    cout << "<<<<<<<<<<<<<<<<<< ver1" << endl;
    print_conflict(diff, origin, ver1, 0, begin, end);
    cout << "==================" << endl;
    print_conflict(diff, origin, ver2, 1, begin, end);
    cout << ">>>>>>>>>>>>>>>>>> ver2" << endl;
  }
}

int main() {
  const vector<string> origin = get_input();
  const vector<string> ver1 = get_input();
  const vector<string> ver2 = get_input();

  const vector<vector<LCSDir>> lcs_origin_1 = compute_lcs(origin, ver1);
  const vector<vector<LCSDir>> lcs_origin_2 = compute_lcs(origin, ver2);

  const vector<diff_t> diff =
    merge_diff(origin, ver1, lcs_origin_1, ver2, lcs_origin_2);

  print_diff(diff, origin, ver1, ver2);
  return 0;
}