Difference.cs

using System;
using Waher.Runtime.Collections;
 
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;
 
            if (c1 == 0 && c2 == 0)
                return new EditScript<T>(S1, S2, Array.Empty<Step<T>>());
 
            int StartOffset = 0;
 
            while (StartOffset < c1 && StartOffset < c2 &&
                S1[StartOffset].Equals(S2[StartOffset]))
            {
                StartOffset++;
            }
 
            int EndOffset1 = c1;
            int EndOffset2 = c2;
 
            while (EndOffset1 > StartOffset && EndOffset2 > StartOffset &&
                S1[EndOffset1 - 1].Equals(S2[EndOffset2 - 1]))
            {
                EndOffset1--;
                EndOffset2--;
            }
 
            int c1p = EndOffset1 - StartOffset + 1;
            int c2p = EndOffset2 - StartOffset + 1;
            long NrBits = ((long)c1p) * c2p;
            long NrBytes = (NrBits + 7) >> 3;
 
            if (NrBytes > int.MaxValue)
                throw new OutOfMemoryException("Unable to allocate enough memory to process the difference between the two sequences.");
 
            byte[] Processed = new byte[NrBytes];
 
            ChunkedList<State<T>> Current = new ChunkedList<State<T>>();
            ChunkedList<State<T>> Next = new ChunkedList<State<T>>();
            ChunkedList<State<T>> NextNext = new ChunkedList<State<T>>();
            ChunkedList<State<T>> Temp;
            State<T> P, Q;
            bool b1, b2;
            int i, j, iByte;
            byte iBit;
 
            P = null;
            for (i = 0; i <= StartOffset; i++)
            {
                P = new State<T>()
                {
                    Op = EditOperation.Keep,
                    i1 = i,
                    i2 = i,
                    Prev = P
                };
            }
 
            while (true)
            {
                if (P.i1 == EndOffset1 && P.i2 == EndOffset2)
                    break;
 
                i = P.i1 - StartOffset + (P.i2 - StartOffset) * c1p;
                iByte = i >> 3;
                iBit = (byte)(1 << (i & 7));
 
                if ((Processed[iByte] & iBit) == 0)
                {
                    Processed[iByte] |= iBit;
 
                    if (b2 = P.i2 < EndOffset2)
                    {
                        j = i + c1p;
                        if ((Processed[j >> 3] & (byte)(1 << (j & 7))) == 0)
                        {
                            Q = new State<T>()
                            {
                                Op = EditOperation.Insert,
                                i1 = P.i1,
                                i2 = P.i2 + 1,
                                Prev = P
                            };
 
                            if (P.Op == EditOperation.Insert)
                                Next.AddLastItem(Q);
                            else
                                NextNext.AddLastItem(Q);
                        }
                    }
 
                    if (b1 = P.i1 < EndOffset1)
                    {
                        j = i + 1;
                        if ((Processed[j >> 3] & (byte)(1 << (j & 7))) == 0)
                        {
                            Q = new State<T>()
                            {
                                Op = EditOperation.Delete,
                                i1 = P.i1 + 1,
                                i2 = P.i2,
                                Prev = P
                            };
 
                            if (P.Op == EditOperation.Delete)
                                Next.AddLastItem(Q);
                            else
                                NextNext.AddLastItem(Q);
                        }
                    }
 
                    if (b1 && b2 && S1[P.i1].Equals(S2[P.i2]))
                    {
                        j = i + 1 + c1p;
                        if ((Processed[j >> 3] & (byte)(1 << (j & 7))) == 0)
                        {
                            Q = new State<T>()
                            {
                                Op = EditOperation.Keep,
                                i1 = P.i1 + 1,
                                i2 = P.i2 + 1,
                                Prev = P
                            };
 
                            Current.AddLastItem(Q);
 
                            if (Q.i1 == EndOffset1 && Q.i2 == EndOffset2)
                            {
                                P = Q;
                                break;
                            }
                        }
                    }
                }
 
                if (!Current.HasFirstItem)
                {
                    Temp = Current;
 
                    if (!Next.HasFirstItem)
                        Current = NextNext;
                    else
                    {
                        Current = Next;
                        Next = NextNext;
                    }
 
                    NextNext = Temp;
                }
 
                P = Current.RemoveLast();
            }
 
            while (EndOffset1 < c1 && EndOffset2 < c2)
            {
                P = new State<T>()
                {
                    Op = EditOperation.Keep,
                    i1 = ++EndOffset1,
                    i2 = ++EndOffset2,
                    Prev = P
                };
            }
 
            State<T> Loop = P;
            int NrSteps = 0;
 
            while (!(Loop.Prev is null))
            {
                NrSteps++;
                Loop = Loop.Prev;
            }
 
            State<T>[] Steps = new State<T>[NrSteps];
            for (i = NrSteps, Loop = P; i > 0; Loop = Loop.Prev)
                Steps[--i] = Loop;
 
            ChunkedList<T> Elements = new ChunkedList<T>();
            ChunkedList<Step<T>> Operations = new ChunkedList<Step<T>>();
            EditOperation Op;
 
            Q = Steps[0];
            Op = Q.Op;
 
            for (i = 0; i < NrSteps; i++)
            {
                P = Steps[i];
                if (P.Op != Op)
                {
                    Operations.Add(new Step<T>(Elements.ToArray(), Q.i1, Q.i2, Op));
                    Q = P;
                    Op = P.Op;
                    Elements.Clear();
                }
 
                if (Op == EditOperation.Insert)
                    Elements.Add(S2[P.i2 - 1]);
                else
                    Elements.Add(S1[P.i1 - 1]);
            }
 
            Operations.Add(new Step<T>(Elements.ToArray(), Q.i1, Q.i2, Op));
 
            return new EditScript<T>(S1, S2, Operations.ToArray());
        }
 
        private class State<T>
        {
            public EditOperation Op;
            public int i1;
            public int i2;
            public State<T> Prev;
 
            public override string ToString()
            {
                return this.Op.ToString() + " " + this.i1.ToString() + "," + this.i2.ToString();
            }
        }
 
        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');
        }
 
    }
}