[Bug]: SourceList.EditDiff ignores duplicates in new list

[gewald314]

Describe the bug 🐞

When calling SourceList.EditDiff with duplicate items which already have an equal item in the SourceList, the new items do not match the wanted items.

Step to reproduce

In the EditDiff tests, add test

[Fact]
public void EditDiffWithDuplicates()
{
    // Person("Name" + 1, 1) already exists in _cache.
    Person[] newPeople = [new Person("Name" + 1, 1), new Person("Name" + 1, 1)];

    _cache.EditDiff(newPeople, Person.NameAgeGenderComparer);

    _cache.Count.Should().Be(2);
    _cache.Items.Should().BeEquivalentTo(newPeople);
    _result.Messages.Count.Should().Be(1);
}

This will fail with: Expected _cache.Count to be 2, but found 1.

Reproduction repository

Expected behavior

AI suggests this implementation based on https://en.wikipedia.org/wiki/Longest_common_subsequence. This would also solve #402. Though performance will be worse than the current implementation. It might make sense to at least provide a flag which defines whether to use a slower but order- and duplicate-aware implementation.

source.Edit(list =>
{
    var eq = equalityComparer ?? EqualityComparer<T>.Default;
    var oldList = list.AsArray();
    var newList = items.AsArray();

    // Build LCS table
    int oldLen = oldList.Length;
    int newLen = newList.Length;
    var dp = new int[oldLen + 1, newLen + 1];

    for (int i = oldLen - 1; i >= 0; i--)
    {
        for (int j = newLen - 1; j >= 0; j--)
        {
            if (eq.Equals(oldList[i], newList[j]))
                dp[i, j] = dp[i + 1, j + 1] + 1;
            else
                dp[i, j] = Math.Max(dp[i + 1, j], dp[i, j + 1]);
        }
    }

    // Walk the LCS table to produce removes and inserts.
    // We track a `listIndex` which is the current index into
    // the mutating list as we apply operations.
    int oi = 0, ni = 0, listIndex = 0;

    while (oi < oldLen && ni < newLen)
    {
        if (eq.Equals(oldList[oi], newList[ni]))
        {
            // Matched in LCS — keep this item
            oi++;
            ni++;
            listIndex++;
        }
        else if (dp[oi + 1, ni] >= dp[oi, ni + 1])
        {
            // Removing from old list is at least as good
            list.RemoveAt(listIndex);
            oi++;
        }
        else
        {
            // Insert from new list
            list.Insert(listIndex, newList[ni]);
            ni++;
            listIndex++;
        }
    }

    // Remove remaining old items
    while (oi < oldLen)
    {
        list.RemoveAt(listIndex);
        oi++;
    }

    // Insert remaining new items
    while (ni < newLen)
    {
        list.Insert(listIndex, newList[ni]);
        ni++;
        listIndex++;
    }
});

Screenshots 🖼️

No response

IDE

No response

Operating system

No response

Version

No response

Device

No response

DynamicData Version

9.4.31

Additional information ℹ️

No response