Comparing Two IEnumerables for Change Detection

Question

For my first post here, I have a question regarding IEnumerable comparison. I have a linking structure based on enumeration logic. IEnumerable content changes over time, and I have to manually trigger CollectionChanged events.

I have a very naive algorithm that allows me to detect simple changes between two IEnumerable states (simple add, simple remove, multiple add, multiple remove), but it is not very efficient and does not detect everything.

A quick example of what I need:

State 1 IEnumerable: A * B * C * D * E

State 2 IEnumerable: A * C * B * D * D1

In this example, I would need to detect

• One-motion operation: B modified index from 1 to 2
• One add operation: D1 was inserted at index 4
• One delete operation: E was deleted

Is there an algorithm to solve this problem as efficiently as possible (O (nLog (n)) will be a good start)?

Thank!

Answer 1

This is uncompiled, untested, and at least partially psuedo code.

Given that a single motion detection is enough. Elements can only move forward, moving backward will result from moving or removing another item.

eg. State 1 IEnumerable: A * B * C * D * E

State 2 IEnumerable: A * D * B * C * D1

The result for both B and for moving forward.

enum1pos = -1;
enum2pos = 0;
  Value2 = enum2.Next()
  enum2pos++;
List<int> SkipList = new SkipList();
while(enum1 has values left)
{
  Value1 = enum1.Next()
  enum1pos++;
  //Skip over moved items.
  while (SkipList.Count > 0 && SkipList[0] == enum2.Position)
  {
    Value2 = enum2.Next()
    enum2pos++;
  }
  if (Value1 == Value2)
    Value2 = enum2.Next()
    enum2pos++;
    continue;

  int temp = enum2pos;
  while(Value1 !=Value and enum2 has more values)
  {
    Value2 = enum2.Next();
    enum2pos++;
  }
  if(Value1 != Value2)
    ItemDeleted(Value1);
  else
  {
    ItemMoved(Value1, enum2pos);
    SkipList.Add(enum2pos);
  }
  //This is expensive for IEnumerable!
  enum2.First();
  loop temp times
    enum2.Next();
  //if 
}
while (enum2 has values left)
{
  while (SkipList.Count > 0 && SkipList[0] == enum2.Position)
  {
    Value2 = enum2.Next()
    enum2pos++;
  }
  if (enum2 has values left)
  Added(Value2, enum2pos)
}

: A A

B D
B
B → 2
2
Reset Enum2
C D
C
C → 3
3
Reset Enum2

D D

(2)
(3)
E D1
E (E)

Enum1 (D1,4)

, - , enum2pos , , , enum1, , enum2 reset all .

Answer 2

Linq, , .. , .

var a = new List<string>{"A","B","C","D","E"};
var b = new List<string>{"A","C","B","D","D1"};

var removed = a.Except(b);
var moved = a.Where(x => b[a.IndexOf(x)] != x && !removed.Contains(x));
List<string> newlyInserted = new List<string>();
foreach (var item in removed)
{
    //Newly inserted into the list - D1
    newlyInserted.Add(b[a.IndexOf(item)]);
    //Index of D1 if required
    var indexOfNewlyAddedItem = a.IndexOf(item);
}

var newlyAdded = b.Except(a);