Dwifft.cs

using System.Collections.Generic;
using System.Linq;
using System;
using System.Text;

public static class ArrayExtensions
{
	public static Diff<T> Diff<T>(IEnumerable<T> @this, IEnumerable<T> other)
		where T : IEquatable<T>
	{
		var v1 = @this.ToList();
		var v2 = other.ToList();
		var table = BuildTable<T>(v1, v2, v1.Count, v2.Count); 
		return DiffFromIndices<T>(table, v1, v2, v1.Count, v2.Count);
	}
	
	private static Diff<T> DiffFromIndices<T>(IList<IList<int>> table, IList<T> x, IList<T> y, int i, int j)
	{
		if (i ==0 && j == 0)
		{
			return new Diff<T>(Enumerable.Empty<DiffStep<T>>());
		}
		else if (i == 0)
		{
			return DiffFromIndices(table, x, y, i, j-1).Add(new DiffStep<T>(true, j - 1, y[j - 1]));
		}
		else if (j == 0)
		{
			return DiffFromIndices(table, x, y, i-1, j).Add(new DiffStep<T>(false, i - 1, x[i - 1]));
		}
		else if (table[i][j] == table[i][j-1])
		{
			return DiffFromIndices(table, x, y, i, j-1).Add(new DiffStep<T>(true, j - 1, y[j - 1]));
		}
		else if (table[i][j] == table[i-1][j])
		{
			return DiffFromIndices(table, x, y, i-1, j).Add(new DiffStep<T>(false, i - 1, x[i - 1]));
		}
		else
		{
			return DiffFromIndices(table, x, y, i-1, j-1);
		}
	}
	
	private static int[][] BuildTable<T>(IList<T> x, IList<T> y, int n, int m)
		where T : IEquatable<T>
	{
		var table = new int[n + 1][];
		for (var i = 0; i < table.Length; i++)
		{
			table[i] = new int[m + 1];
			for (var j = 0; j < table[i].Length; j++)
			{
				table[i][j] = 0;
			}
		}
			
			
		for (var i = 0; i <= n; i++)
		{
			for (var j = 0; j <= m; j++)
			{
				//Console.WriteLine(x[i-1] + " == " + y[j-1]);
				if (i == 0 || j == 0)
				{
					table[i][j] = 0;
				}
				else if (x[i-1].Equals(y[j-1]))
				{
					
					table[i][j] = table[i-1][j-1] + 1;
				}
				else
				{
					table[i][j] = Math.Max(table[i-1][j], table[i][j-1]);
				}
			}
		}
			
		
		foreach (var i in table)
		{
			Console.WriteLine(string.Join(",", i));
		}
		return table;
	}
}

public class Diff<T> {
	private readonly List<DiffStep<T>> _results;
	
	public Diff(IEnumerable<DiffStep<T>> results)
	{
		_results = results.ToList();
	}
	
	public IEnumerable<DiffStep<T>> Results
	{
		get { return _results; }
	}
	
	public IEnumerable<DiffStep<T>> Deletions
	{
		get { return _results.Where(x => !x.IsInsertion); }
	}
	
	public IEnumerable<DiffStep<T>> Insertions
	{
		get { return _results.Where(x => x.IsInsertion); }
	}
	
	public Diff<T> Reverse()
	{
		return new Diff<T>(_results.Select(x => new DiffStep<T>(!x.IsInsertion, x.Index, x.Value)));
	}
	
	public Diff<T> Add(DiffStep<T> diffStep)
	{
		return new Diff<T>(Results.Concat(new [] { diffStep }));
	}
	
	public override string ToString()
	{
		var sb = new StringBuilder();
		foreach (var r in _results)
		{
			sb.AppendLine(r.ToString());
		}
		return sb.ToString();
	}
}

public class DiffStep<T> {
	private readonly bool _isInsert;
	private readonly int _idx;
	private readonly T _value;
	
	public DiffStep(bool isInsert, int idx, T val)
	{
		_isInsert = isInsert;
		_idx = idx;
		_value = val;
	}

	public bool IsInsertion
	{
		get { return _isInsert;	}
	}
	
	public int Index
	{
		get { return _idx; }
	}
	
	public T Value
	{
		get { return _value; }
	}
	
	public override string ToString()
	{
		if (IsInsertion)
		{
			return "+" + Index + "@" + Value;
		}
		else	
		{
			return "-" + Index + "@" + Value;
		}
	}
}




public class Program
{
	public static void Main()
	{
		var moo = new List<int> { 1, 2, 3 };
		var cow = new List<int> { 5, 1, 2, 3 };

		Console.WriteLine(ArrayExtensions.Diff<int>(moo, cow));
					
	}
}