.NET 3.5+

Retrieving Items from the End of a Sequence

by Richard Carr, published at http://www.blackwasp.co.uk/TakeLast.aspx

Language-Integrated Query (LINQ) provides the Take partitioning operator that extracts items from the start of any sequence. No similar operator is provided to retrieve the items from the end of a sequence. This article describes such a method.

Partition Operators

In earlier articles I've described the partitioning operators provided by LINQ, which allow you to retrieve items from the start of a sequence, or to skip a number of items before retrieving all, or a number of, the remaining items. I've also described a custom extension method that allows you to take every nth item from a sequence, which could be described as a partitioning operator.

Sometimes you will want to obtain a number of items from the end of a sequence, rather than from the start. One way in which you could achieve this for many collections is shown below. Here we use the Count method to find the total number of items in the sequence. We then subtract the number of items we want to take from the end of the sequence and use the result of this calculation with the Skip operator.

var lastFive = collection.Skip(collection.Count() - 5);

This approach works for many types of collection but it is flawed. If the source sequence can only be enumerated once, the results will be incorrect or an exception may be thrown. To allow for this potential bug, in this article we'll create a new, custom query operator that can be used to extract that last items from a sequence.

TakeLast

As with other custom LINQ-style operators described in the articles on this web site, we'll split the extension method into two parts. The main, public method will validate the input parameters, allowing exceptions to be thrown as soon as the code calling TakeLast is encountered. A private method will perform the partitioning, using an iterator to provide some deferred execution.

To create the public method, generate a new static class and add the following generic method. Here we validate the sequence to ensure it isn't null. We could also validate the count parameter and throw an exception if it is negative. In this case the negative check is omitted. If a negative value is provided, the resultant sequence will be empty.

public static IEnumerable<T> TakeLast<T>(this IEnumerable<T> sequence, int count)
{
    if (sequence == null) throw new ArgumentNullException("sequence");

    return TakeLastImpl(sequence, count);
}

The iterator part of the operator is quite simple. We start by creating a queue. We then loop through all of the items in the source, adding each item into the queue using the Enqueue method. Once the queue contains the number of items that we wish to extract, we begin removing one item each time that we add one. This means that the queue will always hold the desired number of the latest items read.

When the source sequence is exhausted, the final item in the queue will be the last item from the sequence. The item as the front of the queue will be the first item that we wish to extract. To return the sequence, we simply dequeue all of the contained items, using yield return to return them one by one.

private static IEnumerable<T> TakeLastImpl<T>(IEnumerable<T> sequence, int count)
{
    int queued = 0;
    Queue<T> queue = new Queue<T>();
    foreach (T item in sequence)
    {
        queue.Enqueue(item);
        if (queued < count)
            queued++;
        else
            queue.Dequeue();
    }
    while (queue.Count > 0)
    {
        yield return queue.Dequeue();
    }
}

Optimising for Collections

Although the use of queuing yields the correct results, for collections it is not as efficient as using a combination of Count and Take. We can achieve the best of both approaches by detecting collections in the public method and using the most appropriate approach. To do this, we'll start by adding an overloaded version of TakeLastImpl that accepts an ICollection<T> instead of IEnumerable<T>, as follows:

private static IEnumerable<T> TakeLastImpl<T>(ICollection<T> collection, int count)
{
    return collection.Skip(collection.Count - count);
}

We can now update the TakeLast method to use the optimised version. First we cast the sequence as an ICollection<T> using the as operator. This will either return a collection, which can be used with the new private method, or null, in which case we will call the original TakeLastImpl method using the provided sequence.

Update the method as follows:

public static IEnumerable<T> TakeLast<T>(this IEnumerable<T> sequence, int count)
{
    if (sequence == null) throw new ArgumentNullException("sequence");

    ICollection<T> collection = sequence as ICollection<T>;
    if (collection != null)
        return TakeLastImpl(collection, count);
    else
        return TakeLastImpl(sequence, count);
}

Testing

Finally, we can test the method for a collection and a simple enumerable sequence. Try running the following code and reviewing the results of the two TakeLast operations using the Visual Studio debugger.

char[] alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".ToCharArray();
IEnumerable<char> alphabetEnumerable = alphabet.Select(c => c);

var last10 = alphabet.TakeLast(10);
var last20 = alphabetEnumerable.TakeLast(20);