Is it possible to group LINQ elements based on a sequence?

Question

I've been wondering; in the company I work for, we manage lots of data, but as it's effectively given to us by customers, we don't necessarily trust it - with good reason. A lot of it has the wrong timestamp, or some of it is missing, or whatever else have you.

One of the tasks that I have had to do a lot recently is basically find elements that are null within a set of elements, then find the next non-null element, then average out the difference between those null records. That is, say we have dataset A:

A = { 0f, 1f, 2f, 5f, Null, Null, Null, 7f, Null, 8f }

It's important to note that we have to distinguish between 0 and Null. The difference is obviously that 0 is 0, while Null is no data at all.

Using LINQ, is there a way that we can basically access the following subsection of A:

Subsection { Null, Null, Null, 7f }

And have it in a collection such that we can transform it into (7/4f) over the four records..

Subsection { 1.75f, 1.75f, 1.75f, 1.75f }

Such that when iterating over A again, we get the following output:

{ 0f, 1f, 2f, 5f, 1.75f, 1.75f, 1.75f, 1.75f, 4f, 4f }

Currently the way I do this is do a pass using a numeric for, looking for a null element, then storing all consecutive nulls in a List<T>, and after finding the next non-null, assigning all variables by iterating over said List<T>. It does the job but it looks pretty nasty.

So, for the sake of narcicissim, is there a way of doing this neatly (= less code clutter)?

Pseudo

a = { 0, 1, 2, 5, null, null, null, 7, null, 0 }


nullList = new List()
for i = 0, a.length
    if i == null
        nullList.add(i)
    else
        if nullList.length > 0
            nullList.add(i)
            int avg = nullList.Aggregate(x => x)
            foreach element in nullList
                element = avg
            nullList.clear()

Answer 1

If I understand your question correctly, you want to replace the null values in the list with a value based on the first non-null value. I don't see why you'd need a second list of nulls for this. Here's an attempt to just modify the list in-place, although it's not much shorter than what you already have:

var A = new List<float?> { 0f, 1f, 2f, 5f, null, null, null, 7f, null, 8f };

for (int i = A.IndexOf(null); i != -1; i = A.IndexOf(null, i))
{
    int j = 0;
    do { j++; } while (A[i + j] == null);
    float f = A[i + j].Value / (j + 1);
    do { A[i++] = f; } while (j --> 0);
}

// A == { 0f, 1f, 2f, 5f, 1.75f, 1.75f, 1.75f, 1.75f, 4f, 4f }

The code repeatedly searches the list for a nulls (continuing where it left off when it found a null previously), counts the number of nulls next to each other, and then distributes the first non-null value across the gap. The code assumes that there is always a non-null value after each gap.

As pointed out in numerous comments, the use of LINQ does not provide any real advantage here.

Answer 2

So first off we'll use a helper method called GroupWhile. It will take in a sequence and a function; that function will be given the previous item and the current item and based on that will determine if the current item should be part of a new group, or part of the previous group. It lets us group items while some condition is met:

public static IEnumerable<IEnumerable<T>> GroupWhile<T>(
    this IEnumerable<T> source, Func<T, T, bool> predicate)
{
    using (var iterator = source.GetEnumerator())
    {
        if (!iterator.MoveNext())
            yield break;

        List<T> list = new List<T>() { iterator.Current };

        T previous = iterator.Current;

        while (iterator.MoveNext())
        {
            if (predicate(previous, iterator.Current))
            {
                list.Add(iterator.Current);
            }
            else
            {
                yield return list;
                list = new List<T>() { iterator.Current };
            }

            previous = iterator.Current;
        }
        yield return list;
    }
}

Using this we can group items while the previous item is null. We then take each group, repeat the average value of that group group.Count() times, and then flatten the sequence out again:

public static IEnumerable<float> ConsolodateNulls<T>(IEnumerable<float?> source)
    where T : struct
{
    return source.GroupWhile((prev, curr) => prev == null)
        .SelectMany(group => Enumerable.Repeat(
            group.LastOrDefault(item => item != null) ?? 0 / group.Count(),
            group.Count()));
}

Answer 3

You can create an extension method that does this. This extension method can then be used in a normal LINQ statement:

public static IEnumerable<float> SmoothGaps(this IEnumerable<float?> source)
{
    int numberOfNulls = 0;
    foreach(var item in source)
    {
        if(item == null)
        {
            ++numberOfNulls;
        }
        else
        {
            if(numberOfNulls != 0)
            {
                for(int i=0; i <= numberOfNulls; ++i)
                    yield return item.Value / (numberOfNulls + 1);
            }
            else
                yield return item.Value;
            numberOfNulls = 0;
        }
    }
}

Usage would be simply:

var result = a.SmoothGaps();

nulls at the end of source will simply be removed.

Answer 4

Here is how you can do it purely within LINQ:

var data = new List<float?> { 0f, 1f, 2f, 5f, null, null, null, 7f, null, 8f };
var corrected = data
    .Select((v,i) => new {
        Index = i
        // Find the index of the next non-null item in the list
    ,   NextNonNull = i + data
            .Skip(i)
            .Select((vv,j) => new {j,vv})
            .First(p => p.vv.HasValue).j
    ,   Value = v
    })
    .GroupBy(p => p.NextNonNull)
    // For each group, insert its average g.Count() times
    .SelectMany(g => g.Select(e => data[g.Key]/g.Count()))
    .ToList();
for (var i = 0 ; i != data.Count ; i++ ) {
    Console.WriteLine("{0} - {1}", data[i], corrected[i]);
}

Disclaimer: this solution is provided for amusement purposes only. It is going to be slower than your solution that is based on a for loop, potentially adding an extra order to the complexity (i.e. making it O(n^2) instead of O(n)).

Answer 5

A pure LINQ version using Aggregate for your amusement :

float?[] A = { 0f, 1f, 2f, 5f, null, null, null, 7f, null, 8f };
var result = A.Aggregate(Tuple.Create(new List<float>(), 0), 
 (items, current) => 
 {
    if(current.HasValue)
    {
        if(items.Item2 == 0)
            items.Item1.Add(current.Value);
        else
        {
            var avg = current.Value / (items.Item2 + 1);
            for(int i = 0; i <= items.Item2; i++)
                items.Item1.Add(avg);
        }
        return Tuple.Create(items.Item1, 0);
    }
    else
        return Tuple.Create(items.Item1, items.Item2 + 1);
 }).Item1;

I wouldn't use this in production code because the head of an average developer will explode on Aggregate, using Tuple in C# always look kinda ugly and an imperative solution works well and is more understandable than this.

Answer 6

I don't think it can be done with pure linq (existing linq methods), but I'd write an iterator to do this:

public IEnumerable<float?> ProcessSequence(IEnumerable<float?> seq)
{
int nullCount = 0;
foreach(var x in seq)
{
    if (x == null)
    {
        nullCount++;
    }
    else if (nullCount > 0)
    {
        nullCount++;
        var mid = x / nullCount;
        for (var i = 0; i<nullCount; i++)
        {
            yield return mid;
        }
        nullCount = 0;
    }       
    else
    {
        yield return x;
    }
}
}