LINQ: Implementing The TakeLast Operator

LINQ With C# (Portuguese)

Following my last post, in this post I’ll introduce the implementation of the TakeLast operator.

The TakeLast operator returns a specified number of contiguous elements from the end of a sequence and is implemented as the TakeLast extension method:

public static IEnumerable<TSource> TakeLast<TSource>(this IEnumerable<TSource> source, int count)

To implement this operator, first we start by buffering, at most, a count number of items from the source sequence in an array that acts as a circular buffer:

var sourceEnumerator = source.GetEnumerator();
var buffer = new TSource[count];
var numOfItems = 0;
int idx;

for (idx = 0; (idx < count) && sourceEnumerator.MoveNext(); idx++, numOfItems++)
{
    buffer[idx] = sourceEnumerator.Current;
}

If the number of buffered items (numOfItems) is less than the requested number of items (count), we just yield all the buffered items:

if (numOfItems < count)
{
    for (idx = 0; idx < numOfItems; idx++)
    {
        yield return buffer[idx];
    }

    yield break;
}

Next, we iterate over the rest of the items circularly buffering them:

for (idx = 0; sourceEnumerator.MoveNext(); idx = (idx + 1) % count)
{
    buffer[idx] = sourceEnumerator.Current;
}

And finally, we just iterate over the buffered items and yield them:

for (; numOfItems > 0; idx = (idx + 1) % count, numOfItems--)
{
    yield return buffer[idx];
}

There are two optimizations you can make here.

The first is obvious, if the requested number of items is 0 (zero), we just return an empty sequence:

if (count <= 0)
{
    return System.Linq.Enumerable.Empty<TSource>();
}

The second is if the source sequence is known to implement the IList<T> interface. Objects implementing this interface have a Count property and indexed access to its items which allows us to optimize the production of the final sequence.

Producing the final sequence consists of yielding the required number of items from the end of the list (or all of them if the list contains less items than required):

int listCount = list.Count;

for (int idx = listCount - ((count < listCount) ? count : listCount); idx < listCount; idx++)
{
    yield return list[idx];
}

You can find the complete implementation of this operator (and more) CodePlex project for LINQ utilities and operators: PauloMorgado.Linq

Comments are closed.