Comparing two IEnumerable to detect changes

Question

For my first post here, I have a question regarding IEnumerable comparison. I have a bindable structure based on an enumeration logic. The content of the IEnumerable changes over time and I have to manually fire CollectionChanged events.

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

A quick example of what I need :

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

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

For this example, I would have to detect

• One move operation : B changed index from 1 to 2
• One Add operation : D1 was inserted at index 4
• One remove operation : E was removed

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

Thanks !

Answer 1

This is uncompiled, untested and atleast partially psuedo code.

Given a single move detection being sufficient Items can only move forward, moving backwards will be the result of another item being move or removed

e.g. State 1 of the IEnumerable : A * B * C * D * E

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

Result in both B and C 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)
}

Result: Compare A and A
Next
Compare B and D
Find B
B Moved -> 2
Add 2 to Skip List
Reset Enum2
Compare C and D
Find C
C Moved -> 3
Add 3 to Skip List
Reset Enum2
Next
Compare D and D
Next
Skip(2)
Skip(3)
Compare E and D1
Find E
Removed(E)
Next
End of Enum1 Added(D1,4)

I think there's a saving somewhere if enum2pos gets too far behind to see if it's been removed and if it hasn't add a skip to for it's original position in enum1, this would help with with enum2's position being reset all of the time.