Fixed merge algorithm regarding adjacent modifications

JGit merge algorithm behaved differently from C Git when
we had adjacent modifications. If line 9 was modified by
OURS and line 10 by theirs then C Git will return a
conflict while JGit was seeing this as independent
modifications. This change is not only there to achieve
compatibility, but there where also some really wrong
merge results produced by JGit in the area of adjacent
modifications.

Change-Id: I8d77cb59e82638214e45b3cf9ce3a1f1e9b35c70
Signed-off-by: Christian Halstrick <christian.halstrick@sap.com>

org.eclipse.jgit.test/tst/org/eclipse/jgit/merge/MergeAlgorithmTest.java

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/merge/MergeAlgorithmTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/merge/MergeAlgorithmTest.java
index c929629..9b4b714 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/merge/MergeAlgorithmTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/merge/MergeAlgorithmTest.java
@@ -107,7 +107,7 @@ public void testTwoNonConflictingModifications() throws IOException {
 	 * @throws IOException
 	 */
 	public void testTwoComplicatedModifications() throws IOException {
-		assertEquals(t("a<ZZZZfZh=bYdYYYY>ZY"),
+		assertEquals(t("a<ZZZZfZhZj=bYdYYYYiY>"),
 				merge("abcdefghij", "aZZZZfZhZj", "abYdYYYYiY"));
 	}
 
@@ -153,6 +153,18 @@ public void testDeleteVsModify() throws IOException {
 				merge("abcdefghij", "abdefghij", "abZdefghij"));
 	}
 
+	public void testInsertVsModify() throws IOException {
+		assertEquals(t("a<bZ=XY>"), merge("ab", "abZ", "aXY"));
+	}
+
+	public void testAdjacentModifications() throws IOException {
+		assertEquals(t("a<Zc=bY>d"), merge("abcd", "aZcd", "abYd"));
+	}
+
+	public void testSeperateModifications() throws IOException {
+		assertEquals(t("aZcYe"), merge("abcde", "aZcde", "abcYe"));
+	}
+
 	private String merge(String commonBase, String ours, String theirs) throws IOException {
 		MergeResult r = MergeAlgorithm.merge(RawTextComparator.DEFAULT,
 				T(commonBase), T(ours), T(theirs));

org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeAlgorithm.java

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeAlgorithm.java b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeAlgorithm.java
index 8682487..aee0ba9 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeAlgorithm.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeAlgorithm.java
@@ -103,7 +103,7 @@ public static <S extends Sequence> MergeResult<S> merge(
 		// leave the loop when there are no edits more for ours or for theirs
 		// (or both)
 		while (theirsEdit != END_EDIT || oursEdit != END_EDIT) {
-			if (oursEdit.getEndA() <= theirsEdit.getBeginA()) {
+			if (oursEdit.getEndA() < theirsEdit.getBeginA()) {
 				// something was changed in ours not overlapping with any change
 				// from theirs. First add the common part in front of the edit
 				// then the edit.
@@ -115,7 +115,7 @@ public static <S extends Sequence> MergeResult<S> merge(
 						ConflictState.NO_CONFLICT);
 				current = oursEdit.getEndA();
 				oursEdit = nextEdit(baseToOurs);
-			} else if (theirsEdit.getEndA() <= oursEdit.getBeginA()) {
+			} else if (theirsEdit.getEndA() < oursEdit.getBeginA()) {
 				// something was changed in theirs not overlapping with any
 				// from ours. First add the common part in front of the edit
 				// then the edit.
@@ -179,10 +179,10 @@ public static <S extends Sequence> MergeResult<S> merge(
 				Edit nextOursEdit = nextEdit(baseToOurs);
 				Edit nextTheirsEdit = nextEdit(baseToTheirs);
 				for (;;) {
-					if (oursEdit.getEndA() > nextTheirsEdit.getBeginA()) {
+					if (oursEdit.getEndA() >= nextTheirsEdit.getBeginA()) {
 						theirsEdit = nextTheirsEdit;
 						nextTheirsEdit = nextEdit(baseToTheirs);
-					} else if (theirsEdit.getEndA() > nextOursEdit.getBeginA()) {
+					} else if (theirsEdit.getEndA() >= nextOursEdit.getBeginA()) {
 						oursEdit = nextOursEdit;
 						nextOursEdit = nextEdit(baseToOurs);
 					} else {