How to take all but the last element in a sequence using LINQ?

Question

Hi everyone, Let's say I have a sequence.

IEnumerable<int> sequence = GetSequenceFromExpensiveSource();
// sequence now contains: 0,1,2,3,...,999999,1000000

Getting the sequence is not cheap and is dynamically generated, and I want to iterate through it once only.

I want to get 0 - 999999 (i.e. everything but the last element)

I recognize that I could do something like:

sequence.Take(sequence.Count() - 1);

but that results in two enumerations over the big sequence.

Is there a LINQ construct that lets me do:

sequence.TakeAllButTheLastElement();

?

Thanks!

-Mike

Answer 1

I don't know a Linq solution - But you can easily code the algorithm by yourself using generators (yield return).

public static IEnumerable<T> TakeAllButLast<T>(this IEnumerable<T> source) {
    var it = source.GetEnumerator();
    bool hasRemainingItems = false;
    bool isFirst = true;
    T item = default(T);

    do {
        hasRemainingItems = it.MoveNext();
        if (hasRemainingItems) {
            if (!isFirst) yield return item;
            item = it.Current;
            isFirst = false;
        }
    } while (hasRemainingItems);
}

static void Main(string[] args) {
    var Seq = Enumerable.Range(1, 10);

    Console.WriteLine(string.Join(", ", Seq.Select(x => x.ToString()).ToArray()));
    Console.WriteLine(string.Join(", ", Seq.TakeAllButLast().Select(x => x.ToString()).ToArray()));
}

Or as a generalized solution discarding the last n items (using a queue like suggested in the comments):

public static IEnumerable<T> SkipLastN<T>(this IEnumerable<T> source, int n) {
    var  it = source.GetEnumerator();
    bool hasRemainingItems = false;
    var  cache = new Queue<T>(n + 1);

    do {
        if (hasRemainingItems = it.MoveNext()) {
            cache.Enqueue(it.Current);
            if (cache.Count > n)
                yield return cache.Dequeue();
        }
    } while (hasRemainingItems);
}

static void Main(string[] args) {
    var Seq = Enumerable.Range(1, 4);

    Console.WriteLine(string.Join(", ", Seq.Select(x => x.ToString()).ToArray()));
    Console.WriteLine(string.Join(", ", Seq.SkipLastN(3).Select(x => x.ToString()).ToArray()));
}

Answer 2

Nothing in the BCL (or MoreLinq I believe), but you could create your own extension method.

public static IEnumerable<T> TakeAllButLast<T>(this IEnumerable<T> source)
{
    var enumerator = source.GetEnumerator();
    bool first = true;
    T prev;
    while(enumerator.MoveNext())
    {
        if (!first)
            yield return prev;
        first = false;
        prev = enumerator.Current;
    }
}

Answer 3

As an alternative to creating your own method and in a case the elements order is not important, the next will work:

var result = sequence.Reverse().Skip(1);

Answer 4

Because I think Dario's solution is less elegant than it could be, an alternative:

public static IEnumerable<T> DropLast<T>(this IEnumerable<T> source)
{
    if (source == null)
        throw new ArgumentNullException("source");

    T buffer = default(T);
    bool buffered = false;

    foreach (T x in source)
    {
        if (buffered)
            yield return buffer;

        buffer = x;
        buffered = true;
    }
}

As per Eric Lippert's suggestion, it easily generalizes to n items:

public static IEnumerable<T> DropLast<T>(this IEnumerable<T> source, int n)
{
    if (source == null)
        throw new ArgumentNullException("source");

    if (n < 0)
        throw new ArgumentOutOfRangeException("n", 
            "Argument n should be non-negative.");

    Queue<T> buffer = new Queue<T>(n + 1);

    foreach (T x in source)
    {
        buffer.Enqueue(x);

        if (buffer.Count == n + 1)
            yield return buffer.Dequeue();
    }
}

Where I changed the order of buffering to handle n == 0 without special casing.

Answer 5

Why not just .ToList on the seq, then call count and take like you did originally.. but since it's been pulled into a list, it shouldnt do an expensive enumeration twice. Right?