title: List/Array Diffing Algorithm
body: <p>I'd like to implement List/Array diffing in C#, but I've hit a snag. Here's what I have so far:</p>
  
  <pre><code>public struct ListDiff
  {
      public IReadOnlyList&lt;int&gt; Insertions { get; }
      public IReadOnlyList&lt;int&gt; Deletions { get; }
      public IReadOnlyList&lt;(int source, int destination)&gt; Moves { get; }
  
      ListDiff(IReadOnlyList&lt;int&gt; insertions, IReadOnlyList&lt;int&gt; deletions, IReadOnlyList&lt;(int, int)&gt; moves)
      {
          Insertions = insertions;
          Deletions = deletions;
          Moves = moves;
      }
  
      static IReadOnlyDictionary&lt;T, int&gt; ToDict&lt;T&gt;(IReadOnlyList&lt;T&gt; values)
      {
          var dict = new Dictionary&lt;T, int&gt;();
  
          for (int i = 0; i &lt; values.Count(); ++i)
          {
              dict[values[i]] = i;
          }
  
          return dict;
      }
  
      // Assuming a T with a meaningful implementation of GetHashCode()
      public static ListDiff GetDiff&lt;T&gt;(IReadOnlyList&lt;T&gt; previous, IReadOnlyList&lt;T&gt; current)
      {
          // map into Dictionary&lt;T, int&gt; for fast "contains member"-lookup
          var previousDict = ToDict(previous);
          var currentDict = ToDict(current);
  
          var deletions = new List&lt;int&gt;();
          var insertions = new List&lt;int&gt;();
          var moves = new List&lt;(int source, int destination)&gt;();
  
          foreach (var (item, index) in previousDict)
          {
              if (currentDict.ContainsKey(item))
              {
                  if (currentDict[item] != index)
                  {
                      // item is in both and its index has changed == it moved
                      moves.Add((index, currentDict[item]));
                  }
              }
              else
              {
                  // item was in previous, not in current
                  deletions.Add(index);
              }
          }
  
          foreach (var (item, index) in currentDict)
          {
              if (!previousDict.ContainsKey(item))
              {
                  // item is in current, not in previous
                  insertions.Add(index);
              }
          }
  
          return new ListDiff(insertions, deletions, moves);
      }
  }
  </code></pre>
  
  <p>There are three types of "actions": <code>insertions</code>, <code>deletions</code>, and <code>moves</code>. This all works fine--if not super efficiently--for identifying items that were inserted and deleted. The snag is that any items that were "moved" as a result of insertions or deletions are returned as <code>moves</code>: i.e. if <code>myItem</code> was in the old List at index 1 and the new List deleted at 0, <code>myItem</code> counts as a move from 1->0 even though its movement was strictly a result of other actions.</p>
  
  <p><strong>For my purposes I need to ignore moves that were strictly a result of other actions. What algorithm can I use to "cancel out" redundant moves?</strong></p>
  
  <p>Or is there a library/built-in method I'm missing that does this more efficiently than I could ever dream? </p>
  
  <p>General Notes:</p>
  
  <ul>
  <li>I'm currently dealing with Lists of at most 3 items, but would like to apply this process to Lists of potentially around 100 elements</li>
  <li>awaiting an async semi-long-running process is acceptable if necessary</li>
  <li>A solution that also accounts for "updated" Ts is ideal but not necessary</li>
  </ul>