Difference.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
 
namespace Waher.Runtime.Text
{
    public static class Difference
    {
        public static EditScript<T> Analyze<T>(T[] S1, T[] S2)
        {
            int c1 = S1.Length;
            int c2 = S2.Length;
            int c1p = c1 + 1;
            int c2p = c2 + 1;
            BitArray Processed = new BitArray(c1p * c2p);
            LinkedList<State<T>> Current = new LinkedList<State<T>>();
            LinkedList<State<T>> Next = new LinkedList<State<T>>();
            LinkedList<State<T>> NextNext = new LinkedList<State<T>>();
            LinkedList<State<T>> Temp;
            State<T> P, Q;
            bool b1, b2;
            int i;
 
            P = new State<T>()
            {
                Op = EditOperation.Keep,
                i1 = 0,
                i2 = 0,
                Prev = null
            };
 
            while (true)
            {
                if (P.i1 == c1 && P.i2 == c2)
                    break;
 
                i = P.i1 + P.i2 * c1p;
                if (!Processed[i])
                {
                    Processed[i] = true;
 
                    if (b2 = (P.i2 < c2))
                    {
                        if (!Processed[i + c1p])
                        {
                            Q = new State<T>()
                            {
                                Op = EditOperation.Insert,
                                i1 = P.i1,
                                i2 = P.i2 + 1,
                                Prev = P
                            };
 
                            if (P.Op == EditOperation.Insert)
                                Next.AddLast(Q);
                            else
                                NextNext.AddLast(Q);
                        }
                    }
 
                    if (b1 = (P.i1 < c1))
                    {
                        if (!Processed[i + 1])
                        {
                            Q = new State<T>()
                            {
                                Op = EditOperation.Delete,
                                i1 = P.i1 + 1,
                                i2 = P.i2,
                                Prev = P
                            };
 
                            if (P.Op == EditOperation.Delete)
                                Next.AddLast(Q);
                            else
                                NextNext.AddLast(Q);
                        }
                    }
 
                    if (b1 && b2 && S1[P.i1].Equals(S2[P.i2]))
                    {
                        if (!Processed[i + 1 + c1p])
                        {
                            Q = new State<T>()
                            {
                                Op = EditOperation.Keep,
                                i1 = P.i1 + 1,
                                i2 = P.i2 + 1,
                                Prev = P
                            };
 
                            Current.AddLast(Q);
 
                            if (Q.i1 == c1 && Q.i2 == c2)
                            {
                                P = Q;
                                break;
                            }
                        }
                    }
                }
 
                if (Current.First is null)
                {
                    Temp = Current;
 
                    if (Next.First is null)
                        Current = NextNext;
                    else
                    {
                        Current = Next;
                        Next = NextNext;
                    }
 
                    NextNext = Temp;
                }
 
                P = Current.Last.Value;
                Current.RemoveLast();
            }
 
            LinkedList<T> SameOp = new LinkedList<T>();
            LinkedList<Step<T>> Steps = new LinkedList<Step<T>>();
            EditOperation Op = P.Op;
            State<T> First = P;
            T[] Symbols;
 
            c1 = 0;
            c2 = 0;
 
            while (!((Q = P.Prev) is null))
            {
                if (P.Op != Op)
                {
                    Symbols = new T[c1];
                    SameOp.CopyTo(Symbols, 0);
                    Steps.AddFirst(new Step<T>(Symbols, First.i1, First.i2, Op));
 
                    SameOp.Clear();
                    c1 = 0;
                    c2++;
                    Op = P.Op;
                }
 
                switch (Op)
                {
                    case EditOperation.Keep:
                    case EditOperation.Delete:
                        SameOp.AddFirst(S1[P.i1 - 1]);
                        break;
 
                    case EditOperation.Insert:
                        SameOp.AddFirst(S2[P.i2 - 1]);
                        break;
                }
 
                c1++;
                First = P;
                P = Q;
            }
 
            Symbols = new T[c1];
            SameOp.CopyTo(Symbols, 0);
            Steps.AddFirst(new Step<T>(Symbols, First.i1, First.i2, Op));
            c2++;
 
            Step<T>[] Result = new Step<T>[c2];
            Steps.CopyTo(Result, 0);
 
            return new EditScript<T>(S1, S2, Result);
        }
 
        private class State<T>
        {
            public EditOperation Op;
            public int i1;
            public int i2;
            public State<T> Prev;
        }
 
        public static EditScript<char> AnalyzeStrings(string s1, string s2)
        {
            return Analyze(s1.ToCharArray(), s2.ToCharArray());
        }
 
        public static EditScript<string> AnalyzeRows(string Text1, string Text2)
        {
            return Analyze(ExtractRows(Text1), ExtractRows(Text2));
        }
 
        public static string[] ExtractRows(string Text)
        {
            return Text.Replace("\r\n", "\n").Replace('\r', '\n').Split('\n');
        }
 
    }
}