Comparing two lists to find added or removed element in one of them

Question

TL;DR version:

Is there a way to enumerate over two lists deffering by exactly one element (which may be either an additional or a missing element) and tell which element is changed, while matching all the other elements?

My class have a List<View> property, which Is created from a List<Model> injected via constructor. Each View wraps its respective Model as a public property.

In the same scope, there is an void Update(List<Model> newList) routine, which receives another list of Model with the following condition: it is the same List<Model> as before, plus or minus exactly one element . That is because Update is called every time an item is added or removed from a data-bound list elsewhere, and the application only has the option to add/remove one element at a time.

The motivation for the Update operation, instead of simply replacing the Models (wrapped in Views) of the old list with new one, is that View classes store state, so I want to replace their model, but keep their state - which is not stored in the Models anyway.

The problem is: I have to add new View if there is a new Model, I have to remove the respective View when the respective Model is absent, and I must match already existing views with their already existing models, except for the element added or removed. I'm unsure how to do that.

So I was thinking about comparing the Model in the first element of the list to the first element of the new list, and if they match then go to the second element, and so on. At one point, they will differ, but this can be because of the addition of an element (and then the remaining will be shifted one index), or due to removal of one element (in which case the remaining will be shifted down, and the different element will actually be an already-existing element in the list).

Is there any sensible way to tell if the first different element is due to addition or removal?

If might be an overkill but you can try using https://github.com/GregFinzer/Compare-Net-Objects — Alexey Zimarev, Apr 18 '16 at 18:42
Sounds like what you want is the opposite of an Intersect (apparently called a Symmetric Difference), described [here](http://stackoverflow.com/questions/5620266/the-opposite-of-intersect). The way to know if something is an addition or removal is to find which of the two lists the different model is part of. If it was part of the "before" but not the "after", it was removed. If it's part of the "after" but not the "before", it was added. — Heretic Monkey, Apr 18 '16 at 19:18
@ArturoMenchaca, well put. As I said, Views are wrappers for Models, so in reality I am comparing View.Model with Model. Sorry about the mistake, and thanks for the correction! — heltonbiker, Apr 18 '16 at 19:39

score 4 · Accepted Answer · answered Apr 18 '16 at 20:06

You can use Except() extension, for example:

List<Model> models = new List<Model>();
List<View> views = new List<View>();

Then you can get the desired added/removed item doing this:

//If models.Count > views.Count
var addedModel = models.Except(views.Select(v => v.Model)).FirstOrDefault();

//If views.Count > models.Count
var modelToRemove = views.Select(v => v.Model).Except(models).FirstOrDefault();
var viewToRemove = views.Single(v => v.Model == modelToRemove);

Perhaps you will need to pass a IEqualityComparer<Model> for custom comparison.

If the lists are or can be sorted according to some criteria, you can do what you said in the question, find the index where the lists differs:

//for simplicity sorts the lists according to some 'Id'
models.Sort((a, b) => a.Id.CompareTo(b.Id));
views.Sort((a, b) => a.Model.Id.CompareTo(b.Model.Id));

Then, get the index comparing the values:

var index = Enumerable.Range(0, Math.Min(models.Count, views.Count))
                      .First(i => !Model.Equals(models[i], views[i].Model));

//If models.Count > views.Count
var addedModel = models[index];

//If views.Count > models.Count
var viewToRemove = views[index];

score 2 · Answer 2 · answered Apr 19 '16 at 07:06

Not the shortest solution in terms of lines of code, but If it is known that no more than single element can be inserter or removed at a time (but more than single change in whole list) you can use the following loop:

var i = 0;
var j = 0;

while(i < oldList.Count || j < newList.Count)
{
    if (i >= oldList.Count)
    {
        for(; j < newList.Count; j++)
        {
            Console.WriteLine("{0} added", newList[j]);
        }
        break;
    }
    if (j >= newList.Count)
    {
        for(; i < oldList.Count; i++)
        {
            Console.WriteLine("{0} removed", oldList[i]);
        }
        break;
    }

    if (oldList[i] == newList[j])
    {
        Console.WriteLine("{0} not changed", oldList[i]);
        i++;
        j++;
    }
    else if(j < (newList.Count - 1) && oldList[i] == newList[j+1])
    {
        Console.WriteLine("{0} added", newList[j]);
        j++;
    }
    else
    {
        Console.WriteLine("{0} removed", oldList[i]);
        i++;

    }
}

I think, it has following advantages over Except solution:

Can find more than one change
O(n+m) max complexicity
More control in terms of how you find changes: Except solution can check only equality but here you can check if some model properties changed while others doesn't

score 0 · Answer 3 · answered Apr 18 '16 at 20:06

It is quite easy if you add an action state {None, Added, Updated, Deleted} to your View item like this

View
{
  ActionState State{get;set;}
}

and then you can query from your input list like this

var changedElement= views.FirstOrDefault(x=> x.State != ActionState.None);

Next, depending on the action you can add/update/remove the respective view from the existing list that you have.

Hope this help.

Comparing two lists to find added or removed element in one of them

3 Answers3