Created
July 18, 2016 17:41
-
-
Save thedillonb/3f07a80535bcab48ca565e00e17ccf97 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment