difftools.cs

YetAnotherForum.Net+ScrewTurnWiki中文完美汉化增强版

using System;
using System.Collections;
using System.Text;
using System.Text.RegularExpressions;
using System.Web;

namespace ScrewTurn.Wiki {

	/// <summary>
	/// Provides methods for diffing text and items.
	/// </summary>
	public static class DiffTools {

		public static string DiffRevisions(string rev1, string rev2) {
			string[] aLines = rev1.Split('\n');
			string[] bLines = rev2.Split('\n');
			Difference.Item[] f = Difference.DiffText(rev1, rev2, true, false, false);

			StringBuilder result = new StringBuilder();

			result.Append(@"<table cellpadding=""0"" cellspacing=""0"" style=""color: #000000; background-color: #FFFFFF;"">");

			int n = 0;
			for(int fdx = 0; fdx < f.Length; fdx++) {
				Difference.Item aItem = f[fdx];
				// Write unchanged lines
				while((n < aItem.StartB) && (n < bLines.Length)) {
					result.Append(WriteLine(n, "", bLines[n]));
					n++;
				}

				// Write deleted lines
				for(int m = 0; m < aItem.deletedA; m++) {
					result.Append(WriteLine(-1, "d", aLines[aItem.StartA + m]));
				}

				// Write inserted lines
				while(n < aItem.StartB + aItem.insertedB) {
					result.Append(WriteLine(n, "i", bLines[n]));
					n++;
				}
			}

			// Write the rest of unchanged lines
			while(n < bLines.Length) {
				result.Append(WriteLine(n, "", bLines[n]));
				n++;
			}

			result.Append("</table>");

			return result.ToString();
		}

		private static string WriteLine(int n, string typ, string line) {
			StringBuilder sb = new StringBuilder();
			sb.Append("<tr>");

			sb.Append(@"<td valign=""top"" width=""30"" style=""font-family: Courier New, monospace;"">");
			if(n >= 0) sb.Append(((int)(n + 1)).ToString());
			else sb.Append("&nbsp;");
			sb.Append("</td>");

			sb.Append(@"<td valign=""top"" style=""font-family: Courier New, monospace;"">");
			sb.Append(@"<div style=""");
			switch(typ) {
				case "i":
					sb.Append("background-color: #88CC33;");
					break;
				case "d":
					sb.Append("background-color: #FFDF66;");
					break;
			}
			sb.Append(@""">" + HttpContext.Current.Server.HtmlEncode(line) + "</div>");
			sb.Append("</td>");

			sb.Append("</tr>");
			return sb.ToString();
		}

	}

	/// <summary>
	/// O(ND) Difference Algorithm for C#
	/// Created by Matthias Hertel, see http://www.mathertel.de
	/// This work is licensed under a Creative Commons Attribution 2.0 Germany License.
	/// see http://creativecommons.org/licenses/by/2.0/de/
	/// </summary>
	public class Difference {

		/// <summary>details of one difference.</summary>
		public struct Item {
			/// <summary>Start Line number in Data A.</summary>
			public int StartA;
			/// <summary>Start Line number in Data B.</summary>
			public int StartB;

			/// <summary>Number of changes in Data A.</summary>
			public int deletedA;
			/// <summary>Number of changes in Data A.</summary>
			public int insertedB;
		} // Item

		/// <summary>
		/// Shortest Middle Snake Return Data
		/// </summary>
		private struct SMSRD {
			internal int x, y;
			// internal int u, v;  // 2002.09.20: no need for 2 points 
		}

		/// <summary>
		/// Find the difference in 2 texts, comparing by textlines.
		/// </summary>
		/// <param name="TextA">A-version of the text (usualy the old one)</param>
		/// <param name="TextB">B-version of the text (usualy the new one)</param>
		/// <returns>Returns a array of Items that describe the differences.</returns>
		public Item[] DiffText(string TextA, string TextB) {
			return (DiffText(TextA, TextB, false, false, false));
		} // DiffText


		/// <summary>
		/// Find the difference in 2 text documents, comparing by textlines.
		/// The algorithm itself is comparing 2 arrays of numbers so when comparing 2 text documents
		/// each line is converted into a (hash) number. This hash-value is computed by storing all
		/// textlines into a common hashtable so i can find dublicates in there, and generating a 
		/// new number each time a new textline is inserted.
		/// </summary>
		/// <param name="TextA">A-version of the text (usualy the old one)</param>
		/// <param name="TextB">B-version of the text (usualy the new one)</param>
		/// <param name="trimSpace">When set to true, all leading and trailing whitespace characters are stripped out before the comparation is done.</param>
		/// <param name="ignoreSpace">When set to true, all whitespace characters are converted to a single space character before the comparation is done.</param>
		/// <param name="ignoreCase">When set to true, all characters are converted to their lowercase equivivalence before the comparation is done.</param>
		/// <returns>Returns a array of Items that describe the differences.</returns>
		public static Item[] DiffText(string TextA, string TextB, bool trimSpace, bool ignoreSpace, bool ignoreCase) {
			// prepare the input-text and convert to comparable numbers.
			Hashtable h = new Hashtable(TextA.Length + TextB.Length);

			// The A-Version of the data (original data) to be compared.
			DiffData DataA = new DiffData(DiffCodes(TextA, h, trimSpace, ignoreSpace, ignoreCase));

			// The B-Version of the data (modified data) to be compared.
			DiffData DataB = new DiffData(DiffCodes(TextB, h, trimSpace, ignoreSpace, ignoreCase));

			h = null; // free up hashtable memory (maybe)

			LCS(DataA, 0, DataA.Length, DataB, 0, DataB.Length);
			return CreateDiffs(DataA, DataB);
		} // DiffText


		/// <summary>
		/// Find the difference in 2 arrays of integers.
		/// </summary>
		/// <param name="ArrayA">A-version of the numbers (usualy the old one)</param>
		/// <param name="ArrayB">B-version of the numbers (usualy the new one)</param>
		/// <returns>Returns a array of Items that describe the differences.</returns>
		public static Item[] DiffInt(int[] ArrayA, int[] ArrayB) {
			// The A-Version of the data (original data) to be compared.
			DiffData DataA = new DiffData(ArrayA);

			// The B-Version of the data (modified data) to be compared.
			DiffData DataB = new DiffData(ArrayB);

			LCS(DataA, 0, DataA.Length, DataB, 0, DataB.Length);
			return CreateDiffs(DataA, DataB);
		} // Diff


		/// <summary>
		/// This function converts all textlines of the text into unique numbers for every unique textline
		/// so further work can work only with simple numbers.
		/// </summary>
		/// <param name="aText">the input text</param>
		/// <param name="h">This extern initialized hashtable is used for storing all ever used textlines.</param>
		/// <param name="trimSpace">ignore leading and trailing space characters</param>
		/// <returns>a array of integers.</returns>
		private static int[] DiffCodes(string aText, Hashtable h, bool trimSpace, bool ignoreSpace, bool ignoreCase) {
			// get all codes of the text
			string[] Lines;
			int[] Codes;
			int lastUsedCode = h.Count;
			object aCode;
			string s;

			// strip off all cr, only use lf as textline separator.
			aText = aText.Replace("\r", "");
			Lines = aText.Split('\n');

			Codes = new int[Lines.Length];

			for(int i = 0; i < Lines.Length; ++i) {
				s = Lines[i];
				if(trimSpace)
					s = s.Trim();

				if(ignoreSpace) {
					s = Regex.Replace(s, "\\s+", " ");            // TODO: optimization: faster blank removal.
				}

				if(ignoreCase)
					s = s.ToLower();

				aCode = h[s];
				if(aCode == null) {
					lastUsedCode++;
					h[s] = lastUsedCode;
					Codes[i] = lastUsedCode;
				}
				else {
					Codes[i] = (int)aCode;
				} // if
			} // for
			return (Codes);
		} // DiffCodes


		/// <summary>
		/// This is the algorithm to find the Shortest Middle Snake (SMS).
		/// </summary>
		/// <param name="DataA">sequence A</param>
		/// <param name="LowerA">lower bound of the actual range in DataA</param>
		/// <param name="UpperA">upper bound of the actual range in DataA (exclusive)</param>
		/// <param name="DataB">sequence B</param>
		/// <param name="LowerB">lower bound of the actual range in DataB</param>
		/// <param name="UpperB">upper bound of the actual range in DataB (exclusive)</param>
		/// <returns>a MiddleSnakeData record containing x,y and u,v</returns>
		private static SMSRD SMS(DiffData DataA, int LowerA, int UpperA, DiffData DataB, int LowerB, int UpperB) {
			SMSRD ret;
			int MAX = DataA.Length + DataB.Length + 1;

			int DownK = LowerA - LowerB; // the k-line to start the forward search
			int UpK = UpperA - UpperB; // the k-line to start the reverse search