Get Difference Between Two Strings in Terms of Remove and Insert Actions

Question

So I have a text box and on the text changed event I have the old text and the new text, and want to get the difference between them. In this case, I want to be able to recreate the new text with the old text using one remove function and one insert function. That is possible because there are a few possibilities of the change that was in the text box:

1. Text was only removed (one character or more using selection) - ABCD -> AD
2. Text was only added (one character or more using paste) - ABCD -> ABXXCD
3. Text was removed and added (by selecting text and entering text in the same action) - ABCD -> AXD

So I want to have these functions:

Sequence GetRemovedCharacters(string oldText, string newText)
{

}
Sequence GetAddedCharacters(string oldText, string newText)
{

}

My Sequence class:

public class Sequence
{

    private int start;
    private int end;

    public Sequence(int start, int end)
    {
        StartIndex = start; EndIndex = end;
    }

    public int StartIndex { get { return start; } set { start = value; Length = end - start + 1; } }
    public int EndIndex { get { return end; } set { end = value; Length = end - start + 1; } }
    public int Length { get; private set; }

    public override string ToString()
    {
        return "(" + StartIndex + ", " + EndIndex + ")";
    }

    public static bool operator ==(Sequence a, Sequence b)
    {
        if(IsNull(a) && IsNull(b))
            return true;
        else if(IsNull(a) || IsNull(b))
            return false;
        else
            return a.StartIndex == b.StartIndex && a.EndIndex == b.EndIndex;
    }
    public override bool Equals(object obj)
    {
        return base.Equals(obj);
    }
    public static bool operator !=(Sequence a, Sequence b)
    {
        if(IsNull(a) && IsNull(b))
            return false;
        else if(IsNull(a) || IsNull(b))
            return true;
        else
            return a.StartIndex != b.StartIndex && a.EndIndex != b.EndIndex;
    }
    public override int GetHashCode()
    {
        return base.GetHashCode();
    }

    static bool IsNull(Sequence sequence)
    {
        try
        {
            return sequence.Equals(null);
        }
        catch(NullReferenceException)
        {
            return true;
        }
    }

}

Extra Explanation: I want to know which characters were removed and which characters were added to the text in order to get the new text so I can recreate this. Let's say I have ABCD -> AXD. 'B' and 'C' would be the characters that were removed and 'X' would be the character that was added. So the output from the GetRemovedCharacters function would be (1, 2) and the output from the GetAddedCharacters function would be (1, 1). The output from the GetRemovedCharacters function refers to indexes in the old text and the output from the GetAddedCharacters function refers to indexes in the old text after removing the removed characters.

EDIT: I've thought of a few directions:

1. This code I created* which returns the sequence that was affected - if characters were removed it returns the sequence of the characters that were removed in the old text; if characters were added it returns the sequence of the characters that were added in the new text. It does not return the right value (which I myself not sure what I want it to be) when removing and adding text.
2. Maybe the SelectionStart property in the text box could help - the position of the caret after the text was changed.

*

private static Sequence GetChangeSequence(string oldText, string newText)
{
    if(newText.Length > oldText.Length)
    {
        for(int i = 0; i < newText.Length; i++)
            if(i == oldText.Length || newText[i] != oldText[i])
                return new Sequence(i, i + (newText.Length - oldText.Length) - 1);
        return null;
    }
    else if(newText.Length < oldText.Length)
    {
        for(int i = 0; i < oldText.Length; i++)
            if(i == newText.Length || oldText[i] != newText[i])
                return new Sequence(i, i + (oldText.Length - newText.Length) - 1);
        return null;
    }
    else
        return null;
}

Thanks.

Answer 1

A simple string comparison wont do the job since you are asking for a algorithm which supports added and removed chars at the same time and is hence not easy to achive in a few lines of code. Id suggest to use a library instead of writing your own comparison algorithm.

Have a look at this project for example.

Answer 2

I quickly threw this together to give you an idea of what I did to solve your question. It doesn't use your classes but it does find an index so it's customizable for you. There are also obvious limitations to this as it is just bare bones.

This method will spot out changes made to the original string by comparing it to the changed string

// Find the changes made to a string
string StringDiff (string originalString, string changedString)
{
    string diffString = "";

    // Iterate over the original string
    for (int i = 0; i < originalString.Length; i++)
    {
        // Get the character to search with
        char diffChar = originalString[i];

        // If found char in the changed string
        if (FindInString(diffChar, changedString, out int index))
        {
            // Remove from the changed string at the index as we don't want to match to this char again
            changedString = changedString.Remove(index, 1);
        }
        // If not found then this is a difference
        else
        {
            // Add to diff string
            diffString += diffChar;
        }
    }

    return diffString;
}

This method will return true at the first matching occurrence (an obvious limitation but this is more to give you an idea)

// Find char at first occurence in string
bool FindInString (char c, string search, out int index)
{
    index = -1;

    // Iterate over search string
    for (int i = 0; i < search.Length; i++)
    {
        // If found then return true with index
        if (c == search[i])
        {
            index = i;
            return true;
        }
    }

    return false;
}

This is a simple helper method to show you an example

void SplitStrings(string oldStr, string newStr)
{
    Console.WriteLine($"Old : {oldStr}, New: {newStr}");
    Console.WriteLine("Removed - " + StringDiff(oldStr, newStr));
    Console.WriteLine("Added - " + StringDiff(newStr, oldStr));
}

Answer 3

I've done it.

static void Main(string[] args)
{

    while(true)
    {
        Console.WriteLine("Enter the Old Text");
        string oldText = Console.ReadLine();
        Console.WriteLine("Enter the New Text");
        string newText = Console.ReadLine();
        Console.WriteLine("Enter the Caret Position");
        int caretPos = int.Parse(Console.ReadLine());
        Sequence removed = GetRemovedCharacters(oldText, newText, caretPos);
        if(removed != null)
            oldText = oldText.Remove(removed.StartIndex, removed.Length);
        Sequence added = GetAddedCharacters(oldText, newText, caretPos);
        if(added != null)
            oldText = oldText.Insert(added.StartIndex, newText.Substring(added.StartIndex, added.Length));
        Console.WriteLine("Worked: " + (oldText == newText).ToString());
        Console.ReadKey();
        Console.Clear();
    }

}

static Sequence GetRemovedCharacters(string oldText, string newText, int caretPosition)
{
    int startIndex = GetStartIndex(oldText, newText);
    if(startIndex != -1)
    {
        Sequence sequence = new Sequence(startIndex, caretPosition + (oldText.Length - newText.Length) - 1);
        if(SequenceValid(sequence))
            return sequence;
    }
    return null;
}
static Sequence GetAddedCharacters(string oldText, string newText, int caretPosition)
{
    int startIndex = GetStartIndex(oldText, newText);
    if(startIndex != -1)
    {
        Sequence sequence = new Sequence(GetStartIndex(oldText, newText), caretPosition - 1);
        if(SequenceValid(sequence))
            return sequence;
    }
    return null;
}
static int GetStartIndex(string oldText, string newText)
{
    for(int i = 0; i < Math.Max(oldText.Length, newText.Length); i++)
        if(i >= oldText.Length || i >= newText.Length || oldText[i] != newText[i])
            return i;
    return -1;
}
static bool SequenceValid(Sequence sequence)
{
    return sequence.StartIndex >= 0 && sequence.EndIndex >= 0 && sequence.EndIndex >= sequence.StartIndex;
}