// <nowiki>

// Three-way merge utility

//

// Extracted from Synchrotron (https://github.com/tonyg/synchrotron)

// Minor modifications by Wikipedia user Suffusion of Yellow

// Original copyright notice follows:



// Copyright (c) 2006, 2008 Tony Garnock-Jones <tonyg@lshift.net>

// Copyright (c) 2006, 2008 LShift Ltd. <query@lshift.net>

//

// Permission is hereby granted, free of charge, to any person

// obtaining a copy of this software and associated documentation files

// (the "Software"), to deal in the Software without restriction,

// including without limitation the rights to use, copy, modify, merge,

// publish, distribute, sublicense, and/or sell copies of the Software,

// and to permit persons to whom the Software is furnished to do so,

// subject to the following conditions:

//

// The above copyright notice and this permission notice shall be

// included in all copies or substantial portions of the Software.

//

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,

// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF

// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND

// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS

// BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN

// ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN

// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

// SOFTWARE.



var Diff3 = {

	longest_common_subsequence: function(file1, file2) {

		/* Text diff algorithm following Hunt and McIlroy 1976.

		 * J. W. Hunt and M. D. McIlroy, An algorithm for differential file

		 * comparison, Bell Telephone Laboratories CSTR #41 (1976)

		 * http://www.cs.dartmouth.edu/~doug/

		 *

		 * Expects two arrays of strings.

		 */

		var equivalenceClasses;

		var file2indices;

		var newCandidate;

		var candidates;

		var line;

		var c, i, j, jX, r, s;



		equivalenceClasses = new Map();

		for (j = 0; j < file2.length; j++) {

			line = file2j];

			if (equivalenceClasses.get(line)) {

				equivalenceClasses.get(line).push(j);

			} else {

				equivalenceClasses.set(line,[j]);

			}

		}



		candidates = [{file1index: -1,

					   file2index: -1,

					   chain: null}];



		for (i = 0; i < file1.length; i++) {

			line = file1i];

			file2indices = equivalenceClasses.get(line) || [];



			r = 0;

			c = candidates0];



			for (jX = 0; jX < file2indices.length; jX++) {

				j = file2indicesjX];



				for (s = r; s < candidates.length; s++) {

					if ((candidatess].file2index < j) &&

						((s == candidates.length - 1) ||

						 (candidatess + 1].file2index > j)))

						break;

				}



				if (s < candidates.length) {

					newCandidate = {file1index: i,

									file2index: j,

									chain: candidatess]};

					if (r == candidates.length) {

						candidates.push(c);

					} else {

						candidatesr = c;

					}

					r = s + 1;

					c = newCandidate;

					if (r == candidates.length) {

						break; // no point in examining further (j)s

					}

				}

			}



			candidatesr = c;

		}



		// At this point, we know the LCS: it's in the reverse of the

		// linked-list through .chain of

		// candidates[candidates.length - 1].



		return candidatescandidates.length - 1];

	},



	diff_indices: function(file1, file2) {

		// We apply the LCS to give a simple representation of the

		// offsets and lengths of mismatched chunks in the input

		// files. This is used by diff3_merge_indices below.



		var result = [];

		var tail1 = file1.length;

		var tail2 = file2.length;



		for (var candidate = Diff3.longest_common_subsequence(file1, file2);

			 candidate !== null;

			 candidate = candidate.chain)

		{

			var mismatchLength1 = tail1 - candidate.file1index - 1;

			var mismatchLength2 = tail2 - candidate.file2index - 1;

			tail1 = candidate.file1index;

			tail2 = candidate.file2index;



			if (mismatchLength1 || mismatchLength2) {

				result.push({file1: tail1 + 1, mismatchLength1],

							 file2: tail2 + 1, mismatchLength2]});

			}

		}



		result.reverse();

		return result;

	},



	diff3_merge_indices: function (a, o, b) {

		// Given three files, A, O, and B, where both A and B are

		// independently derived from O, returns a fairly complicated

		// internal representation of merge decisions it's taken. The

		// interested reader may wish to consult

		//

		// Sanjeev Khanna, Keshav Kunal, and Benjamin C. Pierce. "A

		// Formal Investigation of Diff3." In Arvind and Prasad,

		// editors, Foundations of Software Technology and Theoretical

		// Computer Science (FSTTCS), December 2007.

		//

		// (http://www.cis.upenn.edu/~bcpierce/papers/diff3-short.pdf)

		var i;



		var m1 = Diff3.diff_indices(o, a);

		var m2 = Diff3.diff_indices(o, b);



		var hunks = [];

		function addHunk(h, side) {

			hunks.push([h.file10], side, h.file11], h.file20], h.file21]]);

		}

		for (i = 0; i < m1.length; i++) { addHunk(m1i], 0); }

		for (i = 0; i < m2.length; i++) { addHunk(m2i], 2); }

		hunks.sort(function (x, y) { return x0 - y0]; });



		var result = [];

		var commonOffset = 0;

		function copyCommon(targetOffset) {

			if (targetOffset > commonOffset) {

				result.push([1, commonOffset, targetOffset - commonOffset]);

				commonOffset = targetOffset;

			}

		}



		for (var hunkIndex = 0; hunkIndex < hunks.length; hunkIndex++) {

			var firstHunkIndex = hunkIndex;

			var hunk = hunkshunkIndex];

			var regionLhs = hunk0];

			var regionRhs = regionLhs + hunk2];

			while (hunkIndex < hunks.length - 1) {

				var maybeOverlapping = hunkshunkIndex + 1];

				var maybeLhs = maybeOverlapping0];

				if (maybeLhs > regionRhs) break;

				regionRhs = Math.max(regionRhs, maybeLhs + maybeOverlapping2]);

				hunkIndex++;

			}



			copyCommon(regionLhs);

			if (firstHunkIndex == hunkIndex) {

				// The "overlap" was only one hunk long, meaning that

				// there's no conflict here. Either a and o were the

				// same, or b and o were the same.

				if (hunk4 > 0) {

					result.push([hunk1], hunk3], hunk4]]);

				}

			} else {

				// A proper conflict. Determine the extents of the

				// regions involved from a, o and b. Effectively merge

				// all the hunks on the left into one giant hunk, and

				// do the same for the right; then, correct for skew

				// in the regions of o that each side changed, and

				// report appropriate spans for the three sides.

				var regions = {

					0: a.length, -1, o.length, -1],

					2: b.length, -1, o.length, -1

				};

				for (i = firstHunkIndex; i <= hunkIndex; i++) {

					hunk = hunksi];

					var side = hunk1];

					var r = regionsside];

					var oLhs = hunk0];

					var oRhs = oLhs + hunk2];

					var abLhs = hunk3];

					var abRhs = abLhs + hunk4];

					r0 = Math.min(abLhs, r0]);

					r1 = Math.max(abRhs, r1]);

					r2 = Math.min(oLhs, r2]);

					r3 = Math.max(oRhs, r3]);

				}

				var aLhs = regions0][0 + (regionLhs - regions0][2]);

				var aRhs = regions0][1 + (regionRhs - regions0][3]);

				var bLhs = regions2][0 + (regionLhs - regions2][2]);

				var bRhs = regions2][1 + (regionRhs - regions2][3]);

				result.push([-1,

							 aLhs,      aRhs      - aLhs,

							 regionLhs, regionRhs - regionLhs,

							 bLhs,      bRhs      - bLhs]);

			}

			commonOffset = regionRhs;

		}



		copyCommon(o.length);

		return result;

	},



	diff3_merge: function (a, o, b, excludeFalseConflicts) {

		// Applies the output of Diff.diff3_merge_indices to actually

		// construct the merged file; the returned result alternates

		// between "ok" and "conflict" blocks.



		var result = [];

		var files = a, o, b];

		var indices = Diff3.diff3_merge_indices(a, o, b);



		var okLines = [];

		function flushOk() {

			if (okLines.length) {

				result.push({ok: okLines});

			}

			okLines = [];

		}

		function pushOk(xs) {

			for (var j = 0; j < xs.length; j++) {

				okLines.push(xsj]);

			}

		}



		function isTrueConflict(rec) {

			if (rec2 != rec6]) return true;

			var aoff = rec1];

			var boff = rec5];

			for (var j = 0; j < rec2]; j++) {

				if (aj + aoff != bj + boff]) return true;

			}

			return false;

		}



		for (var i = 0; i < indices.length; i++) {

			var x = indicesi];

			var side = x0];

			if (side == -1) {

				if (excludeFalseConflicts && !isTrueConflict(x)) {

					pushOk(files0].slice(x1], x1 + x2]));

				} else {

					flushOk();

					result.push({conflict: {a: a.slice(x1], x1 + x2]),

											aIndex: x1],

											o: o.slice(x3], x3 + x4]),

											oIndex: x3],

											b: b.slice(x5], x5 + x6]),

											bIndex: x5]}});

				}

			} else {

				pushOk(filesside].slice(x1], x1 + x2]));

			}

		}



		flushOk();

		return result;

	}

};

// </nowiki>