Merge branch 'cq-diff'

Per CQ 3559 "JGit - Eugene Myers O(ND) difference algorithm" we
have approval to check this into our master branch.

* cq-diff:
  Add file content merge algorithm
  Add performance tests for MyersDiff
  Add javadoc comments, remove unused code, shift comments to correct place
  Fixed MyersDiff to be able to handle more than 100k
  Fix some warnings regarding unnecessary imports and accessing static methods
  Add the "jgit diff" command
  Prepare RawText for diff-index and diff-files
  Add a test class for Myers' diff algorithm
  Add Myers' algorithm to generate diff scripts
  Add set to IntList

Conflicts:
	org.eclipse.jgit/src/org/eclipse/jgit/diff/RawText.java

Change-Id: Ia8e98d81ba1ab52f84d0258a40e6ef5eece9a5b1
CC: Christian Halstrick <christian.halstrick@sap.com>

9 files changed, 1429 insertions, 1 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffFormatter.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffFormatter.java
index 639ed77ee8..115d9baff3 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffFormatter.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffFormatter.java
@@ -114,7 +114,15 @@ public class DiffFormatter {
 		formatEdits(out, a, b, head.toEditList());
 	}
 
-	private void formatEdits(final OutputStream out, final RawText a,
+	/**
+	 * Formats a list of edits in unified diff format
+	 * @param out where the unified diff is written to
+	 * @param a the text A which was compared
+	 * @param b the text B which was compared
+	 * @param edits some differences which have been calculated between A and B
+	 * @throws IOException
+	 */
+	public void formatEdits(final OutputStream out, final RawText a,
 			final RawText b, final EditList edits) throws IOException {
 		for (int curIdx = 0; curIdx < edits.size();) {
 			Edit curEdit = edits.get(curIdx);
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/MyersDiff.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/MyersDiff.java
new file mode 100644
index 0000000000..055729961b
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/MyersDiff.java
@@ -0,0 +1,535 @@
+/*
+ * Copyright (C) 2008-2009, Johannes E. Schindelin <johannes.schindelin@gmx.de>
+ * Copyright (C) 2009, Johannes Schindelin <johannes.schindelin@gmx.de>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.eclipse.jgit.diff;
+
+import org.eclipse.jgit.util.IntList;
+import org.eclipse.jgit.util.LongList;
+
+/**
+ * Diff algorithm, based on "An O(ND) Difference Algorithm and its
+ * Variations", by Eugene Myers.
+ *
+ * The basic idea is to put the line numbers of text A as columns ("x") and the
+ * lines of text B as rows ("y").  Now you try to find the shortest "edit path"
+ * from the upper left corner to the lower right corner, where you can
+ * always go horizontally or vertically, but diagonally from (x,y) to
+ * (x+1,y+1) only if line x in text A is identical to line y in text B.
+ *
+ * Myers' fundamental concept is the "furthest reaching D-path on diagonal k":
+ * a D-path is an edit path starting at the upper left corner and containing
+ * exactly D non-diagonal elements ("differences").  The furthest reaching
+ * D-path on diagonal k is the one that contains the most (diagonal) elements
+ * which ends on diagonal k (where k = y - x).
+ *
+ * Example:
+ *
+ *    H E L L O   W O R L D
+ *    ____
+ *  L     \___
+ *  O         \___
+ *  W             \________
+ *
+ * Since every D-path has exactly D horizontal or vertical elements, it can
+ * only end on the diagonals -D, -D+2, ..., D-2, D.
+ *
+ * Since every furthest reaching D-path contains at least one furthest
+ * reaching (D-1)-path (except for D=0), we can construct them recursively.
+ *
+ * Since we are really interested in the shortest edit path, we can start
+ * looking for a 0-path, then a 1-path, and so on, until we find a path that
+ * ends in the lower right corner.
+ *
+ * To save space, we do not need to store all paths (which has quadratic space
+ * requirements), but generate the D-paths simultaneously from both sides.
+ * When the ends meet, we will have found "the middle" of the path.  From the
+ * end points of that diagonal part, we can generate the rest recursively.
+ *
+ * This only requires linear space.
+ *
+ * The overall (runtime) complexity is
+ *
+ *	O(N * D^2 + 2 * N/2 * (D/2)^2 + 4 * N/4 * (D/4)^2 + ...)
+ *	= O(N * D^2 * 5 / 4) = O(N * D^2),
+ *
+ * (With each step, we have to find the middle parts of twice as many regions
+ * as before, but the regions (as well as the D) are halved.)
+ *
+ * So the overall runtime complexity stays the same with linear space,
+ * albeit with a larger constant factor.
+ */
+public class MyersDiff {
+	/**
+	 * The list of edits found during the last call to {@link #calculateEdits()}
+	 */
+	protected EditList edits;
+
+	/**
+	 * The first text to be compared. Referred to as "Text A" in the comments
+	 */
+	protected Sequence a;
+
+	/**
+	 * The second text to be compared. Referred to as "Text B" in the comments
+	 */
+	protected Sequence b;
+
+	/**
+	 * The only constructor
+	 *
+	 * @param a   the text A which should be compared
+	 * @param b   the text B which should be compared
+	 */
+	public MyersDiff(Sequence a, Sequence b) {
+		this.a = a;
+		this.b = b;
+		calculateEdits();
+	}
+
+	/**
+	 * @return the list of edits found during the last call to {@link #calculateEdits()}
+	 */
+	public EditList getEdits() {
+		return edits;
+	}
+
+	// TODO: use ThreadLocal for future multi-threaded operations
+	MiddleEdit middle = new MiddleEdit();
+
+	/**
+	 * Entrypoint into the algorithm this class is all about. This method triggers that the
+	 * differences between A and B are calculated in form of a list of edits.
+	 */
+	protected void calculateEdits() {
+		edits = new EditList();
+
+		middle.initialize(0, a.size(), 0, b.size());
+		if (middle.beginA >= middle.endA &&
+				middle.beginB >= middle.endB)
+			return;
+
+		calculateEdits(middle.beginA, middle.endA,
+				middle.beginB, middle.endB);
+	}
+
+	/**
+	 * Calculates the differences between a given part of A against another given part of B
+	 * @param beginA start of the part of A which should be compared (0<=beginA<sizeof(A))
+	 * @param endA end of the part of A which should be compared (beginA<=endA<sizeof(A))
+	 * @param beginB start of the part of B which should be compared (0<=beginB<sizeof(B))
+	 * @param endB end of the part of B which should be compared (beginB<=endB<sizeof(B))
+	 */
+	protected void calculateEdits(int beginA, int endA,
+			int beginB, int endB) {
+		Edit edit = middle.calculate(beginA, endA, beginB, endB);
+
+		if (beginA < edit.beginA || beginB < edit.beginB) {
+			int k = edit.beginB - edit.beginA;
+			int x = middle.backward.snake(k, edit.beginA);
+			calculateEdits(beginA, x, beginB, k + x);
+		}
+
+		if (edit.getType() != Edit.Type.EMPTY)
+			edits.add(edits.size(), edit);
+
+		// after middle
+		if (endA > edit.endA || endB > edit.endB) {
+			int k = edit.endB - edit.endA;
+			int x = middle.forward.snake(k, edit.endA);
+			calculateEdits(x, endA, k + x, endB);
+		}
+	}
+
+	/**
+	 * A class to help bisecting the sequences a and b to find minimal
+	 * edit paths.
+	 *
+	 * As the arrays are reused for space efficiency, you will need one
+	 * instance per thread.
+	 *
+	 * The entry function is the calculate() method.
+	 */
+	class MiddleEdit {
+		void initialize(int beginA, int endA, int beginB, int endB) {
+			this.beginA = beginA; this.endA = endA;
+			this.beginB = beginB; this.endB = endB;
+
+			// strip common parts on either end
+			int k = beginB - beginA;
+			this.beginA = forward.snake(k, beginA);
+			this.beginB = k + this.beginA;
+
+			k = endB - endA;
+			this.endA = backward.snake(k, endA);
+			this.endB = k + this.endA;
+		}
+
+		/*
+		 * This function calculates the "middle" Edit of the shortest
+		 * edit path between the given subsequences of a and b.
+		 *
+		 * Once a forward path and a backward path meet, we found the
+		 * middle part.  From the last snake end point on both of them,
+		 * we construct the Edit.
+		 *
+		 * It is assumed that there is at least one edit in the range.
+		 */
+		// TODO: measure speed impact when this is synchronized
+		Edit calculate(int beginA, int endA, int beginB, int endB) {
+			if (beginA == endA || beginB == endB)
+				return new Edit(beginA, endA, beginB, endB);
+			this.beginA = beginA; this.endA = endA;
+			this.beginB = beginB; this.endB = endB;
+
+			/*
+			 * Following the conventions in Myers' paper, "k" is
+			 * the difference between the index into "b" and the
+			 * index into "a".
+			 */
+			int minK = beginB - endA;
+			int maxK = endB - beginA;
+
+			forward.initialize(beginB - beginA, beginA, minK, maxK);
+			backward.initialize(endB - endA, endA, minK, maxK);
+
+			for (int d = 1; ; d++)
+				if (forward.calculate(d) ||
+						backward.calculate(d))
+					return edit;
+		}
+
+		/*
+		 * For each d, we need to hold the d-paths for the diagonals
+		 * k = -d, -d + 2, ..., d - 2, d.  These are stored in the
+		 * forward (and backward) array.
+		 *
+		 * As we allow subsequences, too, this needs some refinement:
+		 * the forward paths start on the diagonal forwardK =
+		 * beginB - beginA, and backward paths start on the diagonal
+		 * backwardK = endB - endA.
+		 *
+		 * So, we need to hold the forward d-paths for the diagonals
+		 * k = forwardK - d, forwardK - d + 2, ..., forwardK + d and
+		 * the analogue for the backward d-paths.  This means that
+		 * we can turn (k, d) into the forward array index using this
+		 * formula:
+		 *
+		 *	i = (d + k - forwardK) / 2
+		 *
+		 * There is a further complication: the edit paths should not
+		 * leave the specified subsequences, so k is bounded by
+		 * minK = beginB - endA and maxK = endB - beginA.  However,
+		 * (k - forwardK) _must_ be odd whenever d is odd, and it
+		 * _must_ be even when d is even.
+		 *
+		 * The values in the "forward" and "backward" arrays are
+		 * positions ("x") in the sequence a, to get the corresponding
+		 * positions ("y") in the sequence b, you have to calculate
+		 * the appropriate k and then y:
+		 *
+		 *	k = forwardK - d + i * 2
+		 *	y = k + x
+		 *
+		 * (substitute backwardK for forwardK if you want to get the
+		 * y position for an entry in the "backward" array.
+		 */
+		EditPaths forward = new ForwardEditPaths();
+		EditPaths backward = new BackwardEditPaths();
+
+		/* Some variables which are shared between methods */
+		protected int beginA, endA, beginB, endB;
+		protected Edit edit;
+
+		abstract class EditPaths {
+			private IntList x = new IntList();
+			private LongList snake = new LongList();
+			int beginK, endK, middleK;
+			int prevBeginK, prevEndK;
+			/* if we hit one end early, no need to look further */
+			int minK, maxK; // TODO: better explanation
+
+			final int getIndex(int d, int k) {
+// TODO: remove
+if (((d + k - middleK) % 2) == 1)
+	throw new RuntimeException("odd: " + d + " + " + k + " - " + middleK);
+				return (d + k - middleK) / 2;
+			}
+
+			final int getX(int d, int k) {
+// TODO: remove
+if (k < beginK || k > endK)
+	throw new RuntimeException("k " + k + " not in " + beginK + " - " + endK);
+				return x.get(getIndex(d, k));
+			}
+
+			final long getSnake(int d, int k) {
+// TODO: remove
+if (k < beginK || k > endK)
+	throw new RuntimeException("k " + k + " not in " + beginK + " - " + endK);
+				return snake.get(getIndex(d, k));
+			}
+
+			private int forceKIntoRange(int k) {
+				/* if k is odd, so must be the result */
+				if (k < minK)
+					return minK + ((k ^ minK) & 1);
+				else if (k > maxK)
+					return maxK - ((k ^ maxK) & 1);
+				return k;
+			}
+
+			void initialize(int k, int x, int minK, int maxK) {
+				this.minK = minK;
+				this.maxK = maxK;
+				beginK = endK = middleK = k;
+				this.x.clear();
+				this.x.add(x);
+				snake.clear();
+				snake.add(newSnake(k, x));
+			}
+
+			abstract int snake(int k, int x);
+			abstract int getLeft(int x);
+			abstract int getRight(int x);
+			abstract boolean isBetter(int left, int right);
+			abstract void adjustMinMaxK(final int k, final int x);
+			abstract boolean meets(int d, int k, int x, long snake);
+
+			final long newSnake(int k, int x) {
+				long y = k + x;
+				long ret = ((long) x) << 32;
+				return ret | y;
+			}
+
+			final int snake2x(long snake) {
+				return (int) (snake >>> 32);
+			}
+
+			final int snake2y(long snake) {
+				return (int) snake;
+			}
+
+			final boolean makeEdit(long snake1, long snake2) {
+				int x1 = snake2x(snake1), x2 = snake2x(snake2);
+				int y1 = snake2y(snake1), y2 = snake2y(snake2);
+				/*
+				 * Check for incompatible partial edit paths:
+				 * when there are ambiguities, we might have
+				 * hit incompatible (i.e. non-overlapping)
+				 * forward/backward paths.
+				 *
+				 * In that case, just pretend that we have
+				 * an empty edit at the end of one snake; this
+				 * will force a decision which path to take
+				 * in the next recursion step.
+				 */
+				if (x1 > x2 || y1 > y2) {
+					x1 = x2;
+					y1 = y2;
+				}
+				edit = new Edit(x1, x2, y1, y2);
+				return true;
+			}
+
+			boolean calculate(int d) {
+				prevBeginK = beginK;
+				prevEndK = endK;
+				beginK = forceKIntoRange(middleK - d);
+				endK = forceKIntoRange(middleK + d);
+				// TODO: handle i more efficiently
+				// TODO: walk snake(k, getX(d, k)) only once per (d, k)
+				// TODO: move end points out of the loop to avoid conditionals inside the loop
+				// go backwards so that we can avoid temp vars
+				for (int k = endK; k >= beginK; k -= 2) {
+					int left = -1, right = -1;
+					long leftSnake = -1L, rightSnake = -1L;
+					// TODO: refactor into its own function
+					if (k > prevBeginK) {
+						int i = getIndex(d - 1, k - 1);
+						left = x.get(i);
+						int end = snake(k - 1, left);
+						leftSnake = left != end ?
+							newSnake(k - 1, end) :
+							snake.get(i);
+						if (meets(d, k - 1, end, leftSnake))
+							return true;
+						left = getLeft(end);
+					}
+					if (k < prevEndK) {
+						int i = getIndex(d - 1, k + 1);
+						right = x.get(i);
+						int end = snake(k + 1, right);
+						rightSnake = right != end ?
+							newSnake(k + 1, end) :
+							snake.get(i);
+						if (meets(d, k + 1, end, rightSnake))
+							return true;
+						right = getRight(end);
+					}
+					int newX;
+					long newSnake;
+					if (k >= prevEndK ||
+							(k > prevBeginK &&
+							 isBetter(left, right))) {
+						newX = left;
+						newSnake = leftSnake;
+					}
+					else {
+						newX = right;
+						newSnake = rightSnake;
+					}
+					if (meets(d, k, newX, newSnake))
+						return true;
+					adjustMinMaxK(k, newX);
+					int i = getIndex(d, k);
+					x.set(i, newX);
+					snake.set(i, newSnake);
+				}
+				return false;
+			}
+		}
+
+		class ForwardEditPaths extends EditPaths {
+			final int snake(int k, int x) {
+				for (; x < endA && k + x < endB; x++)
+					if (!a.equals(x, b, k + x))
+						break;
+				return x;
+			}
+
+			final int getLeft(final int x) {
+				return x;
+			}
+
+			final int getRight(final int x) {
+				return x + 1;
+			}
+
+			final boolean isBetter(final int left, final int right) {
+				return left > right;
+			}
+
+			final void adjustMinMaxK(final int k, final int x) {
+				if (x >= endA || k + x >= endB) {
+					if (k > backward.middleK)
+						maxK = k;
+					else
+						minK = k;
+				}
+			}
+
+			final boolean meets(int d, int k, int x, long snake) {
+				if (k < backward.beginK || k > backward.endK)
+					return false;
+				// TODO: move out of loop
+				if (((d - 1 + k - backward.middleK) % 2) == 1)
+					return false;
+				if (x < backward.getX(d - 1, k))
+					return false;
+				makeEdit(snake, backward.getSnake(d - 1, k));
+				return true;
+			}
+		}
+
+		class BackwardEditPaths extends EditPaths {
+			final int snake(int k, int x) {
+				for (; x > beginA && k + x > beginB; x--)
+					if (!a.equals(x - 1, b, k + x - 1))
+						break;
+				return x;
+			}
+
+			final int getLeft(final int x) {
+				return x - 1;
+			}
+
+			final int getRight(final int x) {
+				return x;
+			}
+
+			final boolean isBetter(final int left, final int right) {
+				return left < right;
+			}
+
+			final void adjustMinMaxK(final int k, final int x) {
+				if (x <= beginA || k + x <= beginB) {
+					if (k > forward.middleK)
+						maxK = k;
+					else
+						minK = k;
+				}
+			}
+
+			final boolean meets(int d, int k, int x, long snake) {
+				if (k < forward.beginK || k > forward.endK)
+					return false;
+				// TODO: move out of loop
+				if (((d + k - forward.middleK) % 2) == 1)
+					return false;
+				if (x > forward.getX(d, k))
+					return false;
+				makeEdit(forward.getSnake(d, k), snake);
+				return true;
+			}
+		}
+	}
+
+	/**
+	 * @param args two filenames specifying the contents to be diffed
+	 */
+	public static void main(String[] args) {
+		if (args.length != 2) {
+			System.err.println("Need 2 arguments");
+			System.exit(1);
+		}
+		try {
+			RawText a = new RawText(new java.io.File(args[0]));
+			RawText b = new RawText(new java.io.File(args[1]));
+			MyersDiff diff = new MyersDiff(a, b);
+			System.out.println(diff.getEdits().toString());
+		} catch (Exception e) {
+			e.printStackTrace();
+		}
+	}
+}
\ No newline at end of file
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawText.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawText.java
index efc5c6d82f..9a206af190 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawText.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/RawText.java
@@ -44,6 +44,8 @@
 
 package org.eclipse.jgit.diff;
 
+import java.io.File;
+import java.io.FileInputStream;
 import java.io.IOException;
 import java.io.OutputStream;
 
@@ -87,6 +89,19 @@ public class RawText implements Sequence {
 		hashes = computeHashes();
 	}
 
+	/**
+	 * Create a new sequence from a file.
+	 * <p>
+	 * The entire file contents are used.
+	 *
+	 * @param file
+	 *            the text file.
+	 * @throws IOException if Exceptions occur while reading the file
+	 */
+	public RawText(File file) throws IOException {
+		this(readFile(file));
+	}
+
 	public int size() {
 		// The line map is always 2 entries larger than the number of lines in
 		// the file. Index 0 is padded out/unused. The last index is the total
@@ -187,4 +202,16 @@ public class RawText implements Sequence {
 			hash = (hash << 5) ^ (raw[ptr] & 0xff);
 		return hash;
 	}
+
+	private static byte[] readFile(File file) throws IOException {
+		byte[] result = new byte[(int)file.length()];
+		FileInputStream in = new FileInputStream(file);
+		for (int off = 0; off < result.length; ) {
+			int read = in.read(result, off, result.length - off);
+			if (read < 0)
+				throw new IOException("Early EOF");
+			off += read;
+		}
+		return result;
+	}
 }
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeAlgorithm.java b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeAlgorithm.java
new file mode 100644
index 0000000000..deae82e762
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeAlgorithm.java
@@ -0,0 +1,230 @@
+/*
+ * Copyright (C) 2009, Christian Halstrick <christian.halstrick@sap.com>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.eclipse.jgit.merge;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+import org.eclipse.jgit.diff.Edit;
+import org.eclipse.jgit.diff.EditList;
+import org.eclipse.jgit.diff.MyersDiff;
+import org.eclipse.jgit.diff.Sequence;
+import org.eclipse.jgit.merge.MergeChunk.ConflictState;
+
+/**
+ * Provides the merge algorithm which does a three-way merge on content provided
+ * as RawText. Makes use of {@link MyersDiff} to compute the diffs.
+ */
+public final class MergeAlgorithm {
+
+	/**
+	 * Since this class provides only static methods I add a private default
+	 * constructor to prevent instantiation.
+	 */
+	private MergeAlgorithm() {
+	}
+
+	// An special edit which acts as a sentinel value by marking the end the
+	// list of edits
+	private final static Edit END_EDIT = new Edit(Integer.MAX_VALUE,
+			Integer.MAX_VALUE);
+
+	/**
+	 * Does the three way merge between a common base and two sequences.
+	 *
+	 * @param base the common base sequence
+	 * @param ours the first sequence to be merged
+	 * @param theirs the second sequence to be merged
+	 * @return the resulting content
+	 */
+	public static MergeResult merge(Sequence base, Sequence ours,
+			Sequence theirs) {
+		List<Sequence> sequences = new ArrayList<Sequence>(3);
+		sequences.add(base);
+		sequences.add(ours);
+		sequences.add(theirs);
+		MergeResult result = new MergeResult(sequences);
+		EditList oursEdits = new MyersDiff(base, ours).getEdits();
+		Iterator<Edit> baseToOurs = oursEdits.iterator();
+		EditList theirsEdits = new MyersDiff(base, theirs).getEdits();
+		Iterator<Edit> baseToTheirs = theirsEdits.iterator();
+		int current = 0; // points to the next line (first line is 0) of base
+		                 // which was not handled yet
+		Edit oursEdit = nextEdit(baseToOurs);
+		Edit theirsEdit = nextEdit(baseToTheirs);
+
+		// iterate over all edits from base to ours and from base to theirs
+		// 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()) {
+				// 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.
+				if (current != oursEdit.getBeginA()) {
+					result.add(0, current, oursEdit.getBeginA(),
+							ConflictState.NO_CONFLICT);
+				}
+				result.add(1, oursEdit.getBeginB(), oursEdit.getEndB(),
+						ConflictState.NO_CONFLICT);
+				current = oursEdit.getEndA();
+				oursEdit = nextEdit(baseToOurs);
+			} 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.
+				if (current != theirsEdit.getBeginA()) {
+					result.add(0, current, theirsEdit.getBeginA(),
+							ConflictState.NO_CONFLICT);
+				}
+				result.add(2, theirsEdit.getBeginB(), theirsEdit.getEndB(),
+						ConflictState.NO_CONFLICT);
+				current = theirsEdit.getEndA();
+				theirsEdit = nextEdit(baseToTheirs);
+			} else {
+				// here we found a real overlapping modification
+
+				// if there is a common part in front of the conflict add it
+				if (oursEdit.getBeginA() != current
+						&& theirsEdit.getBeginA() != current) {
+					result.add(0, current, Math.min(oursEdit.getBeginA(),
+							theirsEdit.getBeginA()), ConflictState.NO_CONFLICT);
+				}
+
+				// set some initial values for the ranges in A and B which we
+				// want to handle
+				int oursBeginB = oursEdit.getBeginB();
+				int theirsBeginB = theirsEdit.getBeginB();
+				// harmonize the start of the ranges in A and B
+				if (oursEdit.getBeginA() < theirsEdit.getBeginA()) {
+					theirsBeginB -= theirsEdit.getBeginA()
+							- oursEdit.getBeginA();
+				} else {
+					oursBeginB -= oursEdit.getBeginA() - theirsEdit.getBeginA();
+				}
+
+				// combine edits:
+				// Maybe an Edit on one side corresponds to multiple Edits on
+				// the other side. Then we have to combine the Edits of the
+				// other side - so in the end we can merge together two single
+				// edits.
+				//
+				// It is important to notice that this combining will extend the
+				// ranges of our conflict always downwards (towards the end of
+				// the content). The starts of the conflicting ranges in ours
+				// and theirs are not touched here.
+				//
+				// This combining is an iterative process: after we have
+				// combined some edits we have to do the check again. The
+				// combined edits could now correspond to multiple edits on the
+				// other side.
+				//
+				// Example: when this combining algorithm works on the following
+				// edits
+				// oursEdits=((0-5,0-5),(6-8,6-8),(10-11,10-11)) and
+				// theirsEdits=((0-1,0-1),(2-3,2-3),(5-7,5-7))
+				// it will merge them into
+				// oursEdits=((0-8,0-8),(10-11,10-11)) and
+				// theirsEdits=((0-7,0-7))
+				//
+				// Since the only interesting thing to us is how in ours and
+				// theirs the end of the conflicting range is changing we let
+				// oursEdit and theirsEdit point to the last conflicting edit
+				Edit nextOursEdit = nextEdit(baseToOurs);
+				Edit nextTheirsEdit = nextEdit(baseToTheirs);
+				for (;;) {
+					if (oursEdit.getEndA() > nextTheirsEdit.getBeginA()) {
+						theirsEdit = nextTheirsEdit;
+						nextTheirsEdit = nextEdit(baseToTheirs);
+					} else if (theirsEdit.getEndA() > nextOursEdit.getBeginA()) {
+						oursEdit = nextOursEdit;
+						nextOursEdit = nextEdit(baseToOurs);
+					} else {
+						break;
+					}
+				}
+
+				// harmonize the end of the ranges in A and B
+				int oursEndB = oursEdit.getEndB();
+				int theirsEndB = theirsEdit.getEndB();
+				if (oursEdit.getEndA() < theirsEdit.getEndA()) {
+					oursEndB += theirsEdit.getEndA() - oursEdit.getEndA();
+				} else {
+					theirsEndB += oursEdit.getEndA() - theirsEdit.getEndA();
+				}
+
+				// Add the conflict
+				result.add(1, oursBeginB, oursEndB,
+						ConflictState.FIRST_CONFLICTING_RANGE);
+				result.add(2, theirsBeginB, theirsEndB,
+						ConflictState.NEXT_CONFLICTING_RANGE);
+
+				current = Math.max(oursEdit.getEndA(), theirsEdit.getEndA());
+				oursEdit = nextOursEdit;
+				theirsEdit = nextTheirsEdit;
+			}
+		}
+		// maybe we have a common part behind the last edit: copy it to the
+		// result
+		if (current < base.size()) {
+			result.add(0, current, base.size(), ConflictState.NO_CONFLICT);
+		}
+		return result;
+	}
+
+	/**
+	 * Helper method which returns the next Edit for an Iterator over Edits.
+	 * When there are no more edits left this method will return the constant
+	 * END_EDIT.
+	 *
+	 * @param it
+	 *            the iterator for which the next edit should be returned
+	 * @return the next edit from the iterator or END_EDIT if there no more
+	 *         edits
+	 */
+	private static Edit nextEdit(Iterator<Edit> it) {
+		return (it.hasNext() ? it.next() : END_EDIT);
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeChunk.java b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeChunk.java
new file mode 100644
index 0000000000..2b2cf3384d
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeChunk.java
@@ -0,0 +1,142 @@
+/*
+ * Copyright (C) 2009, Christian Halstrick <christian.halstrick@sap.com>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.eclipse.jgit.merge;
+
+/**
+ * One chunk from a merge result. Each chunk contains a range from a
+ * single sequence. In case of conflicts multiple chunks are reported for one
+ * conflict. The conflictState tells when conflicts start and end.
+ */
+public class MergeChunk {
+	/**
+	 * A state telling whether a MergeChunk belongs to a conflict or not. The
+	 * first chunk of a conflict is reported with a special state to be able to
+	 * distinguish the border between two consecutive conflicts
+	 */
+	public enum ConflictState {
+		/**
+		 * This chunk does not belong to a conflict
+		 */
+		NO_CONFLICT,
+
+		/**
+		 * This chunk does belong to a conflict and is the first one of the
+		 * conflicting chunks
+		 */
+		FIRST_CONFLICTING_RANGE,
+
+		/**
+		 * This chunk does belong to a conflict but is not the first one of the
+		 * conflicting chunks. It's a subsequent one.
+		 */
+		NEXT_CONFLICTING_RANGE
+	};
+
+	private final int sequenceIndex;
+
+	private final int begin;
+
+	private final int end;
+
+	private final ConflictState conflictState;
+
+	/**
+	 * Creates a new empty MergeChunk
+	 *
+	 * @param sequenceIndex
+	 *            determines to which sequence this chunks belongs to. Same as
+	 *            in {@link MergeResult#add(int, int, int, ConflictState)}
+	 * @param begin
+	 *            the first element from the specified sequence which should be
+	 *            included in the merge result. Indexes start with 0.
+	 * @param end
+	 *            specifies the end of the range to be added. The element this
+	 *            index points to is the first element which not added to the
+	 *            merge result. All elements between begin (including begin) and
+	 *            this element are added.
+	 * @param conflictState
+	 *            the state of this chunk. See {@link ConflictState}
+	 */
+	protected MergeChunk(int sequenceIndex, int begin, int end,
+			ConflictState conflictState) {
+		this.sequenceIndex = sequenceIndex;
+		this.begin = begin;
+		this.end = end;
+		this.conflictState = conflictState;
+	}
+
+	/**
+	 * @return the index of the sequence to which sequence this chunks belongs
+	 *         to. Same as in
+	 *         {@link MergeResult#add(int, int, int, ConflictState)}
+	 */
+	public int getSequenceIndex() {
+		return sequenceIndex;
+	}
+
+	/**
+	 * @return the first element from the specified sequence which should be
+	 *         included in the merge result. Indexes start with 0.
+	 */
+	public int getBegin() {
+		return begin;
+	}
+
+	/**
+	 * @return the end of the range of this chunk. The element this index
+	 *         points to is the first element which not added to the merge
+	 *         result. All elements between begin (including begin) and this
+	 *         element are added.
+	 */
+	public int getEnd() {
+		return end;
+	}
+
+	/**
+	 * @return the state of this chunk. See {@link ConflictState}
+	 */
+	public ConflictState getConflictState() {
+		return conflictState;
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeFormatter.java b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeFormatter.java
new file mode 100644
index 0000000000..2ff3e9b655
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeFormatter.java
@@ -0,0 +1,155 @@
+/*
+ * Copyright (C) 2009, Christian Halstrick <christian.halstrick@sap.com>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.eclipse.jgit.merge;
+
+import java.io.IOException;
+import java.io.OutputStream;
+import java.util.ArrayList;
+import java.util.List;
+
+import org.eclipse.jgit.diff.RawText;
+import org.eclipse.jgit.merge.MergeChunk.ConflictState;
+
+/**
+ * A class to convert merge results into a Git conformant textual presentation
+ */
+public class MergeFormatter {
+	/**
+	 * Formats the results of a merge of {@link RawText} objects in a Git
+	 * conformant way. This method also assumes that the {@link RawText} objects
+	 * being merged are line oriented files which use LF as delimiter. This
+	 * method will also use LF to separate chunks and conflict metadata,
+	 * therefore it fits only to texts that are LF-separated lines.
+	 *
+	 * @param out
+	 *            the outputstream where to write the textual presentation
+	 * @param res
+	 *            the merge result which should be presented
+	 * @param seqName
+	 *            When a conflict is reported each conflicting range will get a
+	 *            name. This name is following the "<<<<<<< " or ">>>>>>> "
+	 *            conflict markers. The names for the sequences are given in
+	 *            this list
+	 * @param charsetName
+	 *            the name of the characterSet used when writing conflict
+	 *            metadata
+	 * @throws IOException
+	 */
+	public void formatMerge(OutputStream out, MergeResult res,
+			List<String> seqName, String charsetName) throws IOException {
+		String lastConflictingName = null; // is set to non-null whenever we are
+		// in a conflict
+		boolean threeWayMerge = (res.getSequences().size() == 3);
+		for (MergeChunk chunk : res) {
+			RawText seq = (RawText) res.getSequences().get(
+					chunk.getSequenceIndex());
+			if (lastConflictingName != null
+					&& chunk.getConflictState() != ConflictState.NEXT_CONFLICTING_RANGE) {
+				// found the end of an conflict
+				out.write((">>>>>>> " + lastConflictingName + "\n").getBytes(charsetName));
+				lastConflictingName = null;
+			}
+			if (chunk.getConflictState() == ConflictState.FIRST_CONFLICTING_RANGE) {
+				// found the start of an conflict
+				out.write(("<<<<<<< " + seqName.get(chunk.getSequenceIndex()) +
+						"\n").getBytes(charsetName));
+				lastConflictingName = seqName.get(chunk.getSequenceIndex());
+			} else if (chunk.getConflictState() == ConflictState.NEXT_CONFLICTING_RANGE) {
+				// found another conflicting chunk
+
+				/*
+				 * In case of a non-three-way merge I'll add the name of the
+				 * conflicting chunk behind the equal signs. I also append the
+				 * name of the last conflicting chunk after the ending
+				 * greater-than signs. If somebody knows a better notation to
+				 * present non-three-way merges - feel free to correct here.
+				 */
+				lastConflictingName = seqName.get(chunk.getSequenceIndex());
+				out.write((threeWayMerge ? "=======\n" : "======= "
+						+ lastConflictingName + "\n").getBytes(charsetName));
+			}
+			// the lines with conflict-metadata are written. Now write the chunk
+			for (int i = chunk.getBegin(); i < chunk.getEnd(); i++) {
+				seq.writeLine(out, i);
+				out.write('\n');
+			}
+		}
+		// one possible leftover: if the merge result ended with a conflict we
+		// have to close the last conflict here
+		if (lastConflictingName != null) {
+			out.write((">>>>>>> " + lastConflictingName + "\n").getBytes(charsetName));
+		}
+	}
+
+	/**
+	 * Formats the results of a merge of exactly two {@link RawText} objects in
+	 * a Git conformant way. This convenience method accepts the names for the
+	 * three sequences (base and the two merged sequences) as explicit
+	 * parameters and doesn't require the caller to specify a List
+	 *
+	 * @param out
+	 *            the {@link OutputStream} where to write the textual
+	 *            presentation
+	 * @param res
+	 *            the merge result which should be presented
+	 * @param baseName
+	 *            the name ranges from the base should get
+	 * @param oursName
+	 *            the name ranges from ours should get
+	 * @param theirsName
+	 *            the name ranges from theirs should get
+	 * @param charsetName
+	 *            the name of the characterSet used when writing conflict
+	 *            metadata
+	 * @throws IOException
+	 */
+	public void formatMerge(OutputStream out, MergeResult res, String baseName,
+			String oursName, String theirsName, String charsetName) throws IOException {
+		List<String> names = new ArrayList<String>(3);
+		names.add(baseName);
+		names.add(oursName);
+		names.add(theirsName);
+		formatMerge(out, res, names, charsetName);
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeResult.java b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeResult.java
new file mode 100644
index 0000000000..0da487bc66
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeResult.java
@@ -0,0 +1,161 @@
+/*
+ * Copyright (C) 2009, Christian Halstrick <christian.halstrick@sap.com>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.eclipse.jgit.merge;
+
+import java.util.Iterator;
+import java.util.List;
+
+import org.eclipse.jgit.diff.Sequence;
+import org.eclipse.jgit.merge.MergeChunk.ConflictState;
+import org.eclipse.jgit.util.IntList;
+
+/**
+ * The result of merging a number of {@link Sequence} objects. These sequences
+ * have one common predecessor sequence. The result of a merge is a list of
+ * MergeChunks. Each MergeChunk contains either a range (a subsequence) from
+ * one of the merged sequences, a range from the common predecessor or a
+ * conflicting range from one of the merged sequences. A conflict will be
+ * reported as multiple chunks, one for each conflicting range. The first chunk
+ * for a conflict is marked specially to distinguish the border between two
+ * consecutive conflicts.
+ * <p>
+ * This class does not know anything about how to present the merge result to
+ * the end-user. MergeFormatters have to be used to construct something human
+ * readable.
+ */
+public class MergeResult implements Iterable<MergeChunk> {
+	private final List<Sequence> sequences;
+
+	private final IntList chunks = new IntList();
+
+	private boolean containsConflicts = false;
+
+	/**
+	 * Creates a new empty MergeResult
+	 *
+	 * @param sequences
+	 *            contains the common predecessor sequence at position 0
+	 *            followed by the merged sequences. This list should not be
+	 *            modified anymore during the lifetime of this {@link MergeResult}.
+	 */
+	public MergeResult(List<Sequence> sequences) {
+		this.sequences = sequences;
+	}
+
+	/**
+	 * Adds a new range from one of the merged sequences or from the common
+	 * predecessor. This method can add conflicting and non-conflicting ranges
+	 * controlled by the conflictState parameter
+	 *
+	 * @param srcIdx
+	 *            determines from which sequence this range comes. An index of
+	 *            x specifies the x+1 element in the list of sequences
+	 *            specified to the constructor
+	 * @param begin
+	 *            the first element from the specified sequence which should be
+	 *            included in the merge result. Indexes start with 0.
+	 * @param end
+	 *            specifies the end of the range to be added. The element this
+	 *            index points to is the first element which not added to the
+	 *            merge result. All elements between begin (including begin) and
+	 *            this element are added.
+	 * @param conflictState
+	 *            when set to NO_CONLICT a non-conflicting range is added.
+	 *            This will end implicitly all open conflicts added before.
+	 */
+	public void add(int srcIdx, int begin, int end, ConflictState conflictState) {
+		chunks.add(conflictState.ordinal());
+		chunks.add(srcIdx);
+		chunks.add(begin);
+		chunks.add(end);
+		if (conflictState != ConflictState.NO_CONFLICT)
+			containsConflicts = true;
+	}
+
+	/**
+	 * Returns the common predecessor sequence and the merged sequence in one
+	 * list. The common predecessor is is the first element in the list
+	 *
+	 * @return the common predecessor at position 0 followed by the merged
+	 *         sequences.
+	 */
+	public List<Sequence> getSequences() {
+		return sequences;
+	}
+
+	private static final ConflictState[] states = ConflictState.values();
+
+	/**
+	 * @return an iterator over the MergeChunks. The iterator does not support
+	 * the remove operation
+	 */
+	public Iterator<MergeChunk> iterator() {
+		return new Iterator<MergeChunk>() {
+			int idx;
+
+			public boolean hasNext() {
+				return (idx < chunks.size());
+			}
+
+			public MergeChunk next() {
+				ConflictState state = states[chunks.get(idx++)];
+				int srcIdx = chunks.get(idx++);
+				int begin = chunks.get(idx++);
+				int end = chunks.get(idx++);
+				return new MergeChunk(srcIdx, begin, end, state);
+			}
+
+			public void remove() {
+				throw new UnsupportedOperationException();
+			}
+		};
+	}
+
+	/**
+	 * @return true if this merge result contains conflicts
+	 */
+	public boolean containsConflicts() {
+		return containsConflicts;
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/util/IntList.java b/org.eclipse.jgit/src/org/eclipse/jgit/util/IntList.java
index 510f2a4db9..510032eeb0 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/util/IntList.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/util/IntList.java
@@ -1,5 +1,6 @@
 /*
  * Copyright (C) 2008, Google Inc.
+ * Copyright (C) 2009, Johannes Schindelin <johannes.schindelin@gmx.de>
  * and other copyright owners as documented in the project's IP log.
  *
  * This program and the accompanying materials are made available
@@ -100,6 +101,23 @@ public class IntList {
 	}
 
 	/**
+	 * Assign an entry in the list.
+	 *
+	 * @param index
+	 *            index to set, must be in the range [0, {@link #size()}).
+	 * @param n
+	 *            value to store at the position.
+	 */
+	public void set(final int index, final int n) {
+		if (count < index)
+			throw new ArrayIndexOutOfBoundsException(index);
+		else if (count == index)
+			add(n);
+		else
+			entries[index] = n;
+	}
+
+	/**
 	 * Pad the list with entries.
 	 *
 	 * @param toIndex
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/util/LongList.java b/org.eclipse.jgit/src/org/eclipse/jgit/util/LongList.java
new file mode 100644
index 0000000000..26608bb2a1
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/util/LongList.java
@@ -0,0 +1,152 @@
+/*
+ * Copyright (C) 2009, Christian Halstrick <christian.halstrick@sap.com>
+ * Copyright (C) 2009, Google Inc.
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.eclipse.jgit.util;
+
+/** A more efficient List<Long> using a primitive long array. */
+public class LongList {
+	private long[] entries;
+
+	private int count;
+
+	/** Create an empty list with a default capacity. */
+	public LongList() {
+		this(10);
+	}
+
+	/**
+	 * Create an empty list with the specified capacity.
+	 *
+	 * @param capacity
+	 *            number of entries the list can initially hold.
+	 */
+	public LongList(final int capacity) {
+		entries = new long[capacity];
+	}
+
+	/** @return number of entries in this list */
+	public int size() {
+		return count;
+	}
+
+	/**
+	 * @param i
+	 *            index to read, must be in the range [0, {@link #size()}).
+	 * @return the number at the specified index
+	 * @throws ArrayIndexOutOfBoundsException
+	 *             the index outside the valid range
+	 */
+	public long get(final int i) {
+		if (count <= i)
+			throw new ArrayIndexOutOfBoundsException(i);
+		return entries[i];
+	}
+
+	/** Empty this list */
+	public void clear() {
+		count = 0;
+	}
+
+	/**
+	 * Add an entry to the end of the list.
+	 *
+	 * @param n
+	 *            the number to add.
+	 */
+	public void add(final long n) {
+		if (count == entries.length)
+			grow();
+		entries[count++] = n;
+	}
+
+	/**
+	 * Assign an entry in the list.
+	 *
+	 * @param index
+	 *            index to set, must be in the range [0, {@link #size()}).
+	 * @param n
+	 *            value to store at the position.
+	 */
+	public void set(final int index, final long n) {
+		if (count < index)
+			throw new ArrayIndexOutOfBoundsException(index);
+		else if (count == index)
+			add(n);
+		else
+			entries[index] = n;
+	}
+
+	/**
+	 * Pad the list with entries.
+	 *
+	 * @param toIndex
+	 *            index position to stop filling at. 0 inserts no filler. 1
+	 *            ensures the list has a size of 1, adding <code>val</code> if
+	 *            the list is currently empty.
+	 * @param val
+	 *            value to insert into padded positions.
+	 */
+	public void fillTo(int toIndex, final long val) {
+		while (count < toIndex)
+			add(val);
+	}
+
+	private void grow() {
+		final long[] n = new long[(entries.length + 16) * 3 / 2];
+		System.arraycopy(entries, 0, n, 0, count);
+		entries = n;
+	}
+
+	public String toString() {
+		final StringBuilder r = new StringBuilder();
+		r.append('[');
+		for (int i = 0; i < count; i++) {
+			if (i > 0)
+				r.append(", ");
+			r.append(entries[i]);
+		}
+		r.append(']');
+		return r.toString();
+	}
+}