How can I detect "missing" elements in an IEnumerable<T>?

Question

I've got an IEnumerable<T> containing a list of data elements with consistent intervals in one of the properties:

List<Interval> list = new List<Interval>
            { 
                new Interval{ TIME_KEY = 600},
                new Interval{ TIME_KEY = 605},
                new Interval{ TIME_KEY = 615},
                new Interval{ TIME_KEY = 620},
                new Interval{ TIME_KEY = 630}
            };

How can I query this list (using Linq, preferably), to get a List that looks like this:

 List<Interval> list = new List<Interval>
                { 
                    new Interval{ TIME_KEY = 610},
                    new Interval{ TIME_KEY = 625}
                };

?

EDIT: I will probably know what the interval distance is supposed to be, but if there's a way to determine it by examing the data, that would be a huge bonus!

EDIT: changed to numeric values

Answer 1

Have a look at this question for an extension method which selects consecutive values. From there, you could do something like:

// I'd probably rename SelectBetween to SelectConsecutive
list.SelectConsecutive((x, y) => new { Original = x, Interval = y - x})
    .Where(pair => pair.Interval != 5)
    .Select(pair => new Interval(pair.Original + 5));

(Somewhat pseudocode, but I hope you see where I'm going.)

However, that would only generate one element when it's missing... if you went from 0 to 20, it wouldn't generate 5, 10, 15.

To put some meat on Henk's second suggestion:

var missing = Enumerable.Range(0, expectedElementCount)
                        .Select(x => new Interval(baseInterval + 5 * x)
                        .Except(list);

Answer 2

var newList = 
     Enumerable.Range(0, 6)
               .Select(r=> new Interval() {TIME_KEY = ((r*5)+600) })
               .Except(list )

Answer 3

This would work if the interval is known, if you have access to the Zip method (comes with .NET 4):

list.Zip(list.Skip(1), (x,y) => new { x, delta = y - x })
    .SelectMany(a => Enumerable.Range(1, a.delta/interval - 1)
                               .Select(i => a.x + i*interval));

Note that this iterates the list twice so in case the source is a lazy enumerable, you need to buffer it first. That construction with Zip and Skip is a quick and dirty way of projecting consecutive elements together. Reactive Extensions' System.Interactive library has a Scan method for that and Jon showed a possible implementation in another answer. Neither of those iterates the list twice, so they would be a much better choice.

If the interval is to be determined you can get the minimum delta:

var deltas = list.Zip(list.Skip(1), (x,y) => y - x );
var interval = deltas.Min();
list.Zip(deltas, (x, delta) => new { x, delta })
    .SelectMany(a => Enumerable.Range(1, a.delta/interval - 1)
                               .Select(i => a.x + i*interval));

There are some assumptions I made though:

• all differences between the elements are multiples of the interval;
• the input is sorted.

How it works:

1. First it builds a sequence of pairs with each element but the last and the interval to the element that follows it;
2. Then for each of those pairs, it produces all the missing values within the delta: within each delta there are exactly a.delta/interval - 1 values, and each of these is a certain number of intervals away from the element store in the pair, hence a.x + i*interval.
3. SelectMany takes care of flattening all those sequences of missing values together into one.

Answer 4

Try this:

private static IEnumerable<Interval> CalculateMissingIntervals(IEnumerable<Interval> list, int step) {
  return list.Zip(list.Skip(1), 
    (i1, i2) => IntervalRange(i1.TIME_KEY + step, i2.TIME_KEY, step)).
    SelectMany(x => x);
}
private static IEnumerable<Interval> IntervalRange(int start, int end, int step) {
  for (var i = start; i < end; i += step) {
    yield return new Interval { TIME_KEY = i };
  }
}

The initial list is assumed to be sorted.

Answer 5

IEnumerable<Interval> missingIntervals =
    Enumerable.Range(list.Min(listMember => listMember.TIME_KEY), list.Max(listMember => listMember.TIME_KEY))
              .Where(enumMember => enumMember % intervalDistance == 0)
              .Select(enumMember => new Interval { TIME_KEY = enumMember}
              .Except(list);