\u5b9e\u73b0\u4e00\u4e2a\u50cfBeyond Compare\u7684\u5de5\u5177\uff0c\u5fc5\u7136\u9700\u8981\u4e00\u4e2a\u9ad8\u6027\u80fd\u7684\u6587\u672c\u5bf9\u6bd4\u7b97\u6cd5\uff0cGoogle\u5df2\u7ecf\u5b9e\u73b0\u4e86\u8fd9\u4e2a\u5e93\uff0c\u5e76\u4e14\u63d0\u4f9b\u4e86\u5404\u79cd\u8bed\u8a00\u7248\u672c<\/p>\n\n\n\n
https:\/\/github.com\/google\/diff-match-patch<\/code><\/pre>\n\n\n\n\/*\n * Diff Match and Patch\n * Copyright 2018 The diff-match-patch Authors.\n * https:\/\/github.com\/google\/diff-match-patch\n *\n * Licensed under the Apache License, Version 2.0 (the \"License\");\n * you may not use this file except in compliance with the License.\n * You may obtain a copy of the License at\n *\n * http:\/\/www.apache.org\/licenses\/LICENSE-2.0\n *\n * Unless required by applicable law or agreed to in writing, software\n * distributed under the License is distributed on an \"AS IS\" BASIS,\n * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n * See the License for the specific language governing permissions and\n * limitations under the License.\n *\/\n\nusing System;\nusing System.Collections.Generic;\nusing System.Linq;\nusing System.Text;\nusing System.Text.RegularExpressions;\nusing System.Web;\n\nnamespace DiffMatchPatch\n{\n internal static class CompatibilityExtensions\n {\n \/\/ JScript splice function\n public static List<T> Splice<T>(this List<T> input, int start, int count,\n params T[] objects)\n {\n List<T> deletedRange = input.GetRange(start, count);\n input.RemoveRange(start, count);\n input.InsertRange(start, objects);\n\n return deletedRange;\n }\n\n \/\/ Java substring function\n public static string JavaSubstring(this string s, int begin, int end)\n {\n return s.Substring(begin, end - begin);\n }\n }\n\n \/**-\n * The data structure representing a diff is a List of Diff objects:\n * {Diff(Operation.DELETE, \"Hello\"), Diff(Operation.INSERT, \"Goodbye\"),\n * Diff(Operation.EQUAL, \" world.\")}\n * which means: delete \"Hello\", add \"Goodbye\" and keep \" world.\"\n *\/\n public enum Operation\n {\n DELETE, INSERT, EQUAL\n }\n\n\n \/**\n * Class representing one diff operation.\n *\/\n public class Diff\n {\n public Operation operation;\n \/\/ One of: INSERT, DELETE or EQUAL.\n public string text;\n \/\/ The text associated with this diff operation.\n\n \/**\n * Constructor. Initializes the diff with the provided values.\n * @param operation One of INSERT, DELETE or EQUAL.\n * @param text The text being applied.\n *\/\n public Diff(Operation operation, string text)\n {\n \/\/ Construct a diff with the specified operation and text.\n this.operation = operation;\n this.text = text;\n }\n\n \/**\n * Display a human-readable version of this Diff.\n * @return text version.\n *\/\n public override string ToString()\n {\n string prettyText = this.text.Replace('\\n', '\\u00b6');\n return \"Diff(\" + this.operation + \",\\\"\" + prettyText + \"\\\")\";\n }\n\n \/**\n * Is this Diff equivalent to another Diff?\n * @param d Another Diff to compare against.\n * @return true or false.\n *\/\n public override bool Equals(Object obj)\n {\n \/\/ If parameter is null return false.\n if (obj == null)\n {\n return false;\n }\n\n \/\/ If parameter cannot be cast to Diff return false.\n Diff p = obj as Diff;\n if ((System.Object)p == null)\n {\n return false;\n }\n\n \/\/ Return true if the fields match.\n return p.operation == this.operation && p.text == this.text;\n }\n\n public bool Equals(Diff obj)\n {\n \/\/ If parameter is null return false.\n if (obj == null)\n {\n return false;\n }\n\n \/\/ Return true if the fields match.\n return obj.operation == this.operation && obj.text == this.text;\n }\n\n public override int GetHashCode()\n {\n return text.GetHashCode() ^ operation.GetHashCode();\n }\n }\n\n\n \/**\n * Class representing one patch operation.\n *\/\n public class Patch\n {\n public List<Diff> diffs = new List<Diff>();\n public int start1;\n public int start2;\n public int length1;\n public int length2;\n\n \/**\n * Emulate GNU diff's format.\n * Header: @@ -382,8 +481,9 @@\n * Indices are printed as 1-based, not 0-based.\n * @return The GNU diff string.\n *\/\n public override string ToString()\n {\n string coords1, coords2;\n if (this.length1 == 0)\n {\n coords1 = this.start1 + \",0\";\n }\n else if (this.length1 == 1)\n {\n coords1 = Convert.ToString(this.start1 + 1);\n }\n else\n {\n coords1 = (this.start1 + 1) + \",\" + this.length1;\n }\n if (this.length2 == 0)\n {\n coords2 = this.start2 + \",0\";\n }\n else if (this.length2 == 1)\n {\n coords2 = Convert.ToString(this.start2 + 1);\n }\n else\n {\n coords2 = (this.start2 + 1) + \",\" + this.length2;\n }\n StringBuilder text = new StringBuilder();\n text.Append(\"@@ -\").Append(coords1).Append(\" +\").Append(coords2)\n .Append(\" @@\\n\");\n \/\/ Escape the body of the patch with %xx notation.\n foreach (Diff aDiff in this.diffs)\n {\n switch (aDiff.operation)\n {\n case Operation.INSERT:\n text.Append('+');\n break;\n case Operation.DELETE:\n text.Append('-');\n break;\n case Operation.EQUAL:\n text.Append(' ');\n break;\n }\n\n text.Append(diff_match_patch.encodeURI(aDiff.text)).Append(\"\\n\");\n }\n return text.ToString();\n }\n }\n\n\n \/**\n * Class containing the diff, match and patch methods.\n * Also Contains the behaviour settings.\n *\/\n public class diff_match_patch\n {\n \/\/ Defaults.\n \/\/ Set these on your diff_match_patch instance to override the defaults.\n\n \/\/ Number of seconds to map a diff before giving up (0 for infinity).\n public float Diff_Timeout = 1.0f;\n \/\/ Cost of an empty edit operation in terms of edit characters.\n public short Diff_EditCost = 4;\n \/\/ At what point is no match declared (0.0 = perfection, 1.0 = very loose).\n public float Match_Threshold = 0.5f;\n \/\/ How far to search for a match (0 = exact location, 1000+ = broad match).\n \/\/ A match this many characters away from the expected location will add\n \/\/ 1.0 to the score (0.0 is a perfect match).\n public int Match_Distance = 1000;\n \/\/ When deleting a large block of text (over ~64 characters), how close\n \/\/ do the contents have to be to match the expected contents. (0.0 =\n \/\/ perfection, 1.0 = very loose). Note that Match_Threshold controls\n \/\/ how closely the end points of a delete need to match.\n public float Patch_DeleteThreshold = 0.5f;\n \/\/ Chunk size for context length.\n public short Patch_Margin = 4;\n\n \/\/ The number of bits in an int.\n private short Match_MaxBits = 32;\n\n\n \/\/ DIFF FUNCTIONS\n\n\n \/**\n * Find the differences between two texts.\n * Run a faster, slightly less optimal diff.\n * This method allows the 'checklines' of diff_main() to be optional.\n * Most of the time checklines is wanted, so default to true.\n * @param text1 Old string to be diffed.\n * @param text2 New string to be diffed.\n * @return List of Diff objects.\n *\/\n public List<Diff> diff_main(string text1, string text2)\n {\n return diff_main(text1, text2, true);\n }\n\n \/**\n * Find the differences between two texts.\n * @param text1 Old string to be diffed.\n * @param text2 New string to be diffed.\n * @param checklines Speedup flag. If false, then don't run a\n * line-level diff first to identify the changed areas.\n * If true, then run a faster slightly less optimal diff.\n * @return List of Diff objects.\n *\/\n public List<Diff> diff_main(string text1, string text2, bool checklines)\n {\n \/\/ Set a deadline by which time the diff must be complete.\n DateTime deadline;\n if (this.Diff_Timeout <= 0)\n {\n deadline = DateTime.MaxValue;\n }\n else\n {\n deadline = DateTime.Now +\n new TimeSpan(((long)(Diff_Timeout * 1000)) * 10000);\n }\n return diff_main(text1, text2, checklines, deadline);\n }\n\n \/**\n * Find the differences between two texts. Simplifies the problem by\n * stripping any common prefix or suffix off the texts before diffing.\n * @param text1 Old string to be diffed.\n * @param text2 New string to be diffed.\n * @param checklines Speedup flag. If false, then don't run a\n * line-level diff first to identify the changed areas.\n * If true, then run a faster slightly less optimal diff.\n * @param deadline Time when the diff should be complete by. Used\n * internally for recursive calls. Users should set DiffTimeout\n * instead.\n * @return List of Diff objects.\n *\/\n private List<Diff> diff_main(string text1, string text2, bool checklines,\n DateTime deadline)\n {\n \/\/ Check for null inputs not needed since null can't be passed in C#.\n\n \/\/ Check for equality (speedup).\n List<Diff> diffs;\n if (text1 == text2)\n {\n diffs = new List<Diff>();\n if (text1.Length != 0)\n {\n diffs.Add(new Diff(Operation.EQUAL, text1));\n }\n return diffs;\n }\n\n \/\/ Trim off common prefix (speedup).\n int commonlength = diff_commonPrefix(text1, text2);\n string commonprefix = text1.Substring(0, commonlength);\n text1 = text1.Substring(commonlength);\n text2 = text2.Substring(commonlength);\n\n \/\/ Trim off common suffix (speedup).\n commonlength = diff_commonSuffix(text1, text2);\n string commonsuffix = text1.Substring(text1.Length - commonlength);\n text1 = text1.Substring(0, text1.Length - commonlength);\n text2 = text2.Substring(0, text2.Length - commonlength);\n\n \/\/ Compute the diff on the middle block.\n diffs = diff_compute(text1, text2, checklines, deadline);\n\n \/\/ Restore the prefix and suffix.\n if (commonprefix.Length != 0)\n {\n diffs.Insert(0, (new Diff(Operation.EQUAL, commonprefix)));\n }\n if (commonsuffix.Length != 0)\n {\n diffs.Add(new Diff(Operation.EQUAL, commonsuffix));\n }\n\n diff_cleanupMerge(diffs);\n return diffs;\n }\n\n \/**\n * Find the differences between two texts. Assumes that the texts do not\n * have any common prefix or suffix.\n * @param text1 Old string to be diffed.\n * @param text2 New string to be diffed.\n * @param checklines Speedup flag. If false, then don't run a\n * line-level diff first to identify the changed areas.\n * If true, then run a faster slightly less optimal diff.\n * @param deadline Time when the diff should be complete by.\n * @return List of Diff objects.\n *\/\n private List<Diff> diff_compute(string text1, string text2,\n bool checklines, DateTime deadline)\n {\n List<Diff> diffs = new List<Diff>();\n\n if (text1.Length == 0)\n {\n \/\/ Just add some text (speedup).\n diffs.Add(new Diff(Operation.INSERT, text2));\n return diffs;\n }\n\n if (text2.Length == 0)\n {\n \/\/ Just delete some text (speedup).\n diffs.Add(new Diff(Operation.DELETE, text1));\n return diffs;\n }\n\n string longtext = text1.Length > text2.Length ? text1 : text2;\n string shorttext = text1.Length > text2.Length ? text2 : text1;\n int i = longtext.IndexOf(shorttext, StringComparison.Ordinal);\n if (i != -1)\n {\n \/\/ Shorter text is inside the longer text (speedup).\n Operation op = (text1.Length > text2.Length) ?\n Operation.DELETE : Operation.INSERT;\n diffs.Add(new Diff(op, longtext.Substring(0, i)));\n diffs.Add(new Diff(Operation.EQUAL, shorttext));\n diffs.Add(new Diff(op, longtext.Substring(i + shorttext.Length)));\n return diffs;\n }\n\n if (shorttext.Length == 1)\n {\n \/\/ Single character string.\n \/\/ After the previous speedup, the character can't be an equality.\n diffs.Add(new Diff(Operation.DELETE, text1));\n diffs.Add(new Diff(Operation.INSERT, text2));\n return diffs;\n }\n\n \/\/ Check to see if the problem can be split in two.\n string[] hm = diff_halfMatch(text1, text2);\n if (hm != null)\n {\n \/\/ A half-match was found, sort out the return data.\n string text1_a = hm[0];\n string text1_b = hm[1];\n string text2_a = hm[2];\n string text2_b = hm[3];\n string mid_common = hm[4];\n \/\/ Send both pairs off for separate processing.\n List<Diff> diffs_a = diff_main(text1_a, text2_a, checklines, deadline);\n List<Diff> diffs_b = diff_main(text1_b, text2_b, checklines, deadline);\n \/\/ Merge the results.\n diffs = diffs_a;\n diffs.Add(new Diff(Operation.EQUAL, mid_common));\n diffs.AddRange(diffs_b);\n return diffs;\n }\n\n if (checklines && text1.Length > 100 && text2.Length > 100)\n {\n return diff_lineMode(text1, text2, deadline);\n }\n\n return diff_bisect(text1, text2, deadline);\n }\n\n \/**\n * Do a quick line-level diff on both strings, then rediff the parts for\n * greater accuracy.\n * This speedup can produce non-minimal diffs.\n * @param text1 Old string to be diffed.\n * @param text2 New string to be diffed.\n * @param deadline Time when the diff should be complete by.\n * @return List of Diff objects.\n *\/\n private List<Diff> diff_lineMode(string text1, string text2,\n DateTime deadline)\n {\n \/\/ Scan the text on a line-by-line basis first.\n Object[] a = diff_linesToChars(text1, text2);\n text1 = (string)a[0];\n text2 = (string)a[1];\n List<string> linearray = (List<string>)a[2];\n\n List<Diff> diffs = diff_main(text1, text2, false, deadline);\n\n \/\/ Convert the diff back to original text.\n diff_charsToLines(diffs, linearray);\n \/\/ Eliminate freak matches (e.g. blank lines)\n diff_cleanupSemantic(diffs);\n\n \/\/ Rediff any replacement blocks, this time character-by-character.\n \/\/ Add a dummy entry at the end.\n diffs.Add(new Diff(Operation.EQUAL, string.Empty));\n int pointer = 0;\n int count_delete = 0;\n int count_insert = 0;\n string text_delete = string.Empty;\n string text_insert = string.Empty;\n while (pointer < diffs.Count)\n {\n switch (diffs[pointer].operation)\n {\n case Operation.INSERT:\n count_insert++;\n text_insert += diffs[pointer].text;\n break;\n case Operation.DELETE:\n count_delete++;\n text_delete += diffs[pointer].text;\n break;\n case Operation.EQUAL:\n \/\/ Upon reaching an equality, check for prior redundancies.\n if (count_delete >= 1 && count_insert >= 1)\n {\n \/\/ Delete the offending records and add the merged ones.\n diffs.RemoveRange(pointer - count_delete - count_insert,\n count_delete + count_insert);\n pointer = pointer - count_delete - count_insert;\n List<Diff> subDiff =\n this.diff_main(text_delete, text_insert, false, deadline);\n diffs.InsertRange(pointer, subDiff);\n pointer = pointer + subDiff.Count;\n }\n count_insert = 0;\n count_delete = 0;\n text_delete = string.Empty;\n text_insert = string.Empty;\n break;\n }\n pointer++;\n }\n diffs.RemoveAt(diffs.Count - 1); \/\/ Remove the dummy entry at the end.\n\n return diffs;\n }\n\n \/**\n * Find the 'middle snake' of a diff, split the problem in two\n * and return the recursively constructed diff.\n * See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations.\n * @param text1 Old string to be diffed.\n * @param text2 New string to be diffed.\n * @param deadline Time at which to bail if not yet complete.\n * @return List of Diff objects.\n *\/\n protected List<Diff> diff_bisect(string text1, string text2,\n DateTime deadline)\n {\n \/\/ Cache the text lengths to prevent multiple calls.\n int text1_length = text1.Length;\n int text2_length = text2.Length;\n int max_d = (text1_length + text2_length + 1) \/ 2;\n int v_offset = max_d;\n int v_length = 2 * max_d;\n int[] v1 = new int[v_length];\n int[] v2 = new int[v_length];\n for (int x = 0; x < v_length; x++)\n {\n v1[x] = -1;\n v2[x] = -1;\n }\n v1[v_offset + 1] = 0;\n v2[v_offset + 1] = 0;\n int delta = text1_length - text2_length;\n \/\/ If the total number of characters is odd, then the front path will\n \/\/ collide with the reverse path.\n bool front = (delta % 2 != 0);\n \/\/ Offsets for start and end of k loop.\n \/\/ Prevents mapping of space beyond the grid.\n int k1start = 0;\n int k1end = 0;\n int k2start = 0;\n int k2end = 0;\n for (int d = 0; d < max_d; d++)\n {\n \/\/ Bail out if deadline is reached.\n if (DateTime.Now > deadline)\n {\n break;\n }\n\n \/\/ Walk the front path one step.\n for (int k1 = -d + k1start; k1 <= d - k1end; k1 += 2)\n {\n int k1_offset = v_offset + k1;\n int x1;\n if (k1 == -d || k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1])\n {\n x1 = v1[k1_offset + 1];\n }\n else\n {\n x1 = v1[k1_offset - 1] + 1;\n }\n int y1 = x1 - k1;\n while (x1 < text1_length && y1 < text2_length\n && text1[x1] == text2[y1])\n {\n x1++;\n y1++;\n }\n v1[k1_offset] = x1;\n if (x1 > text1_length)\n {\n \/\/ Ran off the right of the graph.\n k1end += 2;\n }\n else if (y1 > text2_length)\n {\n \/\/ Ran off the bottom of the graph.\n k1start += 2;\n }\n else if (front)\n {\n int k2_offset = v_offset + delta - k1;\n if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1)\n {\n \/\/ Mirror x2 onto top-left coordinate system.\n int x2 = text1_length - v2[k2_offset];\n if (x1 >= x2)\n {\n \/\/ Overlap detected.\n return diff_bisectSplit(text1, text2, x1, y1, deadline);\n }\n }\n }\n }\n\n \/\/ Walk the reverse path one step.\n for (int k2 = -d + k2start; k2 <= d - k2end; k2 += 2)\n {\n int k2_offset = v_offset + k2;\n int x2;\n if (k2 == -d || k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1])\n {\n x2 = v2[k2_offset + 1];\n }\n else\n {\n x2 = v2[k2_offset - 1] + 1;\n }\n int y2 = x2 - k2;\n while (x2 < text1_length && y2 < text2_length\n && text1[text1_length - x2 - 1]\n == text2[text2_length - y2 - 1])\n {\n x2++;\n y2++;\n }\n v2[k2_offset] = x2;\n if (x2 > text1_length)\n {\n \/\/ Ran off the left of the graph.\n k2end += 2;\n }\n else if (y2 > text2_length)\n {\n \/\/ Ran off the top of the graph.\n k2start += 2;\n }\n else if (!front)\n {\n int k1_offset = v_offset + delta - k2;\n if (k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1)\n {\n int x1 = v1[k1_offset];\n int y1 = v_offset + x1 - k1_offset;\n \/\/ Mirror x2 onto top-left coordinate system.\n x2 = text1_length - v2[k2_offset];\n if (x1 >= x2)\n {\n \/\/ Overlap detected.\n return diff_bisectSplit(text1, text2, x1, y1, deadline);\n }\n }\n }\n }\n }\n \/\/ Diff took too long and hit the deadline or\n \/\/ number of diffs equals number of characters, no commonality at all.\n List<Diff> diffs = new List<Diff>();\n diffs.Add(new Diff(Operation.DELETE, text1));\n diffs.Add(new Diff(Operation.INSERT, text2));\n return diffs;\n }\n\n \/**\n * Given the location of the 'middle snake', split the diff in two parts\n * and recurse.\n * @param text1 Old string to be diffed.\n * @param text2 New string to be diffed.\n * @param x Index of split point in text1.\n * @param y Index of split point in text2.\n * @param deadline Time at which to bail if not yet complete.\n * @return LinkedList of Diff objects.\n *\/\n private List<Diff> diff_bisectSplit(string text1, string text2,\n int x, int y, DateTime deadline)\n {\n string text1a = text1.Substring(0, x);\n string text2a = text2.Substring(0, y);\n string text1b = text1.Substring(x);\n string text2b = text2.Substring(y);\n\n \/\/ Compute both diffs serially.\n List<Diff> diffs = diff_main(text1a, text2a, false, deadline);\n List<Diff> diffsb = diff_main(text1b, text2b, false, deadline);\n\n diffs.AddRange(diffsb);\n return diffs;\n }\n\n \/**\n * Split two texts into a list of strings. Reduce the texts to a string of\n * hashes where each Unicode character represents one line.\n * @param text1 First string.\n * @param text2 Second string.\n * @return Three element Object array, containing the encoded text1, the\n * encoded text2 and the List of unique strings. The zeroth element\n * of the List of unique strings is intentionally blank.\n *\/\n protected Object[] diff_linesToChars(string text1, string text2)\n {\n List<string> lineArray = new List<string>();\n Dictionary<string, int> lineHash = new Dictionary<string, int>();\n \/\/ e.g. linearray[4] == \"Hello\\n\"\n \/\/ e.g. linehash.get(\"Hello\\n\") == 4\n\n \/\/ \"\\x00\" is a valid character, but various debuggers don't like it.\n \/\/ So we'll insert a junk entry to avoid generating a null character.\n lineArray.Add(string.Empty);\n\n \/\/ Allocate 2\/3rds of the space for text1, the rest for text2.\n string chars1 = diff_linesToCharsMunge(text1, lineArray, lineHash, 40000);\n string chars2 = diff_linesToCharsMunge(text2, lineArray, lineHash, 65535);\n return new Object[] { chars1, chars2, lineArray };\n }\n\n \/**\n * Split a text into a list of strings. Reduce the texts to a string of\n * hashes where each Unicode character represents one line.\n * @param text String to encode.\n * @param lineArray List of unique strings.\n * @param lineHash Map of strings to indices.\n * @param maxLines Maximum length of lineArray.\n * @return Encoded string.\n *\/\n private string diff_linesToCharsMunge(string text, List<string> lineArray,\n Dictionary<string, int> lineHash, int maxLines)\n {\n int lineStart = 0;\n int lineEnd = -1;\n string line;\n StringBuilder chars = new StringBuilder();\n \/\/ Walk the text, pulling out a Substring for each line.\n \/\/ text.split('\\n') would would temporarily double our memory footprint.\n \/\/ Modifying text would create many large strings to garbage collect.\n while (lineEnd < text.Length - 1)\n {\n lineEnd = text.IndexOf('\\n', lineStart);\n if (lineEnd == -1)\n {\n lineEnd = text.Length - 1;\n }\n line = text.JavaSubstring(lineStart, lineEnd + 1);\n\n if (lineHash.ContainsKey(line))\n {\n chars.Append(((char)(int)lineHash[line]));\n }\n else\n {\n if (lineArray.Count == maxLines)\n {\n \/\/ Bail out at 65535 because char 65536 == char 0.\n line = text.Substring(lineStart);\n lineEnd = text.Length;\n }\n lineArray.Add(line);\n lineHash.Add(line, lineArray.Count - 1);\n chars.Append(((char)(lineArray.Count - 1)));\n }\n lineStart = lineEnd + 1;\n }\n return chars.ToString();\n }\n\n \/**\n * Rehydrate the text in a diff from a string of line hashes to real lines\n * of text.\n * @param diffs List of Diff objects.\n * @param lineArray List of unique strings.\n *\/\n protected void diff_charsToLines(ICollection<Diff> diffs,\n IList<string> lineArray)\n {\n StringBuilder text;\n foreach (Diff diff in diffs)\n {\n text = new StringBuilder();\n for (int j = 0; j < diff.text.Length; j++)\n {\n text.Append(lineArray[diff.text[j]]);\n }\n diff.text = text.ToString();\n }\n }\n\n \/**\n * Determine the common prefix of two strings.\n * @param text1 First string.\n * @param text2 Second string.\n * @return The number of characters common to the start of each string.\n *\/\n public int diff_commonPrefix(string text1, string text2)\n {\n \/\/ Performance analysis: https:\/\/neil.fraser.name\/news\/2007\/10\/09\/\n int n = Math.Min(text1.Length, text2.Length);\n for (int i = 0; i < n; i++)\n {\n if (text1[i] != text2[i])\n {\n return i;\n }\n }\n return n;\n }\n\n \/**\n * Determine the common suffix of two strings.\n * @param text1 First string.\n * @param text2 Second string.\n * @return The number of characters common to the end of each string.\n *\/\n public int diff_commonSuffix(string text1, string text2)\n {\n \/\/ Performance analysis: https:\/\/neil.fraser.name\/news\/2007\/10\/09\/\n int text1_length = text1.Length;\n int text2_length = text2.Length;\n int n = Math.Min(text1.Length, text2.Length);\n for (int i = 1; i <= n; i++)\n {\n if (text1[text1_length - i] != text2[text2_length - i])\n {\n return i - 1;\n }\n }\n return n;\n }\n\n \/**\n * Determine if the suffix of one string is the prefix of another.\n * @param text1 First string.\n * @param text2 Second string.\n * @return The number of characters common to the end of the first\n * string and the start of the second string.\n *\/\n protected int diff_commonOverlap(string text1, string text2)\n {\n \/\/ Cache the text lengths to prevent multiple calls.\n int text1_length = text1.Length;\n int text2_length = text2.Length;\n \/\/ Eliminate the null case.\n if (text1_length == 0 || text2_length == 0)\n {\n return 0;\n }\n \/\/ Truncate the longer string.\n if (text1_length > text2_length)\n {\n text1 = text1.Substring(text1_length - text2_length);\n }\n else if (text1_length < text2_length)\n {\n text2 = text2.Substring(0, text1_length);\n }\n int text_length = Math.Min(text1_length, text2_length);\n \/\/ Quick check for the worst case.\n if (text1 == text2)\n {\n return text_length;\n }\n\n \/\/ Start by looking for a single character match\n \/\/ and increase length until no match is found.\n \/\/ Performance analysis: https:\/\/neil.fraser.name\/news\/2010\/11\/04\/\n int best = 0;\n int length = 1;\n while (true)\n {\n string pattern = text1.Substring(text_length - length);\n int found = text2.IndexOf(pattern, StringComparison.Ordinal);\n if (found == -1)\n {\n return best;\n }\n length += found;\n if (found == 0 || text1.Substring(text_length - length) ==\n text2.Substring(0, length))\n {\n best = length;\n length++;\n }\n }\n }\n\n \/**\n * Do the two texts share a Substring which is at least half the length of\n * the longer text?\n * This speedup can produce non-minimal diffs.\n * @param text1 First string.\n * @param text2 Second string.\n * @return Five element String array, containing the prefix of text1, the\n * suffix of text1, the prefix of text2, the suffix of text2 and the\n * common middle. Or null if there was no match.\n *\/\n\n protected string[] diff_halfMatch(string text1, string text2)\n {\n if (this.Diff_Timeout <= 0)\n {\n \/\/ Don't risk returning a non-optimal diff if we have unlimited time.\n return null;\n }\n string longtext = text1.Length > text2.Length ? text1 : text2;\n string shorttext = text1.Length > text2.Length ? text2 : text1;\n if (longtext.Length < 4 || shorttext.Length * 2 < longtext.Length)\n {\n return null; \/\/ Pointless.\n }\n\n \/\/ First check if the second quarter is the seed for a half-match.\n string[] hm1 = diff_halfMatchI(longtext, shorttext,\n (longtext.Length + 3) \/ 4);\n \/\/ Check again based on the third quarter.\n string[] hm2 = diff_halfMatchI(longtext, shorttext,\n (longtext.Length + 1) \/ 2);\n string[] hm;\n if (hm1 == null && hm2 == null)\n {\n return null;\n }\n else if (hm2 == null)\n {\n hm = hm1;\n }\n else if (hm1 == null)\n {\n hm = hm2;\n }\n else\n {\n \/\/ Both matched. Select the longest.\n hm = hm1[4].Length > hm2[4].Length ? hm1 : hm2;\n }\n\n \/\/ A half-match was found, sort out the return data.\n if (text1.Length > text2.Length)\n {\n return hm;\n \/\/return new string[]{hm[0], hm[1], hm[2], hm[3], hm[4]};\n }\n else\n {\n return new string[] { hm[2], hm[3], hm[0], hm[1], hm[4] };\n }\n }\n\n \/**\n * Does a Substring of shorttext exist within longtext such that the\n * Substring is at least half the length of longtext?\n * @param longtext Longer string.\n * @param shorttext Shorter string.\n * @param i Start index of quarter length Substring within longtext.\n * @return Five element string array, containing the prefix of longtext, the\n * suffix of longtext, the prefix of shorttext, the suffix of shorttext\n * and the common middle. Or null if there was no match.\n *\/\n private string[] diff_halfMatchI(string longtext, string shorttext, int i)\n {\n \/\/ Start with a 1\/4 length Substring at position i as a seed.\n string seed = longtext.Substring(i, longtext.Length \/ 4);\n int j = -1;\n string best_common = string.Empty;\n string best_longtext_a = string.Empty, best_longtext_b = string.Empty;\n string best_shorttext_a = string.Empty, best_shorttext_b = string.Empty;\n while (j < shorttext.Length && (j = shorttext.IndexOf(seed, j + 1,\n StringComparison.Ordinal)) != -1)\n {\n int prefixLength = diff_commonPrefix(longtext.Substring(i),\n shorttext.Substring(j));\n int suffixLength = diff_commonSuffix(longtext.Substring(0, i),\n shorttext.Substring(0, j));\n if (best_common.Length < suffixLength + prefixLength)\n {\n best_common = shorttext.Substring(j - suffixLength, suffixLength)\n + shorttext.Substring(j, prefixLength);\n best_longtext_a = longtext.Substring(0, i - suffixLength);\n best_longtext_b = longtext.Substring(i + prefixLength);\n best_shorttext_a = shorttext.Substring(0, j - suffixLength);\n best_shorttext_b = shorttext.Substring(j + prefixLength);\n }\n }\n if (best_common.Length * 2 >= longtext.Length)\n {\n return new string[]{best_longtext_a, best_longtext_b,\n best_shorttext_a, best_shorttext_b, best_common};\n }\n else\n {\n return null;\n }\n }\n\n \/**\n * Reduce the number of edits by eliminating semantically trivial\n * equalities.\n * @param diffs List of Diff objects.\n *\/\n public void diff_cleanupSemantic(List<Diff> diffs)\n {\n bool changes = false;\n \/\/ Stack of indices where equalities are found.\n Stack<int> equalities = new Stack<int>();\n \/\/ Always equal to equalities[equalitiesLength-1][1]\n string lastEquality = null;\n int pointer = 0; \/\/ Index of current position.\n \/\/ Number of characters that changed prior to the equality.\n int length_insertions1 = 0;\n int length_deletions1 = 0;\n \/\/ Number of characters that changed after the equality.\n int length_insertions2 = 0;\n int length_deletions2 = 0;\n while (pointer < diffs.Count)\n {\n if (diffs[pointer].operation == Operation.EQUAL)\n { \/\/ Equality found.\n equalities.Push(pointer);\n length_insertions1 = length_insertions2;\n length_deletions1 = length_deletions2;\n length_insertions2 = 0;\n length_deletions2 = 0;\n lastEquality = diffs[pointer].text;\n }\n else\n { \/\/ an insertion or deletion\n if (diffs[pointer].operation == Operation.INSERT)\n {\n length_insertions2 += diffs[pointer].text.Length;\n }\n else\n {\n length_deletions2 += diffs[pointer].text.Length;\n }\n \/\/ Eliminate an equality that is smaller or equal to the edits on both\n \/\/ sides of it.\n if (lastEquality != null && (lastEquality.Length\n <= Math.Max(length_insertions1, length_deletions1))\n && (lastEquality.Length\n <= Math.Max(length_insertions2, length_deletions2)))\n {\n \/\/ Duplicate record.\n diffs.Insert(equalities.Peek(),\n new Diff(Operation.DELETE, lastEquality));\n \/\/ Change second copy to insert.\n diffs[equalities.Peek() + 1].operation = Operation.INSERT;\n \/\/ Throw away the equality we just deleted.\n equalities.Pop();\n if (equalities.Count > 0)\n {\n equalities.Pop();\n }\n pointer = equalities.Count > 0 ? equalities.Peek() : -1;\n length_insertions1 = 0; \/\/ Reset the counters.\n length_deletions1 = 0;\n length_insertions2 = 0;\n length_deletions2 = 0;\n lastEquality = null;\n changes = true;\n }\n }\n pointer++;\n }\n\n \/\/ Normalize the diff.\n if (changes)\n {\n diff_cleanupMerge(diffs);\n }\n diff_cleanupSemanticLossless(diffs);\n\n \/\/ Find any overlaps between deletions and insertions.\n \/\/ e.g: <del>abcxxx<\/del><ins>xxxdef<\/ins>\n \/\/ -> <del>abc<\/del>xxx<ins>def<\/ins>\n \/\/ e.g: <del>xxxabc<\/del><ins>defxxx<\/ins>\n \/\/ -> <ins>def<\/ins>xxx<del>abc<\/del>\n \/\/ Only extract an overlap if it is as big as the edit ahead or behind it.\n pointer = 1;\n while (pointer < diffs.Count)\n {\n if (diffs[pointer - 1].operation == Operation.DELETE &&\n diffs[pointer].operation == Operation.INSERT)\n {\n string deletion = diffs[pointer - 1].text;\n string insertion = diffs[pointer].text;\n int overlap_length1 = diff_commonOverlap(deletion, insertion);\n int overlap_length2 = diff_commonOverlap(insertion, deletion);\n if (overlap_length1 >= overlap_length2)\n {\n if (overlap_length1 >= deletion.Length \/ 2.0 ||\n overlap_length1 >= insertion.Length \/ 2.0)\n {\n \/\/ Overlap found.\n \/\/ Insert an equality and trim the surrounding edits.\n diffs.Insert(pointer, new Diff(Operation.EQUAL,\n insertion.Substring(0, overlap_length1)));\n diffs[pointer - 1].text =\n deletion.Substring(0, deletion.Length - overlap_length1);\n diffs[pointer + 1].text = insertion.Substring(overlap_length1);\n pointer++;\n }\n }\n else\n {\n if (overlap_length2 >= deletion.Length \/ 2.0 ||\n overlap_length2 >= insertion.Length \/ 2.0)\n {\n \/\/ Reverse overlap found.\n \/\/ Insert an equality and swap and trim the surrounding edits.\n diffs.Insert(pointer, new Diff(Operation.EQUAL,\n deletion.Substring(0, overlap_length2)));\n diffs[pointer - 1].operation = Operation.INSERT;\n diffs[pointer - 1].text =\n insertion.Substring(0, insertion.Length - overlap_length2);\n diffs[pointer + 1].operation = Operation.DELETE;\n diffs[pointer + 1].text = deletion.Substring(overlap_length2);\n pointer++;\n }\n }\n pointer++;\n }\n pointer++;\n }\n }\n\n \/**\n * Look for single edits surrounded on both sides by equalities\n * which can be shifted sideways to align the edit to a word boundary.\n * e.g: The c<ins>at c<\/ins>ame. -> The <ins>cat <\/ins>came.\n * @param diffs List of Diff objects.\n *\/\n public void diff_cleanupSemanticLossless(List<Diff> diffs)\n {\n int pointer = 1;\n \/\/ Intentionally ignore the first and last element (don't need checking).\n while (pointer < diffs.Count - 1)\n {\n if (diffs[pointer - 1].operation == Operation.EQUAL &&\n diffs[pointer + 1].operation == Operation.EQUAL)\n {\n \/\/ This is a single edit surrounded by equalities.\n string equality1 = diffs[pointer - 1].text;\n string edit = diffs[pointer].text;\n string equality2 = diffs[pointer + 1].text;\n\n \/\/ First, shift the edit as far left as possible.\n int commonOffset = this.diff_commonSuffix(equality1, edit);\n if (commonOffset > 0)\n {\n string commonString = edit.Substring(edit.Length - commonOffset);\n equality1 = equality1.Substring(0, equality1.Length - commonOffset);\n edit = commonString + edit.Substring(0, edit.Length - commonOffset);\n equality2 = commonString + equality2;\n }\n\n \/\/ Second, step character by character right,\n \/\/ looking for the best fit.\n string bestEquality1 = equality1;\n string bestEdit = edit;\n string bestEquality2 = equality2;\n int bestScore = diff_cleanupSemanticScore(equality1, edit) +\n diff_cleanupSemanticScore(edit, equality2);\n while (edit.Length != 0 && equality2.Length != 0\n && edit[0] == equality2[0])\n {\n equality1 += edit[0];\n edit = edit.Substring(1) + equality2[0];\n equality2 = equality2.Substring(1);\n int score = diff_cleanupSemanticScore(equality1, edit) +\n diff_cleanupSemanticScore(edit, equality2);\n \/\/ The >= encourages trailing rather than leading whitespace on\n \/\/ edits.\n if (score >= bestScore)\n {\n bestScore = score;\n bestEquality1 = equality1;\n bestEdit = edit;\n bestEquality2 = equality2;\n }\n }\n\n if (diffs[pointer - 1].text != bestEquality1)\n {\n \/\/ We have an improvement, save it back to the diff.\n if (bestEquality1.Length != 0)\n {\n diffs[pointer - 1].text = bestEquality1;\n }\n else\n {\n diffs.RemoveAt(pointer - 1);\n pointer--;\n }\n diffs[pointer].text = bestEdit;\n if (bestEquality2.Length != 0)\n {\n diffs[pointer + 1].text = bestEquality2;\n }\n else\n {\n diffs.RemoveAt(pointer + 1);\n pointer--;\n }\n }\n }\n pointer++;\n }\n }\n\n \/**\n * Given two strings, compute a score representing whether the internal\n * boundary falls on logical boundaries.\n * Scores range from 6 (best) to 0 (worst).\n * @param one First string.\n * @param two Second string.\n * @return The score.\n *\/\n private int diff_cleanupSemanticScore(string one, string two)\n {\n if (one.Length == 0 || two.Length == 0)\n {\n \/\/ Edges are the best.\n return 6;\n }\n\n \/\/ Each port of this function behaves slightly differently due to\n \/\/ subtle differences in each language's definition of things like\n \/\/ 'whitespace'. Since this function's purpose is largely cosmetic,\n \/\/ the choice has been made to use each language's native features\n \/\/ rather than force total conformity.\n char char1 = one[one.Length - 1];\n char char2 = two[0];\n bool nonAlphaNumeric1 = !Char.IsLetterOrDigit(char1);\n bool nonAlphaNumeric2 = !Char.IsLetterOrDigit(char2);\n bool whitespace1 = nonAlphaNumeric1 && Char.IsWhiteSpace(char1);\n bool whitespace2 = nonAlphaNumeric2 && Char.IsWhiteSpace(char2);\n bool lineBreak1 = whitespace1 && Char.IsControl(char1);\n bool lineBreak2 = whitespace2 && Char.IsControl(char2);\n bool blankLine1 = lineBreak1 && BLANKLINEEND.IsMatch(one);\n bool blankLine2 = lineBreak2 && BLANKLINESTART.IsMatch(two);\n\n if (blankLine1 || blankLine2)\n {\n \/\/ Five points for blank lines.\n return 5;\n }\n else if (lineBreak1 || lineBreak2)\n {\n \/\/ Four points for line breaks.\n return 4;\n }\n else if (nonAlphaNumeric1 && !whitespace1 && whitespace2)\n {\n \/\/ Three points for end of sentences.\n return 3;\n }\n else if (whitespace1 || whitespace2)\n {\n \/\/ Two points for whitespace.\n return 2;\n }\n else if (nonAlphaNumeric1 || nonAlphaNumeric2)\n {\n \/\/ One point for non-alphanumeric.\n return 1;\n }\n return 0;\n }\n\n \/\/ Define some regex patterns for matching boundaries.\n private Regex BLANKLINEEND = new Regex(\"\\\\n\\\\r?\\\\n\\\\Z\");\n private Regex BLANKLINESTART = new Regex(\"\\\\A\\\\r?\\\\n\\\\r?\\\\n\");\n\n \/**\n * Reduce the number of edits by eliminating operationally trivial\n * equalities.\n * @param diffs List of Diff objects.\n *\/\n public void diff_cleanupEfficiency(List<Diff> diffs)\n {\n bool changes = false;\n \/\/ Stack of indices where equalities are found.\n Stack<int> equalities = new Stack<int>();\n \/\/ Always equal to equalities[equalitiesLength-1][1]\n string lastEquality = string.Empty;\n int pointer = 0; \/\/ Index of current position.\n \/\/ Is there an insertion operation before the last equality.\n bool pre_ins = false;\n \/\/ Is there a deletion operation before the last equality.\n bool pre_del = false;\n \/\/ Is there an insertion operation after the last equality.\n bool post_ins = false;\n \/\/ Is there a deletion operation after the last equality.\n bool post_del = false;\n while (pointer < diffs.Count)\n {\n if (diffs[pointer].operation == Operation.EQUAL)\n { \/\/ Equality found.\n if (diffs[pointer].text.Length < this.Diff_EditCost\n && (post_ins || post_del))\n {\n \/\/ Candidate found.\n equalities.Push(pointer);\n pre_ins = post_ins;\n pre_del = post_del;\n lastEquality = diffs[pointer].text;\n }\n else\n {\n \/\/ Not a candidate, and can never become one.\n equalities.Clear();\n lastEquality = string.Empty;\n }\n post_ins = post_del = false;\n }\n else\n { \/\/ An insertion or deletion.\n if (diffs[pointer].operation == Operation.DELETE)\n {\n post_del = true;\n }\n else\n {\n post_ins = true;\n }\n \/*\n * Five types to be split:\n * <ins>A<\/ins><del>B<\/del>XY<ins>C<\/ins><del>D<\/del>\n * <ins>A<\/ins>X<ins>C<\/ins><del>D<\/del>\n * <ins>A<\/ins><del>B<\/del>X<ins>C<\/ins>\n * <ins>A<\/del>X<ins>C<\/ins><del>D<\/del>\n * <ins>A<\/ins><del>B<\/del>X<del>C<\/del>\n *\/\n if ((lastEquality.Length != 0)\n && ((pre_ins && pre_del && post_ins && post_del)\n || ((lastEquality.Length < this.Diff_EditCost \/ 2)\n && ((pre_ins ? 1 : 0) + (pre_del ? 1 : 0) + (post_ins ? 1 : 0)\n + (post_del ? 1 : 0)) == 3)))\n {\n \/\/ Duplicate record.\n diffs.Insert(equalities.Peek(),\n new Diff(Operation.DELETE, lastEquality));\n \/\/ Change second copy to insert.\n diffs[equalities.Peek() + 1].operation = Operation.INSERT;\n equalities.Pop(); \/\/ Throw away the equality we just deleted.\n lastEquality = string.Empty;\n if (pre_ins && pre_del)\n {\n \/\/ No changes made which could affect previous entry, keep going.\n post_ins = post_del = true;\n equalities.Clear();\n }\n else\n {\n if (equalities.Count > 0)\n {\n equalities.Pop();\n }\n\n pointer = equalities.Count > 0 ? equalities.Peek() : -1;\n post_ins = post_del = false;\n }\n changes = true;\n }\n }\n pointer++;\n }\n\n if (changes)\n {\n diff_cleanupMerge(diffs);\n }\n }\n\n \/**\n * Reorder and merge like edit sections. Merge equalities.\n * Any edit section can move as long as it doesn't cross an equality.\n * @param diffs List of Diff objects.\n *\/\n public void diff_cleanupMerge(List<Diff> diffs)\n {\n \/\/ Add a dummy entry at the end.\n diffs.Add(new Diff(Operation.EQUAL, string.Empty));\n int pointer = 0;\n int count_delete = 0;\n int count_insert = 0;\n string text_delete = string.Empty;\n string text_insert = string.Empty;\n int commonlength;\n while (pointer < diffs.Count)\n {\n switch (diffs[pointer].operation)\n {\n case Operation.INSERT:\n count_insert++;\n text_insert += diffs[pointer].text;\n pointer++;\n break;\n case Operation.DELETE:\n count_delete++;\n text_delete += diffs[pointer].text;\n pointer++;\n break;\n case Operation.EQUAL:\n \/\/ Upon reaching an equality, check for prior redundancies.\n if (count_delete + count_insert > 1)\n {\n if (count_delete != 0 && count_insert != 0)\n {\n \/\/ Factor out any common prefixies.\n commonlength = this.diff_commonPrefix(text_insert, text_delete);\n if (commonlength != 0)\n {\n if ((pointer - count_delete - count_insert) > 0 &&\n diffs[pointer - count_delete - count_insert - 1].operation\n == Operation.EQUAL)\n {\n diffs[pointer - count_delete - count_insert - 1].text\n += text_insert.Substring(0, commonlength);\n }\n else\n {\n diffs.Insert(0, new Diff(Operation.EQUAL,\n text_insert.Substring(0, commonlength)));\n pointer++;\n }\n text_insert = text_insert.Substring(commonlength);\n text_delete = text_delete.Substring(commonlength);\n }\n \/\/ Factor out any common suffixies.\n commonlength = this.diff_commonSuffix(text_insert, text_delete);\n if (commonlength != 0)\n {\n diffs[pointer].text = text_insert.Substring(text_insert.Length\n - commonlength) + diffs[pointer].text;\n text_insert = text_insert.Substring(0, text_insert.Length\n - commonlength);\n text_delete = text_delete.Substring(0, text_delete.Length\n - commonlength);\n }\n }\n \/\/ Delete the offending records and add the merged ones.\n pointer -= count_delete + count_insert;\n diffs.Splice(pointer, count_delete + count_insert);\n if (text_delete.Length != 0)\n {\n diffs.Splice(pointer, 0,\n new Diff(Operation.DELETE, text_delete));\n pointer++;\n }\n if (text_insert.Length != 0)\n {\n diffs.Splice(pointer, 0,\n new Diff(Operation.INSERT, text_insert));\n pointer++;\n }\n pointer++;\n }\n else if (pointer != 0\n && diffs[pointer - 1].operation == Operation.EQUAL)\n {\n \/\/ Merge this equality with the previous one.\n diffs[pointer - 1].text += diffs[pointer].text;\n diffs.RemoveAt(pointer);\n }\n else\n {\n pointer++;\n }\n count_insert = 0;\n count_delete = 0;\n text_delete = string.Empty;\n text_insert = string.Empty;\n break;\n }\n }\n if (diffs[diffs.Count - 1].text.Length == 0)\n {\n diffs.RemoveAt(diffs.Count - 1); \/\/ Remove the dummy entry at the end.\n }\n\n \/\/ Second pass: look for single edits surrounded on both sides by\n \/\/ equalities which can be shifted sideways to eliminate an equality.\n \/\/ e.g: A<ins>BA<\/ins>C -> <ins>AB<\/ins>AC\n bool changes = false;\n pointer = 1;\n \/\/ Intentionally ignore the first and last element (don't need checking).\n while (pointer < (diffs.Count - 1))\n {\n if (diffs[pointer - 1].operation == Operation.EQUAL &&\n diffs[pointer + 1].operation == Operation.EQUAL)\n {\n \/\/ This is a single edit surrounded by equalities.\n if (diffs[pointer].text.EndsWith(diffs[pointer - 1].text,\n StringComparison.Ordinal))\n {\n \/\/ Shift the edit over the previous equality.\n diffs[pointer].text = diffs[pointer - 1].text +\n diffs[pointer].text.Substring(0, diffs[pointer].text.Length -\n diffs[pointer - 1].text.Length);\n diffs[pointer + 1].text = diffs[pointer - 1].text\n + diffs[pointer + 1].text;\n diffs.Splice(pointer - 1, 1);\n changes = true;\n }\n else if (diffs[pointer].text.StartsWith(diffs[pointer + 1].text,\n StringComparison.Ordinal))\n {\n \/\/ Shift the edit over the next equality.\n diffs[pointer - 1].text += diffs[pointer + 1].text;\n diffs[pointer].text =\n diffs[pointer].text.Substring(diffs[pointer + 1].text.Length)\n + diffs[pointer + 1].text;\n diffs.Splice(pointer + 1, 1);\n changes = true;\n }\n }\n pointer++;\n }\n \/\/ If shifts were made, the diff needs reordering and another shift sweep.\n if (changes)\n {\n this.diff_cleanupMerge(diffs);\n }\n }\n\n \/**\n * loc is a location in text1, compute and return the equivalent location in\n * text2.\n * e.g. \"The cat\" vs \"The big cat\", 1->1, 5->8\n * @param diffs List of Diff objects.\n * @param loc Location within text1.\n * @return Location within text2.\n *\/\n public int diff_xIndex(List<Diff> diffs, int loc)\n {\n int chars1 = 0;\n int chars2 = 0;\n int last_chars1 = 0;\n int last_chars2 = 0;\n Diff lastDiff = null;\n foreach (Diff aDiff in diffs)\n {\n if (aDiff.operation != Operation.INSERT)\n {\n \/\/ Equality or deletion.\n chars1 += aDiff.text.Length;\n }\n if (aDiff.operation != Operation.DELETE)\n {\n \/\/ Equality or insertion.\n chars2 += aDiff.text.Length;\n }\n if (chars1 > loc)\n {\n \/\/ Overshot the location.\n lastDiff = aDiff;\n break;\n }\n last_chars1 = chars1;\n last_chars2 = chars2;\n }\n if (lastDiff != null && lastDiff.operation == Operation.DELETE)\n {\n \/\/ The location was deleted.\n return last_chars2;\n }\n \/\/ Add the remaining character length.\n return last_chars2 + (loc - last_chars1);\n }\n\n \/**\n * Convert a Diff list into a pretty HTML report.\n * @param diffs List of Diff objects.\n * @return HTML representation.\n *\/\n public string diff_prettyHtml(List<Diff> diffs)\n {\n StringBuilder html = new StringBuilder();\n foreach (Diff aDiff in diffs)\n {\n string text = aDiff.text.Replace(\"&\", \"&\").Replace(\"<\", \"<\")\n .Replace(\">\", \">\").Replace(\"\\n\", \"¶<br>\");\n switch (aDiff.operation)\n {\n case Operation.INSERT:\n html.Append(\"<ins style=\\\"background:#e6ffe6;\\\">\").Append(text)\n .Append(\"<\/ins>\");\n break;\n case Operation.DELETE:\n html.Append(\"<del style=\\\"background:#ffe6e6;\\\">\").Append(text)\n .Append(\"<\/del>\");\n break;\n case Operation.EQUAL:\n html.Append(\"<span>\").Append(text).Append(\"<\/span>\");\n break;\n }\n }\n return html.ToString();\n }\n\n \/**\n * Compute and return the source text (all equalities and deletions).\n * @param diffs List of Diff objects.\n * @return Source text.\n *\/\n public string diff_text1(List<Diff> diffs)\n {\n StringBuilder text = new StringBuilder();\n foreach (Diff aDiff in diffs)\n {\n if (aDiff.operation != Operation.INSERT)\n {\n text.Append(aDiff.text);\n }\n }\n return text.ToString();\n }\n\n \/**\n * Compute and return the destination text (all equalities and insertions).\n * @param diffs List of Diff objects.\n * @return Destination text.\n *\/\n public string diff_text2(List<Diff> diffs)\n {\n StringBuilder text = new StringBuilder();\n foreach (Diff aDiff in diffs)\n {\n if (aDiff.operation != Operation.DELETE)\n {\n text.Append(aDiff.text);\n }\n }\n return text.ToString();\n }\n\n \/**\n * Compute the Levenshtein distance; the number of inserted, deleted or\n * substituted characters.\n * @param diffs List of Diff objects.\n * @return Number of changes.\n *\/\n public int diff_levenshtein(List<Diff> diffs)\n {\n int levenshtein = 0;\n int insertions = 0;\n int deletions = 0;\n foreach (Diff aDiff in diffs)\n {\n switch (aDiff.operation)\n {\n case Operation.INSERT:\n insertions += aDiff.text.Length;\n break;\n case Operation.DELETE:\n deletions += aDiff.text.Length;\n break;\n case Operation.EQUAL:\n \/\/ A deletion and an insertion is one substitution.\n levenshtein += Math.Max(insertions, deletions);\n insertions = 0;\n deletions = 0;\n break;\n }\n }\n levenshtein += Math.Max(insertions, deletions);\n return levenshtein;\n }\n\n \/**\n * Crush the diff into an encoded string which describes the operations\n * required to transform text1 into text2.\n * E.g. =3\\t-2\\t+ing -> Keep 3 chars, delete 2 chars, insert 'ing'.\n * Operations are tab-separated. Inserted text is escaped using %xx\n * notation.\n * @param diffs Array of Diff objects.\n * @return Delta text.\n *\/\n public string diff_toDelta(List<Diff> diffs)\n {\n StringBuilder text = new StringBuilder();\n foreach (Diff aDiff in diffs)\n {\n switch (aDiff.operation)\n {\n case Operation.INSERT:\n text.Append(\"+\").Append(encodeURI(aDiff.text)).Append(\"\\t\");\n break;\n case Operation.DELETE:\n text.Append(\"-\").Append(aDiff.text.Length).Append(\"\\t\");\n break;\n case Operation.EQUAL:\n text.Append(\"=\").Append(aDiff.text.Length).Append(\"\\t\");\n break;\n }\n }\n string delta = text.ToString();\n if (delta.Length != 0)\n {\n \/\/ Strip off trailing tab character.\n delta = delta.Substring(0, delta.Length - 1);\n }\n return delta;\n }\n\n \/**\n * Given the original text1, and an encoded string which describes the\n * operations required to transform text1 into text2, compute the full diff.\n * @param text1 Source string for the diff.\n * @param delta Delta text.\n * @return Array of Diff objects or null if invalid.\n * @throws ArgumentException If invalid input.\n *\/\n public List<Diff> diff_fromDelta(string text1, string delta)\n {\n List<Diff> diffs = new List<Diff>();\n int pointer = 0; \/\/ Cursor in text1\n string[] tokens = delta.Split(new string[] { \"\\t\" },\n StringSplitOptions.None);\n foreach (string token in tokens)\n {\n if (token.Length == 0)\n {\n \/\/ Blank tokens are ok (from a trailing \\t).\n continue;\n }\n \/\/ Each token begins with a one character parameter which specifies the\n \/\/ operation of this token (delete, insert, equality).\n string param = token.Substring(1);\n switch (token[0])\n {\n case '+':\n \/\/ decode would change all \"+\" to \" \"\n param = param.Replace(\"+\", \"%2b\");\n\n param = HttpUtility.UrlDecode(param);\n \/\/} catch (UnsupportedEncodingException e) {\n \/\/ \/\/ Not likely on modern system.\n \/\/ throw new Error(\"This system does not support UTF-8.\", e);\n \/\/} catch (IllegalArgumentException e) {\n \/\/ \/\/ Malformed URI sequence.\n \/\/ throw new IllegalArgumentException(\n \/\/ \"Illegal escape in diff_fromDelta: \" + param, e);\n \/\/}\n diffs.Add(new Diff(Operation.INSERT, param));\n break;\n case '-':\n \/\/ Fall through.\n case '=':\n int n;\n try\n {\n n = Convert.ToInt32(param);\n }\n catch (FormatException e)\n {\n throw new ArgumentException(\n \"Invalid number in diff_fromDelta: \" + param, e);\n }\n if (n < 0)\n {\n throw new ArgumentException(\n \"Negative number in diff_fromDelta: \" + param);\n }\n string text;\n try\n {\n text = text1.Substring(pointer, n);\n pointer += n;\n }\n catch (ArgumentOutOfRangeException e)\n {\n throw new ArgumentException(\"Delta length (\" + pointer\n + \") larger than source text length (\" + text1.Length\n + \").\", e);\n }\n if (token[0] == '=')\n {\n diffs.Add(new Diff(Operation.EQUAL, text));\n }\n else\n {\n diffs.Add(new Diff(Operation.DELETE, text));\n }\n break;\n default:\n \/\/ Anything else is an error.\n throw new ArgumentException(\n \"Invalid diff operation in diff_fromDelta: \" + token[0]);\n }\n }\n if (pointer != text1.Length)\n {\n throw new ArgumentException(\"Delta length (\" + pointer\n + \") smaller than source text length (\" + text1.Length + \").\");\n }\n return diffs;\n }\n\n\n \/\/ MATCH FUNCTIONS\n\n\n \/**\n * Locate the best instance of 'pattern' in 'text' near 'loc'.\n * Returns -1 if no match found.\n * @param text The text to search.\n * @param pattern The pattern to search for.\n * @param loc The location to search around.\n * @return Best match index or -1.\n *\/\n public int match_main(string text, string pattern, int loc)\n {\n \/\/ Check for null inputs not needed since null can't be passed in C#.\n\n loc = Math.Max(0, Math.Min(loc, text.Length));\n if (text == pattern)\n {\n \/\/ Shortcut (potentially not guaranteed by the algorithm)\n return 0;\n }\n else if (text.Length == 0)\n {\n \/\/ Nothing to match.\n return -1;\n }\n else if (loc + pattern.Length <= text.Length\n && text.Substring(loc, pattern.Length) == pattern)\n {\n \/\/ Perfect match at the perfect spot! (Includes case of null pattern)\n return loc;\n }\n else\n {\n \/\/ Do a fuzzy compare.\n return match_bitap(text, pattern, loc);\n }\n }\n\n \/**\n * Locate the best instance of 'pattern' in 'text' near 'loc' using the\n * Bitap algorithm. Returns -1 if no match found.\n * @param text The text to search.\n * @param pattern The pattern to search for.\n * @param loc The location to search around.\n * @return Best match index or -1.\n *\/\n protected int match_bitap(string text, string pattern, int loc)\n {\n \/\/ assert (Match_MaxBits == 0 || pattern.Length <= Match_MaxBits)\n \/\/ : \"Pattern too long for this application.\";\n\n \/\/ Initialise the alphabet.\n Dictionary<char, int> s = match_alphabet(pattern);\n\n \/\/ Highest score beyond which we give up.\n double score_threshold = Match_Threshold;\n \/\/ Is there a nearby exact match? (speedup)\n int best_loc = text.IndexOf(pattern, loc, StringComparison.Ordinal);\n if (best_loc != -1)\n {\n score_threshold = Math.Min(match_bitapScore(0, best_loc, loc,\n pattern), score_threshold);\n \/\/ What about in the other direction? (speedup)\n best_loc = text.LastIndexOf(pattern,\n Math.Min(loc + pattern.Length, text.Length),\n StringComparison.Ordinal);\n if (best_loc != -1)\n {\n score_threshold = Math.Min(match_bitapScore(0, best_loc, loc,\n pattern), score_threshold);\n }\n }\n\n \/\/ Initialise the bit arrays.\n int matchmask = 1 << (pattern.Length - 1);\n best_loc = -1;\n\n int bin_min, bin_mid;\n int bin_max = pattern.Length + text.Length;\n \/\/ Empty initialization added to appease C# compiler.\n int[] last_rd = new int[0];\n for (int d = 0; d < pattern.Length; d++)\n {\n \/\/ Scan for the best match; each iteration allows for one more error.\n \/\/ Run a binary search to determine how far from 'loc' we can stray at\n \/\/ this error level.\n bin_min = 0;\n bin_mid = bin_max;\n while (bin_min < bin_mid)\n {\n if (match_bitapScore(d, loc + bin_mid, loc, pattern)\n <= score_threshold)\n {\n bin_min = bin_mid;\n }\n else\n {\n bin_max = bin_mid;\n }\n bin_mid = (bin_max - bin_min) \/ 2 + bin_min;\n }\n \/\/ Use the result from this iteration as the maximum for the next.\n bin_max = bin_mid;\n int start = Math.Max(1, loc - bin_mid + 1);\n int finish = Math.Min(loc + bin_mid, text.Length) + pattern.Length;\n\n int[] rd = new int[finish + 2];\n rd[finish + 1] = (1 << d) - 1;\n for (int j = finish; j >= start; j--)\n {\n int charMatch;\n if (text.Length <= j - 1 || !s.ContainsKey(text[j - 1]))\n {\n \/\/ Out of range.\n charMatch = 0;\n }\n else\n {\n charMatch = s[text[j - 1]];\n }\n if (d == 0)\n {\n \/\/ First pass: exact match.\n rd[j] = ((rd[j + 1] << 1) | 1) & charMatch;\n }\n else\n {\n \/\/ Subsequent passes: fuzzy match.\n rd[j] = ((rd[j + 1] << 1) | 1) & charMatch\n | (((last_rd[j + 1] | last_rd[j]) << 1) | 1) | last_rd[j + 1];\n }\n if ((rd[j] & matchmask) != 0)\n {\n double score = match_bitapScore(d, j - 1, loc, pattern);\n \/\/ This match will almost certainly be better than any existing\n \/\/ match. But check anyway.\n if (score <= score_threshold)\n {\n \/\/ Told you so.\n score_threshold = score;\n best_loc = j - 1;\n if (best_loc > loc)\n {\n \/\/ When passing loc, don't exceed our current distance from loc.\n start = Math.Max(1, 2 * loc - best_loc);\n }\n else\n {\n \/\/ Already passed loc, downhill from here on in.\n break;\n }\n }\n }\n }\n if (match_bitapScore(d + 1, loc, loc, pattern) > score_threshold)\n {\n \/\/ No hope for a (better) match at greater error levels.\n break;\n }\n last_rd = rd;\n }\n return best_loc;\n }\n\n \/**\n * Compute and return the score for a match with e errors and x location.\n * @param e Number of errors in match.\n * @param x Location of match.\n * @param loc Expected location of match.\n * @param pattern Pattern being sought.\n * @return Overall score for match (0.0 = good, 1.0 = bad).\n *\/\n private double match_bitapScore(int e, int x, int loc, string pattern)\n {\n float accuracy = (float)e \/ pattern.Length;\n int proximity = Math.Abs(loc - x);\n if (Match_Distance == 0)\n {\n \/\/ Dodge divide by zero error.\n return proximity == 0 ? accuracy : 1.0;\n }\n return accuracy + (proximity \/ (float)Match_Distance);\n }\n\n \/**\n * Initialise the alphabet for the Bitap algorithm.\n * @param pattern The text to encode.\n * @return Hash of character locations.\n *\/\n protected Dictionary<char, int> match_alphabet(string pattern)\n {\n Dictionary<char, int> s = new Dictionary<char, int>();\n char[] char_pattern = pattern.ToCharArray();\n foreach (char c in char_pattern)\n {\n if (!s.ContainsKey(c))\n {\n s.Add(c, 0);\n }\n }\n int i = 0;\n foreach (char c in char_pattern)\n {\n int value = s[c] | (1 << (pattern.Length - i - 1));\n s[c] = value;\n i++;\n }\n return s;\n }\n\n\n \/\/ PATCH FUNCTIONS\n\n\n \/**\n * Increase the context until it is unique,\n * but don't let the pattern expand beyond Match_MaxBits.\n * @param patch The patch to grow.\n * @param text Source text.\n *\/\n protected void patch_addContext(Patch patch, string text)\n {\n if (text.Length == 0)\n {\n return;\n }\n string pattern = text.Substring(patch.start2, patch.length1);\n int padding = 0;\n\n \/\/ Look for the first and last matches of pattern in text. If two\n \/\/ different matches are found, increase the pattern length.\n while (text.IndexOf(pattern, StringComparison.Ordinal)\n != text.LastIndexOf(pattern, StringComparison.Ordinal)\n && pattern.Length < Match_MaxBits - Patch_Margin - Patch_Margin)\n {\n padding += Patch_Margin;\n pattern = text.JavaSubstring(Math.Max(0, patch.start2 - padding),\n Math.Min(text.Length, patch.start2 + patch.length1 + padding));\n }\n \/\/ Add one chunk for good luck.\n padding += Patch_Margin;\n\n \/\/ Add the prefix.\n string prefix = text.JavaSubstring(Math.Max(0, patch.start2 - padding),\n patch.start2);\n if (prefix.Length != 0)\n {\n patch.diffs.Insert(0, new Diff(Operation.EQUAL, prefix));\n }\n \/\/ Add the suffix.\n string suffix = text.JavaSubstring(patch.start2 + patch.length1,\n Math.Min(text.Length, patch.start2 + patch.length1 + padding));\n if (suffix.Length != 0)\n {\n patch.diffs.Add(new Diff(Operation.EQUAL, suffix));\n }\n\n \/\/ Roll back the start points.\n patch.start1 -= prefix.Length;\n patch.start2 -= prefix.Length;\n \/\/ Extend the lengths.\n patch.length1 += prefix.Length + suffix.Length;\n patch.length2 += prefix.Length + suffix.Length;\n }\n\n \/**\n * Compute a list of patches to turn text1 into text2.\n * A set of diffs will be computed.\n * @param text1 Old text.\n * @param text2 New text.\n * @return List of Patch objects.\n *\/\n public List<Patch> patch_make(string text1, string text2)\n {\n \/\/ Check for null inputs not needed since null can't be passed in C#.\n \/\/ No diffs provided, compute our own.\n List<Diff> diffs = diff_main(text1, text2, true);\n if (diffs.Count > 2)\n {\n diff_cleanupSemantic(diffs);\n diff_cleanupEfficiency(diffs);\n }\n return patch_make(text1, diffs);\n }\n\n \/**\n * Compute a list of patches to turn text1 into text2.\n * text1 will be derived from the provided diffs.\n * @param diffs Array of Diff objects for text1 to text2.\n * @return List of Patch objects.\n *\/\n public List<Patch> patch_make(List<Diff> diffs)\n {\n \/\/ Check for null inputs not needed since null can't be passed in C#.\n \/\/ No origin string provided, compute our own.\n string text1 = diff_text1(diffs);\n return patch_make(text1, diffs);\n }\n\n \/**\n * Compute a list of patches to turn text1 into text2.\n * text2 is ignored, diffs are the delta between text1 and text2.\n * @param text1 Old text\n * @param text2 Ignored.\n * @param diffs Array of Diff objects for text1 to text2.\n * @return List of Patch objects.\n * @deprecated Prefer patch_make(string text1, List<Diff> diffs).\n *\/\n public List<Patch> patch_make(string text1, string text2,\n List<Diff> diffs)\n {\n return patch_make(text1, diffs);\n }\n\n \/**\n * Compute a list of patches to turn text1 into text2.\n * text2 is not provided, diffs are the delta between text1 and text2.\n * @param text1 Old text.\n * @param diffs Array of Diff objects for text1 to text2.\n * @return List of Patch objects.\n *\/\n public List<Patch> patch_make(string text1, List<Diff> diffs)\n {\n \/\/ Check for null inputs not needed since null can't be passed in C#.\n List<Patch> patches = new List<Patch>();\n if (diffs.Count == 0)\n {\n return patches; \/\/ Get rid of the null case.\n }\n Patch patch = new Patch();\n int char_count1 = 0; \/\/ Number of characters into the text1 string.\n int char_count2 = 0; \/\/ Number of characters into the text2 string.\n \/\/ Start with text1 (prepatch_text) and apply the diffs until we arrive at\n \/\/ text2 (postpatch_text). We recreate the patches one by one to determine\n \/\/ context info.\n string prepatch_text = text1;\n string postpatch_text = text1;\n foreach (Diff aDiff in diffs)\n {\n if (patch.diffs.Count == 0 && aDiff.operation != Operation.EQUAL)\n {\n \/\/ A new patch starts here.\n patch.start1 = char_count1;\n patch.start2 = char_count2;\n }\n\n switch (aDiff.operation)\n {\n case Operation.INSERT:\n patch.diffs.Add(aDiff);\n patch.length2 += aDiff.text.Length;\n postpatch_text = postpatch_text.Insert(char_count2, aDiff.text);\n break;\n case Operation.DELETE:\n patch.length1 += aDiff.text.Length;\n patch.diffs.Add(aDiff);\n postpatch_text = postpatch_text.Remove(char_count2,\n aDiff.text.Length);\n break;\n case Operation.EQUAL:\n if (aDiff.text.Length <= 2 * Patch_Margin\n && patch.diffs.Count() != 0 && aDiff != diffs.Last())\n {\n \/\/ Small equality inside a patch.\n patch.diffs.Add(aDiff);\n patch.length1 += aDiff.text.Length;\n patch.length2 += aDiff.text.Length;\n }\n\n if (aDiff.text.Length >= 2 * Patch_Margin)\n {\n \/\/ Time for a new patch.\n if (patch.diffs.Count != 0)\n {\n patch_addContext(patch, prepatch_text);\n patches.Add(patch);\n patch = new Patch();\n \/\/ Unlike Unidiff, our patch lists have a rolling context.\n \/\/ https:\/\/github.com\/google\/diff-match-patch\/wiki\/Unidiff\n \/\/ Update prepatch text & pos to reflect the application of the\n \/\/ just completed patch.\n prepatch_text = postpatch_text;\n char_count1 = char_count2;\n }\n }\n break;\n }\n\n \/\/ Update the current character count.\n if (aDiff.operation != Operation.INSERT)\n {\n char_count1 += aDiff.text.Length;\n }\n if (aDiff.operation != Operation.DELETE)\n {\n char_count2 += aDiff.text.Length;\n }\n }\n \/\/ Pick up the leftover patch if not empty.\n if (patch.diffs.Count != 0)\n {\n patch_addContext(patch, prepatch_text);\n patches.Add(patch);\n }\n\n return patches;\n }\n\n \/**\n * Given an array of patches, return another array that is identical.\n * @param patches Array of Patch objects.\n * @return Array of Patch objects.\n *\/\n public List<Patch> patch_deepCopy(List<Patch> patches)\n {\n List<Patch> patchesCopy = new List<Patch>();\n foreach (Patch aPatch in patches)\n {\n Patch patchCopy = new Patch();\n foreach (Diff aDiff in aPatch.diffs)\n {\n Diff diffCopy = new Diff(aDiff.operation, aDiff.text);\n patchCopy.diffs.Add(diffCopy);\n }\n patchCopy.start1 = aPatch.start1;\n patchCopy.start2 = aPatch.start2;\n patchCopy.length1 = aPatch.length1;\n patchCopy.length2 = aPatch.length2;\n patchesCopy.Add(patchCopy);\n }\n return patchesCopy;\n }\n\n \/**\n * Merge a set of patches onto the text. Return a patched text, as well\n * as an array of true\/false values indicating which patches were applied.\n * @param patches Array of Patch objects\n * @param text Old text.\n * @return Two element Object array, containing the new text and an array of\n * bool values.\n *\/\n public Object[] patch_apply(List<Patch> patches, string text)\n {\n if (patches.Count == 0)\n {\n return new Object[] { text, new bool[0] };\n }\n\n \/\/ Deep copy the patches so that no changes are made to originals.\n patches = patch_deepCopy(patches);\n\n string nullPadding = this.patch_addPadding(patches);\n text = nullPadding + text + nullPadding;\n patch_splitMax(patches);\n\n int x = 0;\n \/\/ delta keeps track of the offset between the expected and actual\n \/\/ location of the previous patch. If there are patches expected at\n \/\/ positions 10 and 20, but the first patch was found at 12, delta is 2\n \/\/ and the second patch has an effective expected position of 22.\n int delta = 0;\n bool[] results = new bool[patches.Count];\n foreach (Patch aPatch in patches)\n {\n int expected_loc = aPatch.start2 + delta;\n string text1 = diff_text1(aPatch.diffs);\n int start_loc;\n int end_loc = -1;\n if (text1.Length > this.Match_MaxBits)\n {\n \/\/ patch_splitMax will only provide an oversized pattern\n \/\/ in the case of a monster delete.\n start_loc = match_main(text,\n text1.Substring(0, this.Match_MaxBits), expected_loc);\n if (start_loc != -1)\n {\n end_loc = match_main(text,\n text1.Substring(text1.Length - this.Match_MaxBits),\n expected_loc + text1.Length - this.Match_MaxBits);\n if (end_loc == -1 || start_loc >= end_loc)\n {\n \/\/ Can't find valid trailing context. Drop this patch.\n start_loc = -1;\n }\n }\n }\n else\n {\n start_loc = this.match_main(text, text1, expected_loc);\n }\n if (start_loc == -1)\n {\n \/\/ No match found. :(\n results[x] = false;\n \/\/ Subtract the delta for this failed patch from subsequent patches.\n delta -= aPatch.length2 - aPatch.length1;\n }\n else\n {\n \/\/ Found a match. :)\n results[x] = true;\n delta = start_loc - expected_loc;\n string text2;\n if (end_loc == -1)\n {\n text2 = text.JavaSubstring(start_loc,\n Math.Min(start_loc + text1.Length, text.Length));\n }\n else\n {\n text2 = text.JavaSubstring(start_loc,\n Math.Min(end_loc + this.Match_MaxBits, text.Length));\n }\n if (text1 == text2)\n {\n \/\/ Perfect match, just shove the Replacement text in.\n text = text.Substring(0, start_loc) + diff_text2(aPatch.diffs)\n + text.Substring(start_loc + text1.Length);\n }\n else\n {\n \/\/ Imperfect match. Run a diff to get a framework of equivalent\n \/\/ indices.\n List<Diff> diffs = diff_main(text1, text2, false);\n if (text1.Length > this.Match_MaxBits\n && this.diff_levenshtein(diffs) \/ (float)text1.Length\n > this.Patch_DeleteThreshold)\n {\n \/\/ The end points match, but the content is unacceptably bad.\n results[x] = false;\n }\n else\n {\n diff_cleanupSemanticLossless(diffs);\n int index1 = 0;\n foreach (Diff aDiff in aPatch.diffs)\n {\n if (aDiff.operation != Operation.EQUAL)\n {\n int index2 = diff_xIndex(diffs, index1);\n if (aDiff.operation == Operation.INSERT)\n {\n \/\/ Insertion\n text = text.Insert(start_loc + index2, aDiff.text);\n }\n else if (aDiff.operation == Operation.DELETE)\n {\n \/\/ Deletion\n text = text.Remove(start_loc + index2, diff_xIndex(diffs,\n index1 + aDiff.text.Length) - index2);\n }\n }\n if (aDiff.operation != Operation.DELETE)\n {\n index1 += aDiff.text.Length;\n }\n }\n }\n }\n }\n x++;\n }\n \/\/ Strip the padding off.\n text = text.Substring(nullPadding.Length, text.Length\n - 2 * nullPadding.Length);\n return new Object[] { text, results };\n }\n\n \/**\n * Add some padding on text start and end so that edges can match something.\n * Intended to be called only from within patch_apply.\n * @param patches Array of Patch objects.\n * @return The padding string added to each side.\n *\/\n public string patch_addPadding(List<Patch> patches)\n {\n short paddingLength = this.Patch_Margin;\n string nullPadding = string.Empty;\n for (short x = 1; x <= paddingLength; x++)\n {\n nullPadding += (char)x;\n }\n\n \/\/ Bump all the patches forward.\n foreach (Patch aPatch in patches)\n {\n aPatch.start1 += paddingLength;\n aPatch.start2 += paddingLength;\n }\n\n \/\/ Add some padding on start of first diff.\n Patch patch = patches.First();\n List<Diff> diffs = patch.diffs;\n if (diffs.Count == 0 || diffs.First().operation != Operation.EQUAL)\n {\n \/\/ Add nullPadding equality.\n diffs.Insert(0, new Diff(Operation.EQUAL, nullPadding));\n patch.start1 -= paddingLength; \/\/ Should be 0.\n patch.start2 -= paddingLength; \/\/ Should be 0.\n patch.length1 += paddingLength;\n patch.length2 += paddingLength;\n }\n else if (paddingLength > diffs.First().text.Length)\n {\n \/\/ Grow first equality.\n Diff firstDiff = diffs.First();\n int extraLength = paddingLength - firstDiff.text.Length;\n firstDiff.text = nullPadding.Substring(firstDiff.text.Length)\n + firstDiff.text;\n patch.start1 -= extraLength;\n patch.start2 -= extraLength;\n patch.length1 += extraLength;\n patch.length2 += extraLength;\n }\n\n \/\/ Add some padding on end of last diff.\n patch = patches.Last();\n diffs = patch.diffs;\n if (diffs.Count == 0 || diffs.Last().operation != Operation.EQUAL)\n {\n \/\/ Add nullPadding equality.\n diffs.Add(new Diff(Operation.EQUAL, nullPadding));\n patch.length1 += paddingLength;\n patch.length2 += paddingLength;\n }\n else if (paddingLength > diffs.Last().text.Length)\n {\n \/\/ Grow last equality.\n Diff lastDiff = diffs.Last();\n int extraLength = paddingLength - lastDiff.text.Length;\n lastDiff.text += nullPadding.Substring(0, extraLength);\n patch.length1 += extraLength;\n patch.length2 += extraLength;\n }\n\n return nullPadding;\n }\n\n \/**\n * Look through the patches and break up any which are longer than the\n * maximum limit of the match algorithm.\n * Intended to be called only from within patch_apply.\n * @param patches List of Patch objects.\n *\/\n public void patch_splitMax(List<Patch> patches)\n {\n short patch_size = this.Match_MaxBits;\n for (int x = 0; x < patches.Count; x++)\n {\n if (patches[x].length1 <= patch_size)\n {\n continue;\n }\n Patch bigpatch = patches[x];\n \/\/ Remove the big old patch.\n patches.Splice(x--, 1);\n int start1 = bigpatch.start1;\n int start2 = bigpatch.start2;\n string precontext = string.Empty;\n while (bigpatch.diffs.Count != 0)\n {\n \/\/ Create one of several smaller patches.\n Patch patch = new Patch();\n bool empty = true;\n patch.start1 = start1 - precontext.Length;\n patch.start2 = start2 - precontext.Length;\n if (precontext.Length != 0)\n {\n patch.length1 = patch.length2 = precontext.Length;\n patch.diffs.Add(new Diff(Operation.EQUAL, precontext));\n }\n while (bigpatch.diffs.Count != 0\n && patch.length1 < patch_size - this.Patch_Margin)\n {\n Operation diff_type = bigpatch.diffs[0].operation;\n string diff_text = bigpatch.diffs[0].text;\n if (diff_type == Operation.INSERT)\n {\n \/\/ Insertions are harmless.\n patch.length2 += diff_text.Length;\n start2 += diff_text.Length;\n patch.diffs.Add(bigpatch.diffs.First());\n bigpatch.diffs.RemoveAt(0);\n empty = false;\n }\n else if (diff_type == Operation.DELETE && patch.diffs.Count == 1\n && patch.diffs.First().operation == Operation.EQUAL\n && diff_text.Length > 2 * patch_size)\n {\n \/\/ This is a large deletion. Let it pass in one chunk.\n patch.length1 += diff_text.Length;\n start1 += diff_text.Length;\n empty = false;\n patch.diffs.Add(new Diff(diff_type, diff_text));\n bigpatch.diffs.RemoveAt(0);\n }\n else\n {\n \/\/ Deletion or equality. Only take as much as we can stomach.\n diff_text = diff_text.Substring(0, Math.Min(diff_text.Length,\n patch_size - patch.length1 - Patch_Margin));\n patch.length1 += diff_text.Length;\n start1 += diff_text.Length;\n if (diff_type == Operation.EQUAL)\n {\n patch.length2 += diff_text.Length;\n start2 += diff_text.Length;\n }\n else\n {\n empty = false;\n }\n patch.diffs.Add(new Diff(diff_type, diff_text));\n if (diff_text == bigpatch.diffs[0].text)\n {\n bigpatch.diffs.RemoveAt(0);\n }\n else\n {\n bigpatch.diffs[0].text =\n bigpatch.diffs[0].text.Substring(diff_text.Length);\n }\n }\n }\n \/\/ Compute the head context for the next patch.\n precontext = this.diff_text2(patch.diffs);\n precontext = precontext.Substring(Math.Max(0,\n precontext.Length - this.Patch_Margin));\n\n string postcontext = null;\n \/\/ Append the end context for this patch.\n if (diff_text1(bigpatch.diffs).Length > Patch_Margin)\n {\n postcontext = diff_text1(bigpatch.diffs)\n .Substring(0, Patch_Margin);\n }\n else\n {\n postcontext = diff_text1(bigpatch.diffs);\n }\n\n if (postcontext.Length != 0)\n {\n patch.length1 += postcontext.Length;\n patch.length2 += postcontext.Length;\n if (patch.diffs.Count != 0\n && patch.diffs[patch.diffs.Count - 1].operation\n == Operation.EQUAL)\n {\n patch.diffs[patch.diffs.Count - 1].text += postcontext;\n }\n else\n {\n patch.diffs.Add(new Diff(Operation.EQUAL, postcontext));\n }\n }\n if (!empty)\n {\n patches.Splice(++x, 0, patch);\n }\n }\n }\n }\n\n \/**\n * Take a list of patches and return a textual representation.\n * @param patches List of Patch objects.\n * @return Text representation of patches.\n *\/\n public string patch_toText(List<Patch> patches)\n {\n StringBuilder text = new StringBuilder();\n foreach (Patch aPatch in patches)\n {\n text.Append(aPatch);\n }\n return text.ToString();\n }\n\n \/**\n * Parse a textual representation of patches and return a List of Patch\n * objects.\n * @param textline Text representation of patches.\n * @return List of Patch objects.\n * @throws ArgumentException If invalid input.\n *\/\n public List<Patch> patch_fromText(string textline)\n {\n List<Patch> patches = new List<Patch>();\n if (textline.Length == 0)\n {\n return patches;\n }\n string[] text = textline.Split('\\n');\n int textPointer = 0;\n Patch patch;\n Regex patchHeader\n = new Regex(\"^@@ -(\\\\d+),?(\\\\d*) \\\\+(\\\\d+),?(\\\\d*) @@$\");\n Match m;\n char sign;\n string line;\n while (textPointer < text.Length)\n {\n m = patchHeader.Match(text[textPointer]);\n if (!m.Success)\n {\n throw new ArgumentException(\"Invalid patch string: \"\n + text[textPointer]);\n }\n patch = new Patch();\n patches.Add(patch);\n patch.start1 = Convert.ToInt32(m.Groups[1].Value);\n if (m.Groups[2].Length == 0)\n {\n patch.start1--;\n patch.length1 = 1;\n }\n else if (m.Groups[2].Value == \"0\")\n {\n patch.length1 = 0;\n }\n else\n {\n patch.start1--;\n patch.length1 = Convert.ToInt32(m.Groups[2].Value);\n }\n\n patch.start2 = Convert.ToInt32(m.Groups[3].Value);\n if (m.Groups[4].Length == 0)\n {\n patch.start2--;\n patch.length2 = 1;\n }\n else if (m.Groups[4].Value == \"0\")\n {\n patch.length2 = 0;\n }\n else\n {\n patch.start2--;\n patch.length2 = Convert.ToInt32(m.Groups[4].Value);\n }\n textPointer++;\n\n while (textPointer < text.Length)\n {\n try\n {\n sign = text[textPointer][0];\n }\n catch (IndexOutOfRangeException)\n {\n \/\/ Blank line? Whatever.\n textPointer++;\n continue;\n }\n line = text[textPointer].Substring(1);\n line = line.Replace(\"+\", \"%2b\");\n line = HttpUtility.UrlDecode(line);\n if (sign == '-')\n {\n \/\/ Deletion.\n patch.diffs.Add(new Diff(Operation.DELETE, line));\n }\n else if (sign == '+')\n {\n \/\/ Insertion.\n patch.diffs.Add(new Diff(Operation.INSERT, line));\n }\n else if (sign == ' ')\n {\n \/\/ Minor equality.\n patch.diffs.Add(new Diff(Operation.EQUAL, line));\n }\n else if (sign == '@')\n {\n \/\/ Start of next patch.\n break;\n }\n else\n {\n \/\/ WTF?\n throw new ArgumentException(\n \"Invalid patch mode '\" + sign + \"' in: \" + line);\n }\n textPointer++;\n }\n }\n return patches;\n }\n\n \/**\n * Encodes a string with URI-style % escaping.\n * Compatible with JavaScript's encodeURI function.\n *\n * @param str The string to encode.\n * @return The encoded string.\n *\/\n public static string encodeURI(string str)\n {\n \/\/ C# is overzealous in the replacements. Walk back on a few.\n return new StringBuilder(HttpUtility.UrlEncode(str))\n .Replace('+', ' ').Replace(\"%20\", \" \").Replace(\"%21\", \"!\")\n .Replace(\"%2a\", \"*\").Replace(\"%27\", \"'\").Replace(\"%28\", \"(\")\n .Replace(\"%29\", \")\").Replace(\"%3b\", \";\").Replace(\"%2f\", \"\/\")\n .Replace(\"%3f\", \"?\").Replace(\"%3a\", \":\").Replace(\"%40\", \"@\")\n .Replace(\"%26\", \"&\").Replace(\"%3d\", \"=\").Replace(\"%2b\", \"+\")\n .Replace(\"%24\", \"$\").Replace(\"%2c\", \",\").Replace(\"%23\", \"#\")\n .Replace(\"%7e\", \"~\")\n .ToString();\n }\n }\n}<\/code><\/pre>\n\n\n\n\u6d4b\u8bd5\u4ee3\u7801\uff1a<\/p>\n\n\n\n
\/\/ Copyright 2010 Google Inc.\n\/\/ All Right Reserved.\n\n\/*\n * To compile with Mono:\n * mcs Speedtest.cs ..\/DiffMatchPatch.cs\n * To run with Mono:\n * mono Speedtest.exe\n*\/\n\nusing DiffMatchPatch;\nusing System;\nusing System.Collections.Generic;\n\npublic class Speedtest\n{\n public static void Main(string[] args)\n {\n string text1 = System.IO.File.ReadAllText(\"Speedtest1.txt\");\n string text2 = System.IO.File.ReadAllText(\"Speedtest2.txt\");\n\n diff_match_patch dmp = new diff_match_patch();\n dmp.Diff_Timeout = 0;\n\n \/\/ Execute one reverse diff as a warmup.\n var d1 = dmp.diff_main(text2, text1);\n GC.Collect();\n GC.WaitForPendingFinalizers();\n\n DateTime ms_start = DateTime.Now;\n var d2 = dmp.diff_main(text1, text2);\n DateTime ms_end = DateTime.Now;\n\n Console.WriteLine(\"Elapsed time: \" + (ms_end - ms_start));\n }\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u5b9e\u73b0\u4e00\u4e2a\u50cfBeyond Compare\u7684\u5de5\u5177\uff0c\u5fc5\u7136\u9700\u8981\u4e00\u4e2a\u9ad8\u6027\u80fd\u7684\u6587\u672c\u5bf9\u6bd4\u7b97\u6cd5\uff0cGoogle\u5df2\u7ecf\u5b9e\u73b0\u4e86\u8fd9\u4e2a\u5e93\uff0c […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=\/wp\/v2\/posts\/4414"}],"collection":[{"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4414"}],"version-history":[{"count":4,"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=\/wp\/v2\/posts\/4414\/revisions"}],"predecessor-version":[{"id":4418,"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=\/wp\/v2\/posts\/4414\/revisions\/4418"}],"wp:attachment":[{"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4414"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4414"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4414"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}